Example: simple facility location problem
Describes a model used in documentation of the solution pool.
A simple version of a facility location problem appears
throughout this sequence of topics to show how the solution pool and
the tools associated with it work. Here's a description of the problem:
a company is considering opening as many as four warehouses in order
to serve nine different regions. The goal is to minimize the sum of
fixed costs associated with opening warehouses (constraint c2)
as well as the various transportation costs incurred to ship goods
from the warehouses to the regions (constraint c3).
Whether or not to open a warehouse is represented by
binary variable xi , for i =1
to 4.
Whether or not to ship goods from warehouse i
to region j is represented by binary variable yji ,
for j =1 to 9 and i =1
to 4.
Each region needs a specified amount of goods, and each
warehouse can store only a limited quantity of goods (constraints c4
to c7). In addition, each region must be
served by exactly one warehouse (constraints c8
to c16). Constraints c17
to c52 complete the model by stating that
warehouse i must be open in order for goods
to be shipped from warehouse i to any
region j.
The model for this simple facility location problem is
available online in the formatted LP file yourCPLEXhome/examples/data/location.lp .
In standard form, a model for the simple facility location problem
looks like this:
Minimize
obj: cost
Subject To
c1: - cost + fixed + transport = 0
c2: - fixed + 130 x1 + 150 x2 + 170 x3 + 180 x4 = 0
c3: - transport
+ 10 y11 + 30 y12 + 25 y13 + 55 y14
+ 10 y21 + 25 y22 + 25 y23 + 45 y24
+ 20 y31 + 23 y32 + 30 y33 + 40 y34
+ 25 y41 + 10 y42 + 26 y43 + 40 y44
+ 28 y51 + 12 y52 + 20 y53 + 29 y54
+ 36 y61 + 19 y62 + 16 y63 + 22 y64
+ 40 y71 + 39 y72 + 22 y73 + 27 y74
+ 75 y81 + 65 y82 + 55 y83 + 35 y84
+ 34 y91 + 43 y92 + 41 y93 + 62 y94 = 0
c4: 10 y11 + 10 y21 + 12 y31 + 15 y41 + 15 y51 + 15 y61 + 20 y71 + 25 y81 + 30 y91 - 90 x1 <= 0
c5: 10 y12 + 10 y22 + 12 y32 + 15 y42 + 15 y52 + 15 y62 + 20 y72 + 25 y82 + 30 y92 - 110 x2 <= 0
c6: 10 y13 + 10 y23 + 12 y33 + 15 y43 + 15 y53 + 15 y63 + 20 y73 + 25 y83 + 30 y93 - 130 x3 <= 0
c7: 10 y14 + 10 y24 + 12 y34 + 15 y44 + 15 y54 + 15 y64 + 20 y74 + 25 y84 + 30 y94 - 150 x4 <= 0
c8: y11 + y12 + y13 + y14 = 1
c9: y21 + y22 + y23 + y24 = 1
c10: y31 + y32 + y33 + y34 = 1
c11: y41 + y42 + y43 + y44 = 1
c12: y51 + y52 + y53 + y54 = 1
c13: y61 + y62 + y63 + y64 = 1
c14: y71 + y72 + y73 + y74 = 1
c15: y81 + y82 + y83 + y84 = 1
c16: y91 + y92 + y93 + y94 = 1
c17: x1 - y11 >= 0
c18: x1 - y21 >= 0
c19: x1 - y31 >= 0
c20: x1 - y41 >= 0
c21: x1 - y51 >= 0
c22: x1 - y61 >= 0
c23: x1 - y71 >= 0
c24: x1 - y81 >= 0
c25: x1 - y91 >= 0
c26: x2 - y12 >= 0
c27: x2 - y22 >= 0
c28: x2 - y32 >= 0
c29: x2 - y42 >= 0
c30: x2 - y52 >= 0
c31: x2 - y62 >= 0
c32: x2 - y72 >= 0
c33: x2 - y82 >= 0
c34: x2 - y92 >= 0
c35: x3 - y13 >= 0
c36: x3 - y23 >= 0
c37: x3 - y33 >= 0
c38: x3 - y43 >= 0
c39: x3 - y53 >= 0
c40: x3 - y63 >= 0
c41: x3 - y73 >= 0
c42: x3 - y83 >= 0
c43: x3 - y93 >= 0
c44: x4 - y14 >= 0
c45: x4 - y24 >= 0
c46: x4 - y34 >= 0
c47: x4 - y44 >= 0
c48: x4 - y54 >= 0
c49: x4 - y64 >= 0
c50: x4 - y74 >= 0
c51: x4 - y84 >= 0
c52: x4 - y94 >= 0
Binaries
x1 x2 x3 x4
y11 y12 y13 y14 y21 y22 y23 y24 y31 y32 y33 y34
y41 y42 y43 y44 y51 y52 y53 y54 y61 y62 y63 y64
y71 y72 y73 y74 y81 y82 y83 y84 y91 y92 y93 y94