Optimization Online


New Valid Inequalities and Facets for the Simple Plant Location Problem

Laura Galli(laura.galli***at***unipi.it)
Adam N. Letchford(A.N.Letchford***at***lancaster.ac.uk)
Sebastian J. Miller(sebmiller64***at***hotmail.co.uk)

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.

Download: [PDF]

Entry Submitted: 08/04/2015
Entry Accepted: 08/28/2015
Entry Last Modified: 08/04/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society