Solving A Dantzig-Wolfe Reformulation¶

In this tutorial, we will see how to implement a column generation algorithm to solve a continuous relaxation of the Generalized Assignment Problem (GAP). This relaxation is obtained by relaxing the Dantzig-Wolfe reformulation of the GAP.

Hint

This tutorial regards the advanced topic of Column Generation and Dantzig-Wolfe decomposition. Rudimentary notions in the following subjects are recommended:

A complete example which includes branching is available here.

Problem Definition ¶

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\).

The Natural Formulation ¶

We model the GAP with the following binary linear program:

\[\begin{split}\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, && 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}\]

Here, variable \(x_{ij}\) encodes the assignment decision and equals 1 if and only if task \(j\) is assigned to agent \(i\).

The Dantzig-Wolfe Reformulation ¶

Let us enumerate the list of all feasible assignments, i.e., let

\[\{\bar x^e_{ij} \}_{e\in E} = \left\{ x \in \{ 0,1 \}^{mn} : \sum_{j=1}^n r_{ij}x_{ij} \le C_i \quad i=1,...,m \right\},\]

in which \(E\) denotes a list for their indices.

The Dantzig-Wolfe reformulation of GAP reads

(1)¶\[\begin{split}\min_{\lambda} \quad & \sum_{e\in E} \lambda_e\left( \sum_{i=1}^m\sum_{j=1}^n c_{ij}\bar x_{ij}^e \right) \\ \textrm{s.t.} \quad & \sum_{e\in E} \lambda_e \left( \sum_{i=1}^m \bar x_{ij}^e \right) = 1 \quad j=1,...,n, \\ & \sum_{e\in E} \lambda_e = 1, \\ & \lambda_e \in \{ 0, 1 \} & \text{for all } e\in E.\end{split}\]

Though this model contains an exponential number of variables, it can be solved efficiently using Column Generation and Branch-and-price. In such a case, the pricing problem is a Knapsack Problem.

In this tutorial, we focus on the continuous relaxation of (1).

Automatic Reformulation ¶

The simplest way to solve a problem using Column Generation and idol is through its automatic reformulation feature. To use this, one simply needs to give the original space formulation of the problem and to indicate which constraints should be moved to the pricing problem (here, the knapsack constraints).

We will start by modeling the problem in its natural form and then indicate which constraints should be moved to the pricing problem.

The Natural Formulation ¶

Before we start, we will use a GAP instance stored in a file. This file reads as follows.

3   8
-27 -12 -12 -16 -24 -31 -41 -13
-14  -5 -37  -9 -36 -25  -1 -35
-34 -34 -20  -9 -19 -19  -3 -24
21 13  9  5  7 15  5 24
20  8 18 25  6  6  9  6
16 16 18 24 11 11 16 18
26 25 34

http://www.or.deis.unibo.it/kp/Chapter7.pdf Example 7.3

To read an instance of the GAP, we need to include the header file located in idol/mixed-integer/problems/generalized-assignment-problem/GAP_Instance.h.

Then, we can use the Problems::GAP::read_instance function to read the instance file.

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();

We are now ready to model our problem (for more details, refer to this tutorial on modeling)

// Create optimization environment
Env env;

// Create model
Model model(env);

// 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) {
    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));
}

// Create assignment constraints
for (unsigned int j = 0 ; j < n_jobs ; ++j) {
    model.add(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])));

Giving Decomposition Instructions ¶

We are now at the crucial step of indicating which constraint should be moved to the pricing problem. In idol, this is done by using annotations. Annotations are additional information associated to an optimization object (e.g., a constraint or a variable). Note that annotations are global, i.e., they do not relate to a given optimization model.

Every annotation is formed with a template argument which is the value type of the annotation. Here, the Dantzig-Wolfe decomposition expects an annotation with a value of type unsigned int and which corresponds to the sub-problem index to which the constraint will be moved to.

We create the annotation as follows.

Annotation<unsigned int> decomposition(env, "decomposition", MasterId);

Here, we pass three arguments to the constructor of Annotation<unsigned int>. First, we pass the optimization environment which will store the annotation. Then, a name is given to the annotation: here, “decomposition”. Finally, a default value is given and is set to MasterId. This will tell idol that constraints which have not been annotated should remain in the master problem.

Now, observe how the annotation is applied to the 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); // <== Annotating the capacity constraint
}

Here, the first capacity constraint is moved to the first pricing problem (id: 0), the second constraint to the second pricing problem (id: 1), and so on.

Note that another decomposition would be materialized as follows.

for (unsigned int i = 0 ; i < n_agents ; ++i) {
    Ctr 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, 0); // <== Annotating the capacity constraint
}

Here, all the knapsack constraints would be moved to the same pricing problem (id: 0).

Creating the Column Generation Algorithm ¶

Now that the desired decomposition has been specified, we can set the desired optimizer to solve our model. Here, we want to solve our the continuous relaxation of the Dantzig-Wolfe reformulation using column generation.

To begin with, we need to give some instructions about how each sub-problem will be solved. In other words, we need to specify the optimizer(s) used for pricing during the column generation process. This is done by first creating a DantzigWolfe::SubProblem object.

const auto sub_problem_specifications = DantzigWolfe::SubProblem()
                                            .add_optimizer(Gurobi());

Then, we can create the column generation algorithm (factory) in the following way.

const auto column_generation = DantzigWolfeDecomposition(decomposition)
        .with_master_optimizer(Gurobi::ContinuousRelaxation())
        .with_default_sub_problem_spec(sub_problem_specifications);

We can now tell idol to use this algorithm for solving our model by using the Model::use method.

model.use(column_generation);

Solving ¶

As usual, one can simply call the Model::optimize method to solve the problem.

model.optimize();

That’s it! The problem is being solved by column generation, and possibly branching on fractional variables.

The rest remains unchanged and one can retrieve the solution through the usual methods such as Model::get_status and Model::get_var_primal.