Reference : Polyhedral properties for the intersection of two knapsacks
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/1131
Polyhedral properties for the intersection of two knapsacks
English
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
Mathematical Programming
Springer Science & Business Media B.V.
113
1
15-37
Yes (verified by ORBi)
International
0025-5610
1436-4646
[en] Integer Programming ; Knapsacks ; Valid Inequalities
[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.
Commission européenne : Direction générale de la Recherche
ADONET
Researchers ; Professionals
http://hdl.handle.net/2268/1131
10.1007/s10107-006-0045-9
http://www.springerlink.com/content/m040748534724246/?p=9c1c87f43cf64ce78395b3edbfb1ac46&pi=0
The published version is available at springer.com

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
TwoKnapsacks_postprint.pdfPublisher postprint224.22 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.