The continuous knapsack set

Sanjeeb Dash, Oktay Günlük and Laurence A. Wolsey ()
Additional contact information
Sanjeeb Dash: IBM Watson Research Center
Oktay Günlük: IBM Watson Research Center
Laurence A. Wolsey: Université catholique de Louvain, CORE, Belgium

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

Abstract: We study the convex hull of the continuous knapsack set which consists of a single inequality constraint with n non-negative integer and m non-negative bounded continuous variables. When n = 1, this set is a slight generalization of the single arc flow set studied by Magnanti, Mirchandani, and Vachani (1993). We first show that in any facet-defining inequality, the number of distinct non-zero coefficients of the continuous variables is bounded by 2n − n. Our next result is to show that when n = 2, this upper bound is actually 1. This implies that when n = 2, the coefficients of the continuous variables in any facet-defining inequality are either 0 or 1 after scaling, and that all the facets can be obtained from facets of continuous knapsack sets with m = 1. The convex hull of the sets with n = 2 and m = 1 is then shown to be given by facets of either two-variable pure-integer knapsack sets or continuous knapsack sets with n = 2 and m = 1 in which the continuous variable is unbounded. The convex hull of these two sets has been completely described by Agra and Constantino (2006). Finally we show (via an example) that when n = 3, the non-zero coefficients of the continuous variables can take different values.

Keywords: continuous knapsack set; single arc flow set; convex hull; facet coefficients (search for similar items in EconPapers)
JEL-codes: C11 C26 (search for similar items in EconPapers)
Date: 2014-03-12
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2014.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:2014007

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