boolean quadric polytope – Page 2

Tight cycle relaxations for the cut polytope

Published: 2016/06/07, Updated: 2021/09/30

0-1 Programming, Combinatorial Optimization, Polyhedra boolean quadric polytope, cut polytope, cycle relaxation, metric polytope, odd minor, signed graph

We study the problem of optimizing an arbitrary weight function w’z over the metric polytope of a graph G=(V,E), a well-known relaxation of the cut polytope. We define the signed graph (G, E^-), where E^- consists of the edges of G having negative weight. We characterize the sign patterns of the weight vector w such … Read more

A new family of facet defining inequalities for the maximum edge-weighted clique problem

Published: 2015/08/31, Updated: 2017/08/08

Franklin Djeumou Fomeni

0-1 Programming, Combinatorial Optimization, Cutting Plane Approaches boolean quadric polytope, cutting planes, edge-weighted clique problem, facet defining inequalities, in- teger programming, separation algorithm

This paper considers a family of cutting planes, recently developed for mixed 0-1 polynomial programs and shows that they define facets for the maximum edge-weighted clique problem. There exists a polynomial time exact separation algorithm for these in- equalities. The result of this paper may contribute to the development of more efficient algorithms for the … Read more