Solving a facility location problem with a custom branch-and-bound¶
Problem Definition¶
We consider the capacitated Facility Location Problem (FLP). Given a set of potential facility locations \(V_1\) and a set of customers \(V_2\), the goal is to select a subset of facility location to activate in order to serve all customers’ demand, while minimizing the total cost.
Each facility \(i\in V_1\) has an opening cost \(f_i\) and a maximum capacity \(q_i\). Each customer \(j\in V_2\) has a demand \(d_j\). The unitary cost for serving customer \(j\in V_2\) from facility \(i\in V_1\) is \(t_{ij}\).
We model the capacitated FLP with the MILP:
\[\begin{split}\begin{align*}
\min_{x,y} \quad & \sum_{i\in V_1} f_i x_i + \sum_{i\in V_1} \sum_{j\in V_2} t_{ij} y_{ij} \\
\text{s.t.} \quad & \sum_{j\in V_2} d_j y_{ij} \le q_i, && i\in V_1, \\
& \sum_{i\in V_1} y_{ij} = 1, && j\in V_2, \\
& y_{ij} \le x_i && i\in V_1, j\in V_2, \\
& x_i \in \{0,1\}, && i\in V_1, \\
& y_{ij} \in \{0,1\}, && i\in V_1, j\in V_2.
\end{align*}\end{split}\]
Instance¶
We will use an instance stored in a file called facility.data.txt. This file reads
10 20
109.6 131.484
169.498 103.513
24.7946 41.8319
150.331 156.535
140.651 128.462
68.8231 66.0825
5.40097 33.6793
123.19 113.974
118.503 152.262
27.5682 125.587
36.1992
5.60365
10.0339
20.1965
17.4686
35.8237
14.8866
2.75196
36.7471
2.76135
12.0892
16.2641
11.3815
8.96618
32.1548
13.7501
0.631599
26.9407
36.4762
10.0098
0.674345 0.377274 0.60077 0.725902 0.347025 0.648906 0.635155 0.607522 0.333549 0.300607 0.416598 0.628605 0.753687 0.644812 0.405533 0.152511 0.424802 0.261078 0.50283 0.403443
0.79483 0.0798539 0.347963 0.756363 0.654002 0.484362 0.663717 0.820894 0.220568 0.548021 0.218845 0.779403 0.804299 0.507375 0.592223 0.172742 0.63654 0.0894973 0.819295 0.712606
0.988408 0.473435 0.741449 1.02582 0.420089 0.859221 0.932609 0.913111 0.206479 0.606641 0.592807 0.943148 1.05883 0.871605 0.719628 0.296455 0.735305 0.405338 0.70923 0.472351
0.801213 0.930165 1.12413 0.970236 0.281743 1.11036 0.911725 0.579372 0.840547 0.467774 0.937797 0.721997 0.961574 1.08599 0.57822 0.70739 0.533045 0.812734 0.148052 0.238144
0.033511 0.742563 0.729705 0.21527 0.807152 0.579068 0.209073 0.232984 0.91811 0.384516 0.620859 0.0675881 0.187979 0.528276 0.248045 0.699975 0.263439 0.677736 0.632054 0.831136
0.379508 0.394834 0.402656 0.338167 0.703938 0.315728 0.243857 0.475284 0.607753 0.336413 0.270847 0.38184 0.381389 0.285442 0.271919 0.405371 0.331478 0.346229 0.681973 0.748633
1.01954 0.586318 0.852622 1.08059 0.340762 0.955962 0.989606 0.914744 0.331927 0.616543 0.693984 0.966318 1.10785 0.963435 0.742256 0.385068 0.74801 0.505968 0.654321 0.385256
0.124851 0.647767 0.637432 0.198938 0.766693 0.495492 0.15157 0.278676 0.831333 0.339767 0.525301 0.137635 0.200255 0.446836 0.203461 0.614955 0.238989 0.585824 0.629149 0.796432
0.822042 0.611747 0.850139 0.920143 0.113758 0.898665 0.836445 0.683577 0.462689 0.406345 0.66767 0.759121 0.93636 0.891583 0.542633 0.376275 0.534339 0.501362 0.400407 0.172095
0.728693 0.27883 0.523355 0.749647 0.439242 0.602651 0.655937 0.692852 0.235195 0.391798 0.348472 0.692708 0.785082 0.607712 0.47688 0.0436219 0.506139 0.16976 0.61561 0.497567
On the first line, the number of facilities and the numbers of customers are specified. Then, for each facility, the opening cost and the capacity are given. For each customer, the demand is given. Finally, the cost of serving each customer from each facility is given.
Implementation¶
//
// Created by henri on 06/04/23.
//
#include <iostream>
#include "idol/modeling.h"
#include "idol/mixed-integer/problems/facility-location-problem/FLP_Instance.h"
#include "idol/mixed-integer/optimizers/branch-and-bound/BranchAndBound.h"
#include "idol/mixed-integer/optimizers/branch-and-bound/branching-rules/factories/PseudoCost.h"
#include "idol/mixed-integer/optimizers/branch-and-bound/node-selection-rules/factories/BestEstimate.h"
#include "idol/mixed-integer/optimizers/wrappers/HiGHS/HiGHS.h"
#include "idol/mixed-integer/optimizers/wrappers/GLPK/GLPK.h"
#include "idol/mixed-integer/optimizers/wrappers/Gurobi/Gurobi.h"
#include "idol/mixed-integer/optimizers/branch-and-bound/node-selection-rules/factories/BestBound.h"
#include "idol/mixed-integer/optimizers/branch-and-bound/branching-rules/factories/MostInfeasible.h"
#include "idol/mixed-integer/optimizers/callbacks/ReducedCostFixing.h"
using namespace idol;
int main(int t_argc, const char** t_argv) {
Env env;
// Read instance
const auto instance = Problems::FLP::read_instance_1991_Cornuejols_et_al("facility.data.txt");
const unsigned int n_customers = instance.n_customers();
const unsigned int n_facilities = instance.n_facilities();
// Make model
Model model(env);
auto x = model.add_vars(Dim<1>(n_facilities), 0., 1., Binary, 0., "x");
auto y = model.add_vars(Dim<2>(n_facilities, n_customers), 0., 1., Binary, 0., "y");
for (unsigned int i = 0 ; i < n_facilities ; ++i) {
model.add_ctr(idol_Sum(j, Range(n_customers), instance.demand(j) * y[i][j]) <= instance.capacity(i));
}
for (unsigned int j = 0 ; j < n_customers ; ++j) {
model.add_ctr(idol_Sum(i, Range(n_facilities), y[i][j]) == 1);
}
for (unsigned int i = 0 ; i < n_facilities ; ++i) {
for (unsigned int j = 0 ; j < n_customers ; ++j) {
model.add_ctr(y[i][j] <= x[i]);
}
}
model.set_obj_expr(idol_Sum(i, Range(n_facilities),
instance.fixed_cost(i) * x[i]
+ idol_Sum(j, Range(n_customers),
instance.per_unit_transportation_cost(i, j) *
instance.demand(j) *
y[i][j]
)
)
);
// Set backend options
model.use(
BranchAndBound()
.with_node_optimizer(Gurobi::ContinuousRelaxation())
.with_branching_rule(PseudoCost())
.with_node_selection_rule(BestEstimate())
.add_callback(ReducedCostFixing())
.with_logs(true)
);
model.optimize();
std::cout << save_primal(model) << std::endl;
return 0;
}