How do you choose the best decomposition method for column generation?

1 Problem structure

The first step in choosing a decomposition method for column generation is to identify the problem structure. This means analyzing the original problem formulation and finding the most suitable way to partition it into a master problem and a subproblem. Typically, the master problem should contain the linking constraints and variables that couple the subproblems, while the subproblem should contain the independent constraints and variables that can be solved separately. The goal is to find a decomposition that simplifies the subproblem as much as possible, while preserving the feasibility and optimality of the original problem.

2 Solution method

The second step in choosing a decomposition method for column generation is to decide on the solution method. This means selecting the algorithm and the software that will be used to solve the master problem and the subproblem. There are different options for both, depending on the problem type, the size, and the complexity. For example, the master problem can be solved by linear programming, integer programming, or heuristic methods, while the subproblem can be solved by dynamic programming, shortest path algorithms, or enumeration methods. The choice of the solution method can affect the speed, the accuracy, and the stability of the column generation process.

3 Computational resources

The third step in choosing a decomposition method for column generation is to consider the computational resources. This means estimating the memory, the CPU time, and the communication costs that will be required to implement the column generation technique. Depending on the problem size and the solution method, the column generation process can be very demanding in terms of computational resources. Therefore, it is important to balance the trade-off between the complexity of the decomposition and the efficiency of the solution. For example, a finer decomposition can reduce the subproblem size, but increase the number of columns and the communication overhead. A coarser decomposition can have the opposite effect.

4 Stabilization techniques

The fourth step in choosing a decomposition method for column generation is to apply stabilization techniques. These are methods that aim to improve the convergence and the robustness of the column generation technique, by modifying the master problem or the subproblem in some way. For example, some common stabilization techniques are adding cutting planes, using dual smoothing, or imposing column restrictions. The purpose of these techniques is to avoid or reduce some of the issues that can arise during the column generation process, such as degeneracy, cycling, or oscillation.

5 Performance evaluation

The fifth step in choosing a decomposition method for column generation is to evaluate the performance. This means measuring and comparing the quality and the efficiency of the column generation technique, using different criteria and metrics. For example, some of the criteria that can be used to evaluate the performance are the optimality gap, the number of iterations, the CPU time, or the solution quality. The performance evaluation can help to identify the strengths and the weaknesses of the column generation technique, and to adjust or refine the decomposition method accordingly.

6 Examples and tips

The sixth and final step in choosing a decomposition method for column generation is to look at some examples and tips. These sources can provide inspiration and guidance to apply the technique to your own problems, as well as learn from the experience of others. For instance, you can review classic applications such as vehicle routing, crew scheduling, or cutting stock problems. Additionally, consulting textbooks or papers that explain the theory and practice of column generation in detail (e.g., Barnhart and Laporte 2007 or Desaulniers et al. 2005) can be beneficial. Furthermore, using software tools or libraries that facilitate implementation and testing (such as CPLEX, Gurobi, or SCIP) may be useful. Finally, experimenting with different decomposition methods and solution methods, while analyzing the results and trade-offs, can be beneficial.

7 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?