Ravindra K. Ahuja

Cyclic-Exchange Neighborhood Search and Other Very Large-Scale Neighborhood (VLSN) Search Techniques
Funded by National Science Foundation

Neighborhood search is a popular technique to solve difficult combinatorial optimization problems. A critical issue in the design of a neighborhood search approach is the choice of the neighborhood structure, that is, the manner in which a neighborhood is defined. In this project, we have been conducting research to develop neighborhood search algorithms where the size of the neighborhood is very large (possibly exponential in terms of the input size parameters) and use network optimization and integer programming techniques to implicitly enumerate the neighborhood to identify improved neighbors. We have termed such algorithms as Very Large-Scale Neighborhood (VLSN) Search Algorithms. The VLSN search algorithms allow us to consider neighborhoods with trillions of neighbors while the time to identify improved neighbors is fairly small. We have applied this methodology to several classical combinatorial optimization problems as well as several problems arising in supply-chain management and logistics. This methodology has also been used for solving some real-life scheduling problems arising in airline and railroad industries and obtained significant cost improvements.

Solving Large-Scale Logistics Problems in Real Time - Models, Algorithms, and Information Systems

Funded by National Science Foundation

This project concerns the development of new computational approaches to solve important logistics problems arising in supply-chain management. In mathematical programming terms, the problems that we study are multicommodity flow problems with nonlinear staircase cost structures. Problems of this type arise quite often in transportation and telecommunication industry. Due to the difficulty and scale of these problems, we are concentrating on efficient heuristic methods.

Combined Fleet-Through Assignment Models in Airline Scheduling

Funded by United Airlines, Chicago

The fleet assignment model (FAM) for an airline assigns fleet types to the set of flight legs that satisfies a variety of constraints and minimizes the cost of the assignment. The through assignment model (TAM) identifies a set of profitable throughs between arrival and departure flights flown by the same fleet type at each station to maximize the through benefits. The through assignment model is usually solved after obtaining the solution from a fleet assignment model. In this current sequential approach, the through assignment model cannot change the fleeting in order to get a better through assignment, and the fleet assignment model does not take into account the through benefits. In this project, we integrate these two models into a single model which we call the Combined Through-Fleet Assignment Model (ctFAM). The integrated model is too large to be solved to optimality using integer programming techniques; hence, we solve it heuristically using a very large-scale neighborhood search algorithm. Our algorithm obtained a savings of over $25 million annually on the data provided by United Airlines. We extended our technique to solve the multi-criteria ctFAM where, in addition to the fleeting and through contributions, we consider (i) ground manpower costs; and (ii) crew scheduling costs. Finally, we incorporated the flexible time windows in the ctFAM model where flight departure times can vary in a specified range and the objective is to determine the flight departure times to maximize the fleeting and through contributions. This model resulted in a savings of about $45 million annually.

Improved Locomotive Scheduling Models and Algorithms

Funded by CSX Transportation, Jacksonville

The locomotive scheduling problem (or the locomotive assignment problem) is to assign a consist (a set of locomotives) to each train in a pre-planned train schedule so as to provide them sufficient power to pull them from their origins to their destinations. Locomotive scheduling problems are among the most important problems in railroad scheduling. Locomotive scheduling problems can be studied at two levels - planning level or operational level. At the planning stage of the locomotive scheduling problem, we assign locomotive types to various trains. At the operational stage of the locomotive scheduling problem, we assign individual locomotives to trains taking into account the fueling and maintenance needs of the locomotives, which are ignored in the planning model. In this project, we studied the locomotive scheduling problem at the planning level and developed algorithms to solve this problem. Using problem decomposition, integer programming, and very large-scale neighborhood search, we developed a solution technique to solve this problem within 30 minutes of computation time on a standard workstation. When we compared our solution with the solution obtained by the software in-house developed by CSX Transportation, we obtained a savings of over 5% in locomotive costs, which translates into savings of at least ten million dollars annually.

New Approaches for Solving the Railroad Blocking Problem

