A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation

References

• Ahuja R. K., Dell'Amico M., Maffioli F., Martello S. Flows and paths. Annotated Bibliographies in Combinatorial Optimization (1997) (John Wiley & Sons Ltd., Chichester, NY) 283–309Google Scholar
• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice-Hall, Englewood Cliffs, NJ) Google Scholar
• Alevras D., Grötschel M., Wessäly R. A network dimensioningtool. (1996) . Technical Paper Preprint SC 96-49, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, GermanyGoogle Scholar
• Ali I., Barnett D., Farhangian K., Kennington J., Patty B., Shetty B., McCarl B., Wong P. Multicommodity network problems: applications and computations. IIE Transactions (1984) 16:127–134Crossref, Google Scholar
• Aneja Y. P., Aggarwal V., Nair K. K. Shortest chain subject to side constraints. Networks (1983) 13:295–302Crossref, Google Scholar
• Aneja Y. P., Nair K. K. The constrained shortest path problem. Naval Research Logistics Quarterly (1978) 25:549–555Crossref, Google Scholar
• Assad A. A. Multicommodity network flows—a survey. Networks (1978) 8:37–91Crossref, Google Scholar
• Balakrishnan A., Altinkemer K. Using a hop-constrained model to generate alternative communication network design. ORSA Journal on Computing (1992) 4:192–205Link, Google Scholar
• Balakrishnan A., Magnanti T. L., Mirchandani P., Dell'Amico M., Maffioli F., Martello S. Network design. Annotated Bibliographies in Combinatorial Optimization (1997) (John Wiley & Sons, Ltd., Chichester, NY) 311–334Google Scholar
• Barnhart C. Dual-ascent methods for large-scale multicommodity flow problems. Naval Research Logistics (1993) 40:305–324Crossref, Google Scholar
• Barnhart C., Hane C. A., Johnson E. L., Sigismondi G. A column generation and partitioning approach for multi-commodity flow problems. Telecommunication Systems (1995) 3:239–258Crossref, Google Scholar
• Barnhart C., Hane C. A., Vance P. H., Pardalos P. M., Hearn D. W., Hager W. W. Integer multicommodity flow problems. Network Optimization, Lecture Notes in Economics and Mathematical Systems (1996) (Springer-Verlag, Berlin, Germany) 17–31Crossref, Google Scholar
• Barnhart C., Sheffi Y. A network-based primal-dual heuristic for the solution of multicommodity network flow problems. Transportation Science (1993) 27:102–117Link, Google Scholar
• Castro J. PPRN 1.0 user's guide. (1994) . Technical paper, Statistics and Operations Research Department, Universitat Politècnica de Catalunya, Barcelona, SpainGoogle Scholar
• Castro J., Nabona N. An implementation of linear and nonlinear multicommodity network flows. European Journal of Operational Research (1996) 92:37–53Crossref, Google Scholar
• Chen H., DeWald C. G. A generalized chain labelling algorithm for solving multicommodity flow problems. Computers and Operations Research (1974) 1:437–465Crossref, Google Scholar
• Chen Y. L., Chin Y. H. Multicommodity network flows with safety considerations. Operations Research (1992) 40:48–55Link, Google Scholar
• Climaco J. C. N., Martins E. Q. V. A bicriterion shortest path algorithm. European Journal of Operational Research (1982) 11:399–404Crossref, Google Scholar
• Crowder H. Computational improvements for subgradient optimization. Symposia Mathematica, Vol XIX (1976) (Academic Press, London, U.K.) 357–372Google Scholar
• Desrochers M., Soumis F. A generalized permanent labeling algorithm for the shortest path problem with time windows. INFOR (1988) 26:191–212Google Scholar
• Desrosiers J., Dumas Y., Solomon M. M., Soumis F.Time Constrained Routing and Scheduling (1993) (North-Holland, Amsterdam, The Netherlands) Google Scholar
• Desrosiers J., Pelletier P., Soumis F. Plus court chemin avec contraintes d'Horaires. RAIRO (1983) 17:357–377Crossref, Google Scholar
• Farvolden J. M., Powell W. B., Lustig I. J. A primal partitioning solution for the arc-chain formulation of a multicommodity network flow problem. Operations Research (1993) 41:669–693Link, Google Scholar
• Ford L. R., Fulkerson D. R. A suggested computation for maximal multi-commodity network flows. Management Science (1958) 5:97–101Link, Google Scholar
• Frangioni A., Gallo G. A bundle type dual-ascent approach to linear multicommodity min-cost flow problems. INFORMS Journal on Computing (1999) 11:370–393Link, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Company, New York) Google Scholar
• Gendron B., Crainic T. G. Bounding procedures for multicommodity capacitated network design problems. (1995) . Technical Paper, Centre de recherche sur les transports, Université de Montréal, Montréal, CanadaGoogle Scholar
• Gendron B., Crainic T. G., Frangioni A., Sansó B., Soriano P. Multicommodity capacitated network design. Telecommunications Network Planning (1999) (Kluwer Academic Publishers, Boston, MA) 1–19Crossref, Google Scholar
• Geoffrion A. M., Graves G. W. Multicommodity distribution system design by Benders decomposition. Management Science (1974) 20:822–844Link, Google Scholar
• Gersht A., Shulman A. A new algorithm for the solution of the minimum cost multicommodity flow problem. Proceedings of the 26th Conference on Decision and Control (1987) 748–758Crossref, Google Scholar
• Gratzer F. J., Steiglitz K., Fox J. A heuristic approach to large multicommodity flow problems. Proceedings of the Symposium on Computer-Communications Networks and Teletraffic (1972) New York:311–324Google Scholar
• Grigoriadis M. D., White W. W., Cottle R., Krarup J. Computational experience with a multicommodity network flow algorithm. Optimization Methods for Resource Allocation (1974) (The English Universities Press Ltd, London, U.K.) 205–227Google Scholar
• Handler G. Y., Zang I. A dual algorithm for the constrained shortest path problem. Networks (1980) 10:293–310Crossref, Google Scholar
• Hartman J. K., Lasdon L. S. A generalized upper bounding algorithm for multicommodity network flow problems. Networks (1972) 1:333–354Crossref, Google Scholar
• Held M., Wolfe P., Crowder H. P. Validation of subgradient optimization. Mathematical Programming (1974) 6:62–88Crossref, Google Scholar
• Henningson M., Holmberg K., Näsberg M. A capacitated bus grid network design problem. Proceedings 8th International Conference on Telecommunication Systems: Modeling and Analysis (2000) Nashville, TN:98–113Google Scholar
• Holmberg K., Hellstrand J. Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound. Operations Research (1998) 46:247–259Link, Google Scholar
• Holmberg K., Joborn M., Lundgren J. T. Improved empty freight car distribution. Transportation Science (1998) 32:163–178Link, Google Scholar
• Holmberg K., Yuan D. A Lagrangean heuristic based branch-and-bound approach for the capacitated network design problem. Operations Research (2000) 48:461–481Link, Google Scholar
• Itai A., Perl Y., Shiloach Y. The complexity of finding maximum disjoint paths with length constraints. Networks (1982) 12:277–286Crossref, Google Scholar
• Jaffe J. M. Algorithms for finding paths with multiple constraints. Networks (1984) 14:95–116Crossref, Google Scholar
• Jones K. L., Lustig I. J., Farvolden J. M., Powell W. B. Multicommodity network flows: the impact of formulation on decomposition. Mathematical Programming (1993) 62:95–117Crossref, Google Scholar
• Kennington J. L. Solving multicommodity transportation problems using a primal partitioning simplex technique. Naval Research Logistics Quarterly (1977) 24:309–325Crossref, Google Scholar
• Kennington J. L. A survey of linear cost multicommodity network flows. Operations Research (1978) 26:209–236Link, Google Scholar
• Kennington J. L., Shalaby M. An effective subgradient procedure for minimal cost multicommodity flow problems. Management Science (1977) 23:994–1004Link, Google Scholar
• Maier S. F., Cottle R., Krarup J. A compact inverse scheme applied to a multicommodity network with resource constraints. Optimization Methods for Resource Allocation (1974) (The English Universities Press Ltd, London, U.K.) 179–203Google Scholar
• McCallum C. J. A generalized upper bounding approach to a communications network planning problem. Networks (1977) 7:1–23Crossref, Google Scholar
• Shetty B., Muthukrishnan R. A parallel projection for the multicommodity network model. Journal of the Operational Research Society (1990) 41:837–842Crossref, Google Scholar
• Tomlin J. A. Minimum-cost multicommodity network flows. Operations Research (1966) 14:45–51Link, Google Scholar
• White W. W., Fox J. Mathematical programming, multicommodity flows, and communication nets. Proceedings of the Symposium on Computer Communications Networks and Teletraffic (1972) New York:325–334Google Scholar
• Wollmer R. D. Multicommodity networks with resource constraints: The generalized multicommodity flow problem. Networks (1972) 1:245–263Crossref, Google Scholar