Facility Location Problems

Facility location problems are a classical example of the use of master-slave constraints.

The following definition of the general facility location problem is from J. E. Beasley's OR-Notes.

The general facility location problem is: given a set of facility locations and a set of customers who are served from the facilities then:
  • which facilities should be used;
  • which customers should be served from which facilities so as to minimise the total cost of serving all the customers.

Given the set of facilities ${\cal F}$ and the set of customers ${\cal C}$, we can define binary (0-1) variables:

  1. $z_f$ = 1 if facility $f$ is used, 0 otherwise;
  2. $y_{fc}$ = 1 if facility $f$ serves customer $c$, 0 otherwise.

Now the following master-slave constraint ensures that facility $f$ only serves customers if it is used:

  \[ \sum_{c \in {\cal C}} y_{fc} \leq |{\cal C}| z_f, f \in {\cal F} \] (1)

The decision variables, objective function and constraints vary depending on the problem, but similar master-slave constraints are always present in facility location problems.

We will not delve into it here, but a "tighter" formulation would use the following constraints instead of (1):

\[ y_{fc} \leq z_f, f \in {\cal F}, c \in {\cal C} \]

Facility Location Case Studies

Results from OpsRes web retrieved at 21:42 (GMT)

\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...
Number of topics: 3

-- TWikiAdminGroup - 22 Apr 2008

Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r3 - 2018-11-23 - TWikiAdminUser
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback