Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization

Quantum computing has attracted significant interest in the optimization community because it potentially can solve classes of optimization problems faster than conventional supercomputers. Several researchers proposed quantum computing methods, especially Quantum Interior Point Methods (QIPMs), to solve convex optimization problems, such as Linear Optimization, Semidefinite Optimization, and Second-order Cone Optimization problems. Most of them have … Read more

Formulations of the max k-cut problem on classical and quantum computers

Recent claims on “solving” combinatorial optimization problems via quantum computers have attracted researchers to work on quantum algorithms. The max k-cut problem is a challenging combinatorial optimization problem with multiple notorious mixed integer linear optimization formulations. In this paper, we revisit the binary quadratic optimization formulation of Carlson and Nemhauser (Operations Research, 1966) and provide … Read more

The first heuristic specifically for mixed-integer second-order cone optimization

Mixed-integer second-order cone optimization (MISOCO) has become very popular in the last decade. Various aspects of solving these problems in Branch and Conic Cut (BCC) algorithms have been studied in the literature. This study aims to fill a gap and provide a novel way to find feasible solutions early in the BCC algorithm. Such solutions … Read more

On Pathological Disjunctions and Redundant Disjunctive Conic Cuts

The development of Disjunctive Conic Cuts (DCCs) for Mixed Integer Second Order Cone Optimization (MISOCO) problems has recently gained significant interest in the optimization community. In this paper, we explore the pathological disjunctions where disjunctive cuts do not tighten the description of the feasible set. We focus on the identification of cases when the generated … Read more

The Inmate Assignment and Scheduling Problem and its Application in the PA Department of Correction

The inmate assignment project, in close collaboration with the Pennsylvania Department of Corrections (PADoC), took five years from start to successful implementation. In this project, we developed the Inmate Assignment Decision Support System (IADSS), where the primary goal is simultaneous and system-wide optimal assignment of inmates to correctional institutions (CIs). We develop a novel hier- … Read more

Quadratic convergence to the optimal solution of second-order conic optimization without strict complementarity

Under primal and dual nondegeneracy conditions, we establish the quadratic convergence of Newton’s method to the unique optimal solution of second-order conic optimization. Only very few approaches have been proposed to remedy the failure of strict complementarity, mostly based on nonsmooth analysis of the optimality conditions. Our local convergence result depends on the optimal partition … Read more

A rounding procedure for semidefinite optimization

Recently, Mohammad-Nezhad and Terlaky studied the identification of the optimal partition for semidefinite optimization. An approximation of the optimal partition was obtained from a bounded sequence of solutions on, or in a neighborhood of the central path. Here, we use the approximation of the optimal partition in a rounding procedure to generate an approximate maximally … Read more

Warm-start of interior point methods for second order cone optimization via rounding over optimal Jordan frames

Interior point methods (IPM) are the most popular approaches to solve Second Order Cone Optimization (SOCO) problems, due to their theoretical polynomial complexity and practical performance. In this paper, we present a warm-start method for primal-dual IPMs to reduce the number of IPM steps needed to solve SOCO problems that appear in a Branch and … Read more

A Complete Characterization of Disjunctive Conic Cuts for Mixed Integer Second Order Cone Optimization

We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization problem. We extend our prior work on disjunctive conic cuts, which has thus far been restricted to the case in which the intersection of the hyperplanes and … Read more

On the identification of optimal partition for semidefinite optimization

The concept of the optimal partition was originally introduced for linear optimization and linear complementarity problems and subsequently extended to semidefinite optimization. For linear optimization and sufficient linear complementarity problems, from a central solution sufficiently close to the optimal set, the optimal partition and a maximally complementary optimal solution can be identified in strongly polynomial … Read more