Facility Location Problem (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} \ & \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.} & \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}\]

Implementation with idol

In this example, we show how to model the capacitated FLP with idol and how to solve it using a “hand-crafted” branch-and-bound algorithm.

//
// Created by henri on 06/04/23.
//
#include <iostream>
#include "idol/modeling.h"
#include "idol/problems/facility-location-problem/FLP_Instance.h"
#include "idol/optimizers/mixed-integer-optimization/branch-and-bound/BranchAndBound.h"
#include "idol/optimizers/mixed-integer-optimization/branch-and-bound/branching-rules/factories/PseudoCost.h"
#include "idol/optimizers/mixed-integer-optimization/branch-and-bound/node-selection-rules/factories/BestEstimate.h"
#include "idol/optimizers/mixed-integer-optimization/wrappers/HiGHS/HiGHS.h"
#include "idol/optimizers/mixed-integer-optimization/callbacks/cutting-planes/KnapsackCover.h"
#include "idol/optimizers/mixed-integer-optimization/wrappers/GLPK/GLPK.h"
#include "idol/optimizers/mixed-integer-optimization/wrappers/Gurobi/Gurobi.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("robust_ccg.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, "x");
    auto y = model.add_vars(Dim<2>(n_facilities, n_customers), 0., 1., Binary, "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())
                    .add_callback(Cuts::KnapsackCover())
                    .with_branching_rule(PseudoCost())
                    .with_node_selection_rule(BestEstimate())
    );

    model.optimize();

    std::cout << save_primal(model) << std::endl;

    return 0;
}