3.7.1 Facility Location (facilityLoc)

Run LPL Code  ,  PDF Document

Problem

The facility location problem wants to determine whether a facility has to be built and and from which facility a customer has to be served at minimal cost. Cost has two components: the transportation costs from a facility to the customer and the building cost (construction cost) of a facility.

Modeling Steps

Let i I be a set of customer locations and j J a set of facility locations. (x_ci,y_ci) and (x_fj,y_fj) are the coordinates of the customers and the facilities. Let fj be the opening fixed costs for a facility and ci,j the cost to transport products from facility j to customer i.

xi,j is a binary variable determining whether customer i is assigned to facility j, and yj is a binary variable indicating whether a facility j is open or not. If a facility j is built (yj = 1) then the building cost is fj, and if customer i is served from facility j (xi,j = 1) then the cost is ci,j. Hence, minimize the sums over both type of costs. The first constraint says that every customer must be served by exactly one facility and the second constraint makes sure that a customer can only be served by a facility if it is open (if yj = 0 then no customer i can be served from j, that is, xi,j must be 0 for all i I).

     ∑            ∑
min      ci,jxi,j +    fjyj
      i,j           j
     ∑
s.t.      xi,j = 1             forall i ∈ I
       j
     xi,j ≤ yj               forall i ∈ I, j ∈ J
     xi,j ∈ [0,1], yj ∈ [0,1] forall i ∈ I, j ∈ J

Solution

With the random data of the Julia/JuMP code the graphical output of the LPL program is given in Figure 6.


PIC

Figure 6: Optimal Solution of the Facility Location

Further Comments

The LPL code uses the same random data as the Julia/JuMP code to compare the output graph. The plotting code of Julia was omitted, because it was too long.

The model in Julia is initialized by Model() creating an empty model object. In contrast to most Python implementations, JuMP uses the powerful marcoprogramming of Julia: Variables are declared by a macro  @variable(model,...), constraints are declared by a macro  @constraint(model,...), etc. For the data, Julia’s efficient data structure are used. LPL imports the data from the file facilityLoc.txt in order to generate the same result as Julia/JuMP.

LPL code (run facilityLoc)

model facilityLoc "Facility Location"; 
  parameter m; n; 
  parameter x_c{i}; y_c{i}; x_f{j}; y_f{j}; 
  Read('@facitityLoc.txt', m,n); 
  set i:=1..m; j:=1..n; 
  Read{i}('@%1',x_c=2,y_c=3); 
  Read{j}('@%1',x_f=2,y_f=3); 
 
  parameter c{i,j}:=Sqrt((x_c-x_f)^2 + (y_c-y_f)^2); 
  parameter f{j}:=1; 
  binary variable y{j}; x{i,j}; 
  constraint C1{i}: sum{j} x = 1; 
  constraint C2{i,j}: x <= y; 
  minimize Obj: sum{i,j} c*x + sum{j} f*y; 
 
  Draw.Scale(300,-300); 
  {i,j|x} Draw.Line(x_c,y_c,x_f,y_f); 
  {i} Draw.Circle(x_c,y_c,.02,5); 
  {j} Draw.Rect(x_f-.02,y_f-.02,.04,.04,if(y,3,1),3); 
  Draw.Text('Obj='&Round(Obj,-5),0,0); 
end

LPL’s own random data: Replace the 6 first lines by the this code, if using LPL random data:

  parameter m:=12; n:=5; 
  set i:=1..m; j:=1..n; 
  parameter x_c{i}:=Rnd(0,1); y_c{i}:=Rnd(0,1); 
            x_f{j}:=Rnd(0,1); y_f{j}:=Rnd(0,1);

Julia/JuMP code (download facilityLoc.jl)

using JuMP 
import HiGHS 
import LinearAlgebra 
import Plots 
import Random 
 
Random.seed!(314) 
m = 12 
n = 5 
x_c, y_c = rand(m), rand(m) 
x_f, y_f = rand(n), rand(n) 
f = ones(n); 
c = zeros(m, n) 
for i in 1:m 
  for j in 1:n 
    c[i, j] = LinearAlgebra.norm([x_c[i] - x_f[j], y_c[i] - y_f[j]], 2) 
  end 
end 
 
model = Model(HiGHS.Optimizer) 
set_silent(model) 
@variable(model, y[1:n], Bin); 
@variable(model, x[1:m, 1:n], Bin); 
@constraint(model, client_service[i in 1:m], sum(x[i, j] for j in 1:n) == 1); 
@constraint(model, open_facility[i in 1:m, j in 1:n], x[i, j] <= y[j]); 
@objective(model, Min, f' * y + sum(c .* x)); 
 
optimize!(model) 
println("Optimal value: ", objective_value(model)) 
# plotting code was omitted