Relevant bibliographies by topics / Algorithmes Branch-And-Cut

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers
  5. Reports

Academic literature on the topic 'Algorithmes Branch-And-Cut'

Author: Grafiati
Published: 7 September 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Algorithmes Branch-And-Cut.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Algorithmes Branch-And-Cut"

1

Fragoso, Felipe C., Gilberto F. de Sousa Filho, and Fábio Protti. "Declawing a graph: polyhedra and Branch-and-Cut algorithms." Journal of Combinatorial Optimization 42, no. 1 (April 19, 2021): 85–124. http://dx.doi.org/10.1007/s10878-021-00736-y.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Costa, Luciano, Claudio Contardo, and Guy Desaulniers. "Exact Branch-Price-and-Cut Algorithms for Vehicle Routing." Transportation Science 53, no. 4 (July 2019): 946–85. http://dx.doi.org/10.1287/trsc.2018.0878.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Pereira, Dilson Lucas, Michel Gendreau, and Alexandre Salles da Cunha. "Branch-and-cut and Branch-and-cut-and-price algorithms for the adjacent only quadratic minimum spanning tree problem." Networks 65, no. 4 (February 2, 2015): 367–79. http://dx.doi.org/10.1002/net.21580.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Fouilhoux, Pierre, A. Ridha Mahjoub, Alain Quilliot, and Hélène Toussaint. "Branch-and-Cut-and-Price algorithms for the preemptive RCPSP." RAIRO - Operations Research 52, no. 2 (April 2018): 513–28. http://dx.doi.org/10.1051/ro/2018031.

Full text
Abstract:
In this article, we address the preemptive Resource-Constrained Precedence Scheduling Problem. We propose two mixed integer formulations containing an exponential number of variables and inequalities. An antichain is a set of pairwise incomparable elements with respect to the precedence constraints. In the first formulation, the integer variables are associated with the antichains. For the second, the integer variables are limited to a particular subset of antichains. We propose two Branch-and-Cut-and-Price algorithms for each of these formulations. We introduce some valid inequalities in order to reinforce the second formulation. Finally, we give some computational results on instances of the PSPLIB and compare the formulations.
APA, Harvard, Vancouver, ISO, and other styles
5

Calvete, Herminia I., Concepción Domínguez, Carmen Galé, Martine Labbé, and Alfredo Marín. "The rank pricing problem: Models and branch-and-cut algorithms." Computers & Operations Research 105 (May 2019): 12–31. http://dx.doi.org/10.1016/j.cor.2018.12.011.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Li, Xiangyong, and Y. P. Aneja. "Regenerator location problem: Polyhedral study and effective branch-and-cut algorithms." European Journal of Operational Research 257, no. 1 (February 2017): 25–40. http://dx.doi.org/10.1016/j.ejor.2016.07.032.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Duchenne, Éric, Gilbert Laporte, and Frédéric Semet. "Branch-and-cut algorithms for the undirected m-Peripatetic Salesman Problem." European Journal of Operational Research 162, no. 3 (May 2005): 700–712. http://dx.doi.org/10.1016/j.ejor.2003.09.024.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Archetti, Claudia, Nicola Bianchessi, and M. Grazia Speranza. "Branch-and-cut algorithms for the split delivery vehicle routing problem." European Journal of Operational Research 238, no. 3 (November 2014): 685–98. http://dx.doi.org/10.1016/j.ejor.2014.04.026.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Desaulniers, Guy, Diego Pecin, and Claudio Contardo. "Selective pricing in branch-price-and-cut algorithms for vehicle routing." EURO Journal on Transportation and Logistics 8, no. 2 (June 2019): 147–68. http://dx.doi.org/10.1007/s13676-017-0112-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Di Summa, Marco, Andrea Grosso, and Marco Locatelli. "Branch and cut algorithms for detecting critical nodes in undirected graphs." Computational Optimization and Applications 53, no. 3 (February 9, 2012): 649–80. http://dx.doi.org/10.1007/s10589-012-9458-y.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Algorithmes Branch-And-Cut"

1

Ndiaye, Ndèye Fatma. "Algorithmes d'optimisation pour la résolution du problème de stockage de conteneurs dans un terminal portuaire." Thesis, Le Havre, 2015. http://www.theses.fr/2015LEHA0002/document.

Full text
Abstract:
ADans cette thède, nous traitons le problème de stockage de conteneurs dans un terminal portuaire. Dans un premier temps, noux présentons une étude bibliographique dans laquelle sont analysés les travaux qui ont déhà été rélisé dans ce domaine. Ensuite, nous présentons une étude analytique, puis une modélisation mathématique et des méthodes de résolution numérique qui englobent des algorithmes efficaces. Nous proposons une démonstration de la compexité du problème de stockage de conteneurs en considérant différents cas de stockage. Ce problème étant "Np_difficile" peut être difficilement résolu avec le logiciel d'optimisation "ILOG CPLEX". », raison pour laquelle nous proposons un algorithme de banch-and-cut, qui est une méthode de résolution exacte et qui nous a permis de repousser les limites de "ILOG CPLEX". Nous avons aussi proposé des algorithmes métatheuristiques et des hybridations qui procurent des résultats très satisfaisants et qui sont très avantageux en temps de calcul
AIn this thesis, we trait the container storage problem at port terminal. Initially, we present a state of the art in which the work that have been previously made in this filed are analyzed. After that, we present an analytical study. Thed we propose a mathematical modelling and some methods of resolution including effective algorithms. We propose a demonstration of the complexity of the problem by considering different cases of storage. This problme is "Np_difficult, so not always easy to solve by using the optimization software "ILOG CPLEX”. This is why we propose a branch-and-cut algorithm, wich is an optimal resolution algorithm and wich enables to go beyong the limits of "ILOG CPLEX". We also proposed meta-heuristic algorithms and hybridizations wich provide satisfactory resulys and wich required less calculation times
APA, Harvard, Vancouver, ISO, and other styles
2

