Mixing polyhedra with two non divisible coefficients

Abstract

We consider the mixed-integer set X = {(s, x, y) ∈ R × Z^n × Z^m : s + a1 x j ≥ bj , ∀ j ∈ N1, s + a2 y j ≥ dj, j ∈ N2} where N1 = {1,...,n}, N2 = {1,...,m} and a1, a2 ∈ Z_+\{0}. This set may arise in a relaxation of mixed-integer problems such as lot-sizing problems.We decompose X into a small number of subsets whose convex hull description is trivial. The convex hull of X is equal to the closure of the convex hull of the union of those polyhedra. Using a projection theorem from Balas (Discret Appl Math 89:3–44, 1998) we obtain a compact characterization of the facets of the convex hull of X. Then by studying the projection cone we characterize all the facet-defining inequalities of the convex hull of X in the space of the original variables. Each of those inequalities is either a mixed MIR inequality (Günlük and Pochet in Math Programm 90:429–457, 2001), or it is based on a directed cycle on a special bipartite graph. When a1 and a2 are relative prime, the convex hull of X is described by the mixed MIR inequalities.