Reference : Valid inequalities for the intersection of two knapsacks
Scientific congresses and symposiums : Unpublished conference/Abstract
Physical, chemical, mathematical & earth Sciences : Mathematics
Valid inequalities for the intersection of two knapsacks
Louveaux, Quentin mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Système et modélisation : Optimisation discrète >]
9th combinatorial optimization workshop
March 2005
[en] Integer programming ; 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 combi- natorial valid inequalities appearing in the description of the convex hull of the intersection. In particular, we introduce the notion of an incom- plete 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.

File(s) associated to this reference

Fulltext file(s):

Open access
aussois05ql.pdfAuthor preprint87.16 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.