Extended formulations in mixed integer conic quadratic programming
Extended formulations in mixed integer conic quadratic programming
复制标题
混合整数二次二次规划的扩展公式
DOI：
10.1007/s12532-016-0113-y
复制
发表时间：
2015
影响因子：
6.3
通讯作者：
Miles Lubin
中科院分区：
文献类型：
--
作者：
J. Vielma;Iain Dunning;Joey Huchette;Miles Lubin
在本文中，我们考虑使用的LP为基础的算法的混合整数圆锥二次规划（MICQP）的扩展配方。Vielma等人（INFORMS J Comput 20：438-450，2008）和Hijazi等人（Comput Optim Appl 52：537-558，2012）已经使用扩展公式来构建用于MICQP的算法，其可以提供显著的计算优势。第一种方法是基于Ben-Tal和Nemirovski（Math Oper Res 26（2）：193-205 2001）的洛伦兹锥的扩展或提升的多面体松弛，这是非常经济的，但是其近似质量不能迭代地改进。第二种是基于欧几里得球的提升多面体松弛，可以使用Tawarmalani和Sahinidad介绍的技术来构造（Math Matchmm 103（2）：225-249，2005）。这种松弛不太经济，但其近似质量可以迭代地改进。不幸的是，虽然Vielma，Ahmed和Nemhauser的方法适用于一般的MICQP问题，Hijazi，Bonami和Ouorou的方法只能用于MICQP问题的凸二次约束。在本文中，我们将展示如何均匀化过程可以与技术相结合，由Tawarmalani和Sahinnee，以适应Hijazi，Bonami和Ouorou使用的扩展配方一类圆锥混合整数规划问题，包括一般MICQP问题。然后，我们比较这种新的扩展配方对传统的和扩展配方为基础的算法MICQP的有效性。我们发现，这种新的配方可以用来改善各种LP为基础的算法。特别是，制定提供了一个易于实施的程序，在我们的基准测试，显着提高了商业MICQP求解器的性能。
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 for MICQP. 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.