4 minimize the total (weighted) travel cost from n customers
5 to some facilities with fixed costs and capacities.
7 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
9 from pyscipopt
import Model, quicksum, multidict
12 """flp -- model for the capacitated facility location problem
15 - J: set of facilities
16 - d[i]: demand for customer i
17 - M[j]: capacity of facility j
18 - f[j]: fixed cost for using a facility in point j
19 - c[i,j]: unit cost of servicing demand point i from facility j
20 Returns a model, ready to be solved.
27 y[j] = model.addVar(vtype=
"B", name=
"y(%s)"%j)
29 x[i,j] = model.addVar(vtype=
"C", name=
"x(%s,%s)"%(i,j))
32 model.addCons(
quicksum(x[i,j]
for j
in J) == d[i],
"Demand(%s)"%i)
35 model.addCons(
quicksum(x[i,j]
for i
in I) <= M[j]*y[j],
"Capacity(%s)"%i)
38 model.addCons(x[i,j] <= d[i]*y[j],
"Strong(%s,%s)"%(i,j))
42 quicksum(c[i,j]*x[i,j]
for i
in I
for j
in J),
50 """creates example data set"""
51 I,d =
multidict({1:80, 2:270, 3:250, 4:160, 5:180})
52 J,M,f =
multidict({1:[500,1000], 2:[500,1000], 3:[500,1000]})
53 c = {(1,1):4, (1,2):6, (1,3):9,
54 (2,1):5, (2,2):4, (2,3):7,
55 (3,1):6, (3,2):3, (3,3):4,
56 (4,1):8, (4,2):5, (4,3):3,
57 (5,1):10, (5,2):8, (5,3):4,
63 if __name__ ==
"__main__":
65 model =
flp(I,J,d,M,f,c)
70 edges = [(i,j)
for (i,j)
in x
if model.getVal(x[i,j]) > EPS]
71 facilities = [j
for j
in y
if model.getVal(y[j]) > EPS]
73 print(
"Optimal value:", model.getObjVal())
74 print(
"Facilities at nodes:", facilities)
75 print(
"Edges:", edges)
79 import matplotlib.pyplot
as P
83 other = [j
for j
in y
if j
not in facilities]
84 customers = [
"c%s"%i
for i
in d]
85 G.add_nodes_from(facilities)
86 G.add_nodes_from(other)
87 G.add_nodes_from(customers)
91 position = NX.drawing.layout.spring_layout(G)
92 NX.draw(G,position,node_color=
"y",nodelist=facilities)
93 NX.draw(G,position,node_color=
"g",nodelist=other)
94 NX.draw(G,position,node_color=
"b",nodelist=customers)
97 print(
"install 'networkx' and 'matplotlib' for plotting")