期刊
JOURNAL OF GLOBAL OPTIMIZATION
卷 84, 期 3, 页码 591-606出版社
SPRINGER
DOI: 10.1007/s1OR98-022-01157-9
关键词
Nonconvex quadratic programming; Linear relaxation; Chvatal-Gomory closure; Extended formulation
资金
- Research Training Group 2126 Algorithmic Optimization (ALOP) - German Research Foundation DFG
This paper investigates the use of cutting planes from the Boolean Quadric Polytope to reduce the optimality gap of the NP-hard nonconvex quadratic program with box constraints (BoxQP). By obtaining a compact extended relaxation of all A-odd cycle inequalities, optimization over the Chvatal-Gomory closure can be achieved without repeated calls to separation algorithms and with fewer inequalities. Computational studies confirm the strength of this relaxation and demonstrate that strong bounds can be obtained for the BoxQP, even with a plain linear program, which are significantly stronger than those obtained using heuristic separation of A-odd cycle inequalities by Bonami et al. (Math Program Comput 10(3):333-382, 2018).
Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the NP-hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvatal-Gomory closure of the Boolean Quadric Polytope are A-odd cycle inequalities. We obtain a compact extended relaxation of all A-odd cycle inequalities, which allows to optimize over the Chvatal-Gomory closure without repeated calls to separation algorithms and has less inequalities than the formulation provided by Boros et al. (SIAM J Discrete Math 5(2):163-177, 1992) for sparse matrices. In a computational study, we confirm the strength of this relaxation and show that we can provide very strong bounds for the BoxQP, even with a plain linear program. The resulting bounds are significantly stronger than these from Bonami et al. (Math Program Comput 10(3):333-382, 2018), which arise from separating A-odd cycle inequalities heuristically.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据