Mixed-Integer Linear Programming: Column generation algorithmsPublic 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.
- In Collection: