Optimization Online


On the strength of the cycle relaxation for the boolean quadric polytope

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

Abstract: We study unconstrained zero-one quadratic programming problems. The boolean quadric polytope arises from a standard linearization of the objective function and has been extensively studied in the literature. A well-known relaxation of the boolean quadric polytope is the cycle relaxation, which is closely related to the metric polytope for max-cut. We characterize the sign patterns of the objective function that always yield an integral optimal solution over the cycle relaxation, showing that they correspond to signed graphs with no odd-K4 minor.

Keywords: boolean quadric polytope, metric polytope, signed graph

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming (0-1 Programming )

Citation: University of Wisconsin Madison, 2016

Download: [PDF]

Entry Submitted: 06/07/2016
Entry Accepted: 06/08/2016
Entry Last Modified: 06/07/2016

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