Reference : Intermediate integer programming representations using value disjunctions
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/1129
Intermediate integer programming representations using value disjunctions
English
Köppe, Matthias mailto [Otto-von-Guericke Universität Magdeburg > Fakultät für Mathematik > Institut für Mathematische Optimierung > >]
Louveaux, Quentin mailto [Otto-von-Guericke Universität Magdeburg > Fakultät für Mathematik > Institut für Mathematische Optimierung > >]
Weismantel, Robert mailto [Otto-von-Guericke Universität Magdeburg > Fakultät für Mathematik > Institut für Mathematische Optimierung > >]
May-2008
Discrete Optimization
Elsevier
5
2
In Memory of George B. Dantzig
293-313
Yes
International
1572-5286
[en] We introduce a general technique to create an extended formulation
of a mixed-integer program. We classify the integer variables into blocks,
each of which generates a finite set of vector values. The extended formu-
lation is constructed by creating a new binary variable for each generated
value. Initial experiments show that the extended formulation can have a
more compact complete description than the original formulation.
We prove that, using this reformulation technique, the facet descrip-
tion decomposes into one “linking polyhedron” per block and the “aggre-
gated polyhedron”. Each of these polyhedra can be analyzed separately.
For the case of identical coefficients in a block, we provide a complete
description of the linking polyhedron and a polynomial-time separation
algorithm. Applied to the knapsack with a fixed number of distinct coeffi-
cients, this theorem provides a complete description in an extended space
with a polynomial number of variables.
Based on this theory, we propose a new branching scheme that analyzes
the problem structure. It is designed to be applied in those subproblems
of hard integer programs where LP-based techniques do not provide good
branching decisions. Preliminary computational experiments show that it
is successful for some benchmark problems of multi-knapsack type.
Commission européenne : Direction générale de la Recherche
ADONET
Researchers ; Professionals
http://hdl.handle.net/2268/1129
10.1016/j.disopt.2006.12.003
http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B7GWV-4R2HKSB-2&_user=532038&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000026659&_version=1&_urlVersion=0&_userid=532038&md5=1e6930a57d2f2eb5f184c492cd30574e
The published version is available at ScienceDirect

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
vd-final.pdfAuthor postprint516.05 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.