Generalized Assignment Problem (Branch-and-Price)

Problem Definition

We consider the Generalized Assignment Problem (GAP). Given a set of \(m\) agents and \(n\) jobs, the goal is to assign each job to exactly one agent in such a way that the total cost is minimized, while respecting the capacity constraints of each agent.

Each agent \(i\in\{1,\dotsc,m\}\) has a capacity \(C_i\). Each job \(j\in\{1,\dotsc,n\}\) has a resource consumption \(r_{ij}\) and a cost \(c_{ij}\) when assigned to agent \(i\).

We model the GAP with the following binary linear program:

\[\begin{split}\begin{align*} \min_{x} \ & \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij} \\ \text{s.t.} & \sum_{j=1}^n r_{ij} x_{ij} \le C_i && i=1,\dotsc,m \\ & \sum_{i=1}^m x_{ij} = 1 && j=1,\dotsc,n \\ & x_{ij} \in \{0,1\} && i=1,\dotsc,m, j=1,\dotsc,n. \end{align*}\end{split}\]

Decomposition

In this example, we use Dantzig-Wolfe decomposition to break down the problem into a master problem and subproblems. The master problem coordinates the assignment of jobs to agents, while the subproblems handle the capacity constraints for each agent individually.

Master Problem: The master problem is responsible for ensuring that each job is assigned to exactly one agent. It maintains the overall objective of minimizing the total cost.
Subproblems: Each subproblem corresponds to an agent and ensures that the agent’s capacity constraints are respected. The subproblems are solved independently and their solutions are used to update the master problem.

Implementation with idol

In this example, we show how to model the Generalized Assignment Problem with idol and how to solve it using a Dantzig-Wolfe decomposition within a branch-and-bound framework, i.e., a branch-and-price algorithm.

//
// Created by henri on 13/03/23.
//
#include <iostream>
#include "idol/modeling.h"
#include "idol/problems/generalized-assignment-problem/GAP_Instance.h"
#include "idol/optimizers/mixed-integer-optimization/branch-and-bound/node-selection-rules/factories/WorstBound.h"
#include "idol/optimizers/mixed-integer-optimization/branch-and-bound/BranchAndBound.h"
#include "idol/optimizers/mixed-integer-optimization/callbacks/heuristics/IntegerMaster.h"
#include "idol/optimizers/mixed-integer-optimization/branch-and-bound/branching-rules/factories/MostInfeasible.h"
#include "idol/optimizers/mixed-integer-optimization/dantzig-wolfe/DantzigWolfeDecomposition.h"
#include "idol/optimizers/mixed-integer-optimization/dantzig-wolfe/infeasibility-strategies/FarkasPricing.h"
#include "idol/optimizers/mixed-integer-optimization/dantzig-wolfe/stabilization/Neame.h"
#include "idol/optimizers/mixed-integer-optimization/dantzig-wolfe/logs/Info.h"
#include "idol/optimizers/mixed-integer-optimization/wrappers/GLPK/GLPK.h"

using namespace idol;

int main(int t_argc, const char** t_argv) {

    const auto instance = Problems::GAP::read_instance("assignment-bap.data.txt");

    const unsigned int n_agents = instance.n_agents();
    const unsigned int n_jobs = instance.n_jobs();

    // Create optimization environment
    Env env;

    // Create model
    Model model(env);

    // Create decomposition annotation
    Annotation<Ctr> decomposition(env, "decomposition", MasterId);

    // Create assignment variables (x_ij binaries)
    auto x = model.add_vars(Dim<2>(n_agents, n_jobs), 0., 1., Binary, "x");

    // Create knapsack constraints (i.e., capacity constraints)
    for (unsigned int i = 0 ; i < n_agents ; ++i) {
        auto capacity = model.add_ctr(idol_Sum(j, Range(n_jobs), instance.resource_consumption(i, j) * x[i][j]) <= instance.capacity(i), "capacity_" + std::to_string(i));

        capacity.set(decomposition, i); // Assign constraint to i-th subproblem
    }

    // Create assignment constraints
    for (unsigned int j = 0 ; j < n_jobs ; ++j) {
        model.add_ctr(idol_Sum(i, Range(n_agents), x[i][j]) == 1, "assignment_" + std::to_string(j));
    }

    // Set the objective function
    model.set_obj_expr(idol_Sum(i, Range(n_agents), idol_Sum(j, Range(n_jobs), instance.cost(i, j) * x[i][j])));

    // Build algorithms
    const auto column_generation = DantzigWolfeDecomposition(decomposition)
            .with_master_optimizer(GLPK::ContinuousRelaxation().with_logs(false))
            .with_default_sub_problem_spec(
                    DantzigWolfe::SubProblem()
                            .add_optimizer(GLPK().with_logs(false))
                            .with_column_pool_clean_up(1500, .75)
            )
            .with_logger(Logs::DantzigWolfe::Info().with_frequency_in_seconds(.00000001))
            .with_dual_price_smoothing_stabilization(DantzigWolfe::Neame(.3))
            .with_infeasibility_strategy(DantzigWolfe::FarkasPricing())
            .with_hard_branching(true)
            .with_logs(true);

    const auto branch_and_bound = BranchAndBound()
            .with_subtree_depth(0)
            .with_branching_rule(MostInfeasible())
            .with_node_selection_rule(WorstBound())
            .add_callback(Heuristics::IntegerMaster().with_optimizer(GLPK().with_logs(false)))
            .with_logs(true);

    const auto branch_and_price = branch_and_bound + column_generation;

    // Set optimizer
    model.use(branch_and_price);

    // Solve
    model.optimize();

    // Print solution
    std::cout << save_primal(model) << std::endl;

    return 0;
}