A Separation Algorithm for the Simple Plant Location Problem

The Simple Plant Location Problem (SPLP) is a well-known NP-hard optimisation problem with applications in logistics. Although many families of facet-defining inequalities are known for the associated polyhedron, very little work has been done on separation algorithms. We present the first ever polynomial-time separation algorithm for the SPLP that separates exactly over an exponentially large family of facet-defining inequalities. We also present some promising computational results.


Eventually published as: L. Galli & A.N. Letchford (2021) A separation algorithm for the simple plant location problem. Oper. Res. Lett., 49(4), 610–615.