Mixing polyhedra with two non divisible coefficients
The paper studies the mixed integer set \(X=\{(s,x,y) \in \mathbb{R} \times \mathbb{Z}^n \times \mathbb{Z}^m: s +a_1 x_j \geq b_j,\;j \in N_1, \;s+a_2 y_j \geq d_j,\;j \in N_2\}\), where \(N_1=\{1, \ldots, n\}\), \(N_2 =\{1, \ldots, m\}\) and \(a_1,a_2 \in \mathbb{Z}_+\setminus \{0\}\). After listing basic properties of \(P=conv(X)\), the authors first derive an implicit characterization of the facets of \(P\). This is done by decomposing \(X\) into a small number of subsets that have trivial convex hull descriptions. By using a projection theorem of Balas, they provide an implicit characterization of \(P\). Next, the classes of cycle inequalites and more general lifted cycle inequalities are introduced. The main result shows that all facet defining inequalities of \(P\) are either mixed MIR inequalities or lifted cycle inequalities. Moreover, if \(a_1\) and \(a_2\) are relative prime, then the mixed MIR inequalities suffice to describe \(P\).
- A compact formulation of a mixed-integer set
- Aggregation and Mixed Integer Rounding to Solve MIPs
- Compact formulations as a union of polyhedra
- Cutting planes in integer and mixed integer programming
- Disjunctive programming: Properties of the convex hull of feasible points
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 2084778 (Why is no real title available?)
- Mixing MIR inequalities with two divisible coefficients
- Mixing mixed-integer inequalities
- Network Formulations of Mixed-Integer Programs
- New Hardness Results for Diophantine Approximation
- Production Planning by Mixed Integer Programming
- Strong formulations for mixed integer programs: valid inequalities and extended formulations
- The Mixing Set with Divisible Capacities
- The mixing set with divisible capacities: a simple approach
- The Mixing Set with Flows
- The mixing-MIR set with divisible capacities
- Tight formulations for some simple mixed integer programs and convex objective integer programs
- Facets for continuous multi-mixing set with general coefficients and bounded integer variables
- On the facets of mixed integer programs with two integer variables and two constraints
- Mixed-integer sets from two rows of two adjacent simplex bases
- A compact formulation of a mixed-integer set
- Finding a fully mixed cell in a mixed subdivision of polytopes
- On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints
- On a class of mixed-integer sets with a single integer variable
- Compact formulations as a union of polyhedra
- Mixing MIR inequalities with two divisible coefficients
This page was built for publication: Mixing polyhedra with two non divisible coefficients
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q715089)