Hassan, Abdeljabbar Hassan Mohammed Albarra. "Parallel Scheduling in the Cloud Systems : Approximate and Exact Methods." Thesis, Université de Lorraine, 2016. http://www.theses.fr/2016LORR0223/document.

Full text
Abstract:
Cette thèse porte sur la résolution exacte et heuristique de plusieurs problèmes ayant des applications dans le domaine de l'Informatique dématérialisé (cloud computing). L'Informatique dématérialisée est un domaine en plein extension qui consiste à mutualiser les machines/serveurs en définissant des machines virtuelles représentant des fractions des machines/serveurs. Il est nécessaire d'apporter des solutions algorithmiques performantes en termes de temps de calcul et de qualité des solutions. Dans cette thèse, nous nous sommes intéressés dans un premier temps au problème d'ordonnancement sur plusieurs machines (les machines virtuelles) avec contraintes de précédence, c.-à-d., que certaines tâches ne peuvent s'exécuter que si d'autres sont déjà finies. Ces contraintes représentent une subdivision des tâches en sous tâches pouvant s'exécuter sur plusieurs machines virtuelles. Nous avons proposé plusieurs algorithmes génétiques permettant de trouver rapidement une bonne solution réalisable. Nous les avons comparés avec les meilleurs algorithmes génétiques de la littérature et avons défini les types d'instances où les solutions trouvées sont meilleures avec notre algorithme. Dans un deuxième temps, nous avons modélisé ce problème à l'aide de la programmation linéaire en nombres entiers permettant de résoudre à l'optimum les plus petites instances. Nous avons proposé de nouvelles inégalités valides permettant d'améliorer les performances de notre modèle. Nous avons aussi comparé cette modélisation avec plusieurs formulations trouvées dans la littérature. Dans un troisième temps, nous avons analysé de manière approfondie la sous-structure du sous-graphe d'intervalle ne possédant pas de clique de taille donnée. Nous avons étudié le polytope associé à cette sous-structure et nous avons montré que les facettes que nous avons trouvées sont valides pour le problème d'ordonnancement sur plusieurs machines avec contraintes de précédence mais elles le sont aussi pour tout problème d'ordonnancement sur plusieurs machines. Nous avons étendu la modélisation permettant de résoudre le précédent problème afin de résoudre le problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches, c.-à-d., que certaines tâches ne peuvent s'exécuter en même temps que d'autres. Ces contraintes représentent le partage de ressources critiques ne pouvant pas être utilisées par plusieurs tâches. Nous avons proposé des algorithmes de séparation afin d'insérer de manière dynamique nos facettes dans la résolution du problème puis avons développé un algorithme de type Branch-and-Cut. Nous avons analysé les résultats obtenus afin de déterminer les inégalités les plus intéressantes afin de résoudre ce problème. Enfin dans le dernier chapitre, nous nous sommes intéressés au problème d'ordonnancement d'atelier généralisé ainsi que la version plus classique d'ordonnancement d'atelier (open shop). En effet, le problème d'ordonnancement d'atelier généralisé est aussi un cas particulier du problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches. Nous avons proposé une formulation à l'aide de la programmation mathématique pour résoudre ces deux problèmes et nous avons proposé plusieurs familles d'inégalités valides permettant d'améliorer les performances de notre algorithme. Nous avons aussi pu utiliser les contraintes définies précédemment afin d'améliorer les performances pour le problème d'ordonnancement d'atelier généralisé. Nous avons fini par tester notre modèle amélioré sur les instances classiques de la littérature pour le problème d'ordonnancement d'atelier. Nous obtenons de bons résultats permettant d'être plus rapide sur certaines instances
The Cloud Computing appears as a strong concept to share costs and resources related to the use of end-users. As a consequence, several related models exist and are widely used (IaaS, PaaS, SaaS. . .). In this context, our research focused on the design of new methodologies and algorithms to optimize performances using the scheduling and combinatorial theories. We were interested in the performance optimization of a Cloud Computing environment where the resources are heterogeneous (operators, machines, processors...) but limited. Several scheduling problems have been addressed in this thesis. Our objective was to build advanced algorithms by taking into account all these additional specificities of such an environment and by ensuring the performance of solutions. Generally, the scheduling function consists in organizing activities in a specific system imposing some rules to respect. The scheduling problems are essential in the management of projects, but also for a wide set of real systems (telecommunication, computer science, transportation, production...). More generally, solving a scheduling problem can be reduced to the organization and the synchronization of a set of activities (jobs or tasks) by exploiting the available capacities (resources). This execution has to respect different technical rules (constraints) and to provide the maximum of effectiveness (according to a set of criteria). Most of these problems belong to the NP-Hard problems class for which the majority of computer scientists do not expect the existence of a polynomial exact algorithm unless P=NP. Thus, the study of these problems is particularly interesting at the scientific level in addition to their high practical relevance. In particular, we aimed to build new efficient combinatorial methods for solving parallel-machine scheduling problems where resources have different speeds and tasks are linked by precedence constraints. In our work we studied two methodological approaches to solve the problem under the consideration : exact and meta-heuristic methods. We studied three scheduling problems, where the problem of task scheduling in cloud environment can be generalized as unrelated parallel machines, and open shop scheduling problem with different constraints. For solving the problem of unrelated parallel machines with precedence constraints, we proposed a novel genetic-based task scheduling algorithms in order to minimize maximum completion time (makespan). These algorithms combined the genetic algorithm approach with different techniques and batching rules such as list scheduling (LS) and earliest completion time (ECT). We reviewed, evaluated and compared the proposed algorithms against one of the well-known genetic algorithms available in the literature, which has been proposed for the task scheduling problem on heterogeneous computing systems. Moreover, this comparison has been extended to an existing greedy search method, and to an exact formulation based on basic integer linear programming. The proposed genetic algorithms show a good performance dominating the evaluated methods in terms of problems' sizes and time complexity for large benchmark sets of instances. We also extended three existing mathematical formulations to derive an exact solution for this problem. These mathematical formulations were validated and compared to each other by extensive computational experiments. Moreover, we proposed an integer linear programming formulations for solving unrelated parallel machine scheduling with precedence/disjunctive constraints, this model based on the intervaland m-clique free graphs with an exponential number of constraints. We developed a Branch-and-Cut algorithm, where the separation problems are based on graph algorithms. [...]
APA, Harvard, Vancouver, ISO, and other styles
3

