A dynamic inequality generation scheme for polynomial programming

被引:9
作者
Ghaddar, Bissan [1 ]
Vera, Juan C. [2 ]
Anjos, Miguel F. [3 ,4 ]
机构
[1] IBM Res Corp, Dublin Technol Campus,Damastown Ind Pk,Mulhuddart, Dublin, Ireland
[2] Tilburg Univ, Tilburg Sch Econ & Management, NL-5000 LE Tilburg, Netherlands
[3] Gerad, Discrete Nonlinear Optimizat Engn, Montreal, PQ H3C 3A7, Canada
[4] Ecole Polytech, Montreal, PQ H3C 3A7, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
Polynomial programming; Binary polynomial programming; Semidefinite programming; Inequality generation; EXPLOITING GROUP SYMMETRY; STABILITY NUMBER; RELAXATIONS; REPRESENTATIONS; OPTIMIZATION; MATRICES; SQUARES; CONES; GRAPH; SUMS;
D O I
10.1007/s10107-015-0870-9
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Hierarchies of semidefinite programs have been used to approximate or even solve polynomial programs. This approach rapidly becomes computationally expensive and is often tractable only for problems of small size. In this paper, we propose a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. As a result, the proposed scheme is in principle scalable to large general polynomial programming problems. When all the variables of the problem are non-negative or when all the variables are binary, the general algorithm is specialized to a more efficient algorithm. In the case of binary polynomial programs, we show special cases for which the proposed scheme converges to the global optimal solution. We also present several examples illustrating the computational behavior of the scheme and provide comparisons with Lasserre's approach and, for the binary linear case, with the lift-and-project method of Balas, Ceria, and Cornu,jols.
引用
收藏
页码:21 / 57
页数:37
相关论文
共 40 条