Optimization Online


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

Sertalp B. Çay(sertalpbilal***at***gmail.com)
Imre Pólik(imre.polik***at***sas.com)
Tamás Terlaky(terlaky***at***lehigh.edu)

Abstract: 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.

Keywords: mixed-integer conic optimization, branch and bound, heuristic methods

Category 1: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming

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

Download: [PDF]

Entry Submitted: 01/22/2018
Entry Accepted: 01/22/2018
Entry Last Modified: 01/22/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society