Branch-And-Cut Algorithms for Conic Mixed-Integer Programming

Conic mixed-integer programs (CMIPs) are integer programs with conic constraints. They are natural generalizations of linear mixed-integer programs, and have several applications in several areas, such as, combinatorial optimization, optimal control, finance, and statistical learning theory. However, the current state of solution methodologies for CMIPs is in its infancy. CMIPs are at present solved using the vanilla branch-and-bound method that solves continuous conic relaxations at the nodes of a branch-and-bound search tree. Branch-and-cut methods, that make use of the problem structure for removing fractional solutions of conic relaxations and thereby reducing the search space considerably, have not been explored. Branch-and-cut methods have proved extremely useful in solving linear mixed-integer programs. They are expected to work well in the CMIP case also, because the continuous relaxations of CMIPs can be solved in polynomial time. In this dissertation, we study mixed-integer programs with conic constraints and develop branch-and-cut algorithms to solve them. First, we study unstructured problems and develop valid inequalities for these problems. In Chapter 2, we consider second-order conic mixed-integer programs without any structural assumptions on the conic constraint, and derive general purpose cuts that are linear in a higher dimensional representation of the problem, but are nonlinear in the space of the original variables. These cuts generalize a well-known class of linear cuts, and turn out to be very effective in reducing the computational effort involved in solving some practical problems. In Chapter 3, we consider the problem of lifting conic inequalities that are valid for simple restrictions of conic mixed-integer sets to obtain global valid inequalities. We show that our results generalize several known results of the lifting theory for linear mixed-integer programs. In Chapter 4, we study the problem of mean-risk minimization in the discrete setting, and derive valid inequalities that completely characterize the lower convex envelope of the objective function in the pure binary case. These inequalities prove to be extremely effective in solving large-scale capital budgeting problems. Finally, in Chapter 5, we study the robust binary knapsack polyhedron with an ellipsoidal uncertainty set. We show that there is a strong connection between this polytope, and the binary knapsack polytope. We derive cover inequalities and lifted cover inequalities for the robust knapsack polyhedron. These inequalities prove to be useful in our computational experiments.