Mkadem, Mohamed Amine. "Flow-shop with time delays, linear modeling and exact solution approaches." Thesis, Compiègne, 2017. http://www.theses.fr/2017COMP2390/document.

Full text
Abstract:
Dans le cadre de cette thèse, nous traitons le problème de flow-shop à deux machines avec temps de transport où l’objectif consiste à minimiser le temps de complétion maximal. Dans un premier temps, nous nous sommes intéressés à la modélisation de ce problème. Nous avons proposé plusieurs programmes linéaires en nombres entiers. En particulier, nous avons introduit une formulation linéaire basée sur une généralisation non triviale du modèle d’affectation pour le cas où les durées des opérations sur une même machine sont identiques. Dans un deuxième temps, nous avons élargi la portée de ces formulations mathématiques pour développer plusieurs bornes inférieures et un algorithme exact basé sur la méthode de coupe et branchement (Branch-and-Cut). En effet, un ensemble d’inégalités valides a été considéré afin d’améliorer la relaxation linéaire de ces programmes et d’accélérer leur convergence. Ces inégalités sont basées sur la proposition de nouvelles règles de dominance et l’identification de sous-instances faciles à résoudre. L’identification de ces sous-instances revient à déterminer les cliques maximales dans un graphe d’intervalles. En plus des inégalités valides, la méthode exacte proposée inclut la considération d’une méthode heuristique et d’une procédure visant à élaguer les nœuds. Enfin, nous avons proposé un algorithme par séparation et évaluation (Branch-and-Bound) pour lequel, nous avons introduit des règles de dominance et une méthode heuristique basée sur la recherche locale. Nos expérimentations montrent l’efficacité de nos approches qui dominent celles de la littérature. Ces expérimentations ont été conduites sur plusieurs classes d’instances qui incluent celles de la littérature, ainsi que des nouvelles classes d’instances où les algorithmes de la littérature se sont montrés peu efficaces
In this thesis, we study the two-machine flow-shop problem with time delays in order to minimize the makespan. First, we propose a set of Mixed Integer Programming (MIP) formulations for the problem. In particular, we introduce a new compact mathematical formulation for the case where operations are identical per machine. The proposed mathematical formulations are then used to develop lower bounds and a branch-and-cut method. A set of valid inequalities is proposed in order to improve the linear relaxation of the MIPs. These inequalities are based on proposing new dominance rules and computing optimal solutions of polynomial-time-solvable sub-instances. These sub-instances are extracted by computing all maximal cliques on a particular Interval graph. In addition to the valid inequalities, the branch-and-cut method includes the consideration of a heuristic method and a node pruning procedure. Finally, we propose a branch-and-bound method. For which, we introduce a local search-based heuristic and dominance rules. Experiments were conducted on a variety of classes of instances including both literature and new proposed ones. These experiments show the efficiency of our approaches that outperform the leading methods published in the research literature
APA, Harvard, Vancouver, ISO, and other styles
4

Yuan, Yuan. "Modèles et Algorithmes pour les Problèmes de Livraison du Dernier Kilomètre avec Plusieurs Options d'Expédition." Thesis, Ecole centrale de Lille, 2019. http://www.theses.fr/2019ECLI0011.

Full text
Abstract:
Dans cette thèse, nous étudions les problèmes de tournées de véhicules dans le contexte de la livraison du dernier kilomètre lorsque plusieurs options de livraisons sont proposées aux clients. Le mode de livraison le plus commun est la livraison à domicile ou au travail. La livraison peut également être effectuée dans des points de collecte tels que des consignes ou des magasins. Ces dernières années, un nouveau concept appelé livraison dans le coffre / dans la voiture a été proposé. Avec ce mode de livraison, les colis des clients peuvent être livrés directement dans les coffres des voitures. Notre objectif est de modéliser et de développer des approches de résolution efficaces pour les problèmes de routage dans ce contexte, dans lequel chaque client peut disposer de plusieurs lieux potentiels de livraison. Premièrement, nous proposons un état de l'art sur les problèmes de routage non-Hamiltoniens. Ensuite, nous étudions le cas avec un seul véhicule, qui est modélisé comme un problème du voyageur de commerce généralisé avec fenêtres de temps (GTSPTW). Quatre formulations en programme linéaire à variables mixtes et un algorithme efficace de branch-and-cut sont proposés. Ensuite, nous étudions le cas multi-véhicules, dénommé problème de tournées de véhicules généralisé avec fenêtres de temps (GVRPTW). Une heuristique efficace basée sur la génération de colonnes est proposée pour le résoudre
In this thesis, we study routing problems that arise in the context of last mile delivery when multiple delivery options are proposed to the customers. The most common option to deliver packages is home/workplace delivery. Besides, the delivery can be made to pick-up points such as dedicated lockers or stores. In recent years, a new concept called trunk/in-car delivery has been proposed. Here, customers' packages can be delivered to the trunks of cars. Our goal is to model and develop efficient solution approaches for routing problems in this context, in which each customer can have multiple shipping locations. First, we survey non-Hamiltonian routing problems. Then, we study the single-vehicle case in the considered context, which is modeled as a Generalized Traveling Salesman Problem with Time Windows (GTSPTW). Four mixed integer linear programming formulations and an efficient branch-and-cut algorithm are proposed. Finally, we study the multi-vehicle case which is denoted Generalized Vehicle Routing Problem with Time Windows (GVRPTW). An efficient column generation based heuristic is proposed to solve it
APA, Harvard, Vancouver, ISO, and other styles
5

