ORBi: Köppe Matthias - Intermediate integer programming representations using value disjunctions

Reference : Intermediate integer programming representations using value disjunctions


	Document type :	Scientific journals : Article
	Discipline(s) :	Physical, chemical, mathematical & earth Sciences : Mathematics Engineering, computing & technology : Computer science
	To cite this reference:	http://hdl.handle.net/2268/1129

Title :	Intermediate integer programming representations using value disjunctions
Language :	English
Author, co-author :	Köppe, Matthias [Otto-von-Guericke Universität Magdeburg > Fakultät für Mathematik > Institut für Mathematische Optimierung > >]
	Louveaux, Quentin [Otto-von-Guericke Universität Magdeburg > Fakultät für Mathematik > Institut für Mathematische Optimierung > >]
	Weismantel, Robert [Otto-von-Guericke Universität Magdeburg > Fakultät für Mathematik > Institut für Mathematische Optimierung > >]
Publication date :	May-2008
Journal title :	Discrete Optimization
Publisher :	Elsevier
Volume :	5
Issue/season :	2
Special issue title :	In Memory of George B. Dantzig
Pages :	293-313
Peer reviewed :	Yes
Audience :	International
ISSN :	1572-5286
Abstract :	[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.
Funders :	Commission européenne : Direction générale de la Recherche
Name of the research project :	ADONET
Target :	Researchers ; Professionals
Permalink :	http://hdl.handle.net/2268/1129
DOI :	10.1016/j.disopt.2006.12.003
Other URL :	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
Mentions required by the publisher for OA :	The published version is available at ScienceDirect

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Open access	vd-final.pdf		Author postprint	516.05 kB	View/Open

All documents in ORBi are protected by a user license.

Dspace v1.5