Lifting and Separation Procedures for the Cut Polytope T. Bonato, M. Ju¨nger, G. Reinelt, G. Rinaldi Saarbru¨cken, February 21, 2014 T.Bonatoetal. LiftingandSeparationProceduresfortheCutPolytope 1/33 Outline 1 Max-Cut Problem 2 Contraction-based Separation 3 Computational Results T.Bonatoetal. LiftingandSeparationProceduresfortheCutPolytope 2/33 Outline 1 Max-Cut Problem 2 Contraction-based Separation 3 Computational Results T.Bonatoetal. LiftingandSeparationProceduresfortheCutPolytope 3/33 Any S ⊆ V induces a set δ(S) of edges with exactly one end node in S. The set δ(S) is called a cut of G with shores S and V\S. Finding a cut with maximum aggregate edge weight is known as max-cut problem. Max-Cut Problem Definition Let G = (V,E) be an undirected weighted graph. T.Bonatoetal. LiftingandSeparationProceduresfortheCutPolytope 4/33 Finding a cut with maximum aggregate edge weight is known as max-cut problem. Max-Cut Problem Definition Let G = (V,E) be an undirected weighted graph. S Any S ⊆ V induces a set δ(S) of edges with exactly one end node in S. The set δ(S) is δ(S) called a cut of G with shores S and V\S. V \S T.Bonatoetal. LiftingandSeparationProceduresfortheCutPolytope 4/33 Max-Cut Problem Definition Let G = (V,E) be an undirected weighted graph. S Any S ⊆ V induces a set δ(S) of edges with exactly one end node in S. The set δ(S) is δ(S) called a cut of G with shores S and V\S. V \S Finding a cut with maximum aggregate edge weight is known as max-cut problem. T.Bonatoetal. LiftingandSeparationProceduresfortheCutPolytope 4/33 Applications Unconstrained quadratic +/–1- resp. 0/1-optimization. Computation of ground states of Ising spin glasses. Via minimization in VLSI circuit design. Max-Cut Problem Complexity NP-hard for: general graphs with arbitrary edge weights, almost planar graphs. Polynomial for e.g.: graphs with exclusively negative edge weights, planar graphs, graphs not contractible to K . 5 T.Bonatoetal. LiftingandSeparationProceduresfortheCutPolytope 5/33 Max-Cut Problem Complexity NP-hard for: general graphs with arbitrary edge weights, almost planar graphs. Polynomial for e.g.: graphs with exclusively negative edge weights, planar graphs, graphs not contractible to K . 5 Applications Unconstrained quadratic +/–1- resp. 0/1-optimization. Computation of ground states of Ising spin glasses. Via minimization in VLSI circuit design. T.Bonatoetal. LiftingandSeparationProceduresfortheCutPolytope 5/33 Semimetric polytope MET(G) Relaxation of the max-cut IP formulation described by two inequality classes: Odd-cycle: x(F)−x(C\F) ≤ |F|−1, for each cycle C of G, for all F ⊆ C,|F| odd. Trivial: 0 ≤ x ≤ 1, for all e ∈ E. e CUT(G) and MET(G) have exactly the same integral points. Related Polytopes Cut polytope CUT(G) Convex hull of all incidence vectors of cuts of G. CUT(K3) T.Bonatoetal. LiftingandSeparationProceduresfortheCutPolytope 6/33 CUT(G) and MET(G) have exactly the same integral points. Related Polytopes Cut polytope CUT(G) Convex hull of all incidence vectors of cuts of G. Semimetric polytope MET(G) Relaxation of the max-cut IP formulation described by two inequality classes: CUT(K3) Odd-cycle: x(F)−x(C\F) ≤ |F|−1, for each cycle C of G, for all F ⊆ C,|F| odd. Trivial: 0 ≤ x ≤ 1, for all e ∈ E. e T.Bonatoetal. LiftingandSeparationProceduresfortheCutPolytope 6/33