The Intersection of Knapsack Polyhedra and Extensions

Article in Edited Volumes


Publication Details

Author(s): Martin A, Weismantel R
Editor(s): R.E. Bixby, E.A. Boyd, R.Z. Ríos-Mercado
Title edited volumes: Integer Programming and Combinatorial Optimization
Publication year: 1998
Title of series: Proceedings of the 6th IPCO Conference
Conference Proceedings Title: Integer Programming and Combinatorial Optimization
Pages range: 243 - 256
Language: English


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 Authors / FAU Editors

Martin, Alexander Prof. Dr.
Economics - Discrete Optimization - Mathematics (EDOM)


External institutions with authors

Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)


How to cite

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: 

Last updated on 2018-10-08 at 05:25