On a connection between facility location and perfect graphs

DOI10.1016/J.ORL.2014.08.005MaRDI QIDQ1785286zbMATH OpenOpenAlexFDO

Authors Mourad Baïou, Francisco Barahona

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

polyhedral combinatoricsperfect graphsuncapacitated facility location problem

Mathematics Subject Classification ID

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

Recommendations

• On the integrality of some facility location polytopes
• Total dual integrality in some facility location problems
• On the linear relaxation of the \(p\)-median problem
• scientific article; zbMATH DE number 3882470
• Boolean and Graph Theoretic Formulations of the Simple Plant Location Problem

Cites work

• scientific article; zbMATH DE number 3902681 (Why is no real title available?)
• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• Blocking and anti-blocking pairs of polyhedra
• Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
• Fractional vertices, cuts and facets of the simple plant location problem
• On certain polytopes associated with 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 \(p\)-median polytope
• On the facets of the simple plant location packing polytope
• On the integrality of some facility location polytopes
• On the linear relaxation of the \(p\)-median problem
• Perfect zero–one matrices
• Recognizing Berge graphs
• Some facets of the simple plant location polytope
• The strong perfect graph theorem
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts

Cited in

(5)

• Continuous facility location on graphs
• On the integrality of some facility location polytopes
• Hardness and algorithms for variants of line graphs of directed graphs
• Total dual integrality in some facility location problems
• On the Asymmetric Connected Facility Location Polytope

This page was built for publication: On a connection between facility location and perfect graphs

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