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

摘要

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.View full textDownload full textKeywordscombinatorial optimization, semi-definite programming, cutting-plane methods, interior-point algorithms, warm starts, maximum-cut, facility layoutRelated var addthis_config = { ui_cobrand: "Taylor & Francis Online", services_compact: "citeulike,netvibes,twitter,technorati,delicious,linkedin,facebook,stumbleupon,digg,google,more", pubid: "ra-4dff56cd6bb1830b" }; Add to shortlist Link Permalink http://dx.doi.org/10.1080/10556788.2010.544308