New Valid Inequalities and Facets for the Simple Plant Location Problem
Abstract: The Simple Plant Location Problem is a well-known and NP-hard) combinatorial optimisation problem arising in logistics. We present some new results concerned with the associated family of polyhedra. Our starting point is a family of valid inequalities derived by Karen Aardal. We strengthen that family, using a mixed-integer rounding argument, and then show that the strengthened family can itself be easily generalised. We then show that the original family, the strengthened family, and the generalised family each contain an exponentially large number of facet-defining members.
Keywords: facility location; combinatorial optimisation; branch-and-cut; polyhedral combinatorics
Category 1: Combinatorial Optimization (Polyhedra )
Category 2: Applications -- OR and Management Sciences (Production and Logistics )
Citation: Working paper, Department of Management Science, Lancaster University, August 2015.
Entry Submitted: 08/04/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|