Contenus

Toggle## 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 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):

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 R_{the}. 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.

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 v_{j} associated with constraints. These values are passed to the sub-problem which allows us to obtain the column (s) to add to the set R_{the}.

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 R_{the} and we solve after the new restricted problem (RLP).