Exploiting Structures in Mixed-Integer Second-Order Cone Optimization Problems for Branch-and-Conic-Cut Algorithms

摘要

This thesis studies computational approaches for mixed-integer second-order cone optimization (MISOCO) problems. MISOCO models appear in many real-world applications, so MISOCO has gained significant interest in recent years. However, despite recent advancements, there is a gap between the theoretical developments and computational practice. Three chapters of this thesis address three areas of computational methodology for an efficient branch-and-conic-cut (BCC) algorithm to solve MISOCO problems faster in practice. These chapters include a detailed discussion on practical work on adding cuts in a BCC algorithm, novel methodologies for warm-starting second-order cone optimization (SOCO) subproblems, and heuristics for MISOCO problems.;The first part of this thesis concerns the development of a novel warm-starting method of interior-point methods (IPM) for SOCO problems. The method exploits the Jordan frames of an original instance and solves two auxiliary linear optimization problems. The solutions obtained from these problems are used to identify an ideal initial point of the IPM. Numerical results on public test sets indicate that the warm-start method works well in practice and reduces the number of iterations required to solve related SOCO problems by around 30-40%.;The second part of this thesis presents novel heuristics for MISOCO problems. These heuristics use the Jordan frames from both continuous relaxations and penalty problems and present a way of finding feasible solutions for MISOCO problems. Numerical results on conic and quadratic test sets show significant performance in terms of finding a solution that has a small gap to optimality.;The last part of this thesis presents application of disjunctive conic cuts (DCC) and disjunctive cylindrical cuts (DCyC) to asset allocation problems (AAP). To maximize the benefit from these powerful cuts, several decisions regarding the addition of these cuts are inspected in a practical setting. The analysis in this chapter gives insight about how these cuts can be added in case-specific settings.