Optimization Online


Forbidden minors for tight cycle relaxations

Carla Michini (michini***at***wisc.edu)

Abstract: 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 that all optimal vertices of the metric polytope are integral, and we show that they correspond to signed graphs with no odd-K_5 minor. Our result has significant implications for unconstrained zero-one quadratic programming problems. We relate the strength of the cycle relaxation of the boolean quadric polytope to the sign pattern of the objective function. In this case, the sign patterns such that all optimal vertices of the cycle relaxation are integral correspond to signed graphs with no odd-K_4 minor.

Keywords: cut polytope, metric polytope, boolean quadric polytope, cycle relaxation, signed graph, odd minor

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming (0-1 Programming )

Citation: University of Wisconsin - Madison, 2018.

Download: [PDF]

Entry Submitted: 06/07/2016
Entry Accepted: 06/08/2016
Entry Last Modified: 11/26/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society