Vo, Thi Quynh Trang. "Algorithms and Machine Learning for fair and classical combinatorial optimization." Electronic Thesis or Diss., Université Clermont Auvergne (2021-...), 2024. http://www.theses.fr/2024UCFA0035.

Full text
Abstract:
L'optimisation combinatoire est un domaine des mathématiques dans lequel un problème consiste à trouver une solution optimale dans un ensemble fini d'objets. Elle a des applications cruciales dans de nombreux domaines. Le branch-and-cut est l'un des algorithmes les plus utilisés pour résoudre exactement des problèmes d'optimisation combinatoire. Dans cette thèse, nous nous concentrons sur les aspects informatiques du branch-and-cut et plus particulièrement, sur deux aspects importants de l'optimisation combinatoire: l'équité des solutions et l'intégration de l'apprentissage automatique. Dans la partie I, nous étudions deux approches courantes pour traiter la question de l'équité dans l'optimisation combinatoire, qui a fait l'objet d'une attention particulière au cours des dernières décennies. La première approche est l'optimisation combinatoire équilibrée, qui trouve une solution équitable en minimisant la différence entre les plus grands et les plus petits composants utilisés. En raison des difficultés à délimiter ces composants, aucun cadre général exact basé sur la programmation linéaire en nombres entiers mixtes (MILP) n'a été proposé pour l'optimisation combinatoire équilibrée. Pour combler cette lacune, nous présentons au chapitre 3 une nouvelle classe de plans de coupe locaux adaptés aux problèmes d'optimisation combinatoire équilibrée pour l'algorithme du branch-and-cut. Nous démontrons l'efficacité de la méthode proposée dans la cadre du problème du voyageur de commerce équilibré. Notamment, nous introduisons des algorithmes pour trouver des bornes et des mécanismes pour la détermination des variables afin d'accélérer un peu plus les performances. Une deuxième approche pour traiter l'équité est l'optimisation combinatoire Ordered Weighted Average (OWA), qui utilise l'opérateur OWA dans la fonction objectif. En raison de l'opérateur d'ordonnancement, l'optimisation combinatoire OWA est non linéaire, même si ses contraintes d'origine sont linéaires. Deux formulations MILP de tailles différentes ont été introduites dans la littérature pour linéariser l'opérateur OWA. Cependant, la formulation la plus performante pour l'optimisation combinatoire OWA reste incertaine, car l'intégration des méthodes de linéarisation peut introduire des difficultés supplémentaires. Dans le chapitre 4, nous fournissons des comparaisons théoriques et empiriques des deux formulations MILP pour l'optimisation combinatoire OWA. En particulier, nous prouvons que les formulations sont équivalentes en termes de relaxation de programmation linéaire. Nous montrons empiriquement que pour les problèmes d'optimisation combinatoire OWA, la formulation avec le plus de variables peut être résolue plus rapidement avec le branch-and-cut. Dans la partie II, nous développons des méthodes d'application de l'apprentissage automatique pour améliorer les problèmes de décision fondamentaux du branch-and-cut, en mettant l'accent sur la génération de coupes. Ce dernier problème se réfère à la décision de générer des coupes ou des branches à chaque nœud de l'arbre de recherche. Nous démontrons empiriquement que cette décision a un impact significatif sur les performances du branch-and-cut, en particulier pour les coupes combinatoires qui exploitent les faces de la coque convexe des solutions réalisables. Nous proposons ensuite un cadre général combinant l'apprentissage supervisé et l'apprentissage par renforcement afin d'apprendre des stratégies efficaces pour générer des coupes combinatoires dans la méthode branch-and-cut. Notre cadre comporte deux composantes : un détecteur de coupes pour prédire l'existence de coupes et un évaluateur de coupes pour choisir entre la génération de coupes et le branchement. Enfin, nous fournissons des résultats expérimentaux montrant que la méthode proposée est plus performante que les stratégies couramment utilisées pour la génération de coupes, même sur des instances plus grandes que celles utilisées pour l'apprentissage
Combinatorial optimization is a field of mathematics that searches for an optimal solution in a finite set of objects. It has crucial applications in many fields, including applied mathematics, software engineering, theoretical computer science, and machine learning. extit{Branch-and-cut} is one of the most widely-used algorithms for solving combinatorial optimization problems exactly. In this thesis, we focus on the computational aspects of branch-and-cut when studying two critical dimensions of combinatorial optimization: extit{the fairness of solutions} and extit{the integration of machine learning}.In Partef{part:1} (Chaptersef{chap:bnc-btsp} andef{chap:owa}), we study two common approaches to deal with the issue of fairness in combinatorial optimization, which has gained significant attention in the past decades. The first approach is extit{balanced combinatorial optimization}, which finds a fair solution by minimizing the difference between the largest and smallest components used. Due to the difficulties in bounding these components, to the best of our knowledge, no general exact framework based on mixed-integer linear programming (MILP) has been proposed for balanced combinatorial optimization. To address this gap, in Chapteref{chap:bnc-btsp}, we present a branch-and-cut algorithm and a novel class of local cutting planes tailored for balanced combinatorial optimization problems. We demonstrate the effectiveness of the proposed framework in the Balanced Traveling Salesman Problem. Additionally, we introduce bounding algorithms and mechanisms to fix variables to accelerate performance further.The second approach to handling the issue of fairness is extit{Ordered Weighted Average (OWA) combinatorial optimization}, which integrates the OWA operator into the objective function. Due to the ordering operator, OWA combinatorial optimization is nonlinear, even if its original constraints are linear. Two MILP formulations of different sizes have been introduced in the literature to linearize the OWA operator. However, which formulation performs best for OWA combinatorial optimization remains uncertain, as integrating the linearization methods may introduce additional difficulties. In Chapteref{chap:owa}, we provide theoretical and empirical comparisons of the two MILP formulations for OWA combinatorial optimization. In particular, we prove that the formulations are equivalent in terms of the linear programming relaxation. We empirically show that for OWA combinatorial optimization problems, the formulation with more variables can be solved faster with branch-and-cut.In Partef{part:2} (Chapteref{chap:mlbnc}), we develop methods for applying machine learning to enhance fundamental decision problems in branch-and-cut, with a focus on cut generation. Cut generation refers to the decision of whether to generate cuts or to branch at each node of the search tree. We empirically demonstrate that this decision significantly impacts branch-and-cut performance, especially for combinatorial cuts that exploit the facial structure of the convex hull of feasible solutions. We then propose a general framework combining supervised and reinforcement learning to learn effective strategies for generating combinatorial cuts in branch-and-cut. Our framework has two components: a cut detector to predict cut existence and a cut evaluator to choose between generating cuts and branching. Finally, we provide experimental results showing that the proposed method outperforms commonly used strategies for cut generation, even on instances larger than those used for training
APA, Harvard, Vancouver, ISO, and other styles
6

