A characterization of knapsacks with the max-flow-—min-cut property

Laurent, Monique; Sassano, Antonio

Laurent, Monique; Sassano, Antonio (1992), A characterization of knapsacks with the max-flow-—min-cut property, Operations Research Letters, 11, 2, p. 105-110. http://dx.doi.org/10.1016/0167-6377(92)90041-Z

Type

Article accepté pour publication ou publié

Date

1992

Journal name

Operations Research Letters

Volume

Number

Publisher

Elsevier

Pages

105-110

Publication identifier

http://dx.doi.org/10.1016/0167-6377(92)90041-Z

Metadata

Show full item record

Author(s)

Laurent, Monique
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sassano, Antonio

Abstract (EN)

Using a result of Seymour we give a characterization of a class of knapsack problems for which the clutter of minimal covers has the max-flow—min-cut property with respect to all right-hand sides. This implies that adding the minimal cover cuts to the problem is sufficient to guarantee an integer optimum for the linear programming relaxation. We also give a characterization of all the minimal cover cuts for this class of knapsacks.

Subjects / Keywords

integer programming