Tight cycle relaxations for the cut polytope

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

An exact approach to the problem of extracting an embedded network matrix

We study the problem of detecting a maximum embedded network submatrix in a {-1,0,+1}-matrix. Our aim is to solve the problem to optimality. We introduce a 0-1 integer linear formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an … Read more