La programmation linéaire en nombres entiers est une approche robuste
qui permet de résoudre rapidement de grandes instances de problèmes
d'optimisation discrète. Toutefois, les problèmes gagnent constamment
en complexité et imposent parfois de fortes limites sur le temps de
calcul. Il devient alors nécessaire de développer des méthodes
spécialisées afin de résoudre approximativement ces problèmes, tout en
calculant des bornes sur leurs valeurs optimales afin de prouver la
qualité des solutions obtenues.
Nous proposons d'explorer une approche de reformulation en nombres
entiers guidée par la relaxation lagrangienne. Après l'identification
d'une forte relaxation lagrangienne, un processus systématique permet
d'obtenir une seconde formulation en nombres entiers. Cette
reformulation, plus compacte que celle de Dantzig et Wolfe, comporte
exactement les mêmes solutions entières que la formulation initiale,
mais en améliore la borne linéaire: elle devient égale à la borne
lagrangienne.
L'approche de reformulation permet d'unifier et de généraliser des
formulations et des méthodes de borne connues. De plus, elle offre
une manière simple d'obtenir des reformulations de moins grandes
tailles en contrepartie de bornes plus faibles.
Ces reformulations demeurent de grandes tailles. C'est pourquoi nous
décrivons aussi des méthodes spécialisées pour en résoudre les
relaxations linéaires.
Finalement, nous appliquons l'approche de reformulation à deux
problèmes de localisation. Cela nous mène à de nouvelles formulations
pour ces problèmes; certaines sont de très grandes tailles, mais nos
méthodes de résolution spécialisées les rendent pratiques. / Integer linear programming is a robust and efficient approach to solve
large-scale instances of combinatorial problems. However, problems
constantly gain in complexity and sometimes impose strong constraints
on computation times. We must then develop specialised methods to
compute heuristic primal solutions to the problem and derive lower
bounds on the optimal value, and thus prove the quality of our primal
solutions.
We propose to guide a reformulation approach for mixed integer
programs with Lagrangian relaxations. After the identification of a
strong relaxation, a mechanical process leads to a second integer
formulation. This reformulation is equivalent to the initial one, but
its linear relaxation is equivalent to the strong Lagrangian dual.
We will show that the reformulation approach unifies and generalises
prior formulations and lower bounding approaches, and that it exposes
a simple mechanism to reduce the size of reformulations in return for
weaker bounds.
Nevertheless, our reformulations are large. We address this issue by
solving their linear relaxations with specialised methods.
Finally, we apply the reformulation approach to two location problems.
This yields novel formulations for both problems; some are very large
but, thanks to the aforementioned specialised methods, still
practical.
| Identifer | oai:union.ndltd.org:umontreal.ca/oai:papyrus.bib.umontreal.ca:1866/10538 |
| Date | 12 1900 |
| Creators | Khuong, Paul Virak |
| Contributors | Gendron, Bernard |
| Source Sets | Université de Montréal |
| Language | English |
| Detected Language | French |
| Type | Thèse ou Mémoire numérique / Electronic Thesis or Dissertation |
Page generated in 0.0023 seconds