Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations
Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations
复制标题
DOI：
10.1007/s10107-010-0340-3
复制
发表时间：
2011
影响因子：
2.7
通讯作者：
Anureet Saxena;Pierre Bonami;Jon Lee
中科院分区：
文献类型：
--
作者：
Anureet Saxena;Pierre Bonami;Jon Lee
产生混合二次约束规划（MIQCP）的凸松弛的一种常见方法是通过引入变量Yij来表示以二次形式出现的变量的每个乘积xixj，从而将问题提升到高维空间。这样的扩展松弛的一个优点是，它们可以有效地加强使用（凸）SDP constraintanddisjunctive规划。另一方面，这样一个扩展配方的主要缺点是其巨大的规模，即使对于问题的数量ofxi变量是温和的。在本文中，我们研究的方法来建立低维松弛的MIQCP捕获的扩展配方的强度。为此，我们使用了在提升和项目方法论的背景下开创的投影技术。我们展示了如何扩展配方可以通过求解线性规划算法投影到原始空间。此外，我们扩展的技术，以项目的SDP松弛求解SDP。在一个MIQCP的情况下，一个单一的二次约束，我们提出了一个基于子梯度的启发式有效地解决这些SDP。我们还提出了一个新的本征reformationfor MIQCP，和切割生成技术，以加强这种使用极性的reformationfor MIQCP。我们提出了广泛的计算结果来说明所提出的技术的效率。我们的计算结果有两个亮点。首先，在GLOBALLib实例上，我们能够生成几乎与我们的同伴论文中提出的一样强的弛豫，尽管我们的计算时间平均小了大约100倍。其次，在box-QP实例上，我们的代码生成的增强松弛几乎与经过充分研究的SDP+RLT松弛一样强，并且可以在不到2秒的时间内求解，即使对于具有100个变量的大型实例也是如此;使用最先进的SDP求解器，同一组实例的SDP+RLT松弛可能需要几个小时才能求解。
A common way to produce a convex relaxation of a Mixed Integer Quadratically Constrained Program (MIQCP) is to lift the problem into a higher-dimensional space by introducing variablesYijto represent each of the productsxixjof variables appearing in a quadratic form. One advantage of such extended relaxations is that they can be efficiently strengthened by using the (convex) SDP constraintand disjunctive programming. On the other hand, the main drawback of such an extended formulation is its huge size, even for problems for which the number ofxivariables is moderate. In this paper, we study methods to build low-dimensional relaxations of MIQCP that capture the strength of the extended formulations. To do so, we use projection techniques pioneered in the context of the lift-and-project methodology. We show how the extended formulation can be algorithmically projected to the original space by solving linear programs. Furthermore, we extend the technique to project the SDP relaxation by solving SDPs. In the case of an MIQCP with a single quadratic constraint, we propose a subgradient-based heuristic to efficiently solve these SDPs. We also propose a neweigen-reformulationfor MIQCP, and a cut generation technique to strengthen this reformulation using polarity. We present extensive computational results to illustrate the efficiency of the proposed techniques. Our computational results have two highlights. First, on the GLOBALLib instances, we are able to generate relaxations that are almost as strong as those proposed in our companion paper even though our computing times are about 100 times smaller, on average. Second, on box-QP instances, the strengthened relaxations generated by our code are almost as strong as the well-studied SDP+RLT relaxations and can be solved in less than 2 s, even for large instances with 100 variables; the SDP+RLT relaxations for the same set of instances can take up to a couple of hours to solve using a state-of-the-art SDP solver.