A compact formulation of a mixed-integer set

Abstract

We consider mixed-integer sets of the form X = {(s, y) ∈ ℝ₊ × ℤ ⁿ : s + a _j y _j ≥ b _j , ∀j ∈ N}. A polyhedral characterization for the case where X is defined by two inequalities is provided. From that characterization we give a compact formulation for the particular case where the coefficients of the integer variables can take only two possible integer values a ₁, a ₂ ∈ ℤ₊ : X _n,m = {(s, y) ∈ ℝ₊ × ℤ ^n+m : s + a ₁ y _j ≥ b _j , ∀j ∈ N ₁, s + a ₂ y _j ≥ b _j , j ∈ N ₂} where N ₁ = {1, …, n}, N ₂ = {n + 1, …, n + m}. In addition, we discuss families of facet-defining inequalities for the convex hull of X _n,m .

Keywords:

• polyhedral characterization
• mixed-integer programming
• compact formulation

AMS Subject Classifications::

• 90C11
• 90C57

Acknowledgements

This research was partially supported by Centro de Estudos em Optimização e Controlo–CEOC (first author) and by the Centro de Investigação Operacional–CIO (second author) from the ‘Fundação para a Ciência e a Tecnologia’ FCT, cofinanced by the European Community Fund FEDER.