The continuous knapsack set
In this paper the authors study the continuous knapsack set \(S=S_{LP}\cap (\mathbb{R}^m\times \mathbb{Z}^n)\) where \[ S_{LP}=\{(x,y)\in \mathbb{R}^m \times \mathbb{Z}^n:x_1+x_2+\cdots+x_m+c_1 y_1+c_2 y_2+\cdots+c_n y_n \geq b, u\geq x \geq 0, y \geq 0\} \] with \(u, c, b\in \mathbb{Q} \) and \( u > 0, c > 0, b = u_1+u_2+\cdots+u_m \). The case where \(n=1\), known as the single arc flow set, was first studied by \textit{T. L. Magnanti} et al. [Math. Program. 60, No. 2 (A), 233--250 (1993; Zbl 0788.90071)]. For the case \(n=1\) other authors studied the more general version. Dash at al. first prove, in Section 2, that in any facet-defining inequality, the number of distinct non-zero coefficients of the continuous variables is at most \(2^n-n\) and in Section 3 they study the case when \(n=2\) and show that all facets of \(conv(S)\) can be obtained from three-variable relaxations. The authors analyze the facial structure of \(Q(b,n)\) in Section 4, where \(Q(b,u)\) is the convex hull of non-negative \(w,y_1,y_2\in \mathbb{R}^3\), with \(y_1, y_2\) integral and \(w\leq u\) satisfying \(w+c_1y_1+c_2y_2\geq b\). Finally, in Section 5, they show that the results for \(n=2\) cannot be generalized to \(n\geq 3\).
- Lifted Euclidean inequalities for the integer single node flow set with upper bounds
- Sequence independent lifting for mixed integer programs with variable upper bounds
- The 0-1 knapsack problem with a single continuous variable
- Lifting for mixed integer programs with variable upper bounds
- Continuous knapsack sets with divisible capacities
- Network design arc set with variable upper bounds
- Polyhedral results on single node variable upper-bound flow models with allowed configurations
- Polyhedral description of the integer single node flow set with constant bounds
- Valid inequalities for problems with additive variable upper bounds
- Valid inequalities for the single arc design problem with set-ups
- Description of 2-integer continuous knapsack polyhedra
- Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms
- Mixing sets linked by bidirected paths
- Modeling and Solving the Two-Facility Capacitated Network Loading Problem
- Network design arc set with variable upper bounds
- On splittable and unsplittable flow capacitated network design arc-set polyhedra.
- The convex hull of two core capacitated network design problems
- The splittable flow arc set with capacity and minimum load constraints
This page was built for publication: The continuous knapsack set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962725)
