In this thesis we consider four topics all related to using problem reformulations
in order to solve integer programs, i.e. optimization problems in which the decision
variables must be integer.
We first consider the polyhedral approach.
We start by addressing the question of lifting valid inequalities, i.e. finding a
valid inequality for a set Y from the knowledge of a valid inequality for
a lower-dimensional restriction X of Y. We simplify and clarify the presentation of
the procedure. This allows us to derive conditions under which the computation
of the lifting is tractable.
The second topic is the study of valid inequalities for the single node flow set.
The single node flow set is the problem obtained by considering one node
of a fixed charge network flow problem. We derive valid inequalities for this
set and various generalizations. Our approach is a systematic
procedure using only basic tools of integer programming: fixing and
complementing variables, mixed-integer rounding and lifting. The method allows
us to explain and generate a large range of inequalities describing the convex hull of
such sets.
The last two topics are based on non-standard approaches for integer programming.
We first show how the group relaxation approach can be used to provide reformulations
for the integral basis method. This is based on a study of extended formulations
for the group problem. We present four extended formulations and show that the projections of three
of these formulations provide the convex hull of the original group problem.
Initial computational tests of the approach are also reported.
Finally we consider a problem that is difficult for the standard
branch-and-bound approach even for small instances. A reformulation based
on lattice basis reduction is known to be more effective. However
the step to compute the reduced basis is O(n^4) and becomes a bottleneck
for small to medium instances. By using the structure of the problem,
we show that we can decompose the problem and obtain the basis by
taking the kronecker product of two smaller bases easier to compute. Furthermore,
if the two small bases are reduced, the kronecker product is also reduced
up to a reordering of the vectors. Computational results show the gain from such an approach.
| Identifer | oai:union.ndltd.org:BICfB/oai:ucl.ac.be:ETDUCL:BelnUcetd-06142004-100452 |
| Date | 17 June 2004 |
| Creators | Louveaux, Quentin |
| Publisher | Universite catholique de Louvain |
| Source Sets | Bibliothèque interuniversitaire de la Communauté française de Belgique |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://edoc.bib.ucl.ac.be:81/ETD-db/collection/available/BelnUcetd-06142004-100452/ |
| Rights | unrestricted, J'accepte que le texte de la thèse (ci-après l'oeuvre), sous réserve des parties couvertes par la confidentialité, soit publié dans le recueil électronique des thèses UCL. A cette fin, je donne licence à l'UCL : - le droit de fixer et de reproduire l'oeuvre sur support électronique : logiciel ETD/db - le droit de communiquer l'oeuvre au public Cette licence, gratuite et non exclusive, est valable pour toute la durée de la propriété littéraire et artistique, y compris ses éventuelles prolongations, et pour le monde entier. Je conserve tous les autres droits pour la reproduction et la communication de la thèse, ainsi que le droit de l'utiliser dans de futurs travaux. Je certifie avoir obtenu, conformément à la législation sur le droit d'auteur et aux exigences du droit à l'image, toutes les autorisations nécessaires à la reproduction dans ma thèse d'images, de textes, et/ou de toute oeuvre protégés par le droit d'auteur, et avoir obtenu les autorisations nécessaires à leur communication à des tiers. Au cas où un tiers est titulaire d'un droit de propriété intellectuelle sur tout ou partie de ma thèse, je certifie avoir obtenu son autorisation écrite pour l'exercice des droits mentionnés ci-dessus. |
Page generated in 0.0025 seconds