Supported by National Science Foundation SBIR Program

The Railroad Blocking Problem is also an important optimization problems arising in railroad routing and scheduling. This problem consists of identifying which blocks to build at each railroad terminal and assigning each origin-destination (OD) shipment to a sequence of blocks that represent a path from the shipment’s origin to its destination so that the system-wide shipping and handling costs are minimum. The blocking problem is a network design problem with millions of fixed change variables and hundreds of billions of flow variables, and thus is a very difficult and very large-scale combinatorial optimization problem. We have developed a novel very large-scale neighborhood (VLSN) search algorithm that obtains near-optimal solutions of the railroad blocking problem within one to two hours on a workstation. Applications of this algorithm on the data provided by several railroads yielded improvements of 10%-15% in handling costs, which translates into tens of millions of dollars in savings annually for large US railroad companies.

Solving Real-Life Train Schedule Design Problems

Supported by National Science Foundation SBIR Program

Railroads design their train schedule so that all railcars are transported using minimum resources. The train schedule design problem consists of determining how many trains to run; the origin, destination, and route of each train; the train arrival and departure times for each station at which it stops; the weekly operating schedule for each train; and the assignment of blocks of cars to trains. The train schedule must satisfy numerous practical constraints and business rules as well as achieve the minimum cost of transportation. This problem is a very large-scale, multi-objective integer programming problem containing trillions of decision variables. Using state-of-the-art network optimization and heuristic techniques, we have developed an algorithmic approach to solve this problem within a few hours of computer time on a workstation. Applications of the prototype software on the data provided by two US freight railroads have demonstrated savings of at least 5% in railcar, locomotive, and crew costs.

New approaches for solving the block-to-train assignment problem.
R.K. Ahuja, K.C. Jha, and G. Sahin, Networks 51, 48-62. 2008 view abstract

Real-life locomotive planning: New formulations, algorithms and computational results.
B. Vaidyanathan, R.K. Ahuja, J. Liu, and L.A. Shughart, Transportation Research B, 147-168. 2008 view abstract

Single machine scheduling with stepwise tardiness costs and release times.
G. Sahin and R.K. Ahuja, To appear in Journal of Scheduling. 2008

Neighborhood search approaches to beam orientation optimization in intensity modulated radiation therapy treatment planning.
D. Aleman, A. Kumar, R.K. Ahuja, H.E. Romeijn, and J.F. Dempsey, To appear in Journal of Global Optimization. 2008 view abstract

Incremental network optimization: Theory and algorithms.
O. Seref, R.K. Ahuja, and J.B. Orlin, To appear in Operations Research. 2008

Solving linear cost dynamic lot sizing problems in O(n log n) time.
R.K. Ahuja and D.S. Hochbaum, To appear in Operations Research. 2008 view abstract

Maximum flows.
F.Z. Sargut, R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, . A book chapter to appear in The Handbook of Graph Algorithms and Applications, Volume I, edited by K. Thulasiraman, T. Nishizeki and G. Xue, CRC Press. 2008

Minimum cost flows.
B. Vaidyanathan, R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, . A book chapter to appear in The Handbook of Graph Algorithms and Applications, Volume I, edited by K. Thulasiraman, T. Nishizeki and G. Xue, CRC Press. 2008

Multi-commodity flows.
B. Vaidyanathan, R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, . A book chapter to appear in The Handbook of Graph Algorithms and Applications, Volume I, edited by K. Thulasiraman, T. Nishizeki and G. Xue, CRC Press. 2008

Railroad Locomotive Scheduling.
A. Kumar, B. Vaidyanathan and R.K. Ahuja, To appear In: Encyclopedia of Optimization, 2nd Edition, edited by C.A. Floudas and P.M. Pardalos, Kluwer Academic Publishers. 2008

Railroad Crew Scheduling.
A. Kumar, B. Vaidyanathan and R.K. Ahuja, To appear In: Encyclopedia of Optimization, 2nd Edition, edited by C.A. Floudas and P.M. Pardalos, Kluwer Academic Publishers. 2008