Taktak, Raouia. "Survavibility in Multilayer Networks : models and Polyhedra." Thesis, Paris 9, 2013. http://www.theses.fr/2013PA090076/document.

Full text
Abstract:
Dans cette thèse, nous nous intéressons à un problème de fiabilité dans les réseaux multicouches IP-sur-WDM. Etant donné un ensemble de demandes pour lesquelles on connaît une topologie fiable dans la couche IP, le problème consiste à sécuriser la couche optique WDM en y cherchant une topologie fiable. Nous montrons que le problème est NP-complet même dans le cas d'une seule demande. Ensuite, nous proposons quatre formulations en termes de programmes linéaires en nombres entiers pour le problème. La première est basée sur les contraintes de coupes. Nous considérons le polyèdre associé. Nous identifions de nouvelles familles de contraintes valides et étudions leur aspect facial. Nous proposons également des algorithmes de séparation pour ces contraintes. En utilisant ces résultats, nous développons un algorithme de coupes et branchements pour le problème et présentons une étude expérimentale. La deuxième formulation utilise comme variables des chemins entre des terminaux dans le graphe sous-jacent. Un algorithme de branchements et génération de colonnes est proposé pour cette formulation. Par la suite, nous discutons d'une formulation dite naturelle utilisant uniquement les variables de design. Enfin, nous présentons une formulation étendue compacte qui, en plus des variables naturelles, utilise des variables de routage. Nous montrons que cette formulation fournit une meilleure borne inférieure
This thesis deals with a problem related to survivability issues in multilayer IP-over-WDM networks. Given a set of traffic demands for which we know a survivable logical routing in the IP layer, the aim is determine the corresponding survivable topology in the WDM layer. We show that the problem is NP-hard even for a single demand. Moreover, we propose four integer linear programming formulations for the problem. The first one is based on the so-called cut inequalities. We consider the polyhedron associated with the formulation. We identify several families of valid inequalities and discuss their facial aspect. We also develop separation routines. Using this, we devise a Branch-and-Cut algorithm and present experimental results. The second formulation uses paths between terminals of the underlying graph as variables. We devise a Branch-and-Price algorithm based on that formulation. In addition, we investigate a natural formulation for the problem which uses only the design variables. Finally, we propose an extended compact formulation which, in addition to the design variables, uses routing variables. We show that this formulation provides a tighter bound for the problem
APA, Harvard, Vancouver, ISO, and other styles
7

Naghmouchi, Mohamed yassine. "Gestion de la sécurité dans les systèmes de télécommunications : modèles, polyèdre et algorithmes." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED008.

