Models a capacitated facility location problem and solves it with idol's branch-and-bound algorithm. Each node is solved by GLPK. Reduced cost fixing is used.

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 so as to serve the customers' demand. In doing so, costs should be minimized.

The data of this problem reads:

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 \(c_{ij}\).

We model the capacitated FLP as the MILP

\[ \begin{aligned} \min_{x,y} \quad & \sum_{i\in V_1} f_ix_i + \sum_{i\in V_1} \sum_{j\in V_2} c_{ij} d_j y_{ij} \\ \text{s.t.} \quad & \sum_{j\in V_2} d_jy_{ij} \le q_i x_i, \quad \text{for all } i\in V_1, \\ & \sum_{i\in V_1} y_{ij} = 1, \quad \text{for all } j\in V_2, \\ & x_i \in \{0,1\}, \quad \text{for all } i\in V_1, \\ & y_{ij} \in \{0,1\}, \quad \text{for all } i\in V_1, j\in V_2. \end{aligned} \]

In the following code, we show how this problem can be solved using idol's branch-and-bound algorithm.

#include <iostream>
#include "idol/modeling.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/BestBound.h"
#include "idol/mixed-integer/optimizers/branch-and-bound/branching-rules/factories/MostInfeasible.h"
#include "idol/mixed-integer/optimizers/callbacks/ReducedCostFixing.h"
#include "idol/mixed-integer/optimizers/wrappers/GLPK/GLPK.h"
 
using namespace idol;
 
int main(int t_argc, const char** t_argv) {
 
    /*****************/
    /* Instance data */
    /*****************/
 
    const Vector<double> fixed_costs { 109.6, 169.5, 24.8, 150.3, 140.7, 68.8, 5.4, 123.2, 118.5, 27.6, };
    const Vector<double> capacities { 131.5, 103.5, 41.8, 156.5, 128.5, 66.1, 33.7, 114.0, 152.3, 125.6, };
    const Vector<double> demands { 36.2, 5.6, 10.0, 20.2, 17.5, 35.8, 14.9, 2.8, 36.7, 2.8, 12.1, 16.3, 11.4, 9.0, 32.2, 13.8, 0.6, 26.9, 36.5, 10.0, };
    const Vector<double, 2> transportation_costs {
            {0.7, 0.4, 0.6, 0.7, 0.3, 0.6, 0.6, 0.6, 0.3, 0.3, 0.4, 0.6, 0.8, 0.6, 0.4, 0.2, 0.4, 0.3, 0.5, 0.4, },
            {0.8, 0.1, 0.3, 0.8, 0.7, 0.5, 0.7, 0.8, 0.2, 0.5, 0.2, 0.8, 0.8, 0.5, 0.6, 0.2, 0.6, 0.1, 0.8, 0.7, },
            {1.0, 0.5, 0.7, 1.0, 0.4, 0.9, 0.9, 0.9, 0.2, 0.6, 0.6, 0.9, 1.1, 0.9, 0.7, 0.3, 0.7, 0.4, 0.7, 0.5, },
            {0.8, 0.9, 1.1, 1.0, 0.3, 1.1, 0.9, 0.6, 0.8, 0.5, 0.9, 0.7, 1.0, 1.1, 0.6, 0.7, 0.5, 0.8, 0.1, 0.2, },
            {0.0, 0.7, 0.7, 0.2, 0.8, 0.6, 0.2, 0.2, 0.9, 0.4, 0.6, 0.1, 0.2, 0.5, 0.2, 0.7, 0.3, 0.7, 0.6, 0.8, },
            {0.4, 0.4, 0.4, 0.3, 0.7, 0.3, 0.2, 0.5, 0.6, 0.3, 0.3, 0.4, 0.4, 0.3, 0.3, 0.4, 0.3, 0.3, 0.7, 0.7, },
            {1.0, 0.6, 0.9, 1.1, 0.3, 1.0, 1.0, 0.9, 0.3, 0.6, 0.7, 1.0, 1.1, 1.0, 0.7, 0.4, 0.7, 0.5, 0.7, 0.4, },
            {0.1, 0.6, 0.6, 0.2, 0.8, 0.5, 0.2, 0.3, 0.8, 0.3, 0.5, 0.1, 0.2, 0.4, 0.2, 0.6, 0.2, 0.6, 0.6, 0.8, },
            {0.8, 0.6, 0.9, 0.9, 0.1, 0.9, 0.8, 0.7, 0.5, 0.4, 0.7, 0.8, 0.9, 0.9, 0.5, 0.4, 0.5, 0.5, 0.4, 0.2, },
            {0.7, 0.3, 0.5, 0.7, 0.4, 0.6, 0.7, 0.7, 0.2, 0.4, 0.3, 0.7, 0.8, 0.6, 0.5, 0.0, 0.5, 0.2, 0.6, 0.5, },
    };
    const auto n_facilities = fixed_costs.size();
    const auto n_customers = demands.size();
 
    const bool use_reduced_cost_fixing = true; // Set to false to disable reduced cost fixing
 
    /****************/
    /* Create model */
    /****************/
 
    // Create optimization environment
    Env env;
 
    // Create model
    Model model(env);
 
    // Add variables
    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");
 
    // Add constraints
 
    // Capacity constraints
    for (unsigned int i = 0 ; i < n_facilities ; ++i) {
        model.add_ctr(idol_Sum(j, Range(n_customers), demands[j] * y[i][j]) <= capacities[i] * x[i]);
    }
 
    // Demand constraints
    for (unsigned int j = 0 ; j < n_customers ; ++j) {
        model.add_ctr(idol_Sum(i, Range(n_facilities), y[i][j]) == 1);
    }
 
    // Set objective function
    model.set_obj_expr(idol_Sum(i, Range(n_facilities),
                                fixed_costs[i] * x[i]
                                + idol_Sum(j, Range(n_customers),
                                             transportation_costs[i][j] * demands[j] * y[i][j]
                                         )
                                 )
                         );
 
    /*************************************/
    /* Create branch-and-bound algorithm */
    /*************************************/
 
    // First, we create a virgin branch-and-bound algorithm
    auto branch_and_bound = BranchAndBound();
 
    // Configure how to solve the nodes' problems
    branch_and_bound.with_node_optimizer(GLPK::ContinuousRelaxation());
 
    // Configure node selection rule
    branch_and_bound.with_node_selection_rule(BestBound());
 
    // Configure branching rule
    branch_and_bound.with_branching_rule(PseudoCost());
 
    // If required, we add a reduced cost fixing callback
    if (use_reduced_cost_fixing) {
        branch_and_bound.add_callback(ReducedCostFixing());
    }
 
    /*******************/
    /* Solve the model */
    /*******************/
 
    model.use(branch_and_bound);
    model.optimize();
 
    std::cout << "Status: " << model.get_status() << std::endl;
    std::cout << "Objective value:\n" << model.get_best_obj() << std::endl;
 
    return 0;
}