A heuristic approach to the multi-period single-sourcing problem with production and inventory capacities and perishability constraints.
R.K. Ahuja, W. Huang, H.E. Romeijn, and D. Romero Morales, INFORMS Journal on Computing 19, 14-26. 2007 view abstract

Solving real-life railroad blocking problems.
R.K. Ahuja, K.C. Jha, and J. Liu, To appear in Interfaces. 2007 view abstract

Network flow-based approaches for the railroad crew scheduling problem.
B. Vaidyanathan, K.C. Jha, and R.K. Ahuja, To appear in IBM Journal of Research & Development. 2007 view abstract

Spreadsheet-based decision support systems.
M.M.H. Seref and R.K. Ahuja, A chapter to appear in Handbook on Decision Support Systems, edited by F. Burstein and C.W. Holsapple, Springer Verlag. 2007 view abstract

Optimal network configuration and capacity expansion of railroads.
J. Liu, R.K. Ahuja, and G. Sahin, To appear in Journal of the Operational Research Society. 2007 view abstract

A new linear programming approach to radiation therapy treatment planning problems.
H.E. Romeijn, R.K. Ahuja, J.F. Dempsey, and A. Kumar, Operations Research 54, 201-216. 2006 view abstract

Lower bounding techniques for the degree-constrained network design problem.
G. Sahin, and R.K. Ahuja, Submitted to Networks. 2005 view abstract

Networks models in railroad planning and scheduling.
R.K. Ahuja, C.B. Cunha, and G. Sahin, A chapter in the book entitled “Tutorials in Operations Research”, Vol. 1, pp. 54-101, 2005. view abstract

Very large-scale neighborhood search.
R.K. Ahuja, O. Ergun, J.B. Orlin, and A.P. Punnen, A chapter in the book “Approximation Algorithms and Metaheuristics,” edited by T.F. Gonzalez” 2005.

A network flow algorithm to minimize beam-on time for unconstrained multileaf collimator problems in cancer radiation therapy.
R.K. Ahuja and H. Hamacher, Networks 45, 36-41. 2005 view abstract

Solving real-life locomotive scheduling problems.
R.K. Ahuja, J. Liu, A. Mukherjee, J.B. Orlin, D. Sharma, and L.A. Shughart, Transportation Science 39, 503-517. 2005 view abstract

A column generation approach to radiation therapy treatment planning using aperture modulation.
H.E. Romeijn, R.K. Ahuja, J.F. Dempsey, and A. Kumar, SIAM Journal on Optimization 15, 838-862. 2005 view abstract

A heuristic approach to the multi-period single-sourcing problem with production and inventory capacities and perishability constraints.
R.K. Ahuja, W. Huang, H.E. Romeijn, and D. Romero Morales, To appear in INFORMS Journal on Computing. 2005 view abstract

New approaches for the train dispatching problem.
G. Sahin, C.B. Cunha, and R.K. Ahuja, Submitted to Transportation Research B. 2005 view abstract

Very large scale neighborhood search for the K-constrained multiple knapsack problem.
C.B. Cunha and R.K. Ahuja, Journal of Heuristics 11, 465-481. 2005 view abstract

A multi-exchange heuristic for the single source capacitated facility location.
R.K. Ahuja, J.B. Orlin, S. Pallottino, M.P. Scaparra, and M.G. Scutella, Management Science 50, 749-760. 2004 view abstract

Decision support systems development: An essential part of OR education.
R.K. Ahuja and M.M. Hanna, Operations Research Letters 31, April Issue, 12-13. 2004

Solving the combined through-fleet assignment model with time windows using neighborhood search.
R.K. Ahuja, J. Goodstein, J. Liu, A. Mukherjee, and J.B. Orlin, Networks 44, 160-171. 2004 view abstract

