An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
type: Item
instance of: scholarly article
title: An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
zbMATH Open document ID: 0679.90043
DOI: 10.1016/0377-2217(89)90389-5
author: Celso C. Ribeiro
author: Manoel Camillo Penna
author: Michel Minoux
published in: European Journal of Operational Research
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C06
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4114376
zbMATH Keywords: traffic assignment
zbMATH Keywords: large-scale set partitioning
zbMATH Keywords: matrix decomposition
zbMATH Keywords: column generation technique
zbMATH Keywords: approximate solutions
zbMATH Keywords: lower bounds
zbMATH Keywords: branch- and-bound
MaRDI profile type: Publication
full work available at URL: 0377-2217(89)90389-5
OpenAlex ID: W1971890464
cites work: Traffic assignment in communication satellites
cites work: The generalized simplex method for minimizing a linear form under linear inequality restraints
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: A Linear Programming Approach to the Cutting-Stock Problem
cites work: A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
cites work: Optimal traffic assignment in a SS/TDMA frame : a new approach by set covering and column generation
cites work: A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
cites work: Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
cites work: Q4039868
cites work: On the complexity of decomposing matrices arising in satellite communication
cites work: Finding the K Shortest Loopless Paths in a Network
description: scientific article; zbMATH DE number 4114376