Continuous knapsack sets with divisible capacities
(2015) Mathematical Programming — Vol. 156, n° 1-2, p. 1-20 (2015)
Files
rp2730.pdf
Closed Access - Adobe PDF
- 487.94 KB
Details
- Authors
- 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 as the convex hulls of continuous knapsack sets with a single unbounded continuous variable. The latter convex hulls are completely described by an exponential family of partition inequalities and a polynomial size extended formulation is known in the ≥ case. We also 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 m polynomial size linear programs. A further 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 of the convex hull of such sets.
- Affiliations
Citations
Wolsey, L., & Yaman, H. (2015). Continuous knapsack sets with divisible capacities. Mathematical Programming, 156(1-2), 1-20. https://doi.org/10.1007/s10107-015-0868-3 (Original work published 2015)