A cut based algorithm for the convex dual of the minimum cost network flow problem.
R.K. Ahuja, D. Hochbaum, and J.B. Orlin, Algorithmica 39, 189-208. 2004 view abstract

Dynamic shortest paths minimizing travel times and costs.
R.K. Ahuja, J.B. Orlin, S. Pallottino, and M.G. Scutellà, Networks 41, 197-205. 2003 view abstract

Graph and network optimization.
R.K. Ahuja, J.B. Orlin, Encyclopedia of Life Support Systems, edited by U. Derigs. 2003

A composite very large-scale neighborhood search algorithm for the vehicle routing problem.
R. Agarwal, R.K. Ahuja, G. Laporte, and Z.J. Shen, Handbook of Scheduling: Algorithms, Models and Performance Analysis. Edited by J. Y-T. Leung, Chapman & Hall/CRC, pp. 49-01 to 49-23. 2003 view abstract

Solving the convex cost integer dual network flow problem.
R.K. Ahuja, D. Hochbaum, and J.B. Orlin, Management Science 49, 950-964. 2003 view abstract

A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem.
R.K. Ahuja, J.B. Orlin, and D. Sharma, Operations Research Letters 31, 185-194. 2003 view abstract

A novel linear programming approach to fluence map optimization for intensity modulated radiation therapy treatment planning.
H.E. Romeijn, R.K. Ahuja, J.F. Dempsey, A. Kumar, and J. Li, Physics in Medicine and Biology 48, 3521-3542. 2003 view abstract

Solving multi-criteria combined through-fleet assignment models.
R.K. Ahuja, J. Liu, J. Goodstein, A. Mukherjee, J.B. Orlin, and D. Sharma, Chapter 13 in the book Operations Research in Space and Air, Edited by Tito A. Ciriani, Giorgio Fasano, Stefano Gliozzi, and Roberto Tadei, Kluwer Academic Publishers, pp. 233-256. 2003

Exact and heuristic algorithms for the weapon-target assignment problem.
R.K. Ahuja, A. Kumar, and K.C. Jha, To appear in Operations Research. 2003 view abstract

Combinatorial algorithms for inverse network flow problems.
R.K. Ahuja and J.B. Orlin, Networks 40, 181-187. 2002 view abstract

A survey of very large scale neighborhood search techniques.
R.K. Ahuja, O. Ergun, J.B. Orlin, and A.P. Punnen, Discrete Applied Mathematics 123, 75-102. 2002 view abstract

Minimum time and minimum cost path problems in street networks with traffic lights.
R.K. Ahuja, J.B. Orlin, S. Pallottino, and M. Scutella, Transportation Science 36, 326-336. 2002 view abstract

Very large-scale neighborhood search for airline fleet scheduling.
R.K. Ahuja and J.B. Orlin, SIAM News, Volume 35, Number 9, November Issue. 2002

A very large-scale neighborhood search algorithm for the quadratic assignment problem.
R.K. Ahuja, K.C. Jha, J.B. Orlin, and D. Sharma, Submitted to INFORMS Journal on Computing. 2002 view abstract

A network simplex algorithm with O(n) consecutive degenerate pivots.
R.K. Ahuja, J.B. Orlin, P. Sharma, and P.T. Sokkalingam, Operations Research Letters 30, 141-148. 2002 view abstract

Introduction to network optimization.
R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Handbook of Applied Optimization, edited by M. Resende and P. Pardalos, Oxford University Press, pp. 352-362. 2002

Maximum flow problem.
R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Handbook of Applied Optimization, edited by M. Resende and P. Pardalos, Oxford University Press, pp. 363-374. 2002

Minimum spanning tree problem.
R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Handbook of Applied Optimization, edited by M. Resende and P. Pardalos, Oxford University Press, pp. 422-430. 2002

Inverse optimization.
R.K. Ahuja and J.B. Orlin, Operations Research 49, 771-783. 2001 view abstract

