The strength of Dantzig-Wolfe reformulations for the stable set and related problems

DOI10.1016/J.DISOPT.2018.07.001MaRDI QIDQ1756353zbMATH OpenOpenAlexFDO

Authors Marco E. Lübbecke, Jonas T. Witt

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

zbMATH Keywords

Dantzig-Wolfe reformulationLagrangian relaxationpartial convexificationstable set problemstrength of reformulations

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations
• Partial convexification of general mips by Dantzig-Wolfe reformulation
• Dantzig-Wolfe reformulations for binary quadratic problems
• Reformulation and decomposition of integer programs
• Automatic Dantzig-Wolfe reformulation of mixed integer programs

Cites work

• A branch-and-price approach for the maximum weight independent set problem
• A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A generic view of Dantzig--Wolfe decomposition in mixed integer programming
• A Lagrangean decomposition for the maximum independent set problem applied to map labeling
• Algorithmic graph theory and perfect graphs
• Chordless paths through three vertices
• Conflict graphs in solving integer programming problems
• Critical facets of the stable set polytope
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• Facets with fixed defect of the stable set polytope
• Fractional matchings and the Edmonds-Gallai theorem
• Graph Sandwich Problems
• How tight is the corner relaxation?
• How tight is the corner relaxation? Insights gained from the stable set problem
• scientific article; zbMATH DE number 3496213 (Why is no real title available?)
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• scientific article; zbMATH DE number 3387383 (Why is no real title available?)
• scientific article; zbMATH DE number 3390792 (Why is no real title available?)
• scientific article; zbMATH DE number 3095897 (Why is no real title available?)
• Maximum matching and a polyhedron with 0,1-vertices
• On certain polytopes associated with graphs
• On the complexity of testing for odd holes and induced odd paths
• On the critical lines of a graph
• On the facial structure of set packing polyhedra
• Perfect zero–one matrices
• Polyhedral results on the stable set problem in graphs containing even or odd pairs
• Properties of vertex packing and independence system polyhedra
• Proving integrality gaps without knowing the linear program
• Stable sets, corner polyhedra and the Chvàtal closure

Cited in

(8)

• Enhancing discretized formulations: the knapsack reformulation and the star reformulation
• Quasi-separable Dantzig-Wolfe reformulations for network design
• Partial convexification of general mips by Dantzig-Wolfe reformulation
• Reformulation and decomposition of integer programs
• Consistency cuts for Dantzig-Wolfe reformulations
• A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations
• A data driven Dantzig-Wolfe decomposition framework
• Implied integrality in mixed-integer optimization

This page was built for publication: The strength of Dantzig-Wolfe reformulations for the stable set and related problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756353)