The strength of Dantzig-Wolfe reformulations for the stable set and related problems
type: Item
instance of: scholarly article
title: The strength of Dantzig-Wolfe reformulations for the stable set and related problems
zbMATH Open document ID: 1454.90030
author: Marco E. Lübbecke
author: Jonas T. Witt
published in: Discrete Optimization
publication date: 2019-01-14T00:00:00Z
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 7001176
zbMATH Keywords: Dantzig-Wolfe reformulation
zbMATH Keywords: strength of reformulations
zbMATH Keywords: stable set problem
zbMATH Keywords: Lagrangian relaxation
zbMATH Keywords: partial convexification
MaRDI profile type: Publication
full work available at URL: j.disopt.2018.07.001
OpenAlex ID: W2887249488
cites work: A generic view of Dantzig--Wolfe decomposition in mixed integer programming
cites work: Q4178782
cites work: A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
cites work: Stable sets, corner polyhedra and the Chvàtal closure
cites work: How tight is the corner relaxation? Insights gained from the stable set problem
cites work: How tight is the corner relaxation?
cites work: Q3002764
cites work: Conflict graphs in solving integer programming problems
cites work: A branch-and-price approach for the maximum weight independent set problem
cites work: A Lagrangean decomposition for the maximum independent set problem applied to map labeling
cites work: A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems
cites work: Properties of vertex packing and independence system polyhedra
cites work: On the facial structure of set packing polyhedra
cites work: Facets with fixed defect of the stable set polytope
cites work: Critical facets of the stable set polytope
cites work: On the critical lines of a graph
cites work: Q5656790
cites work: Polyhedral results on the stable set problem in graphs containing even or odd pairs
cites work: Q5834711
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Q4078069
cites work: Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
cites work: Fractional matchings and the Edmonds-Gallai theorem
cites work: Perfect zero–one matrices
cites work: Q5659563
cites work: On certain polytopes associated with graphs
cites work: Graph Sandwich Problems
cites work: Algorithmic graph theory and perfect graphs
cites work: On the complexity of testing for odd holes and induced odd paths
cites work: Chordless paths through three vertices
DOI: 10.1016/J.DISOPT.2018.07.001
description: scientific article; zbMATH DE number 7001176