A fast scaling algorithm for minimizing separable convex functions subject to chain constraints.
R.K. Ahuja and J.B. Orlin, Operations Research 49,784-789. 2001 view abstract

Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem.
R.K. Ahuja, J.B. Orlin, and D. Sharma, Mathematical Programming 91, 71-97. 2001 view abstract

A very large-scale neighborhood search algorithm for the combined through-fleet assignment model.
R.K. Ahuja, J. Goodstein, A. Mukherjee, J.B. Orlin, and D. Sharma, To appear in INFORMS Journal on Computing. 2001 view abstract

The maximum flow problem.
R.K. Ahuja, J. Goodstein, R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Encyclopedia of Optimization, Volume 3, edited by C. A. Floudas and P. Pardalos. Kluwer Academic Publishers, pp. 249-260. 2001

The minimum cost flow problem.
R.K. Ahuja, J. Goodstein, R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Encyclopedia of Optimization, Volume 3, edited by C. A. Floudas and P. Pardalos. Kluwer Academic Publishers, pp. 292-302. 2001

A new polynomial-time cycle-canceling algorithm for the minimum cost flow problem.
P.T. Sokkalingam, R.K. Ahuja, and J.B. Orlin, Networks 36, 53-63. 2000 view abstract

A faster algorithm for the inverse spanning tree problem.
R.K. Ahuja, and J.B. Orlin, Journal of Algorithms 34, 177-193. 2000 view abstract

Minimum spanning trees, Shortest paths, Maximum flows, Minimum cost flow.
J.B. Orlin, and R.K. Ahuja, CRC Handbook of Discrete and Combinatorial Mathematics, K. H. Rosen (Editor-in-chief), CRC Press, New York, pp. 629-633, 652-683. 2000

A greedy genetic algorithm for the quadratic assignment problem.
R.K. Ahuja, J.B. Orlin, and A. Tiwari, Computers and Operations Research 27, 917-934. 2000 view abstract

Very large scale neighborhood search.
R.K. Ahuja, J.B. Orlin, and D. Sharma, International Transactions in Operations Research 7, 301-317. 2000 view abstract

Algorithms for the equal flow problem.
R.K. Ahuja, J.B. Orlin, P. Zuddas, and G. Secki, Management Science 45, 1440-1455. 1999 view abstract

Solving inverse spanning tree problems through network flow techniques.
P.T. Sokkalingam, R.K. Ahuja, and J.B. Orlin, Operations Research 47, 291-300. 1999 view abstract

Diagnosing infeasibilities in network flow problems.
C.C. Aggarwal, R.K. Ahuja, J. Hao, and J.B. Orlin, Mathematical Programming 81, 263-280. 1998 view abstract

A new pivot selection rule for the network simplex algorithm.
P.T. Sokkalingam, P. Sharma, and R.K. Ahuja, Mathematical Programming 78, 149-158. 1997 view abstract

The balanced linear programming problem.
R.K. Ahuja, European Journal of Operational Research 101, 29-38. 1997 view abstract

Developing fitter genetic algorithms.
R.K. Ahuja and J.B. Orlin, ORSA Journal of Computing 7, 251-253. 1997 view abstract

Computational investigation of maximum flow algorithms.
R.K. Ahuja, M. Kodialam, A.K. Mishra, and J.B. Orlin, European Journal on Operational Research 97, 509-542. 1997 view abstract

Paths and Flows.
R.K. Ahuja, Annotated Bibliographies in Combinatorial Optimization: Chapter 17, John Wiley & Sons, 283-306. 1997

Equivalence of primal simplex and dual simplex algorithms for the maximum flow problem.
R.K. Ahuja and J.B. Orlin, Operations Research Letters 20, 101-108, 1997 view abstract

Optimal expansion of capacitated transshipment networks.
R.K. Ahuja, J.L. Batra, S.K. Gupta, and A.P. Punnen, European Journal of Operational Research 89, 176-184, 1996 view abstract

Use of representative counts in computational testing of algorithms.
R.K. Ahuja and J. B. Orlin, ORSA Journal on Computing 6, 318-330, 1996 view abstract

