Thursday, 13:15 - 13:40 h, Room: MA 041


Adam Letchford
A new separation algorithm for the Boolean quadric and cut polytopes

Coauthor: Michael M. Soerensen


A separation algorithm is a procedure for generating cutting planes. We present new separation algorithms for the Boolean quadric and cut polytopes, which are the polytopes associated with zero-one quadratic programming and the max-cut problem, respectively. Our approach exploits, in a non-trivial way, three known results in the literature: one on the separation of {0,\frac12}-cuts, one on the symmetries of the
polytopes in question, and one on the relationship between the polytopes. We remark that our algorithm for the cut polytope is the first combinatorial polynomial-time algorithm that is capable of separating over a class of valid inequalities that includes all odd bicycle wheel inequalities and all (p,2)-circulant inequalities.


Talk 1 of the invited session Thu.2.MA 041
"Convex approaches for quadratic integer programs" [...]
Cluster 14
"Mixed-integer nonlinear programming" [...]


  Payday Loans In New Jersey. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.