Continuous knapsack sets with divisible capacities

Laurence Wolsey (), Hand Yaman and ,
Additional contact information
Laurence Wolsey: Université catholique de Louvain, CORE, Belgium
Hand Yaman: Department of Industrial Engineering, Bilkent University, Turkey

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

Abstract: We study two continuous knapsack sets Y≥ and Y≤ with n integer, one unbounded continuous and m bounded continuous variables in either ≥ or ≤ form. When the coefficients of the integer variables are integer and divisible, we show in both cases that the convex hull is the intersection of the bound constraints and 2m polyhedra arising from a continuous knapsack set with a single unbounded continuous variable. The latter polyhedra are in turn completely described by an exponential family of partition inequalities. A polynomial size extended formulation is known in the ≥ case. We provide an extended formulation for the ≤ case. It follows that, given a specific objective function, optimization over both Y≥ and Y≤ can be carried out by solving a polynomial size linear program. A consequence of these results is that the coefficients of the continuous variables all take the values 0 or 1 (after scaling) in any non-trivial facet-defining inequality.

Keywords: continuous knapsack set; splittable flow arec set; divisible capacities; partition inequalities; convex hull (search for similar items in EconPapers)
JEL-codes: C11 C26 (search for similar items in EconPapers)
Date: 2013-12-11
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2013.html (application/pdf)

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

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 ().