Column generation

Column generation or delayed column generation is an efficient algorithm for solving large linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by solving the considered program with only a subset of its variables. Then iteratively, variables that have the potential to improve the objective function are added to the program. Once it is possible to demonstrate that adding new variables would no longer improve the value of the objective function, the procedure stops. The hope when applying a column generation algorithm is that only a very small fraction of the variables will be generated. This hope is supported by the fact that in the optimal solution, most variables will be non-basic and assume a value of zero, so the optimal solution can be found without them. In many cases, this method allows to solve large linear programs that would otherwise be intractable. The classical example of a problem where it is successfully used is the cutting stock problem. One particular technique in linear programming which uses this kind of approach is the Dantzig–Wolfe decomposition algorithm. Additionally, column generation has been applied to many problems such as crew scheduling, vehicle routing, and the capacitated p-median problem.

Column generation or delayed column generation is an efficient algorithm for solving large linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by solving the considered program with only a subset of its variables. Then iteratively, variables that have the potential to improve the objective function are added to the program. Once it is possible to demonstrate that adding new variables would no longer improve the value of the objective function, the procedure stops. The hope when applying a column generation algorithm is that only a very small fraction of the variables will be generated. This hope is supported by the fact that in the optimal solution, most variables will be non-basic and assume a value of zero, so the optimal solution can be found without them. In many cases, this method allows to solve large linear programs that would otherwise be intractable. The classical example of a problem where it is successfully used is the cutting stock problem. One particular technique in linear programming which uses this kind of approach is the Dantzig–Wolfe decomposition algorithm. Additionally, column generation has been applied to many problems such as crew scheduling, vehicle routing, and the capacitated p-median problem. & A x = b \\ & x \in \mathbb{R}^+ \end{align} which we will call the primal problem as well as its dual linear program: \begin{align} &\max_{u} u^T b \\ &\text{subject to} \\ & u^T A \leq c \\ & u \in \mathbb{R} \end{align} Moreover, let x^* and u^* 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 ( c^T x^* = u^{*T} b ) which we will call z^* . This optimal value is a function of the different coefficients of the primal problem: z^* = z^* (c, A, b) . Note that there exists a dual variable u_i^* for each constraint of the primal linear model. It is possible to show that an optimal dual variable u_i^* can be interpreted as the partial derivative of the optimal value z^* of the objective function with respect to the coefficient b_i of the right-hand side of the constraints: u_i^* = \frac{\partial z^*}{\partial b_i} or otherwise u^* = \frac{\partial z^*}{\partial b} . More simply put, u_i^* indicates by how much increases locally the optimal value of the objective function when the coefficient b_i increases by one unit. Consider now that a variable y was not considered until then in the primal problem. Note that this is equivalent to saying that the variable y 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 y from 0 to \hat{y} . If c_y and A_y are respectively the coefficients associated with the variable y in the objective function and in the constraints then the linear program is modified as follows: \begin{align} &\min_{x} c^T x + c_y \hat{y} \\ &\text{subject to} \\ & A x = b - A_y \hat{y}\\ & x \in \mathbb{R}^+ \end{align} In order to know if it is interesting to add the variable y to the problem (i.e to let it take a non-zero value), we want to know if the value z_{\hat{y}}^* of the objective function of this new problem decreases as the value \hat{y} of the variable y increases. In other words, we want to know \frac{\partial z_{\hat{y}}^*}{\partial \hat{y}} . To do this, note that z_{\hat{y}}^* can be expressed according to the value of the objective function of the initial primal problem: z_{\hat{y}}^* = c_y \hat{y} + z^*(c, A, b-A_y \hat{y}) . We can then compute the derivative that interests us: \begin{align} \frac{\partial z_{\hat{y}}^*}{\partial \hat{y}} & ~=~ & & c_y + \frac{\partial z^*}{\partial \hat{y}} \\ & ~=~ & & c_y + \frac{\partial z^*}{\partial c} \frac{d c}{d \hat{y}} + \frac{\partial z^*}{\partial A} \frac{d A}{d \hat{y}} + \frac{\partial z^*}{\partial b} \frac{d b}{d \hat{y}} \\ & ~=~ & & c_y + \frac{\partial z^*}{\partial b} \frac{d b}{d \hat{y}} \\ & ~=~ & & c_y + u^* (-A_y) \\ & ~=~ & & c_y - u^* A_y \end{align} In other words, the impact of changing the value \hat{y} on the value z _ {\hat{y}}^* translates into two terms. First, this change directly impacts the objective function and second, the right-hand side of the constraints is modified which has an impact on the optimal variables x^* whose magnitude is measured using the dual variables u^* . The derivative \frac{\partial z_{\hat{y}}^*}{\partial \hat{y}} is generally called the reduced cost of the variable y and will be denoted by cr_y in the following. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1342366775 under CC BY-SA 4.0; modifications have been made.