Mixing polyhedra with two non divisible coefficients (Q715089): Difference between revisions

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\).