Full text
Abstract:
Dans cette thèse, nous proposons une nouvelle approche de gestion de risques pour les réseaux de télécommunications. Celle-ci est basée sur le concept de graphes d’analyse de risques appelés Risk Assessment Graphs (RAGs). Ces graphes contiennent deux types de noeuds : des points d’accés qui sont des points de départ pour les attaquants, et des noeuds appelés bien-vulnérabilité. Ces derniers doivent être sécurisés. La propagation potentielle d’un attaquant entre deux noeuds est représentée par un arc dans le RAG. Un poids positif représentant la difficulté de propagation d’un attaquant est associé à chaque arc. D’abord, nous proposons une approche quantitative d’évaluation de risques basée sur le calcul des plus courts chemins entre les points d’accés et les noeuds bien-vulnérabilité. Nous considérons ensuite un problème de traitement de risque appelé Proactive Countermeasure Selection Problem (PCSP). Etant donnés un seuil de difficulté de propagation pour chaque paire de point d’accés et noeud bien-vuln ́erabilité, et un ensemble de contremesures pouvant être placées sur les noeuds bien-vulnérabilité, le problème PCSP consiste à déterminer le sous ensemble de contremesures de coût minimal, de manière à ce que la longueur de chaque plus court chemin d’un point d’accés à un noeud bien-vulnérabilité soit supérieure ou égale au seuil de difficulté de propagation. Nous montrons que le PCSP est NP-complet même quand le graphe est réduit à un arc. Nous donnons aussi une formulation du problème comme un modèle de programmation bi-niveau pour lequel nous proposons deux reformulations en un seul niveau: une formulation compacte basée sur la dualité en programmation linéaire, et une formulation chemins avec un nombre exponentiel de contraintes, obtenue par projection. Nous étudions cette deuxième formulation d’un point de vue polyhèdral. Nous décrivons différentes classes d’inégalités valides. Nous discutons l’aspect facial des inégalités de base et des inégalités valides. Nous concevons aussi des méthodes de séparation pour ces inégalités. En utilisant ces résultats, nous développons un algorithme de coupes et branchements pour le problème. Nous discutons enfin d’une étude numérique approfondie montrant l'éfficacité des résultats polyhèdraux d’un point de vue algorithmique. Notre approche s’applique à une large gamme de cas réels dans le domaine de télécommunications. Nous l’illustrons à travers plusieurs cas d’utilisation couvrant l’internet des objets (IoT), les réseaux orient ́es logiciel (SDN) et les réseaux locaux (LANs). Aussi, nous montrons l’intégration de notre approche dans une application web
In this thesis, we propose a new risk management framework for telecommunication networks. This is based on theconcept of Risk Assessment Graphs (RAGs). These graphs contain two types of nodes: access point nodes, or startingpoints for attackers, and asset-vulnerability nodes. The latter have to be secured. An arc in the RAG represents apotential propagation of an attacker from a node to another. A positive weight, representing the propagation difficulty ofan attacker, is associated to each arc. First, we propose a quantitative risk evaluation approach based on the shortestpaths between the access points and the asset-vulnerability nodes. Then, we consider a risk treatment problem, calledProactive Countermeasure Selection Problem (PCSP). Given a propagation difficulty threshold for each pair of accesspoint and asset-vulnerability node, and a set of countermeasures that can be placed on the asset vulnerability nodes, thePCSP consists in selecting the minimum cost subset of countermeasures so that the length of each shortest path froman access point to an asset vulnerability node is greater than or equal to the propagation difficulty threshold.We show that the PCSP is NP-Complete even when the graph is reduced to an arc. Then, we give a formulation of theproblem as a bilevel programming model for which we propose two single-level reformulations: a compact formulationbased on LP-duality, and a path formulation with an exponential number of constraints, obtained by projection. Moreover,we study the path formulation from a polyhedral point of view. We introduce several classes of valid inequalities. Wediscuss when the basic and valid inequalities define facets. We also devise separation routines for these inequalities.Using this, we develop a Branch-and-Cut algorithm for the PCSP along with an extensive computational study. Thenumerical tests show the efficiency of the polyhedral results from an algorithmic point of view.Our framework applies to a wide set of real cases in the telecommunication industry. We illustrate this in several practicaluse cases including Internet of Things (IoT), Software Defined Network (SDN) and Local Area Networks (LANs). We alsoshow the integration of our approach in a web application
APA, Harvard, Vancouver, ISO, and other styles
8

Hassan, Abdeljabbar Hassan Mohammed Albarra. "Parallel Scheduling in the Cloud Systems : Approximate and Exact Methods." Electronic Thesis or Diss., Université de Lorraine, 2016. http://www.theses.fr/2016LORR0223.

