Mixed-Integer Linear Programming: Column generation algorithms

Public Deposited

Column generation algorithms are used for MILP problems. The formulation was initially proposed by Ford and Fulkerson in 1958 . The main advantage of column generation is that not all possibilities need to be enumerated. Instead, the problem is first formulated as a restricted master problem (RMP). This RMP has as few variables as possible, and new variables are brought into the basis as needed, similar to the simplex method . By similar to the simplex method, it means that if a column with a negative reduced cost can be found, it is added to the RMP and this process is repeated until no more columns can be added to the RMP.

Last modified
  • 11/29/2018
Rights statement


In Collection: