Conflict analysis originally tried to exploit the knowledge that certain nodes in a relaxation-based branch-and-bound are infeasible. It has been extended to derive valid constraints also from feasible nodes. This paper adapts this approach to mixed-integer semidefinite programs. Using dual solutions, the primal constraints are aggregated and the resulting inequalities can be used at different nodes in the tree to tighten variable bounds. We show that this helps to speed up the solutions times by about 8 % on our testset.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Dual Conflict Analysis for Mixed-Integer Semidefinite Programs

  • Marc E. Pfetsch

摘要

Conflict analysis originally tried to exploit the knowledge that certain nodes in a relaxation-based branch-and-bound are infeasible. It has been extended to derive valid constraints also from feasible nodes. This paper adapts this approach to mixed-integer semidefinite programs. Using dual solutions, the primal constraints are aggregated and the resulting inequalities can be used at different nodes in the tree to tighten variable bounds. We show that this helps to speed up the solutions times by about 8 % on our testset.