improving variable by calculating all the reduced cost and choosing a variable with a negative reduced cost. Thus, the idea is to compute only the variable having the minimum reduced cost. This can be done using an optimization problem called the pricing subproblem which strongly depends on the structure of the original problem. The objective function of the subproblem is the reduced cost of the searched variable with respect to the current dual variables, and the constraints require that the variable obeys the naturally occurring constraints. The column generation method is particularly efficient when this structure makes it possible to solve the sub-problem with an efficient algorithm, typically a dedicated combinatorial algorithm. We now detail how and why to compute the reduced cost of the variables. Consider the following linear program in standard form: which we will call the primal problem as well as its dual linear program: Moreover, let and be optimal solutions for these two problems which can be provided by any linear solver. These solutions verify the constraints of their linear program and, by duality, have the same value of objective function () which we will call . This optimal value is a function of the different coefficients of the primal problem: . Note that there exists a dual variable for each constraint of the primal linear model. It is possible to show that an optimal dual variable can be interpreted as the partial derivative of the optimal value of the objective function with respect to the coefficient of the right-hand side of the constraints: ou encore . More simply put, indicates by how much increases locally the optimal value of the objective function when the coefficient increases by one unit. Consider now that a variable was not considered until then in the primal problem. Note that this is equivalent to saying that the variable was present in the model but took a zero value. We will now observe the impact on the primal problem of changing the value of from to . If and are respectively the coefficients associated with the variable in the objective function and in the constraints then the linear program is modified as follows: In order to know if it is interesting to add the variable to the problem (i.e to let it take a non-zero value), we want to know if the value of the objective function of this new problem