Presolving and regularization in mixed-integer second-order cone optimization

Henrik Alsing Friberg

Research output: Book/ReportPh.D. thesisResearch

674 Downloads (Pure)

Abstract

Mixed-integer second-order cone optimization is a powerful mathematical framework capable
of representing both logical conditions and nonlinear relationships in mathematical models of
industrial optimization problems. What is more, solution methods are already part of many
major commercial solvers including that of MOSEK [72] as well as XPRESS [31], GUROBI
[46] and CPLEX [50]. This thesis concerns the performance and reliability of these solvers and
makes two contributions; a theoretical one and a practical one.
In the theoretical part of the thesis a fundamental issue with reliability, affecting both
continuous and mixed-integer conic optimization in general, is discovered and treated. This
part of the thesis continues the studies of facial reduction preceding the work of Borwein and
Wolkowicz [17] in 1981, when the first algorithmic cure for these kinds of reliability issues
were formulated. An important distinction to make between continuous and mixed-integer
optimization, however, is that the reliability issues occurring in mixed-integer optimization
cannot be blamed on the practitioner’s formulation of the problem. Specifically, as shown, the
causes for these issues may well lie within the modifications to the formulation performed by
the solution method itself. Hence, this calls for native support of facial reduction mechanisms
within the commercial solvers to function reliably. In pursuit of such mechanisms, many fast
and accurate heuristics are explored, supplementing the main discovery of this thesis that facial
reduction can be interleaved with common optimization methods of high efficiency. Finally, a
branch-and-bound method utilizing these mechanisms is established.
In the practical part of the thesis, a lack of consensus regarding basic definitions, representations
and file formats is found, thereby increasing barriers for benchmarking with decreased
market transparency as result. These differences are explored and results in the design of a new
file format called The Conic Benchmark Format (CBF). Unlike any other file format for conic
optimization, this one is both cross-platform compatible, high performant and future-proof by
encompassing other conic extensions. Scripts and tools have moreover been developed to aid
parsing (resp. conversion) of the file format in service of software developers (resp. optimization
practitioners), and are actively distributed. The functionality of all of this is proven not only by
first-class citizenship in the modeling language PICOS [87], but also by The Conic Benchmark
Library (CBLIB) where the conversion tools have been used to test its more than a thousand
instances with MOSEK and CPLEX. This benchmark library was compiled as part of this thesis
in support of studies in performance and reliability, but has yet to be used for the theoretical
subjects of this thesis.
Original languageEnglish
PublisherDTU Wind Energy
Number of pages153
Publication statusPublished - 2016

Projects

Combinatorial Optimization over Second-Order and Industrial Applications

Friberg, H. A., Stolpe, M., Andersen, K. H., Andersen, E. D., Andersen, M. S., Pataki, G. & Terlaky, T.

ErhvervsPhD-ordningen VTU

01/10/201204/07/2016

Project: PhD

Cite this