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, SCIP_PARAMSETTING
13 """flp -- model for the capacitated facility location problem
16 - J: set of facilities
17 - d[i]: demand for customer i
18 - M[j]: capacity of facility j
19 - f[j]: fixed cost for using a facility in point j
20 - c[i,j]: unit cost of servicing demand point i from facility j
21 Returns a model, ready to be solved.
24 master = Model(
"flp-master")
25 subprob = Model(
"flp-subprob")
30 y[j] = master.addVar(vtype=
"B", name=
"y(%s)"%j)
40 y[j] = subprob.addVar(vtype=
"B", name=
"y(%s)"%j)
42 x[i,j] = subprob.addVar(vtype=
"C", name=
"x(%s,%s)"%(i,j))
45 subprob.addCons(
quicksum(x[i,j]
for j
in J) == d[i],
"Demand(%s)"%i)
48 subprob.addCons(
quicksum(x[i,j]
for i
in I) <= M[j]*y[j],
"Capacity(%s)"%i)
51 subprob.addCons(x[i,j] <= d[i]*y[j],
"Strong(%s,%s)"%(i,j))
54 quicksum(c[i,j]*x[i,j]
for i
in I
for j
in J),
58 return master, subprob
62 """creates example data set"""
63 I,d =
multidict({1:80, 2:270, 3:250, 4:160, 5:180})
64 J,M,f =
multidict({1:[500,1000], 2:[500,1000], 3:[500,1000]})
65 c = {(1,1):4, (1,2):6, (1,3):9,
66 (2,1):5, (2,2):4, (2,3):7,
67 (3,1):6, (3,2):3, (3,3):4,
68 (4,1):8, (4,2):5, (4,3):3,
69 (5,1):10, (5,2):8, (5,3):4,
75 if __name__ ==
"__main__":
77 master, subprob =
flp(I,J,d,M,f,c)
79 master.setPresolve(SCIP_PARAMSETTING.OFF)
80 master.setBoolParam(
"misc/allowstrongdualreds",
False)
81 master.setBoolParam(
"benders/copybenders",
False)
82 master.initBendersDefault(subprob)
88 master.computeBestSolSubproblems()
92 facilities = [j
for j
in y
if master.getVal(y[j]) > EPS]
94 x, suby = subprob.data
95 edges = [(i,j)
for (i,j)
in x
if subprob.getVal(x[i,j]) > EPS]
97 print(
"Optimal value:", master.getObjVal())
98 print(
"Facilities at nodes:", facilities)
99 print(
"Edges:", edges)
101 master.printStatistics()
106 master.freeBendersSubproblems()
109 import networkx
as NX
110 import matplotlib.pyplot
as P
114 other = [j
for j
in y
if j
not in facilities]
115 customers = [
"c%s"%i
for i
in d]
116 G.add_nodes_from(facilities)
117 G.add_nodes_from(other)
118 G.add_nodes_from(customers)
120 G.add_edge(
"c%s"%i,j)
122 position = NX.drawing.layout.spring_layout(G)
123 NX.draw(G,position,node_color=
"y",nodelist=facilities)
124 NX.draw(G,position,node_color=
"g",nodelist=other)
125 NX.draw(G,position,node_color=
"b",nodelist=customers)
128 print(
"install 'networkx' and 'matplotlib' for plotting")