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