New developments on polyhedral methods for mixed-integer programming
MetadataShow full item record
Branch-and-cut is today the premier method for solving mixed-integer programming (MIP) problems. The tremendous success of branch-and-cut software is due, in great part, to the developments in the theory of inequality description for MIP polyhedra that took place in the last twenty years. This dissertation is about polyhedral theory for MIP and its use within branch-and-cut to solve difficult instances of MIP efficiently. We focus on two directions. The first is cutting planes for general, unstructured MIP. The second takes advantage of combinational structures that are pervasive in applications. Specifically, we study the polyhedron defined by a knapsack constraint and by special ordered sets of type 2 (SOS2), and by a knapsack and cardinality constraints. A family of inequalities of great importance for solving general MIP is mixed integer rounding (MIR). Here we investigate extensions of MIR inequalities, in the hope of learning more about the structure of general MIP polyhedra, the intractability of MIP, and how MIR may be generalized to give inequalities that are more efficient than the state-of-the-art. We accomplish this by studying extensions of the mixing-MIR set. Specifically, we consider the mixing-MIR set with divisible capacities, the mixing-MIR set with two nondivisible capacities, and the continuous mixing set. We establish the computational complexity of optimization over these sets, the structure of their convex hulls, and we point out how to derive cutting planes valid for them efficiently. A nonlinear function can be approximated to an arbitrary degree of accuracy by a piecewise linear function. This is the main application of piecewise linear optimization (PLO), although it arise on its own in a number of important applications, e.g. economics of scale. In the case of separable continuous PLO, it is best to model the piecewise linear function through SOS2. We give several families of inequalities valid for a set defined by a knapsack and SOS2 constraints. We give separation heuristics for the families of inequalities. Finally, we use them in a branch-and-cut algorithm to solve difficult instances of PLO. As our computational results clearly show, the use of such inequalities can improve considerably our ability to solve such problems, to proven optimality or even heuristically, by branch-and-cut. One of the most difficult, and at the same time important, constraint in operations research is that at most a fixed number of variables in the model is nonzero, such cardinality constraint arises, for example in portfolio selection, data mining, and metabolic engineering. We study the polyhedron defined by a knapsack and a cardinality constraints. Our model and our results generalize significantly the state-of-the art. In particular, our knapsack set proves to be considerably richer than the ones studied so far in the literature. Finally, we present conclusions and discuss directions for further research, some of which we are currently investigating.