The Intersection of Knapsack Polyhedra and Extensions

Martin A, Weismantel R (1998)

Publication Language: English

Publication Type: Book chapter / Article in edited volumes

Publication year: 1998

Edited Volumes: Integer Programming and Combinatorial Optimization

Series: Proceedings of the 6th IPCO Conference

Pages Range: 243 - 256

Conference Proceedings Title: Integer Programming and Combinatorial Optimization

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.

Authors with CRIS profile

Alexander Martin Economics - Discrete Optimization - Mathematics (EDOM)

Involved external institutions

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

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: Download