The 0-1 knapsack problem with a single continuous variable

Hugues Marchand and Laurence A. Wolsey ()
Additional contact information
Hugues Marchand: Columbia Business School, New York. Supported by a CIM Doctoral Fellowship
Laurence A. Wolsey: Center for Operations Research and Econometrics (CORE), Université catholique de Louvain (UCL), Louvain la Neuve, Belgium

No 1997020, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: Constraints arising in practice often contain many 0-1 variables and one or a small number of continuous variables. Existing knapsack separation routines cannot be used on such constraints. Here we study such constraint sets, and derive valid inequalities that can be used as cuts for such sets, as well for more general mixed 0-1 constraints. Specifically we investigate the polyhedral structure of the knapsack problem with a single continuous variable, called the continuous 0-1 knapsack problem. First different classes of facet-defining inequalities are derived based on pro jection and lifting. The order of lifting, particularly of the continuous variable, plays an important role. Secondly we show that the flow cover inequalities derived for the single node flow set, consisting of arc flows into and out of a single node with binary variable lower and upper bounds on each arc, can be obtained from valid inequalities for the continuous 0-1 knapsack problem. Thus the separation heuristic we derive for continuous knapsack sets can also be used to derive cuts for more general mixed 0-1 constraints. Initial computational results on a variety of problems are presented.

Keywords: continuous 0-1 knapsacks; valid inequalities; lifting and projection (search for similar items in EconPapers)
Date: 1997-03-01
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1997.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1997020

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().