Column generation algorithms: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
(Updated page up to half way throught the algorithm discussion)
No edit summary
Line 16: Line 16:


In summary, when the master problem is solved, we are able to obtain dual prices for each of the constraints in the master problem. This information is then utilized in the objective function of the subproblem. The subproblem is solved. If the objective value of the subproblem is negative, a variable with negative reduced cost has been identified. This variable is then added to the master problem, and the master problem is re-solved. Re-solving the master problem will generate a new set of dual values, and the process is repeated until no negative reduced cost variables are identified. The subproblem returns a solution with non-negative reduced cost, we can conclude that the solution to the master problem is optimal.
In summary, when the master problem is solved, we are able to obtain dual prices for each of the constraints in the master problem. This information is then utilized in the objective function of the subproblem. The subproblem is solved. If the objective value of the subproblem is negative, a variable with negative reduced cost has been identified. This variable is then added to the master problem, and the master problem is re-solved. Re-solving the master problem will generate a new set of dual values, and the process is repeated until no negative reduced cost variables are identified. The subproblem returns a solution with non-negative reduced cost, we can conclude that the solution to the master problem is optimal.




Line 40: Line 41:
The problem can be modeled as follows:
The problem can be modeled as follows:


<math>\begin{matrix} \\ \min(x)\sum_{s=1}^Sy_s  \\        \      s.t. \sum_kN_{ks}y_s\geq J_k    \forall    k\in K \\ y_s\in \Zeta_+\forall s\in S \end{matrix}
<math>\begin{matrix} \\ \min(y)\sum_{s=1}^Sy_s  \\        \      s.t. \sum_kN_{ks}y_s\geq J_k    \forall    k\in K \\ y_s\in \Zeta_+\forall s\in S \end{matrix}
   
   
</math>
</math>
Line 67: Line 68:
Sometimes |S| could be so large that enumerating all patterns would not be practical. For this purpose, the column generation below can be used:
Sometimes |S| could be so large that enumerating all patterns would not be practical. For this purpose, the column generation below can be used:
  Step 0: initialize the problem
  Step 0: initialize the problem
Generate a subset of patterns S ′ for which the problem has a solution that is feasible (a typical initialization is that of starting with the |I| single-item cutting patterns).  
Generate a subset of patterns S ′ for which the problem has a solution that is feasible (a typical initialization is that of starting with the |I| single-item cutting patterns).


  Step 1: formulation and solution of the master problem
  Step 1: formulation and solution of the master problem
Solve the master problem (restricted to the variables/patterns xj with j J ′ )
Solve the master problem (restricted to the patterns (i.e: variables) ysj with s S ′ )
 
<math>\begin{matrix} \\ \min(y)\sum_{s=1}^(S^') y_s  \\        \      s.t. \sum_kN_{ks}y_s\geq J_k    \forall    k\in K \\ y_s\in \Zeta_+\forall s\in S^'  \end{matrix}
</math>
 
By solving this problem one can obtain first a primal optimal solution '''''y∗''''' and then a dual optimal solution '''''u''''' such that '''''y∗''''' and '''''u''''' satisfy the complementary slackness condition (for example, this could be done with the simplex method).
 
Step 2: solution of the subproblem  
Or in other words, the next step is to find the solution of the following integer linear programming problem (called subproblem or slave problem) with |K| variables and one constraint:
 
<math>\begin{matrix} \\ \max(z)\sum_{k=1}^K u_k*z_k  \\        \      s.t. \sum_kL_2y_s\geq J_k    \forall    k\in K \\ y_s\in \Zeta_+\forall s\in S \end{matrix}
</math>

Revision as of 21:34, 16 November 2020

Author: Lorena Garcia Fernandez (lgf572)

Introduction

Column Generation techniques have the scope of setting up your Mixed integer Programming (MIP) problem by generating only the variables that will have an influence on the objective function. This is important for big problems with many variables where the formulation with these techniques would simplify the problem formulation, since not all the possibilities need to be listed.

Theory, methodology, and algorithmic discussions

Theory

The way this method work is as follows; first, the original problem that is being solved needs to be split into two problems: the master problem and the sub-problem.

  • The master problem is the original column-wise (i.e: one column at a time) formulation of the problem with only a subset of variables being considered.
  • The sub-problem is a new problem created to identify a new promising variable. The objective function of the sub-problem is the reduced cost of the new variable with respect to the current dual variables, and the constraints require that the variable obeys the naturally occurring constraints. The subproblem is also referred to as the RMP or “restricted master problem”. From this we can infer that this method will be a good fit for problems whose constraint set admit a natural breakdown (i.e: decomposition) into sub-systems representing a well understood combinatorial structure.

To execute that decomposition from the original problem into Master and subproblems there are different techniques. The theory behind this method relies on the Dantzig-Wolfe decomposition.

In summary, when the master problem is solved, we are able to obtain dual prices for each of the constraints in the master problem. This information is then utilized in the objective function of the subproblem. The subproblem is solved. If the objective value of the subproblem is negative, a variable with negative reduced cost has been identified. This variable is then added to the master problem, and the master problem is re-solved. Re-solving the master problem will generate a new set of dual values, and the process is repeated until no negative reduced cost variables are identified. The subproblem returns a solution with non-negative reduced cost, we can conclude that the solution to the master problem is optimal.


Methodology in detail

To illustrate the algorithm, we will use a common example: an algorithm for one-dimensional cutting stock problem.

Problem Overview

Given:

A set of item types I,

For every item type i ∈ I, its length Li and the number of pieces to be produced Ri ,

The length W of the starting objects to be cut,

Objective:

To find the minimum number of objects needed to satisfy the demand of all item types.

Model:

The problem can be modeled as follows:

where:

S: set of all possible cutting patterns that can be used to obtain item types in I from the original objects of length W;

Nks : number of pieces of type k ∈ K in the cutting pattern s ∈ S .

ys : number of original objects to be cut with pattern s ∈ S.


The algorithm to solve this problem is built on the solution of the continuous relaxation of the above model, i.e., the model obtained by replacing constraints

with constraints...

Sometimes |S| could be so large that enumerating all patterns would not be practical. For this purpose, the column generation below can be used:

Step 0: initialize the problem

Generate a subset of patterns S ′ for which the problem has a solution that is feasible (a typical initialization is that of starting with the |I| single-item cutting patterns).

Step 1: formulation and solution of the master problem

Solve the master problem (restricted to the patterns (i.e: variables) ysj with s ∈ S ′ )

By solving this problem one can obtain first a primal optimal solution y∗ and then a dual optimal solution u such that y∗ and u satisfy the complementary slackness condition (for example, this could be done with the simplex method).

Step 2: solution of the subproblem  

Or in other words, the next step is to find the solution of the following integer linear programming problem (called subproblem or slave problem) with |K| variables and one constraint: