"""
The Capacitated Facility Location Problem
Each product :math:`j = 1, ... , n` has a production requirement :math:`r_j` and
each facility has capacity :math:`C`. Extensions of this problem arise often in
MILP in problems including network design and rostering.
The MILP formulation of the capacitated facility location problem is
straight-forward. The decision variables are
.. math::
\begin{array}{rcl}
x_{ij} &= &\begin{cases} 1 & \text{if product $j$ is produced at location $i$} \\
0 & \text{otherwise}
\end{cases} \\
y_i &= &\begin{cases} 1 & \text{if a facility is located at location $i$} \\
0 & \text{otherwise}
\end{cases} \\
w_i &= &\text{ ``wasted'' capacity at location $i$}
\end{array}
and the formulation is
.. math::
\begin{array}{rr@{\;}ll r}
\min & \displaystyle \sum_{i=1}^m w_i \\
\text{s.t.} & \displaystyle \sum_{i=1}^m x_{ij} &=1, &j = 1, \ldots, n & \text{ (each product produced)} \\
& \displaystyle \sum_{j=1}^n r_j x_{ij} + w_i &= C y_i, &i = 1, \ldots, m & \text{ (aggregate capacity at location $i$)} \\
& x_{ij} & \le y_i,&i = 1, \ldots, m, j = 1, \ldots, n & \text{ (disaggregate capacity at location $i$)} \\
& x_{ij} \in \{ 0, 1\}, & y_i \in \{0, 1\},&i = 1, \ldots, m, j = 1, \ldots, n
\end{array}
"""
from coinor.pulp import *
# The requirements for the products
PRODUCTS = [1, 2, 3, 4, 5]
#list of requirements
REQUIREMENTS = [7, 5, 3, 2, 2]
# Set of all locations
LOCATIONS = [1, 2, 3, 4, 5]
#Requirement Dictionary
Requirement = dict(zip(PRODUCTS, REQUIREMENTS))
# The capacity of the facilities
Capacity = 8
prob = LpProblem("Facility_Location")
assign_vars = LpVariable.dicts("AtLocation",
[(i, j) for i in LOCATIONS
for j in PRODUCTS],
cat = LpBinary)
use_vars = LpVariable.dicts("UseLocation", LOCATIONS, cat = LpBinary)
waste_vars = LpVariable.dicts("Waste", LOCATIONS, lowBound = 0,
cat = LpContinuous,
upBound = Capacity)
# objective: minimise waste
prob += sum(waste_vars[i] for i in LOCATIONS), "min"
# assignment constraints
for j in PRODUCTS:
prob += sum(assign_vars[(i, j)] for i in LOCATIONS) == 1, 'assignment_%s'%j
# aggregate capacity constraints
for i in LOCATIONS:
prob += sum(assign_vars[(i, j)] * Requirement[j]
for j in PRODUCTS) + waste_vars[i] == \
Capacity * use_vars[i], 'aggregate_capacity_%s'%i
# disaggregate capacity constraints
for i in LOCATIONS:
for j in PRODUCTS:
prob += assign_vars[(i, j)] <= use_vars[i], 'disaggregate_capacity_%s_%s'%(i,j)
prob.solve()
for i in LOCATIONS:
print 'location %s waste %s'%(i, waste_vars[i].value())
for j in PRODUCTS:
if assign_vars[(i, j)].value() >= 0.001:
print '\tproduct %s requirement %s'%(j, Requirement[j])