Split disjunctions and mixed integer linear programs

A Mixed Integer Linear Program (MILP) is an optimization problem, where the objective is to optimize a linear function, the variables have to satisfy a number of linear constraints, and some variables have to have integer values. Many practical problems can be modeled as MILP problems. This work focuses on the use of split disjunctions to solve (general) MILP problems.; In the first part, we relate split cuts and intersection cuts. Both these classes of cuts are derived from split disjunctions. We show that any split cut can be obtained as an intersection cut. This result is then used to give a new proof of the fact that the split closure is a polyhedron.; In the second part, we use the fact that the classical Mixed Integer Gomory (MIG) cuts are split cuts to improve their performance. The MIG cuts are currently the most effective in commercial codes. We provide a closed form formula for the distance cut off by any split cut. We use this formula to design an algorithm for improving the performance of MIG cuts. The idea is to start with the MIG cuts, and then iteratively produce other split cuts. We found that, on several test problems, these new cuts can substantially enhance the performance of a branch-and-bound algorithm.; To solve a MILP, it is important that the LP relaxation provides a good approximation to the mixed integer hull. In the third part, we address this issue by considering the following questions. When can a coefficient of the LP relaxation be improved, and which inequalities can replace the constraints of the LP relaxation to give a better approximation to the set of mixed integer solutions? We show that, if an improving inequality exists, then it is possible to improve a coefficient. We then discuss how to use split disjunctions to improve the formulation of MILP problems. In a computational experiment we demonstrate that coefficient strengthening can significantly reduce the size of the search three in a cut-and-branch framework.