New Valid Inequalities and Facets for the Simple Plant Location Problem

The Simple Plant Location Problem is a well-known (and NP-hard) combinatorial optimisation problem, with applications in logistics. We present a new family of valid inequalities for the associated family of polyhedra, and show that it contains an exponentially large number of new facet-defining members. We also present a new procedure, called facility augmentation, which enables one to derive even more valid and facet-defining inequalities.

Citation

Published as: L. Galli, A.N. Letchford & S.J. Miller (2018) New valid inequalities and facets for the simple plant location problem. European Journal of Operational Research, 269(3), 824–833.