Extended formulations in mixed integer conic quadratic programming. In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma et al. (INFORMS J Comput 20: 438–450, 2008) and Hijazi et al. (Comput Optim Appl 52: 537–558, 2012) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by Ben-Tal and Nemirovski (Math Oper Res 26(2): 193–205 2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (Math Programm 103(2): 225–249, 2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulation-based algorithms forMICQP.We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers.

References in zbMATH (referenced in 13 articles , 1 standard article )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Atamturk, Alper; Gomez, Andres; Han, Shaoning: Sparse and smooth signal estimation: convexification of (\ell_0)-formulations (2021)
  2. Kocuk, Burak: Rational polyhedral outer-approximations of the second-order cone (2021)
  3. Lin, Yun Hui; Tian, Qingyun: Exact approaches for competitive facility location with discrete attractiveness (2021)
  4. Coey, Chris; Lubin, Miles; Vielma, Juan Pablo: Outer approximation with conic certificates for mixed-integer convex problems (2020)
  5. Atamtürk, Alper; Gómez, Andrés: Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra (2019)
  6. Mehmanchi, Erfan; Gómez, Andrés; Prokopyev, Oleg A.: Fractional 0-1 programs: links between mixed-integer linear and conic quadratic formulations (2019)
  7. Kronqvist, Jan; Lundell, Andreas; Westerlund, Tapio: Reformulations for utilizing separability when solving convex MINLP problems (2018)
  8. Ljubić, Ivana; Moreno, Eduardo: Outer approximation and submodular cuts for maximum capture facility location problems with random utilities (2018)
  9. Lubin, Miles; Yamangil, Emre; Bent, Russell; Vielma, Juan Pablo: Polyhedral approximation in mixed-integer convex optimization (2018)
  10. Dunning, Iain; Huchette, Joey; Lubin, Miles: JuMP: a modeling language for mathematical optimization (2017)
  11. Kılınç, Mustafa R.; Linderoth, Jeff; Luedtke, James: Lift-and-project cuts for convex mixed integer nonlinear programs (2017)
  12. Vielma, Juan Pablo; Dunning, Iain; Huchette, Joey; Lubin, Miles: Extended formulations in mixed integer conic quadratic programming (2017)
  13. Lubin, Miles; Yamangil, Emre; Bent, Russell; Vielma, Juan Pablo: Extended formulations in mixed-integer convex programming (2016)