Formulations of mixed-integer sets defined by totally unimodular constraint matrices

A mixed-integer program is an optimization problem where one is required to minimize a linear function over a subset defined by a system of linear inequalities, with the additional restriction that some of the variables must take an integer value. Many real-world problems can be formulated as mixed-integer programs. Solving mixed-integer programs is difficult in general. A common approach to tackle this kind of problems exploits the fact that (under mild assumptions) the convex hull of feasible solutions is a polyhedron. When the inequalities describing such a polyhedron are known explicitly, the mixed-integer program reduces to a linear program, which is a tractable problem. Unfortunately it is usually very hard to find a linear inequality description of the convex hull of feasible solutions of a mixed-integer program. However in some cases the introduction of additional variables allows one to give a simple description of such a convex hull by means of linear inequalities in a higher dimensional space. Such a description is called an extended formulation. If an extended formulation is known that is compact (i.e. it uses a polynomial number of variables and constraints), the original mixed-integer programming problem can be solved in polynomial time by means of linear programming algorithms. In this dissertation we study the family of mixed-integer programs whose feasible regions are defined by linear systems with totally unimodular matrices (i.e. all subdeterminants are 0, 1 or -1) having at most two nonzero entries per row. This class of problems is interesting because many instances arising e.g. in the context of production planning can be formulated as mixed-integer programs of this type. We illustrate a technique to construct an extended formulation for any problem in this family. The approach is based on the enumeration of all possible fractional parts that the variables take at the vertices of the convex hull of the feasible region. We then discuss the compactness of our extended formulation: we give sufficient conditions ensuring that the formulation is compact. When one of these conditions holds, the mixed-integer program can be solved in polynomial time. We also show how our technique can be successfully applied to some interesting practical problems. Next we consider the possibility of describing the convex hull of the feasible region in the original space of definition of the problem (i.e with no additional variables). Such a formulation is found explicitly for some special cases. Finally a possible extension is discussed: we show how a generalization of our technique can lead to a compact extended formulation for a problem that does not belong to the family introduced above.