Mixing polyhedra with two non divisible coefficients
We consider the mixed-integer set where and . 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 (Gunluk and Pochet in Math Programm 90:429-457, 2001), or it is based on a directed cycle on a special bipartite graph. When a (1) and a (2) are relative prime, the convex hull of X is described by the mixed MIR inequalities.
polyhedral description mixed integer programming