An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment (Q1823142): Difference between revisions

The paper is devoted to a method of solving some very large-scale set partitioning problems with special structure, such as the matrix decomposition problem. \textit{P. C. Gilmore} and \textit{R. E. Gomory} [Oper. Res. 9, 849-859 (1961; Zbl 0096.355)] applied the column generation technique to a class of combinatorial problems to obtain good approximate solutions and lower bounds. In this paper the authors show how the branch-and-bound method can be combined with the column generation technique to ensure obtaining the exact optimal integer solution. They also report extensive computational results.