Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms
From MaRDI portal
Publication:2949518
DOI10.1137/140966332zbMath1330.90093OpenAlexW2158095962WikidataQ57702126 ScholiaQ57702126MaRDI QIDQ2949518
Adam N. Letchford, Fabrizio Rossi, Monia Giandomenico, Stefano Smriglio
Publication date: 1 October 2015
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/74728/1/ellipsoids_source.pdf
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
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, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, Projective Cutting-Planes, Strengthening Chvátal-Gomory Cuts for the Stable Set Problem
Uses Software
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
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Applications of second-order cone programming
- Geometric algorithms and combinatorial optimization
- Semidefinite programming relaxation for nonconvex quadratic programs
- Second-order cone programming
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On the Slater condition for the SDP relaxations of nonconvex sets
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- 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 New Approach to the Stable Set Problem Based on Ellipsoids
- The Cutting-Plane Method for Solving Convex Programs
- A comparison of the Delsarte and Lovász bounds
- 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
- Computational Experience with Stable Set Relaxations
- ON GROTSCHEL-LOVASZ-SCHRIJVER'S RELAXATION OF STABLE SET POLYTOPES
- Reducibility among Combinatorial Problems
- On the facial structure of set packing polyhedra
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- A Convex Quadratic Characterization of the Lovász Theta Number
- On Polyhedral Approximations of the Second-Order Cone
- Principles and Practice of Constraint Programming – CP 2003
- A branch-and-cut algorithm for the maximum cardinality stable set problem
- Benchmarking optimization software with performance profiles.
