Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141732 | Discrete Optimization | 2014 | 11 Pages |
Abstract
A separation algorithm is a procedure for generating cutting planes. Up to now, only a few polynomial-time separation algorithms were known for the Boolean quadric and cut polytopes. These polytopes arise in connection with zero–one quadratic programming and the max-cut problem, respectively. We present a new algorithm, which separates over a class of valid inequalities that includes all odd bicycle wheel inequalities and (2p+1,2)(2p+1,2)-circulant inequalities. It exploits, in a non-trivial way, three known results in the literature: one on the separation of {0,12}-cuts, one on the symmetries of the polytopes in question, and one on an affine mapping between the polytopes.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Adam N. Letchford, Michael M. Sørensen,