Tutorial 3: Index-based constraints (Facility Location)

The input to a facility location problem is a set of customer locations $L$ and a set of facilities $F$ .

The objective is to assign customers to facilities by taking into account $c_{ij}$ , the cost of serving a customer $i \in L$ with facility $j \in F$ , as well as $f_j$ , the cost of setting up a facility $j \in F$ . To accommodate different customer demands and different facility configurations, we associate a demand $d_i$ with each customer location $i \in L$ and capacity $k_j$ with each facility $j \in F$ , respectively.

The formulation of the facility location problem is then

\text{minimize} \sum_{i \in L}\sum_{j \in F}{c_{ij}x_{ij}}+\sum_{j \in F}{f_jy_j} \\\sum_{j \in F}{x_{ij}} = 1, \forall i \in L \\x_{ij} \le y_j, \forall i \in L, \forall j \in F \\\sum_{i \in L} d_ix_{ij} \le k_jy_j, \forall j \in F

For the purpose of this example, let us assume 5 locations and 3 facilities. The corresponding index sets are defined as

set L = {1,2,3,4,5}
set F = {1,2,3}

The cost of serving a customer $i \in L$ with facility $j \in F$ is captured as the following matrix:

const c = {{4, 2, 9}, 
           {1, 3, 3}, 
           {7, 4, 5}, 
           {3, 2, 1}, 
           {3, 1, 7}}, forall i in L, forall j in F

Each column of the matrix corresponds to a location and each row to a facility. The remaining inputs, namely the customer demands $d_i$ , the facility setup costs $f_j$ , and the facility capacities $k_j$ , are captured as the following one-dimensional arrays:

const d = {5, 11, 9, 7, 18}, forall i in L
const f = {100, 200, 300} forall j in F
const k = {20, 15, 25}, forall j in F

Next, the variables $x_{ij}$ and $y_j$ are declared to capture the assignment of customers to facilities and the setup of a facility, respectively.

bin x, forall i in L, forall j in F
bin y, forall j in F

The objective function minimizes the total cost of servicing customers and setting up the facilties:

min sum_{i in L}{sum_{j in F}{c_{i,j} * x_{i,j}}} + sum_{j in F}{f_{j} * y_{j}}

There is an important syntax features to take note of when considering the double summation term on the left of the objective function. It is a nested summation and each summation has matching curly brackets – highlighted below in red and blue, respectively.

min sum_{i in L}{  sum_{j in F}{  c_{i,j} * x_{i,j} }   }

Essentially, the entire second summation term is encapsulated within the brackets of the first summation term.

To ensure that each customer $i \in L$ is assigned to a facility, the keyword forall is appended to the constraint formulation so that the constraint is repeated for each customer $i \in L$ .

constr sum_{j in F}{x_{i,j}} = 1, forall i in L

The following two constraint sets ensure first, that a customer $i \in L$ is assigned to a facility $j \in F$ only if the facility is used, and secondly, that the capacity of a facility is enough to accommodate the demand of all the customers that are assigned to it.

constr x_{i,j} <= y_{j}, forall i in L, forall j in F
constr sum_{i in L}{d_{i} * x_{i,j}} <= k_{j} * y_{j}, forall j in F

The following is the complete code listing for solving the facility location problem:

model facility_location
set L = {1,2,3,4,5}
set F = {1,2,3}

const c = {{4, 2, 9}, 
           {1, 3, 3}, 
           {7, 4, 5}, 
           {3, 2, 1}, 
           {3, 1, 7}}, forall i in L, forall j in F

const f = {100, 200, 300} forall j in F
const d = {5, 11, 9, 7, 18}, forall i in L
const k = {20, 15, 25}, forall j in F

bin x, forall i in L, forall j in F
bin y, forall j in F
min sum_{i in L}{sum_{j in F}{c_{i,j} * x_{i,j}}} + sum_{j in F}{f_{j} * y_{j}}
constr sum_{j in F}{x_{i,j}} = 1, forall i in L
constr x_{i,j} <= y_{j}, forall i in L, forall j in F
constr sum_{i in L}{d_{i} * x_{i,j}} <= k_{j} * y_{j}, forall j in F

end

The following Python code, which accompanies the above model formulation, is helpful to understand how solutions for multiple-indexed variables are retrieved and printed on the screen.

import elytica

def main():
  elytica.init_model("facility_location")
  elytica.run_model("facility_location")
  
  L = elytica.get_model_set("facility_location", "L")
  F = elytica.get_model_set("facility_location", "F")
  print("\n\nSolution")
  for j in F:
    print("Customers served by facility ", j)
    for i in L:
      val = elytica.get_variable_value("facility_location", f"x{i},{j}")
      if val > 0.5:
        print(i)
  
  return 0

Leave Comment Cancel reply