On a connection between facility location and perfect graphs

DOI10.1016/j.orl.2014.08.005zbMath1408.90159OpenAlexW2049900951MaRDI QIDQ1785286

Francisco Barahona, Mourad Baïou

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2014.08.005

zbMATH Keywords

perfect graphspolyhedral combinatoricsuncapacitated facility location problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Discrete location and assignment (90B80)

Cites Work

• Unnamed Item
• Unnamed Item
• On the linear relaxation of the \(p\)-median problem
• The strong perfect graph theorem
• On certain polytopes associated with graphs
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• On the facets of the simple plant location packing polytope
• Recognizing Berge graphs
• On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets
• On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems
• On the Integrality of Some Facility Location Polytopes
• Fractional vertices, cuts and facets of the simple plant location problem
• Some facets of the simple plant location polytope
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Perfect zero–one matrices
• Blocking and anti-blocking pairs of polyhedra
• On the \(p\)-median polytope