Solves the generalized assignment problem with idol's branch-and-price algorithm on its Dantzig-Wolfe reformulation.
Given a set of \(m\) machines and \(n\) jobs, the goal is to assign each job to exactly one machine in such a way that the total cost is minimized, while respecting the capacity constraints of each machine.
The data for this problem is as follows:
- Each machine \(i\) with \(i=1,\dotsc,m\) has a capacity \(C_i\);
- Each job \(j\) with \(j=1,\dotsc,n\) consumes \(r_{ij}\) resources if scheduled on machine \(i\);
- Each job \(j\) has a cost of \(c_{ij}\) if scheduled on machine \(i\).
We model the GAP with the following binary linear program:
\[
\begin{align*}
\min_{x} \quad & \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij} \\
\text{s.t.} \quad & \sum_{j=1}^n r_{ij} x_{ij} \le C_i, \quad \text{for all } i=1,\dotsc,m, \\
& \sum_{i=1}^m x_{ij} = 1, \quad \text{for all } j=1,\dotsc,n, \\
& x_{ij} \in \{0,1\}, \quad \text{for all } i=1,\dotsc,m, j=1,\dotsc,n.
\end{align*}
\]
Here, variable \(x_{ij}\) encodes the assignment decision and equals 1 if and only if job \(j\) is assigned to machine \(i\).
We perform a Dantzig-Wolfe reformulation of the problem by enumerating, for each machine \(i\), the set of feasible assignments \(\mathcal{F}_i\), i.e., we let
\[
\mathcal{F}_i = \left\{ a \in \{0,1\}^n : \sum_{j=1}^n r_{ij} a_{j} \le C_i \right\}.
\]
The Dantzig-Wolfe reformulation of the GAP is then given by
\[
\begin{align*}
\min_{y} \quad & \sum_{i=1}^m \sum_{j=1}^n c_{ij} y_{ij} \\
\text{s.t.} \quad & \sum_{a\in \mathcal{F}_i} a_j\lambda_{a} = 1, \quad \text{for all } i=1,\dotsc,m, \\
& \sum_{a\in\mathcal{F}_i} \lambda_{a} = 1, \quad \text{for all } i=1,\dotsc,m \\
& \lambda_{a} \in \{ 0,1 \}, \quad \text{for all } a\in\mathcal{F}_i, \\
\end{align*}
\]
The data for this example is taken from this book (Example 7.3).
#include <iostream>
#include "idol/modeling.h"
#include "idol/mixed-integer/optimizers/branch-and-bound/BranchAndBound.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/dantzig-wolfe/DantzigWolfeDecomposition.h"
#include "idol/mixed-integer/optimizers/dantzig-wolfe/infeasibility-strategies/FarkasPricing.h"
#include "idol/mixed-integer/optimizers/dantzig-wolfe/stabilization/Neame.h"
#include "idol/mixed-integer/optimizers/callbacks/heuristics/IntegerMaster.h"
#include "idol/mixed-integer/optimizers/wrappers/Gurobi/Gurobi.h"
using namespace idol;
int main(int t_argc, const char** t_argv) {
const Vector<double, 2> costs = {
{ -27, -12, -12, -16, -24, -31, -41, -13, },
{ -14, -5, -37, -9, -36, -25, -1, -35, },
{ -34, -34, -20, -9, -19, -19, -3, -24, },
};
const Vector<double, 2> resource_consumption = {
{ 21, 13, 9, 5, 7, 15, 5, 24, },
{ 20, 8, 18, 25, 6, 6, 9, 6, },
{ 16, 16, 18, 24, 11, 11, 16, 18, },
};
const Vector<double> capacities = { 26, 25, 34, };
const unsigned int n_machines = capacities.size();
const unsigned int n_jobs = costs.front().size();
auto x = model.add_vars(
Dim<2>(n_machines, n_jobs), 0., 1., Binary, 0.,
"x");
for (unsigned int i = 0 ; i < n_machines ; ++i) {
model.add_ctr(idol_Sum(j,
Range(n_jobs), resource_consumption[i][j] * x[i][j]) <= capacities[i],
"capacity_" + std::to_string(i));
}
for (unsigned int j = 0 ; j < n_jobs ; ++j) {
model.add_ctr(idol_Sum(i,
Range(n_machines), x[i][j]) == 1,
"assignment_" + std::to_string(j));
}
model.set_obj_expr(idol_Sum(i,
Range(n_machines), idol_Sum(j,
Range(n_jobs), costs[i][j] * x[i][j])));
Annotation decomposition(env,
"decomposition", MasterId);
for (const auto& ctr : model.ctrs()) {
if (ctr.name().starts_with("capacity_")) {
const unsigned int machine_id = std::stoi(ctr.name().substr(9));
ctr.set(decomposition, machine_id);
}
}
column_generation.with_master_optimizer(Gurobi::ContinuousRelaxation());
.with_column_pool_clean_up(1500, .75);
column_generation.with_default_sub_problem_spec(subproblem_specifications);
column_generation.with_hard_branching(false);
column_generation.with_logs(true);
branch_and_bound.with_node_selection_rule(
BestBound());
branch_and_bound.with_logs(true);
const auto branch_and_price = branch_and_bound + column_generation;
model.use(branch_and_price);
model.optimize();
std::cout << save_primal(model) << std::endl;
return 0;
}