signed graph

Tight cycle relaxations for the cut polytope

  • Carla Michini
    • Categories 0-1 Programming, Combinatorial Optimization, Polyhedra Tags , , , , ,

    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

  • Cid C. de Souza
  • Martine LabbĂ©
  • R. M. V. Figueiredo
    • Categories Branch and Cut Algorithms, Network Optimization, Polyhedra Tags , , ,

    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