Strong lift-and-project cutting planes for the stable set problem

DOI10.1007/s10107-012-0513-3zbMath1280.90087OpenAlexW2090669908MaRDI QIDQ378110

Monia Giandomenico, Fabrizio Rossi, Stefano Smriglio

Publication date: 11 November 2013

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-012-0513-3

zbMATH Keywords

cutting planesBenders decompositionLovász and Schrijver lift-and-project operatorsstable set problem

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem ⋮ Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming ⋮ The stable set problem: clique and nodal inequalities revisited ⋮ Strong lift-and-project cutting planes for the stable set problem ⋮ Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms ⋮ Drainage area maximization in unconventional hydrocarbon fields with integer linear programming techniques ⋮ An extended formulation for the 1‐wheel inequalities of the stable set polytope ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ On the Lovász theta function and some variants ⋮ General cut-generating procedures for the stable set polytope ⋮ A new lift-and-project operator ⋮ A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts ⋮ Strengthening Chvátal-Gomory Cuts for the Stable Set Problem ⋮ Symplectic group lattices

Uses Software

• Concorde
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong lift-and-project cutting planes for the stable set problem
• A branch and cut solver for the maximum stable set problem
• The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
• A boundary point method to solve semidefinite programs
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• Valid inequalities for mixed integer linear programs
• Partitioning procedures for solving mixed-variables programming problems
• Geometric algorithms and combinatorial optimization
• A class of facet producing graphs for vertex packing polyhedra
• An exact algorithm for the maximum stable set problem
• Wheel inequalities for stable set polytopes
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Antiweb-wheel inequalities and their separation problems over the stable set polytopes
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
• Exploring the relationship between max-cut and stable set relaxations
• A note on the selection of Benders' cuts
• A New Approach to the Stable Set Problem Based on Ellipsoids
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• On the Shannon capacity of a graph
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• Computational Experience with Stable Set Relaxations
• On the facial structure of set packing polyhedra
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• A branch-and-cut algorithm for the maximum cardinality stable set problem