Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

The Intersection of Knapsack Polyhedra and Extensions

Please always quote using this URN: urn:nbn:de:0297-zib-3300
  • This paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvatal-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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Alexander Martin, Robert Weismantel
Document Type:ZIB-Report
Date of first Publication:1997/12/04
Series (Serial Number):ZIB-Report (SC-97-61)
ZIB-Reportnumber:SC-97-61
Published in:Appeared in: Integer Programming and Combinatorial Optimization (R.E. Bixby, E.A. Boyd, and R.Z. Rios-Mercado, Hsg.), Proceedings of the 6th IPCO Conference, 1998, 243-256
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.