Column generation

When a linear program has many 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 obtaining an optimal solution. The goal of this method is to solve a small problem with a limited set of variables.

The initial problem is called the master problem, and the reduced problem is called the restricted problem.
The restricted problem is simpler to solve, but if all of its variables do not contain those that give the optimal solution for the master problem, we must add to the restricted problem variables that can be used to improve the solution.

The problem of finding the best variable to add to the restricted problem is called the sub-problem associated with the master (or oracle) problem. It aims to find the minimum cost variable (or column) (ie the most promising one to improve the solution).

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

We consider the following continuous linear program (PL):

gencolonne1

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

The restricted problem (RLP) is given in the following form:
gencolonne2

The problem (RLP) is now small and will be easier to solve by a solver. This resolution will provide us the optimal values of the dual variables vj associated with the constraints. These values are passed to the subproblem which obtains the column or columns to be added in the set Rl.

The reduced cost calculation allows us to know if a column has decreased the value of the goal (and therefore improve it). Take for example the column xi of the master problem (LP), its reduced cost is:
gencolonne3

Since (LP) is a minimization problem, the sub-problem also seeks to minimize this reduced cost. If the minimum reduced cost is positive, then no column can be added to the restricted problem (RLP) to improve the goal. 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 reduced negative cost by updating the set Rl and then resolving the new restricted problem (RLP).

 

Publicités