Facility location problem

Specific Domains Optimization (Mathematical)
1

facing a issue with my implementation of the facility location problem.
I tried implementing the problem however the optimization model just does not seem to stop even after 3 hours not sure if I have slow computer.


n = 5                    # <- number of candidate facilities
m = 100                  # <- number of customers

# Location of facilities and customers are assumed to be normalized so that they belong to [0,1] × [0,1] 
## location of facilities
f_x, f_y = rand(n), rand(n)      # x- and y-coordinates
## location of customers
c_x, c_y = rand(m), rand(m)       # x- and y-coordinates

# Costs
## installation cost of each facility; it is assumed that all facilities have the same normalized installation cost of 9
b = 20 * ones(n)   
## delivery cost from facility i to customer j is computed based on the distance between the facility and the customer
c = zeros(n,m)
for i=1:n, j=1:m
    c[i,j] = norm([f_x[i]; f_y[i]] - [c_x[j]; c_y[j]])
end

# Demand and capacity
## demand of each customer
d = 5 * rand(m)
## capacity of each facility
M = 200 * rand(n)   

# 'fig' plots the geographic information
fig = scatter(f_x, f_y, label="candidate facilities", xlim=[0,1], ylim=[0,1], aspect_ratio = 1, legend = :outertopright, xticks=:false, yticks=:false)
scatter!(fig, c_x, c_y, label="customers")
display(fig)

This is the initialization provided on the Julia programming site
my implementation of the facility location problem model

@variable(model,y[1:n], Bin)
@variable(model,x[1:m,1:n],Bin)
@constraint(model,demand,x'*d .<=  m.*y)
@constraint(model,client_service[i in 1:m], sum(x[i,: ])== 1)
@objective(model,Min,  b'*y+ sum(c* x) )```

The optimize command keeps running it does not end even after hours
The same uncapacited location problem provides a solution of 281

uc_model = Model(GLPK.Optimizer)
@variable(uc_model,x[i in 1:m,j in 1:n],Bin)
@variable(uc_model,y[i in 1:n],Bin)
@constraint(uc_model,uncapacity_demand[i in 1:m,j in 1:n],x[i,j] <= y[j])
@constraint(uc_model,demand[i in 1:m, j in 1:n], sum( x[i,:]) ==1)
@objective(uc_model, Min, sum(c* x) + b’*y)
optimize!(uc_model)

the model for the same
Just not able to figure out the issue here.
2

Hi @aditya_lokesh, welcome to the forum :smile:

I’ve moved your question to the “Optimization (Mathematical)” section.

Don’t use GLPK.jl Use a solver like HiGHS.jl instead.

Here’s how I would write your model:

julia> using JuMP, HiGHS, LinearAlgebra

julia> begin
           n = 5
           m = 100
           f_x, f_y = rand(n), rand(n)      # x- and y-coordinates
           c_x, c_y = rand(m), rand(m)       # x- and y-coordinates
           b = 20 * ones(n)   
           c = zeros(n,m)
           for i in 1:n, j in 1:m
               c[i, j] = norm([f_x[i]; f_y[i]] - [c_x[j]; c_y[j]])
           end
           d = 5 * rand(m)
           M = 200 * rand(n)   
           uc_model = Model(HiGHS.Optimizer)
           set_silent(uc_model)
           @variable(uc_model, x[1:m, 1:n], Bin)
           @variable(uc_model, y[1:n], Bin)
           @constraint(uc_model, x' * d .<= M .* y)
           @constraint(uc_model, [i in 1:m], sum(x[i, :]) == 1)
           @objective(uc_model, Min, sum(c * x) + b' * y)
           optimize!(uc_model)
           solution_summary(uc_model)
       end
* Solver : HiGHS

* Status
  Result count       : 1
  Termination status : OPTIMAL
  Message from the solver:
  "kHighsModelStatusOptimal"

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : NO_SOLUTION
  Objective value    : 3.08230e+02
  Objective bound    : 3.08230e+02
  Relative gap       : 0.00000e+00
  Dual objective value : NaN

* Work counters
  Solve time (sec)   : 7.46224e-03
  Simplex iterations : 181
  Barrier iterations : -1
  Node count         : 1