<  Back to the Polytechnique Montréal portal

Étude et séparation des inégalités valides pour des problèmes de partitionnement et de couverture

Mounira Groiez

PhD thesis (2013)

[img]
Preview
Download (850kB)
Cite this document: Groiez, M. (2013). Étude et séparation des inégalités valides pour des problèmes de partitionnement et de couverture (PhD thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/1170/
Show abstract Hide abstract

Abstract

RÉSUMÉ : Cette thèse s'intéresse aux inégalités valides et leurs algorithmes de séparation pour les problèmes de partitionnement et de couverture suivants : le problème d'horaires de véhicules avec plusieurs dépôts (Multiple Depot Vehicle Scheduling Problem, MDVSP), le problème de partitionnement d'ensemble (Set Partitioning Problem, SPP) et le problème du transversal de circuits de cardinalité minimale (MINimum cardinality Feedback Vertex Set problem, MIFVS). Notons que les inégalités valides introduites sont aussi applicables à d'autres problèmes ayant des structures similaires aux problèmes étudiés. Dans la première partie de cette thèse, nous présentons un algorithme combinant la méthode d'élimination de variables, la méthode de séparation et évaluation progressive et la méthode de génération de plans coupants pour la résolution du MDVSP. Nous utilisons la formulation mathématique de multi-flot dans les réseaux, proposée par Ribeiro et Soumis (1994). Pour réduire la taille du problème nous débutons par l'application de la méthode d'élimination de variables. Dans la première phase, nous appliquons une proposition énoncée par Nemhauser et Wosley (1988) et dans la deuxième phase, nous utilisons le principe introduit par Irnich et al.(2010) mais sans génération de colonnes. Ensuite, afin d'améliorer la valeur de la borne inférieure, nous décrivons une méthode de génération de plans coupants. Cette dernière est basée sur une généralisation des inégalités valides introduites par Hadjar et al. (2006). Pour séparer ces inégalités valides, nous proposons d'identifier deux structures particulières propres au MDVSP. Par la suite, nous comparons la performance de différentes stratégies de notre algorithme à l'aide des instances générées aléatoirement. Finalement, nous concluons qu'en général notre algorithme est meilleur que le solveur commercial CPLEX. La première méthode de séparation proposée pour identifier la première structure, que nous nommons structure de cycle impair conflictuel, utilise la similitude entre le problème du stable et le MDVSP. Notre méthode consiste à construire un graphe de conflit à l'aide d'un sous-ensemble d'arcs possédant certaines propriétés dans le multigraphe représentant le MDVSP. Nous prouvons qu'un trou impair dans le graphe de conflit correspond à un cycle impair conflictuel dans le multigraphe du MDVSP. Afin d'identifier les trous impairs nous adaptons l'algorithme proposé par Nemhauser et Sigismondi (1992). En outre, nous démontrons que chaque cycle impair conflictuel permet d'obtenir une inégalité valide violée par la solution fractionnaire courante. Afin d'enrichir ces inégalités, nous décrivons une procédure de liftage. La deuxième méthode de séparation proposée pour identifier la deuxième structure, que nous nommons structure de coupe impaire, exploite la ressemblance entre le problème de couplage et le MDVSP et, par conséquent, entre les inégalités valides du MDVSP et les inégalités d'Edmonds (1965). La relation entre les deux problèmes est basée sur le principe de conflit, pour le problème de couplage, deux arêtes adjacentes sont toujours en conflit et pour le MDVSP deux sous-chemins adjacents peuvent être en conflit s'ils ont la même source ou le même puits ou s'ils sont de couleurs différentes), donc si nous remplaçons un sous-chemin par une arête, alors les inégalités d'Edmonds engendrent des inégalités valides du MDVSP. Afin d'identifier des structures de coupes impaires, nous construisons un graphe de chemins réguliers, où un chemin régulier est une suite d'arcs de même couleur. Ensuite, nous formulons le problème de séparation comme un programme linéaire en nombres entiers et nous prouvons que certaines solutions entières de ce dernier nous permettent d'identifier des inégalités de coupe impaire. Afin de l'enrichir, nous proposons une procédure de liftage. Nous démontrons que chaque coupe impaire liftée correspond à une inégalité valide pour le MDVSP. Dans la deuxième partie de cette thèse, nous proposons la résolution du problème de partitionnement d'ensemble par une méthode combinant la méthode de séparation et évaluation progressive et la méthode de génération de plans coupants. Notons que nous nous intéressons au problème de partitionnement pur. Nous introduisons deux nouvelles classes d'inégalités valides: nommées les inégalités de type I et de type II, pour le problème de partitionnement. En outre, nous formulons le problème de séparation de chaque classe d'inégalités valides comme un programme linéaire en nombres entiers et nous montrons que certaines solutions entières de ce dernier permettent d'identifier des inégalités valides pour le problème de partitionnement. Ensuite, nous proposons de séparer les inégalités de clique en résolvant un autre problème auxiliaire en nombres entiers. Enfin, nous analysons l'efficacité de notre algorithme en utilisant quelques instances de Hoffman et Padberg (1993) et d'autres générées aléatoirement à l'aide du générateur proposé par Lewis et al. (2008). Finalement, nous concluons que notre algorithme est plus efficace que CPLEX lorsque la densité du problème à résoudre est supérieure à 16% et ne l'est pas dans le cas contraire. Dans la dernière partie de cette thèse, nous présentons une méthode combinant la génération de contraintes et des plans coupants afin de résoudre une variante du problème de transversal de circuits de cardinalité minimale. Ce dernier est relié à l'analyse des dictionnaires des langues naturelles. Nous nous intéressons à un des problèmes de linguistique qui consiste à déterminer le nombre minimum de mots à connaître pour comprendre toutes les définitions d'un dictionnaire donné. Ce problème est formulé comme un problème de transversal de circuits de cardinalité minimale. Nous décrivons des méthodes de séparation de trois classes d'inégalités valides : deux classes particulières des inégalités de Chvátal-Gomory et les inégalités de clique de cardinalité 3. Nous formulons le problème de séparation de chaque classe comme un programme linéaire en nombres entiers et nous démontrons que certaines solutions entières permettent d'identifier des inégalités valides pour le problème à résoudre. Enfin, nous présentons et nous analysons les résultats des tests effectués à l'aide des exemplaires extraits de dictionnaires de langue anglaise. Malheureusement, les résultats obtenus ne sont pas concluants étant donné que pour certaines instances nous n'avons pas réussi à trouver les solutions optimales en utilisant le solveur commercial, ni à prouver l'optimalité en utilisant notre algorithme. Néanmoins, nous constatons que l'ajout des inégalités valides permet de trouver de meilleures solutions réalisables dans le temps limite imparti et dans certains cas à trouver la solution optimale. Les travaux présentés dans cette thèse constituent une démarche basée sur les caractéristiques du problème à résoudre. Notre objectif est de présenter de nouveaux algorithmes efficaces pour la séparation des inégalités valides, permettant l'amélioration de la valeur de la relaxation linéaire, mais « bien qu'on ait du cœur à l'ouvrage, l'art est long et le temps est court ». (Charles Baudelaire, Les fleurs du mal).----------ABSTRACT : In this thesis, we study valid inequalities and we propose branch-and-cut algorithms for some classical problems such as : the Multiple Depot Vehicle Scheduling Problem (MDVSP), the Set Partitioning Problem (SPP) and the MINimum cardinality Feedback Set problem (MINFVS). In the first part of this thesis, we present an algorithm combining branch-and-bound, cutting planes and variable fixing to solve the MDVSP. We use the multicommodity flow model of the MDVSP, proposed by Reibero and Soumis (1994). In the first step, we apply a proposition to fix the variables that was introduced by Nemhauser and Wosley (1988) and used by Hadjar et al. (2006). In order to eliminate more variables, we use the same rule as Irnich et al.(2010) but without column generation. In the second step, we describe a method for separating the valid inequalities introduced by Hadjar et al. (2006) and generalized in the present work. Our method identifies two special structures corresponding to valid inequalities. Then we present the results of computational experiments comparing the performance of several strategies using the random instances. We conclude that our algorithm is better than the commercial software. The separation procedure that we propose to identify the first structure, called odd conflictual cycle, uses the similarity between the MDVSP and the stable set problem. We start by creating a conflict graph of the multigraph representing the MDVSP, we consider only the arcs in conflict. Then we prove that each odd hole in this conflict graph is an odd conflictual cycle in the multigraph representing the MDVSP. In order to identify odd holes we adopt the polynomial algorithm proposed by Nemhauser and Sigismondi (1992). Moreover we prove that every odd conflictual cycle identifies a valid inequality violated by the fractional solution. We also present a lifting procedure in order to enrich the valid inequalities. The separation procedure that we present to identify the second structure, called odd set, uses the relationship between the MDVSP and the matching problem, consequently the relationship between the valid inequalities for the MDVSP and the blossom inequalities introduced by Edmonds (1965). In the matching problem two adjacent edges are always in conflict and for the MDVSP two adjacent subpaths may be in conflict (if they are the same source or the same sink or of different colours). In order to identify the odd set, we use the regular path graph, where a regular path is a sequence of the arcs with the same colour. Then we formulate the separation problem as an integer program and we prove that each integer solution identifies, under certain conditions, an odd set. In addition, we present a lifting procedure and we prove that each inequality obtained by lifted odd set is a valid inequality for the MDVSP. In the second part of this thesis, we propose an algorithm combining branch-and-bound and the cutting planes method to solve the set partitioning problem. Note that we are interested in the pure partitioning problem. We derive new classes of valid inequalities for the problem. Moreover, we present a separation procedure for each class by solving an auxiliary integer program using a fractional solution of the set partitioning problem. Then we prove that each integer solution of this program, under certain conditions, is a valid inequality for the problem. We lift this inequality with variables of value $0$. Also we propose to separate a clique inequality by using another auxiliary integer program and we prove that each integer solution of this program, under certain conditions, is a clique inequality for the set partitioning problem. Finally, we present the results of a computational study and we compare our results with the commercial software. Note that we use instances of Hoffman and Padberg (1993) and other randomly generated instances using the generator proposed by Lewis et al. (2008). We conclude that our algorithm is better than the commercial software when the density of the problem is greater than 16% and is not otherwise. In the last part of this thesis, we present a method combining constraint generation and cutting planes generation in order to solve a class of feedback vertex set problem arising in the analysis of the natural language dictionaries. A dictionary is a set of definitions, where a definition consist of one or several sentences represented by the sequence of words. We are interested in the linguistic problem of determining the minimum number of words to know in order to understand all definitions in the dictionary. We propose to separate two classes of Chvátal-Gomory inequalities and clique inequalities of cardinality 3 by solving an auxiliary integer program for each of them. Also we prove that each integer solution of the auxiliary program identifies a valid inequality for the feedback vertex set problem. Finally we present and analyze the resultats of computational experiments using the dictionaries of the English language are available on the Word Wide Web. Unfortunately, the results are not conclusive because we are not able to find optimal solution using a solver commercial or prove optimality using our algorithm. However, we observe that adding the valid inequalities permits to find better feasibles solutions within the time limit prescribed. The work presented in this thesis is an approach based on the characteristics of the problem. Our objective is to present new efficient algorithms for the separation of valid inequalities in order to improve the value of the linear relaxation.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Dissertation/thesis director: Guy Desaulniers and Odile Marcotte
Date Deposited: 23 Oct 2013 13:53
Last Modified: 27 Jun 2019 16:49
PolyPublie URL: https://publications.polymtl.ca/1170/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only