Applications of Network Optimization.
R.K. Ahuja, T. L. Magnanti, J. B. Orlin, and M. R. Reddy, Handbooks of Operations Research and Management Science, Volume 7: Network Models, Edited by M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, Elsevier, North-Holland, Amsterdam, pp. 1-83, 1995

A capacity scaling algorithm for the constrained maximum flow problem.
R.K. Ahuja and J. B. Orlin, Networks 25, 89-98, 1995 view abstract

A polynomial-time algorithm for message routing in hierarchical communication networks.
G.G. Polak and R. K. Ahuja, European Journal of Operational Research 80, 139-146, 1995 view abstract

Improved algorithms for bipartite network flows.
R.K. Ahuja, J.B. Orlin, C. Stein, and R.E. Tarjan, SIAM Journal on Computing 23, 906-933, 1994 view abstract

Finding minimum-cost flows by double scaling.
R. K. Ahuja, A.V. Goldberg, J. B. Orlin, and R.E. Tarjan, Mathematical Programming 53, 243-266, 1992 view abstract

The scaling network simplex algorithm.
R.K. Ahuja and J.B. Orlin, Operations Research 40, S5-S13, 1992

New scaling algorithms for the assignment and minimum cycle mean problems.
J.B. Orlin and R.K. Ahuja, Mathematical Programming 54, 41-56, 1992 view abstract

Some recent advances in network flows.
R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, SIAM Review 33, 175-219, 1991 view abstract

Distance-directed algorithms for maximum flow and parametric maximum flow problems.
J.B. Orlin and R.K. Ahuja, Naval Research Logistics 38, 413-430, 1991 view abstract

Faster algorithms for the shortest path problem.
R.K. Ahuja, K. Mehlhorn, J.B. Orlin, and R.E. Tarjan, Journal of ACM 37, 213-223, 1990 view abstract

Network Flows Handbooks in Operations Research and Management Science.
R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Vol. 1: Optimization, Edited by G. L. Nemhauser, A. H. G. Rinnooy Kan, and M. J. Todd, Elsevier, North-Holland, Amsterdam, pp. 211-360, 1989

Improved time bounds for the maximum flow problem.
R.K. Ahuja, J.B. Orlin, and R.E. Tarjan, SIAM Journal of Computing 18, 939-954, 1989 view abstract

A fast and simple algorithm for the maximum flow problem.
R.K. Ahuja and J.B. Orlin, Operations Research 37, 748-759, 1989 view abstract

Minimum cost to reliability ratio path problem.
R.K. Ahuja, Computers and Operations Research 15, 83-89, 1988 view abstract

New lower planes for the network design problems.
R.K. Ahuja and V.V.S. Murty, Networks 17, 113-127, 1987 view abstract

Exact and heuristic algorithms for the optimum communication spanning tree problem.
R.K. Ahuja and V.V.S. Murty, Transportation Science 21, 163-170, 1987 view abstract

Algorithms for the minimax transportation problem.
R.K. Ahuja, Naval Research Logistics Quarterly 33, 725-740, 1986 view abstract

Minimax linear programming problem.
R.K. Ahuja, Operations Research Letters 4, 131-134, 1985

A parametric algorithm for the convex cost flow and related problems.
R.K. Ahuja, J.L. Batra, and S.K. Gupta, European Journal of Operational Research 16, 222-235, 1984 view abstract

Combinatorial optimization with rational objective functions: A communication.
R.K. Ahuja, J.L. Batra, and S.K. Gupta, Mathematics of Operations Research 8, 314, 1983 view abstract

The constrained maximum flow problem.
R.K. Ahuja, J.L. Batra, and S.K. Gupta, Scientific Management of Transport Systems, N. K. Jaiswal (Ed.), North-Holland Publishing Co., 304-316, 1981

Maximum arc-disjoint and node-disjoint flows in two-commodity networks.
R.K. Ahuja and A.K. Mittal, Opsearch 18, 92-103, 1981