发帖
雷达卡
英文文献：An Exact Algorithm for Quadratic Integer Minimization using Nonconvex Relaxations-利用非凸松弛的二次整数极小化的精确算法
英文文献作者：Christoph Buchheim,Marianna De Santis,Laura Palagi,Mauro Piacentini
英文文献摘要：
We propose a branch-and-bound algorithm for minimizing a not necessarily convex quadratic function over integer variables. The algorithm is based on lower bounds computed as continuous minima of the objective function over appropriate ellipsoids. In the nonconvex case, we use ellipsoids enclosing the feasible region of the problem. In spite of the nonconvexity, these minima can be computed quickly. We present several ideas that allow to accelerate the solution of the continuous relaxation within a branch-and-bound scheme and examine the performance of the overall algorithm by computational experiments.
我们提出了一个分枝定界算法来最小化一个在整变量上不一定凸的二次函数。该算法基于目标函数在适当椭球面上连续极小值的下界计算。在非凸情况下，我们用椭球包住问题的可行域。尽管具有非凸性，但这些极小值可以很快地计算出来。我们提出了几个思想，允许加速解决连续松弛在分支和有界方案，并通过计算实验检查整体算法的性能。
京公网安备 11010802022788号
