Wolsey, Laurence
[UCL]
Yaman, Hande
[Bilkent University]
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.
- Agra A., Constantino M., Description of 2-integer continuous knapsack polyhedra, 10.1016/j.disopt.2005.10.008
- Atamt�rk Alper, On the facets of the mixed?integer knapsack polyhedron, 10.1007/s10107-003-0400-z
- Atamt�rk Alper, On capacitated network design cut?set polyhedra, 10.1007/s101070100284
- Dash, S., Günlük, O., Wolsey, L.A.: The continuous knapsack set. In: Core discussion paper DP2014/7, Core, Université catholique de Louvain, Louvain-la-Neuve, Belgium (2014)
- Gupte, A.: Convex hulls of superincreasing knapsacks and lexicographic orderings. Optim. Online (2012)
- Kellerer Hans, Pferschy Ulrich, Pisinger David, Knapsack Problems, ISBN:9783642073113, 10.1007/978-3-540-24777-7
- Kianfar Kiavash, On n-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets, 10.1016/j.dam.2012.02.025
- Laurent M, Sassano A, A characterization of knapsacks with the max-flow-—min-cut property, 10.1016/0167-6377(92)90041-z
- Lovász L., Graph Theory and Integer Programming, Discrete Optimization I, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium (1979) ISBN:9780444853226 p.141-158, 10.1016/s0167-5060(08)70822-7
- Magnanti Thomas L., Mirchandani Prakash, Vachani Rita, The convex hull of two core capacitated network design problems, 10.1007/bf01580612
- Magnanti Thomas L., Mirchandani Prakash, Vachani Rita, Modeling and Solving the Two-Facility Capacitated Network Loading Problem, 10.1287/opre.43.1.142
- Marchand Hugues, Wolsey Laurence A., The 0-1 Knapsack problem with a single continuous variable, 10.1007/s101070050044
- Marcotte Odile, The cutting stock problem and integer rounding, 10.1007/bf01582013
- Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Interpretations. Wiley-Interscience, New York (1990)
- Pochet Y., Weismantel R., The Sequential Knapsack Polytope, 10.1137/s1052623495285217
- Pochet Yves, Wolsey Laurence A., Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation, 10.1016/0166-218x(95)90600-k
- Richard J.-P.P., de Farias Jr I.R., Nemhauser G.L., Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms, 10.1007/s10107-003-0398-2
| Bibliographic reference |
Wolsey, Laurence ; Yaman, Hande. Continuous knapsack sets with divisible capacities. In: Mathematical Programming, Vol. 156, no.1-2, p. 1-20 (2015) |
| Permanent URL |
http://hdl.handle.net/2078.1/173105 |
