The continuous knapsack set
(2014)
Files
coredp2014_7web.pdf
Open Access - Adobe PDF
- 408.21 KB
Details
- Authors
- 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.
- Affiliations
Citations
Dash, S., Günlük, O., & Wolsey, L. (2014). The continuous knapsack set (CORE Discussion Paper 2014/7). https://hdl.handle.net/2078.5/200547