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 have a huge impact on reducing tree size and proving the feasibility of the problem. Despite the rich literature on mixed-integer linear optimization (MILO), there is no work on heuristic methods specific to MISOCO problems. In this work, we use the optimal Jordan frames of a second-order cone optimization (SOCO) subproblem to generate MILO rounding problems. These rounding problems can provide feasible solutions for the original MISOCO instances in a relatively short time. Based on extensive computational experiments, the proposed heuristics provide feasible solutions for 1327 out of 1328 problems in CBLIB and QPLIB test problems at the root node.
Citation
Sertalp B. Çay, Imre Pólik, and Tamás Terlaky. The first heuristic specifically for mixed-integer second-order cone optimization. Technical Report 18T-002, Lehigh University, January 2018
Article
View The first heuristic specifically for mixed-integer second-order cone optimization