On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems

Abstract

We describe an improved technique for handling large numbers of cutting planes when using an interior-point method for the solution of linear and semi-definite programming relaxations of combinatorial optimization problems. The approach combines an infeasible primal-dual interior-point algorithm with a cutting-plane scheme that does not solve successive relaxations to optimality, but adds and removes cuts at intermediate iterates based on indicators for cut violation and feasibility of the associated slacks. The slack variables of added cuts are initialized using a recently proposed interior-point warm-start technique that relaxes the interiority condition on the original primal-dual variables and enables a restart from the current iterate without additional centring or correction steps. Our computational tests on relaxations of the maximum-cut and single-row facility-layout problem demonstrate that this new scheme is robust for both unconstrained and constrained binary quadratic problems and that its performance is superior to solving only the final relaxation with all relevant cuts known in advance.

Keywords:

• combinatorial optimization
• semi-definite programming
• cutting-plane methods
• interior-point algorithms
• warm starts
• maximum-cut
• facility layout

Acknowledgements

The authors thank two anonymous referees for their valuable remarks and in particular for suggesting ways to improve the computational comparisons in Table 1. This research was supported by MITACS, by the Natural Sciences and Engineering Research Council of Canada, and by a Fellowship from the Humboldt Foundation.