ORBi: Louveaux Quentin - Polyhedral properties for the intersection of two knapsacks

Reference : Polyhedral properties for the intersection of two knapsacks


	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/1131

Title :	Polyhedral properties for the intersection of two knapsacks
Language :	English
Author, co-author :	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 :	Mathematical Programming
Publisher :	Springer Science & Business Media B.V.
Volume :	113
Issue/season :	1
Pages :	15-37
Audience :	International
ISSN :	0025-5610
e-ISSN :	1436-4646
Keywords :	[en] Integer Programming ; Knapsacks ; Valid Inequalities
Abstract :	[en] We address the question to what extent polyhedral knowledge about individual knapsack constraints suffices or lacks to describe the convex hull of the binary solutions to their intersection. It turns out that the sign patterns of the weight vectors are responsible for the types of combinatorial valid inequalities appearing in the description of the convex hull of the intersection. In partic- ular, we introduce the notion of an incomplete set inequality which is based on a combinatorial principle for the intersection of two knapsacks. We outline schemes to compute nontrivial bounds for the strength of such inequalities w.r.t. the intersection of the convex hulls of the initial knapsacks. An extension of the inequalities to the mixed case is also given. This opens up the possibility to use the inequalities in an arbitrary simplex tableau.
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/1131
DOI :	10.1007/s10107-006-0045-9
Other URL :	http://www.springerlink.com/content/m040748534724246/?p=9c1c87f43cf64ce78395b3edbfb1ac46&pi=0
Mentions required by the publisher for OA :	The published version is available at springer.com

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Open access	TwoKnapsacks_postprint.pdf		Publisher postprint	224.22 kB	View/Open

All documents in ORBi are protected by a user license.

Dspace v1.5