The Intersection of Knapsack Polyhedra and Extensions

Beitrag in einem Sammelwerk


Details zur Publikation

Autor(en): Martin A, Weismantel R
Herausgeber: R.E. Bixby, E.A. Boyd, R.Z. Ríos-Mercado
Titel Sammelwerk: Integer Programming and Combinatorial Optimization
Jahr der Veröffentlichung: 1998
Titel der Reihe: Proceedings of the 6th IPCO Conference
Tagungsband: Integer Programming and Combinatorial Optimization
Seitenbereich: 243 - 256
Sprache: Englisch


Abstract


This paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvátal-Gomory cutting planes and important special cases such as odd hole and clique inequalities for the stable set polyhedron or families of inequalities for the knapsack polyhedron. We analyze how relations between covering and incomparability numbers associated with the matrix can be used to bound coefficients in these inequalities. For the intersection of several knapsack polyhedra, incomparabilities between the column vectors of the associated matrix will be shown to transfer into inequalities of the associated polyhedron. Our scheme has been incorporated into the mixed integer programming code SIP. About experimental results will be reported.



FAU-Autoren / FAU-Herausgeber

Martin, Alexander Prof. Dr.
Lehrstuhl für Wirtschaftsmathematik


Autor(en) der externen Einrichtung(en)
Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)


Zitierweisen

APA:
Martin, A., & Weismantel, R. (1998). The Intersection of Knapsack Polyhedra and Extensions. In R.E. Bixby, E.A. Boyd, R.Z. Ríos-Mercado (Eds.), Integer Programming and Combinatorial Optimization (pp. 243 - 256).

MLA:
Martin, Alexander, and Robert Weismantel. "The Intersection of Knapsack Polyhedra and Extensions." Integer Programming and Combinatorial Optimization Ed. R.E. Bixby, E.A. Boyd, R.Z. Ríos-Mercado, 1998. 243 - 256.

BibTeX: 

Zuletzt aktualisiert 2018-10-08 um 05:25