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_c_{i},y_c_{i}) and
(x_f_{j},y_f_{j}) are the coordinates of the customers and the facilities. Let f_{j} be the opening fixed
costs for a facility and c_{i,j} the cost to transport products from facility j to customer
i.

x_{i,j} is a binary variable determining whether customer i is assigned to facility j, and y_{j} is a
binary variable indicating whether a facility j is open or not. If a facility j is built (y_{j} = 1)
then the building cost is f_{j}, and if customer i is served from facility j (x_{i,j} = 1)
then the cost is c_{i,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 y_{j} = 0 then no customer i can be served from j, that is, x_{i,j} must be 0 for all
i ∈ I).

Solution

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

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