Computational Methods for Discrete Conic Optimization Problems

This thesis addresses computational aspects of discrete conic optimization. Westudy two well-known classes of optimization problems closely related to mixedinteger linear optimization problems. The case of mixed integer second-ordercone optimization problems (MISOCP) is a generalization in which therequirement that solutions be in the non-negative orthant is replaced by arequirement that they be in a second-order cone. Inverse MILP, on the otherhand, is the problem of determining the objective function that makes a givensolution to a given MILP optimal.Although these classes seem unrelated on the surface, the proposedsolution methodology for both classes involves outer approximation of a conicfeasible region by linear inequalities. In both cases, an iterative algorithmin which a separation problem is solved to generate the approximation isemployed. From a complexity standpoint, both MISOCP and inverse MILP areNP--hard. As in the case of MILPs, the usual decision version ofMISOCP is NP-complete, whereas in contrast to MILP, we provide the firstproof that a certain decision version of inverse MILP is rathercoNP-complete.With respect to MISOCP, we first introduce a basic outer approximationalgorithm to solve SOCPs based on a cutting-plane approach. As expected, theperformance of our implementation of such an algorithm is shown to lag behindthe well-known interior point method. Despite this, such a cutting-planeapproach does have promise as a method of producing bounds when embedded withina state-of-the-art branch-and-cut implementation due to its superior ability towarm-start the bound computation after imposing branching constraints. Ourouter-approximation-based branch-and-cut algorithm relaxes both integrality andconic constraints to obtain a linear relaxation. This linear relaxation isstrengthened by the addition of valid inequalities obtained by separatinginfeasible points. Valid inequalities may be obtained by separation from theconvex hull of integer solution lying within the relaxed feasible region or byseparation from the feasible region described by the (relaxed) conicconstraints. Solutions are stored when both integer and conic feasibility isachieved. We review the literature on cutting-plane procedures for MISOCP andmixed integer convex optimization problems.With respect to inverse MILP, we formulate this problem as a conicproblem and derive a cutting-plane algorithm for it. The separation problem inthis algorithm is a modified version of the original MILP. We show that thereis a close relationship between this algorithm and a similar iterativealgorithm for separating infeasible points from the convex hull of solutions tothe original MILP that forms part of the basis for the well-known result ofGrotschel-Lovasz-Schrijver that demonstrates the complexity-wiseequivalence of separation and optimization.In order to test our ideas, we implement a number of software librariesthat together constitute DisCO, a full-featured solver for MISOCP. Thefirst of the supporting libraries is OsiConic, an abstract base classin C++ for interfacing to SOCP solvers. We provide interfaces using thislibrary for widely used commercial and open source SOCP/nonlinear problemsolvers. We also introduce CglConic, a library that implements cuttingprocedures for MISOCP feasible set. We perform extensive computationalexperiments with DisCO comparing a wide range of variants of our proposedalgorithm, as well as other approaches. As DisCO is built on top of a libraryfor distributed parallel tree search algorithms, we also perform experimentsshowing that our algorithm is effective and scalable when parallelized.