Tight formulations for some simple mixed integer programs and convex objective integer programs (Q1424279)

In the case of the two variables set \(\{ \, (s,z)\in \mathbb R_+ \times \mathbb Z \, : \, s\geq z-b\, \} (b\in \mathbb R)\) the addition of the mixed integer rounding (MIR) inequality \(s\geq (1+\lfloor b \rfloor -b)(z-\lfloor b \rfloor )\) suffices to give a description of its convex hull. The aim of the paper is to study to what extent similar properties hold for more general sets. Specifically, it is shown that the convex hull of the set \[ V=\{ \, (\sigma ,z)\in \mathbb R_+ ^t\times \mathbb Z \, : \, \sigma _k\geq z-b_k \;\text{ for } \;k=1,\ldots, t\, \} \] is described by the inequalities \[ \sigma _k \geq \max \{ \, 0,z-b_k, (1+\lfloor b_k \rfloor -b_k)(z-\lfloor b_k \rfloor) \, : \, k=1,\ldots, t\, \}. \] Similar results are obtained for sets of the form \[ W=\{ \, (\varphi ,z)\in \mathbb R\times \mathbb Z \, : \, \varphi \geq a_kz-c_k \;\text{ for } \;k=1,\ldots, t\, \}, \] where \(0=a_0=c_0\) and \(a_k\geq 0\) for \(k=1,\ldots, t\). These results imply tight formulation for all single variable piecewise-linear convex functions appearing in the objective function of an integer program. It is also shown that after the addition of constraints on the integer variables with a totally unimodular constraint matrix, the reformulation still has integer solutions. In the case of the set \[ Y=\{(\varphi ,y)\in \mathbb R_+ \times \mathbb Z ^n\, : \, \varphi \geq b_j-y_j \;\text{ for } \;j=1,\dots, n\}, \] (already studied by \textit{Y. Pochet} and \textit{L. A. Wolsey} [Math. Program. 67A, No. 3, 297--323 (1994; Zbl 0822.90049)] and \textit{O. Günlük} and \textit{Y. Pochet} [ibid. 90A, No. 3, 429--457 (2001; Zbl 1041.90033)]), it is addressed the question of what additional constraints can be added without losing integrality. A characterization of the facets of conv\((Z)\), where \[ Z=\{(\varphi ,r,y)\in \mathbb R_+ \times \mathbb R_+ ^n \times \mathbb Z ^n\, : \, \varphi \geq b_j-r_j- y_j \;\text{ for } \;j=1,\dots, n\}, \] is not known, but an extended formulation, related to that presented for \(\text{conv}(Y)\), is given. The results allow reformulations for integer programs with piecewise affine convex objective functions. Applications to discrete lot-sizing are given in another paper by the same authors.