On Selecting Disjunctions for Solving Mixed Integer Programming Problems.

Mixed integer linear programs (MIPs) offer a flexible way to model a variety of real-world problems. In this thesis, we undertake a comprehensive study of "general disjunctions" that are a fundamental concept underlying most solution techniques for MIPs, with the aim of extending the current understanding of the theory of these disjunctions and also of developing novel ways of using them so as to enhance the performance of current state of the art MIP solvers. Solving MIPs is difficult both theoretically (it lies in the class of so called NP -hard problems) and in practice as well. Two algorithms that have been most successful in solving MIPs are the "branch-and-bound" and the "cutting-plane" algorithm. The concept of valid disjunctions, which are logical conditions that will be satisfied by any feasible solution is fundamental to both these algorithms. In branch-and-bound, one recursively imposes valid disjunctions on the problem to create smaller "subproblems" and solves the LP relaxations of these subproblems until a solution is found or the problem can be shown infeasible. The cutting-plane algorithm works on the principle that any inequality valid for each subproblem resulting from the imposition of a given disjunction is also valid for the original MIP. Such valid inequalities are iteratively added until an optimal solution is exposed or the feasible region can be shown to be empty. The performance of both algorithms thus greatly depends on which valid disjunctions are selected and imposed at each step. In this thesis, we consider the problem of selecting disjunctions from a rich class that we call "general disjunctions." Our work is divided into two parts: theory and computation. In the first part, we analyze the computational complexity of finding the "optimal" disjunction based on specific criteria. We show that the problem is in general NP -hard, i.e., this problem is theoretically as difficult as solving the original MIP. We also show that the problem of selecting a general disjunction remains NP -hard when several natural restrictions are imposed. These results lead to analogous results for the branch-and-bound and the cutting-plane algorithm: the problem of selecting a general disjunction that maximally improves the bound when used to branch and the problem of finding an "elementary split inequality" that maximally improves the bound are both NP -hard. We also develop a polynomial-time algorithm that solves the separation problem for the elementary split closure when the point to be separated lies on an edge (i.e., a one dimensional face) of the feasible region of the LP relaxation. In the second part, we perform several computational experiments to study the effect of employing methods for finding an "optimal" general disjunction on the performance of the branch-and-cut algorithm. We start by formulating the problem of finding an "optimal" general disjunction as a MIP. In a branch-and-bound setting, the solutions obtained from exact solution of these problems lead to significant reduction in the number of steps in the recursive procedure. When the set of allowed disjunctions is further restricted, one can use explicit enumeration techniques to select the optimal disjunction. We develop a procedure that eliminates poor choices of disjunctions in such a procedure by analyzing the solutions obtained from other disjunctions. We observe in our experiments that the use of this procedure reduces significantly the number of disjunctions that are evaluated for two particular types of general disjunctions. We also use the disjunctions obtained from the techniques described above to generate valid inequalities. We...