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

Creator

• Kedric Daly

DOI

• https://doi.org/10.21985/N2N45P

Keyword

• Column Generations
• Algorithms

Rights statement

• In Copyright