Full text
Abstract:
Cette thèse porte sur la résolution exacte et heuristique de plusieurs problèmes ayant des applications dans le domaine de l'Informatique dématérialisé (cloud computing). L'Informatique dématérialisée est un domaine en plein extension qui consiste à mutualiser les machines/serveurs en définissant des machines virtuelles représentant des fractions des machines/serveurs. Il est nécessaire d'apporter des solutions algorithmiques performantes en termes de temps de calcul et de qualité des solutions. Dans cette thèse, nous nous sommes intéressés dans un premier temps au problème d'ordonnancement sur plusieurs machines (les machines virtuelles) avec contraintes de précédence, c.-à-d., que certaines tâches ne peuvent s'exécuter que si d'autres sont déjà finies. Ces contraintes représentent une subdivision des tâches en sous tâches pouvant s'exécuter sur plusieurs machines virtuelles. Nous avons proposé plusieurs algorithmes génétiques permettant de trouver rapidement une bonne solution réalisable. Nous les avons comparés avec les meilleurs algorithmes génétiques de la littérature et avons défini les types d'instances où les solutions trouvées sont meilleures avec notre algorithme. Dans un deuxième temps, nous avons modélisé ce problème à l'aide de la programmation linéaire en nombres entiers permettant de résoudre à l'optimum les plus petites instances. Nous avons proposé de nouvelles inégalités valides permettant d'améliorer les performances de notre modèle. Nous avons aussi comparé cette modélisation avec plusieurs formulations trouvées dans la littérature. Dans un troisième temps, nous avons analysé de manière approfondie la sous-structure du sous-graphe d'intervalle ne possédant pas de clique de taille donnée. Nous avons étudié le polytope associé à cette sous-structure et nous avons montré que les facettes que nous avons trouvées sont valides pour le problème d'ordonnancement sur plusieurs machines avec contraintes de précédence mais elles le sont aussi pour tout problème d'ordonnancement sur plusieurs machines. Nous avons étendu la modélisation permettant de résoudre le précédent problème afin de résoudre le problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches, c.-à-d., que certaines tâches ne peuvent s'exécuter en même temps que d'autres. Ces contraintes représentent le partage de ressources critiques ne pouvant pas être utilisées par plusieurs tâches. Nous avons proposé des algorithmes de séparation afin d'insérer de manière dynamique nos facettes dans la résolution du problème puis avons développé un algorithme de type Branch-and-Cut. Nous avons analysé les résultats obtenus afin de déterminer les inégalités les plus intéressantes afin de résoudre ce problème. Enfin dans le dernier chapitre, nous nous sommes intéressés au problème d'ordonnancement d'atelier généralisé ainsi que la version plus classique d'ordonnancement d'atelier (open shop). En effet, le problème d'ordonnancement d'atelier généralisé est aussi un cas particulier du problème d'ordonnancement sur plusieurs machines avec des contraintes disjonctives entre les tâches. Nous avons proposé une formulation à l'aide de la programmation mathématique pour résoudre ces deux problèmes et nous avons proposé plusieurs familles d'inégalités valides permettant d'améliorer les performances de notre algorithme. Nous avons aussi pu utiliser les contraintes définies précédemment afin d'améliorer les performances pour le problème d'ordonnancement d'atelier généralisé. Nous avons fini par tester notre modèle amélioré sur les instances classiques de la littérature pour le problème d'ordonnancement d'atelier. Nous obtenons de bons résultats permettant d'être plus rapide sur certaines instances
The Cloud Computing appears as a strong concept to share costs and resources related to the use of end-users. As a consequence, several related models exist and are widely used (IaaS, PaaS, SaaS. . .). In this context, our research focused on the design of new methodologies and algorithms to optimize performances using the scheduling and combinatorial theories. We were interested in the performance optimization of a Cloud Computing environment where the resources are heterogeneous (operators, machines, processors...) but limited. Several scheduling problems have been addressed in this thesis. Our objective was to build advanced algorithms by taking into account all these additional specificities of such an environment and by ensuring the performance of solutions. Generally, the scheduling function consists in organizing activities in a specific system imposing some rules to respect. The scheduling problems are essential in the management of projects, but also for a wide set of real systems (telecommunication, computer science, transportation, production...). More generally, solving a scheduling problem can be reduced to the organization and the synchronization of a set of activities (jobs or tasks) by exploiting the available capacities (resources). This execution has to respect different technical rules (constraints) and to provide the maximum of effectiveness (according to a set of criteria). Most of these problems belong to the NP-Hard problems class for which the majority of computer scientists do not expect the existence of a polynomial exact algorithm unless P=NP. Thus, the study of these problems is particularly interesting at the scientific level in addition to their high practical relevance. In particular, we aimed to build new efficient combinatorial methods for solving parallel-machine scheduling problems where resources have different speeds and tasks are linked by precedence constraints. In our work we studied two methodological approaches to solve the problem under the consideration : exact and meta-heuristic methods. We studied three scheduling problems, where the problem of task scheduling in cloud environment can be generalized as unrelated parallel machines, and open shop scheduling problem with different constraints. For solving the problem of unrelated parallel machines with precedence constraints, we proposed a novel genetic-based task scheduling algorithms in order to minimize maximum completion time (makespan). These algorithms combined the genetic algorithm approach with different techniques and batching rules such as list scheduling (LS) and earliest completion time (ECT). We reviewed, evaluated and compared the proposed algorithms against one of the well-known genetic algorithms available in the literature, which has been proposed for the task scheduling problem on heterogeneous computing systems. Moreover, this comparison has been extended to an existing greedy search method, and to an exact formulation based on basic integer linear programming. The proposed genetic algorithms show a good performance dominating the evaluated methods in terms of problems' sizes and time complexity for large benchmark sets of instances. We also extended three existing mathematical formulations to derive an exact solution for this problem. These mathematical formulations were validated and compared to each other by extensive computational experiments. Moreover, we proposed an integer linear programming formulations for solving unrelated parallel machine scheduling with precedence/disjunctive constraints, this model based on the intervaland m-clique free graphs with an exponential number of constraints. We developed a Branch-and-Cut algorithm, where the separation problems are based on graph algorithms. [...]
APA, Harvard, Vancouver, ISO, and other styles
9

Ahr, Dino. "Multiple postmen problems fundamentals and new algorithms." Saarbrücken VDM Verlag Dr. Müller, 2004. http://d-nb.info/986348074/04.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Hunsaker, Braden K. "Measuring facets of polyhedra to predict usefulness in branch-and-cut algorithms." Diss., Available online, Georgia Institute of Technology, 2004:, 2003. http://etd.gatech.edu/theses/available/etd-04082004-180242/unrestricted/hunsaker%5Fbraden%5Fk%5F200312%5Fphd.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Algorithmes Branch-And-Cut"

1

Nowak, Ivo. "Branch-Cut-and-Price Algorithms." In International Series of Numerical Mathematics, 155–79. Basel: Birkhäuser Basel, 2005. http://dx.doi.org/10.1007/3-7643-7374-1_13.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Fortz, Bernard. "A Branch-and-Cut Algorithm." In Network Theory and Applications, 91–114. Boston, MA: Springer US, 2000. http://dx.doi.org/10.1007/978-1-4615-4669-6_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Salazar-González, Juan-José. "Branch-and-Cut versus Cut-and-Branch Algorithms for Cell Suppression." In Privacy in Statistical Databases, 29–40. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-15838-4_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Becker, Bernd, Markus Behle, Friedrich Eisenbrand, and Ralf Wimmer. "BDDs in a Branch and Cut Framework." In Experimental and Efficient Algorithms, 452–63. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11427186_39.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Kyoda, Yoshiaki, Keiko Imai, Fumihiko Takeuchi, and Akira Tajima. "A branch-and-cut approach for minimum weight triangulation." In Algorithms and Computation, 384–93. Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/3-540-63890-3_41.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Martinelli, Rafael, Diego Pecin, Marcus Poggi, and Humberto Longo. "A Branch-Cut-and-Price Algorithm for the Capacitated Arc Routing Problem." In Experimental Algorithms, 315–26. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-20662-7_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Bergner, Martin, Marco E. Lübbecke, and Jonas T. Witt. "A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs." In Experimental Algorithms, 34–45. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-07959-2_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Abeledo, Hernán, Ricardo Fukasawa, Artur Pessoa, and Eduardo Uchoa. "The Time Dependent Traveling Salesman Problem: Polyhedra and Branch-Cut-and-Price Algorithm." In Experimental Algorithms, 202–13. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-13193-6_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Anjos, Miguel F., Frauke Liers, Gregor Pardella, and Andreas Schmutzer. "Engineering Branch-and-Cut Algorithms for the Equicut Problem." In Discrete Geometry and Optimization, 17–32. Heidelberg: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-319-00200-2_2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Bomze, Immanuel, Markus Chimani, Michael Jünger, Ivana Ljubić, Petra Mutzel, and Bernd Zey. "Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut." In Algorithms and Computation, 427–39. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-17517-6_38.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Algorithmes Branch-And-Cut"

1

Wang, Zicheng, and Zehui Shao. "A Branch and Cut Algorithm for DNA Encoding." In 2007 Second International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA). IEEE, 2007. http://dx.doi.org/10.1109/bicta.2007.4806461.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Reinert, K., H. P. Lenhof, P. Mutzel, K. Mehlhorn, and J. D. Kececioglu. "A branch-and-cut algorithm for multiple sequence alignment." In the first annual international conference. New York, New York, USA: ACM Press, 1997. http://dx.doi.org/10.1145/267521.267845.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Mittal, Adhyan Vijeta, Animisha Sharanappa, Konish Bagchi, Senthil Prabu Ramalingam, and Prabhakar Karthikeyan Shanmugam. "Electric Vehicle Charging Scheduling using Branch and Cut Algorithm." In 2023 3rd International Conference on Advanced Research in Computing (ICARC). IEEE, 2023. http://dx.doi.org/10.1109/icarc57651.2023.10145685.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Lam, Edward, Pierre Le Bodic, Daniel D. Harabor, and Peter J. Stuckey. "Branch-and-Cut-and-Price for Multi-Agent Pathfinding." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/179.

Full text
Abstract:
There are currently two broad strategies for optimal Multi-agent Pathfinding (MAPF): (1) search-based methods, which model and solve MAPF directly, and (2) compilation-based solvers, which reduce MAPF to instances of well-known combinatorial problems, and thus, can benefit from advances in solver techniques. In this work, we present an optimal algorithm, BCP, that hybridizes both approaches using Branch-and-Cut-and-Price, a decomposition framework developed for mathematical optimization. We formalize BCP and compare it empirically against CBSH and CBSH-RM, two leading search-based solvers. Conclusive results on standard benchmarks indicate that its performance exceeds the state-of-the-art: solving more instances on smaller grids and scaling reliably to 100 or more agents on larger game maps.
APA, Harvard, Vancouver, ISO, and other styles
5

Uematsu, Naoya, Shunji Umetani, and Yoshinobu Kawahara. "An Efficient Branch-and-Cut Algorithm for Approximately Submodular Function Maximization." In 2019 IEEE International Conference on Systems, Man and Cybernetics (SMC). IEEE, 2019. http://dx.doi.org/10.1109/smc.2019.8913989.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Sarubbi, J., G. Miranda, H. P. Luna, and G. Mateus. "A Cut-and-Branch algorithm for the Multicommodity Traveling Salesman Problem." In 2008 IEEE International Conference on Service Operations and Logistics, and Informatics (SOLI). IEEE, 2008. http://dx.doi.org/10.1109/soli.2008.4682823.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Peng Wang, Yang Wang, and Qing Xia. "Fast bounding technique for branch-and-cut algorithm based monthly SCUC." In 2012 IEEE Power & Energy Society General Meeting. New Energy Horizons - Opportunities and Challenges. IEEE, 2012. http://dx.doi.org/10.1109/pesgm.2012.6345349.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Liangliang Sun, P. B. Luh, Shian-Ching Chiou, Shi-Chung Chang, Jen-Hsuan Ho, Hsin Yuan Chen, Ji-Lun Chen, Joey Chang, and Sam Hsu. "Efficient dual-armed cluster tool performance via branch and cut optimization algorithm." In 2011 9th World Congress on Intelligent Control and Automation (WCICA 2011). IEEE, 2011. http://dx.doi.org/10.1109/wcica.2011.5970651.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Zhuozan, Gan. "Combining Deep Learning and Branch-and-Cut Algorithm for Transmission-constrained Unit Commitment." In 2024 9th Asia Conference on Power and Electrical Engineering (ACPEE). IEEE, 2024. http://dx.doi.org/10.1109/acpee60788.2024.10532275.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Djeddi, Saoussen, Tarek Bentahar, Atef Bentahar, Riad Saidi, and Hanane Djellab. "A Comparative Analysis of Branch-Cut and Quality-Guided Algorithms For inSAR Interferogram." In 2024 8th International Conference on Image and Signal Processing and their Applications (ISPA). IEEE, 2024. http://dx.doi.org/10.1109/ispa59904.2024.10536705.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Algorithmes Branch-And-Cut"

1

CARR, ROBERT D., GIUSEPPE LANCIA, and SORIN ISTRAIL. Branch-and-Cut Algorithms for Independent Set Problems: Integrality Gap and An Application to Protein Structure Alignment. Office of Scientific and Technical Information (OSTI), September 2000. http://dx.doi.org/10.2172/764804.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Algorithmes Branch-And-Cut' for particular source types:
Journal articles Dissertations / Theses
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography