Column generation or delayed column generation is an efficient approach to solving large linear programming problems.
The general idea of the method is that many linear programming problems are too large to explicitly write out all the variables. Since most variables will not be included in the basis, and therefore will have a zero value in the optimal solution, only a subset of the variables is necessary to solve the problem. Column generation supports this idea by generating only those variables that have the potential to improve the objective function - that is, only variables with a negative are searched for (we assume that the minimization problem is solved).
The task falls into two - the main task and the subtask. The main task is the original problem with the assumption that only a subset of variables is considered. The subtask is a new task, the purpose of which is to search for new variables. The objective function of the subtask is the reduced price for the current dual variables, and the constraints are generated by the natural constraints on the variables.
The process works as follows. We solve the main problem, from the solution we obtain dual variables for each constraint of the original problem. This information is used in the objective subtask function. We solve the subtask. If the objective function of the subtask is negative, a variable with a negative reduced price is found, and this variable is added to the main problem and we produce the next solution to the main problem. A new optimal solution to the main problem will give new dual variables, and the process is repeated until the solutions of the subtask give negative values. When the solution of the subtask gives a positive value of the objective function, we can conclude that the optimal solution to the main problem is found.
In many cases, this approach allows us to solve large linear programming problems. A classic example of applying the column generation method is the nesting task . One of the techniques of linear programming that uses the same approach is the Danzig-Wolfe decomposition . In addition, column generation is used in many tasks, such as the [1] , and the p-median problem with constraints [2] [3] .
String Generation in a Variable Basis Method
When solving large problems using the variable basis method (see the simplex method , section “The variable basis method”), a similar case often arises when you can generate not only columns, but also rows. The variable basis method takes advantage of the fact that in large linear programming problems in which most of the constraints are given by inequalities, most of the constraints do not meet a strict constraint (the additional variable is not equal to zero), which means that such a constraint may not be considered in the final solution. When solving problems using the variable basis method, one more sub-task can be solved - the definition of the output column. Using this approach, it is possible to solve some problems of game theory (see, for example, Blotto Games ) containing millions of rows and columns.
Notes
- ↑ Per Sjörgen. Solving the Master Linear Program in Column Generation Algorithms for Airline Crew Scheduling using a Subgradient Method. - 2009.
- ↑ Luiz AN Lorena, Edson LF Senne. The p-median problem with constraints.
- ↑ P. Avella, A. Sassano, I. Vasil'ev. Computational study of large-scale p-median problems Technical Report 08-03. - Universit`a di Roma “La Sapienza”, 2003. The branch and bound method for solving large p-median problems is presented. The method of generating columns and rows is used to solve the weakened linear programming problem and cutting hyperplanes to strengthen conditions. The authors claim that they managed to solve problems with more than 900 arcs of the graph.
Literature
- J. Desaulniers, J. Desrosiers, M. Solomon. Column Generation. - New York: Springer, 2005.