Column generation

Column generation

When a linear program has a lot of variables, it is not possible to solve it by a simplex. The generation of columns makes it possible to generate the useful variables progressively until an optimal solution is obtained. The objective of this method is to solve a reduced problem with a limited set of variables.

The initial problem of a generation of columns is called the master problem, and the reduced problem is called the restricted problem.
The restricted problem of a generation of columns is simpler to solve, but if the set of its variables does not contain those which give the optimal solution for the master problem, to reach the optimal solution of the master problem, it is necessary to add to the problem restricted to variables that can be used to improve the solution.

The problem consisting in finding the best variable to add in the restricted problem is called sub-problem associated with the master problem (or oracle). Its objective is to find the variable (or column) of minimum reduced cost (ie the most promising to improve the solution).

The reduced cost of the variables is calculated using the dual variables obtained after solving the restricted problem. The point of the dual thus used in the sub-problem is called the point of separation. Often this is an optimal solution of the dual of the restricted problem.

We consider the following continuous linear program (LP):

Column generation

We assume that the number of variables in T is too large for the problem (LP) to be solved in reasonable time, and that we want to solve it by generating columns. We therefore seek to solve the restricted problem associated with the master problem with a restricted set of variables denoted by Rthe. The restricted problem must be feasible. It is possible to use simple columns, for example random columns, or even those resulting from a feasible solution obtained from a heuristic.

Column generation

The problem (RLP) is now small and will be easier to solve by a solver. This resolution will provide us with the optimal values of the dual variables vj associated with constraints. These values are passed to the sub-problem which allows us to obtain the column (s) to add to the set Rthe.

Column generation

The calculation of the reduced cost allows us to know if a column decreased the value of the objective (and therefore improved it).

Since (LP) is a problem of minimization, the subproblem also seeks to minimize this reduced cost. If the minimum reduced cost is positive, then no columns can be added to the restricted problem (RLP) to improve the objective. The optimal solution of the restricted problem is therefore an optimal solution of the master problem (LP). Otherwise, we add one or more columns among those having a negative reduced cost by updating the set Rthe and we solve after the new restricted problem (RLP).

To share