This thesis addresses computational aspects of discrete conic optimization. We study two well-known classes of optimization problems closely related to mixed integer linear optimization problems. The case of mixed integer second-order cone optimization problems (MISOCP) is a generalization in which the requirement that solutions be in the non-negative orthant is replaced by a requirement that they be in a second-order cone. Inverse MILP, on the other hand, is the problem of determining the objective function that makes a given solution to a given MILP optimal.;Although these classes seem unrelated on the surface, the proposed solution methodology for both classes involves outer approximation of a conic feasible region by linear inequalities. In both cases, an iterative algorithm in which a separation problem is solved to generate the approximation is employed. From a complexity standpoint, both MISOCP and inverse MILP are NP-hard. As in the case of MILPs, the usual decision version of MISOCP is NP-complete, whereas in contrast to MILP, we provide the first proof that a certain decision version of inverse MILP is rather co-NP-complete.;With respect to MISOCP, we first introduce a basic outer approximation algorithm to solve SOCPs based on a cutting-plane approach. As expected, the performance of our implementation of such an algorithm is shown to lag behind the well-known interior point method. Despite this, such a cutting-plane approach does have promise as a method of producing bounds when embedded within a state-of-the-art branch-and-cut implementation due to its superior ability to warm-start the bound computation after imposing branching constraints. Our outer-approximation-based branch-and-cut algorithm relaxes both integrality and conic constraints to obtain a linear relaxation. This linear relaxation is strengthened by the addition of valid inequalities obtained by separating infeasible points. Valid inequalities may be obtained by separation from the convex hull of integer solution lying within the relaxed feasible region or by separation from the feasible region described by the (relaxed) conic constraints. Solutions are stored when both integer and conic feasibility is achieved. We review the literature on cutting-plane procedures for MISOCP and mixed integer convex optimization problems.;With respect to inverse MILP, we formulate this problem as a conic problem and derive a cutting-plane algorithm for it. The separation problem in this algorithm is a modified version of the original MILP. We show that there is a close relationship between this algorithm and a similar iterative algorithm for separating infeasible points from the convex hull of solutions to the original MILP that forms part of the basis for the well-known result of Grotschel-Lovasz-Schrijver that demonstrates the complexity-wise equivalence of separation and optimization.;In order to test our ideas, we implement a number of software libraries that together constitute DisCO, a full-featured solver for MISOCP. The first of the supporting libraries is OsiConic, an abstract base class in C++ for interfacing to SOCP solvers. We provide interfaces using this library for widely used commercial and open source SOCP/nonlinear problem solvers. We also introduce CglConic, a library that implements cutting procedures for MISOCP feasible set. We perform extensive computational experiments with DisCO comparing a wide range of variants of our proposed algorithm, as well as other approaches. As DisCO is built on top of a library for distributed parallel tree search algorithms, we also perform experiments showing that our algorithm is effective and scalable when parallelized.
展开▼
