An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment

DOI10.1016/0377-2217(89)90389-5zbMath0679.90043OpenAlexW1971890464MaRDI QIDQ1823142

Manoel Camillo Penna, Celso Carneiro Ribeiro, Michel Minoux

Publication date: 1989

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(89)90389-5

zbMATH Keywords

approximate solutionslower boundstraffic assignmentmatrix decompositioncolumn generation techniquebranch- and-boundlarge-scale set partitioning

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Integer programming (90C10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Solving binary cutting stock problems by column generation and branch- and-bound, A column generation approach to job grouping for flexible manufacturing systems, A heuristic for decomposing traffic matrices in TDMA satellite communication, The assignment problem with nearly Monge arrays and incompatible partner indices, A binary cat swarm optimization algorithm for the non-unicost set covering problem, Graph theoretic relaxations of set covering and set partitioning problems, Column generation applied to linear programs in course registration, New bounds for optimum traffic assignment in satellite communication., Adaptive feasible and infeasible tabu search for weighted vertex coloring, Modeling and solving a crew assignment problem in air transportation, Exact weighted vertex coloring via branch-and-price, A survey on vertex coloring problems, Combinatorial aspects of construction of competition Dutch professional football leagues, Enhancing an algorithm for set covering problems, Knowledge based approach to the cutting stock problem, A survey of algorithms for the generalized assignment problem, Exact approaches for integrated aircraft fleeting and routing at TunisAir, A one-to-one correspondence between colorings and stable sets, Rank-Cluster-and-Prune: An algorithm for generating clusters in complex set partitioning problems, Column-Generation in Integer Linear Programming, Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs, Models and heuristic algorithms for a weighted vertex coloring problem, Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem, Design of cellular manufacturing systems, Algorithms for large scale set covering problems, Penalty computations for the set partitioning problem

Cites Work

• Unnamed Item
• Traffic assignment in communication satellites
• On the complexity of decomposing matrices arising in satellite communication
• The generalized simplex method for minimizing a linear form under linear inequality restraints
• A Linear Programming Approach to the Cutting-Stock Problem
• Optimal traffic assignment in a SS/TDMA frame : a new approach by set covering and column generation
• A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• Finding the K Shortest Loopless Paths in a Network
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem