The strength of Dantzig-Wolfe reformulations for the stable set and related problems
From MaRDI portal
Publication:1756353
DOI10.1016/j.disopt.2018.07.001zbMath1454.90030OpenAlexW2887249488MaRDI QIDQ1756353
Jonas T. Witt, Marco E. Lübbecke
Publication date: 14 January 2019
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2018.07.001
Lagrangian relaxationDantzig-Wolfe reformulationstable set problempartial convexificationstrength of reformulations
Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- How tight is the corner relaxation? Insights gained from the stable set problem
- Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
- Chordless paths through three vertices
- Critical facets of the stable set polytope
- How tight is the corner relaxation?
- Stable sets, corner polyhedra and the Chvàtal closure
- Fractional matchings and the Edmonds-Gallai theorem
- On the complexity of testing for odd holes and induced odd paths
- On certain polytopes associated with graphs
- Facets with fixed defect of the stable set polytope
- Polyhedral results on the stable set problem in graphs containing even or odd pairs
- Algorithmic graph theory and perfect graphs
- Conflict graphs in solving integer programming problems
- A Lagrangean decomposition for the maximum independent set problem applied to map labeling
- A generic view of Dantzig--Wolfe decomposition in mixed integer programming
- On the critical lines of a graph
- A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems
- Properties of vertex packing and independence system polyhedra
- Perfect zero–one matrices
- Graph Sandwich Problems
- On the facial structure of set packing polyhedra
- Maximum matching and a polyhedron with 0,1-vertices
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A branch-and-price approach for the maximum weight independent set problem
