James B. Orlin

Edward Pennell Brooks Professor of Operation Research
Co-director, Operations Research Center
M.I.T. E40-147
Cambridge, MA. 02139

EDUCATION:

 

University of Pennsylvania

BA

1974

Caltech

MS

1976

University of Waterloo

MMath

1976

Stanford University 

Ph.D.

1981

PRINCIPAL FIELDS OF INTEREST:

Mathematical Programming, Combinatorial and Network Optimization,
Design and Analysis of Algorithms and Heuristics, Logistics.

HISTORY OF M.I.T. APPOINTMENTS:

 

Professor

July 1, 1987

Current

Associate Professor

July 1, 1983

June 30, 1987

Assistant Professor

July 1, 1979

June 30, 1983

Management Science Area, Head

 July 1, 1993

 June 30, 2000

Operations Research center, Co-director

July 1, 1998

current

AWARDS:

Lanchester Prize, 1993. Awarded by the Operations Research Society of America for the best paper or book in Operations Research for the year. Awarded for the book Network Flows, co-authored with Ravindra K. Ahuja and Thomas L. Magnanti

Presidential Young Investigator Award. 1985-1990. Awarded by the National Science Foundation.

Fulbright Research Grant 1984-1985. Given by the Netherlands Fulbright Commission.

Co-winner of the 1981 Dissertation Prize Sponsored by the Transportation Group of the Operations Research Society of America.

Co-winner of the 1978 George E. Nicholson, Jr. Student Paper Competition Sponsored by the Operations Research Society of Americal (Paper [4]).

Finalist of the 1977 Student Paper Competition.

 

CURRENT PROFESSIONAL MEMBERSHIP:
 

INFORMS (formerly ORSA) Member

Association of Computing Machinery

Mathematical Programming Society

Society for Industrial and Applied Mathematics

SUBJECTS TAUGHT
 

15.053 Introduction to Management Science

15.060 Data, Models and Decisions

15.062 Decision Models for Management

15.063 Data, Models and Decisions

15.081J Introduction to Math Programming

15.082 Network Optimization

15.083 Combinatorial Optimization

15.085 Topics in Optimization

15.574 Information Systems, Data Structures, and Data Bases

THESIS SUPERVISION:

Ph.D.

Thesis supervisor for John VandeVate 1985
Title: The Linear Matroid Parity Problem

Thesis supervisor for Chat Rajapar 1987

Title: Analysis of Algorithms and
Heuristics for Some Clustering Problems

Thesis supervisor for Andrew Boyd 1987
Title: Optimization Problems on Greedoids

Thesis supervisor for Murali Kodialam 1991
Title: Algorithms for Periodic Graph Problems.

Thesis supervisor for Rina Rotshild Schneur 1991
Title: Scaling-based Algorithms for Multicommodity Flows
and Network Flow Problems with Side Constraints

Thesis supervisor for Hershel Safer 1992
Title: Fast Approximation Algorithms for Multi-criteria
Combinatorial Optimization Problems

Thesis supervisor for James Walton 1992
Title: Algorithms for Sensor Management

Thesis supervisor for Yusin Lee 1993
Title: Computational Analysis of Network Optimization Algorithms

Thesis supervisor for Charu Aggarwal 1996
Title: Faster Algorithms for Some Minimum Cost Flow Algorithms

Thesis supervisor for Ozie Ergun 2001
Title: Large Scale Neighborhood Search

Thesis supervisor for Dushyant Sharma 2002
Title: Topics in Neighborhood Search

Thesis supervisor for Mahesh Kumar: current
Title: Topics in Neighborhood Search

Thesis supervisor for Agustin Bompadre: current
Title: Topics in Neighborhood Search


 

M.S.

          Thesis supervisor for Charles Marge 1986
          Title: An Explainer System for the Transportation Problem

Thesis supervisor for Robert Huelskamp 1986
Title: The Scheduling of Pilots and Students for Air Force Training

Thesis supervisor for Dipanwita Misra 1992
Title: Data Compression for Shortest Path Problems

Thesis supervisor for Kavitha Rajan 1993
Title: Analysis of Heuristics for the Hierarchical Network Design Problem

Thesis supervisor for Sougata Datta 1994
Title: Algorithms for Assembling Physical Maps from DNA Fingerprints

Thesis supervisor for Alan Kaufman 1994
Title: Algorithms for Assembling Physical Maps

Thesis supervisor for I-lin Wang 1995
Title: Implementing the Premultiplier Method for the Minimum Cost Flow Problem

Thesis supervisor for Viswanathan Lakshmi 1996
Title: Genetic Algorithms for Uncapacitated Network Design

Thesis supervisor for Krishna Bhagatavula 1997
Title: Approximate Shortest Path Algorithms for Hierarchical Networks

Thesis supervisor for Sudipta Sengupa 1999
Title: Scheduling with rejection.

Thesis supervisor for Anurag Chandra  2001
Title:  Locomotive Scheduling

Thesis supervisor for Ashwin Krishnamurthy  2002
Title:  A New Approach to Conjoint Analysis

 

PUBLICATIONS:

 

[1] "Contentment in Graph Theory: Covering Graphs with Cliques", Indigationes Mathematicae, 80, (1977), 406-424

 

[2] "The Minimal Integral Separator of a Threshold Graph", Annals of Discrete Mathematics 1, (1977), 415-419.

[3] "Line-digraphs, Arborescences, and theorems of Tutte and Knuth", Journal of Combinatorial Theory (B), 25, (1978), 187-198.

[4] Cyclic Scheduling via Integer Programs with Circular Ones", with J.J. Bartholdi III and H. D. Ratliff, Operations Research,, 28, (1980), 1074-1085.

[5] An O(n2) Algorithm for Coloring Proper Circular Arc Graphs, with Maurizio A. Bonnuccelli and Daniel P. Bovet, SIAM J. Alg. Disc. Meth. , 2, (1981), 88-93.

[6] "Parametric Shortest Path Algorithms with an Application to Cyclic Staffing", with Richard M. Karp, Discrete Applied Mathematics, 3, (1981), 37-45.

[7] "The Complexity of Dynamic Languages and Dynamic Optimization Problems", Transactions of the 13th Annual ACM Symposium on The Theory of Computing, May 1981, 218-227.

[8] "A Polynomial Algorithm for Integer Programming Covering Problems Satisfying the Integer Round-up Property, Mathematical Programming, 22, (1982), 231-235.

[9] "Minimizing the Number of Vehicles to Meet a Fixed Periodic Schedule: An Application of Periodic Posets", Operations Research, 30, (1982), 760-776.

[10] "A Partitioning Problem with Additive Objective with an Application to Optimal Inventory Grouping for Joint Replenishment:", with A.K. Chakravarty and U.G. Rothblum, Operations Research, 30, (1982), 1018-1022.

[11] "Maximum Throughput Dynamic Network Flows", Mathematical Programming, 27, (1983), 214-223.

[12] "Dynamic Matchings and Quasidynamic Fractional Matchings I", Networks, 13, (1983), 551-562.

[13] "Dynamic Matchings and Quasidynamic Fractional Matchings II", Networks, 13, (1983), 563-580.

[14] "Minimum Convex Cost Dynamic Network Flows", Mathematics of Operations Research, 9, (1984), 190-207.

[15] "Algorithms for Problems on Dynamic/Periodic Graphs", in Progress in Combinatorial Optimization, William Pulleyblank, ed., Academic Press, Toronto, 1984, 273-294.

[16] "NP-completeness for Minimizing Maximum Edge Length in Grid Embeddings", with Z. Miller, Journal of Algorithms, 6, (1985), 10-16.

[17] "Consecutive Optimizors for a Partitioning Problem with Applications to Optimal Inventory Grouping for Joint Replenishment", with A.K. Chakravarty and U.G. Rothblum, Operations Research, 33, (1985), 820-832.

[18] "A Minimum Concave Cost Dynamic Network Flow Problem, with an Application to Lot-Sizing", with Stephen Graves, Networks, 15, (1985), 59-71.

[19] "On the Simplex Algorithm for Networks and Generalized Networks", Mathematical Programming Study, 24, (1985), 166-178.

[20] "Some Very Easy Knapsack/Partition Problems", Operations Research, 33, (1985), 1154-1160.

[21] "A Finitely Convergent Cutting Plane Technique", Operations Research Letters, 4, (1985), 1-4.

[22] "Computing Optimal Scalings by Parametric Network Algorithms ", with Uriel Rothblum, Mathematical Programming, 32, (1985), 1-10.

[23] "On the Complexity of Four Polyhedral Set containment Problems", with Robert Freund, Mathematical Programming, 33, (1985), 1-7.

[24] "A Dual Version of Tardos's Algorithm for Linear Programming". O.R. Letters 5, (1986), 221-226.

[25] "Parametric Linear Programming and Anti-Cycling Pivoting Rules" with Tom Magnanti. Mathematical Programming 41, (1988) 317-325.

[26] "A Faster Strongly Polynomial Algorithm for the Minimum Cost Flow Problem." Proceedings of the 20th Annual ACM Conference on the Symposium of Computing. ACM Press. (1988), 377-387. Operations Research 41, (1993), 338-350.

[27] "A Fast and Simple Algorithm for the Maximum Flow Problem" with Ravi Ahuja. Operations Research 37, (1989), 748-759.

[28] "The Structure of Bases in Bicircular Matroids" with Marianne Gardner, Alan Shuchat, and Randy Shull. Discrete Applied Mathematics. 23, (1989) 267-283.

[29] "Improved Time Bounds for the Maximum Flow Problem" with Ravi Ahuja and Bob Tarjan." SIAM J. of Computing 18, (1989), 939-954.

[30] "Network Flows" with Ravi Ahuja and Tom Magnanti. Chapter IV of the Handbooks in Operations Research and Management Science, Volume 1: Optimization, eds. G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd, North Holland, 1989. 211-369

[31] "Solving the Linear Matroid Parity Problem as a Sequence of Matroid Intersection Problems." With John Vande Vate. Mathematical Programming, 47, (1990) 81-106.

[32] "Faster Algorithms for the Shortest Path Problem" with Ravi Ahuja, Kurt Mehlhorn and Bob Tarjan. J. Association of Computing Machinery 37, (1990), 213-223.

[33] "Distance-Directed Algorithms for Maximum Flow and Parametric Maximum Flow Problems" with Ravi Ahuja. Naval Research Logistics, 38, (1990), 413-430.

[34] "Recent Advances in Network Flows." With Ravi Ahuja and Tom Magnanti. Siam Review 33, (1991), 175-219.

[35] "Faster Parametric Shortest Path and Minimum Balance Algorithms" with Robert Tarjan and Neal Young. Networks. 21, (1991), 205-221.

[36] "Single Transferable Vote Resists Strategic Voting" with John Bartholdi. Social Choice and Welfare. 8, (1991), 341-354

[37] "New Scaling Algorithms for the Assignment and Minimum Cycle Mean Problems" with Ravi Ahuja. Mathematical Programming 54, (1992), 41-56.

[38] "The Scaling Network Simplex Algorithm" with Ravi Ahuja. Operations Research.40, Supplement 1, (1992), S5-S13.

[39] "Finding Minimum-Cost Flows by Double Scaling:" with Ravi Ahuja, Andrew Goldberg, and Bob Tarjan. Mathematical Programming 53, (1992), 243-266.

[40] "Recognizing Hidden Bicircular Networks" with Marianne Gardner, Alan Shuchat, and Randy Shull. Discrete Applied Mathematics 41, (1993), 13-53.

[41] "Determination of Optimal Vertices from Feasible Solutions in Unimodular Linear Programming" with Shinji Mizuno and Romesh Saigal. Mathematical Programming 59, (1993), 23-32.

[42] "Polynomial Dual Network Simplex Algorithms" with Serge Plotkin and Eva Tardos. Mathematical Programming 60, (1993), 255-276.

[43] "Parallel Algorithms for the Assignment and Minimum Cost Flow Problems" with Cliff Stein. OR Letters 14, (1993), 181-186.

[44] "Finding Minimum Cost to Time Ratio Cycles with Small Integral Transit Times" with Mark Hartmann. Networks 23, (1993), 567-574.

[45] Network Flows: Theory, Algorithms, and Applications. With Ravindra K. Ahuja and Thomas L. Magnanti. Prentice Hall, Englewood Cliffs, N.J. 1993.

[46] "A Technique for Speeding up the Solution of the Lagrangian Dual" with Dimitris Bertsimas. Mathematical Programming 63, (1994), 23-46.

[47] "Improved Algorithms for Bipartite Network Flow" with Ravi Ahuja, Cliff Stein, and Bob Tarjan. SIAM Journal of Computing 23, (1994), 906-933.

[48] "A Faster Algorithm for Finding a Minimum Cut in a Graph" with Jianxiu Hao. Journal of Algorithms 17, (1994), 424-446.

[49] "On Very Large Scale Assignment Problems," with Yusin Lee. In Large Scale Optimization: State of the Art, W.W. Hager, D. W. Hearn and P.M Pardalos, Editors. Kluwer Academic Publishers, Dordrecht, The Netherlands, (1994), 206-244.

[50] "A Capacity Scaling Algorithm for the Constrained Maximum Flow Problem" with Ravi Ahuja. Networks 25, (1995), 89-98.

[51] "An STS-based map of the human genome" with Tom Hudson, Lincoln Stein, David Page, Eric Lander and 45 other co-authors. Science 270, (1995), 1945-1954.

[52] "Applications of Network Optimization" with Ravi Ahuja,Tom Magnanti, and M.R. Reddy. Chapter 1 of the Handbooks in Operations Research and Management Science, Volume 7: Network Models, eds. M. O. Ball, T. L. Magnanti, C. L. Monma, and G.L. Nemhauser. Elsevier, North Holland, (1995) 1-84.

[53] "Use of Representative Operation Counts in Computational Testings of Algorithms" with Ravi Ahuja. Informs Journal of Computing 8, (1996), 318-330

[54] "A Parametric Worst Case Analysis for a Machine Scheduling Problem" with Paul Mireault and Rakesh Vohra. Operations Research 45, (1997), 116-125.

[55] "A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows. Mathematical Programming 78, (1997), 109-129.

[56]  “Optimized Crossover for the Independent Set Problem" with Charu Aggarwal and Ray Tai. Operations Research 45, (1997), 226-234.

 

[57]  “Equivalence of Primal and Dual Simplex Algorithms for the Maximum Flow Problem,” with Ravi Ahuja.  Sloan School Working paper 3884-96, March 1996. Operations Research Letters 20, (1997) 101-108.

 

[58]  "Computational Investigations of Maximum Flow Algorithms" with Ajay Mishra, Murali Kodialam and Ravindra Ahuja. European Journal of Operations Research 97, (1997), 509-542.

 

[59]  “Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem” with Donald Goldfarb and Zhiying Jin. Mathematics of Operations Research 22, (1997), 793-802.

 

[60]  "A Scaling Algorithm for Multicommodity Flow Problems" with Rina R. Schneur. Operations Research 46, (1998), 231-246.

 

[61]  "Diagnosing Infeasibilities in Network Flow Problems," with Charu Aggarwal, Ravi Ahuja, and Jianxiu Hao.  Mathematical Programming 81, (1998), 263-280.

 

[62]  "Arc Weighting in Hidden Bicircular Networks" with Randy Shull, Alan Shuchat, and Marianne Lepp.  Congressus Numerantium 125 (1997) 161-171.

 

[63]  "Solving inverse spanning tree problems through network flow techniques" with P. T. Sokkalingam and Ravi Ahuja. Operations Research 47, (1999),  291-300.

 

[64]  “A Greedy Genetic Algorithm for the Quadratic Assignment Problem” with Ravi Ahuja and Ashish Tiwari. Computers and Operations Research 27, (2000), 917-934.

 

[65]  "Algorithms for the Simple Equal Flow Problem" with Ravi Ahuja, Giovanni Sechi, and Paola Zuddas. Management Science 45, (1999), 1440-1455.

 

[66]  “Optimal Rounding of Fractional, Stationary, Dynamic Flows When Flows are Instantaneous” with Lisa Fleischer. SIAM Journal of Discrete Mathematics 13 (1999) 145-153.

 

[67]  “New Polynomial-Time Cycle-Canceling Algorithms for Minimum Cost Flows” with P.T. Sokkalingam and Ravi Ahuja.  Networks 36, (2000) 53-63.

 

[68]  "On Multi-Route Maximum Flows in Networks" with Charu Aggarwal. Networks 39, (2002), 43-52.

 

[69]  "A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints" with Ravi Ahuja. Operations Research 35, (2001), 784-789.

 

[70]  "Inverse Optimization, Part I: Linear Programming and General Problem" with Ravi Ahuja. Operations Research 35, (2001), 771-783.

 

[71]   "A Faster Algorithm for the Inverse Spanning Tree Problem" with Ravi Ahuja Journal of Algorithms 34, (2000) 177-193.

 

[72]  "A Survey of Very Large Scale Neighborhood Search Techniques", with Ravi Ahuja, Ozlem Ergun, and Abraham Punnen. Discrete Applied Mathematics 23 (2002), 75-102.

 

[73]  "Very large scale neighborhood search." with Ravi Ahuja and Dushyant Sharma, International Transactions in Operations Research 7, (2002)  301-317.

 

[74]  Multi-exchange Neighborhood Search Algorithms for the Capacitated Minimum Spanning Tree Problem", with Ravi Ahuja and Dushyant Sharma. Mathematical Programming 91, (2001), 71-97.

 

[75]  "Minimum Time and Minimum Cost Path Problems in Street Networks with Periodic Traffic Lights" with Ravi Ahuja, Stefano Pallotino and Maria Grazia Scutella. Transportation Science 36, (2002) 326-336.

 

[76]  "A Network Simplex Algorithm with O(n) Consecutive Degenerate Pivots" with Ravi Ahuja, Prabha Sharma, and P. T. Sokkalingam. OR Letters 30, (2002), 141-148.

 

[77]  "Combinatorial Algorithms for Inverse Network Flow Problems" with Ravi Ahuja. Networks 40 (2002) 181-187.

 

[78]    "Solving the Convex Cost Integer Dual Network Flow Problem" with Ravi Ahuja and Dorit Hochbaum. Appeared in the 1999 IPCO proceedings. Management Science 49, (2003), 950-964.

 

[79]  "A Composite Neighborhood Search Algorithm for the Capacitated Minimum Spanning Tree Problem," with Ravi Ahuja and Dushyant Sharma.  Operations Research Letters 31, (2003), 185-194.

 

[80]  “Very Large-scale Neighborhood Search” with Ravi Ahuja and Dushyant Sharma, International Transactions in Operations Research 7, (2000)  301-317.

 

[81]  "Dynamic Shortest Paths Minimizing Travel Times and Costs", with Ravi Ahuja, Stefano Pallottino, and Maria G. Scutellą. Networks, 41, (2003) 197-205

 

[82]  “A Cut-Based Algorithm for the Nonlinear Dual of the Minimum Cost Network Flow Problem” with Ravi Ahuja and Dorit Hochbaum.  (2003).  Accepted for publication by Algorithmica.

 

[83]   "The Extended Neighborhood: Definition and Characterization" with Dushyant Sharma, September, 2002. Accepted for publication by Math Programming.

 

[84]   "A Multi-exchange Heuristic for the Single Source Capacitated Facility Location Problem" with Ravi Ahuja, Stefano Pallottino, Maria Scaparra, and Maria Scutellį, July 2002.   Accepted for publication by Management Science.

 

[85]    “Solving multi-criteria combined through-fleet assignment models” with Ravi Ahuja, J. Liu, John Goodstein, Amit Mukherjee, and Dushyant 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, (2003) 233-256.

 

 

WORKING PAPERS AND TECHNICAL REPORTS:

 

 

[WP1]  "Genuinely Polynomial Simplex and Non Simplex Algorithms for the Minimum Cost Flow Problem". MIT Sloan School working paper 1615-84.  December, 1984. 

 

[WP2]  "Analysis and Solution Algorithms of Sealift Routing and Scheduling Problems: Final Report", with Harilaos Psaraftis, Daniel Bienstock, and Paul Thompson, MIT Sloan School Working Paper 1700-85, 1985.

 

[WP 3]    "The Theory of Cyclic Transfers" with Paul Thompson.  M.I.T.  Operations Research Center Report OR 200-89, 1989.

 

[WP 4]  "QuickMatch: A Very Fast Algorithm for the Assignment Problem," with Yusin Lee.  MIT Sloan School Working Paper 3547-93.  March 1993.

 

[WP 5]  "Fast Approximation Schemes for Multi-Criteria Combinatorial Optimization" with Hershel Safer.   Sloan School Working paper 3756-95,  January 1995.

 

[WP 6]  "Fast Approximation Schemes for Multi-Criteria Flow, Knapsack, and Scheduling Problems" with Hershel Safer.   Sloan School Working paper 3757-95,  January 1995.

 

[WP 7]  “On the Sum-of-Squares Algorithm for Bin Packing” with Janos Csirik, David Johnson, Claire Kenyon, Peter Shor, and Richard  Weber.  October 2002.  Extended abstract. Thirty-Second Annual ACM Symposium on Theory of Computing (STOC '00). 

 

[WP 8]  “On e-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization” with Andreas S Schulz, and Sudipta Sengupta.  Extended Abstract. Thirty-Second Annual ACM Symposium on Theory of Computing (STOC '00).

 

[WP 9]  "Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs" with Ramkumar Ramaswamy and Nilopal Chakravarty. Working Paper, April 2001.

 

[WP 10]  "A Very Large-Scale Neighborhood Search Algorithm for the Combined Through and Fleet Assignment Model", with Ravi Ahuja, Jon Goodstein, Amit Mukherjee, and Dushyant Sharma. December, 2001.

 

[WP 11]  "Solving Real-Life Locomotive Scheduling Problems", with Ravi Ahuja, Jian Liu, Dushyant Sharma, and Larry Shughart. April 2002.

 

[WP 12]  "Branch and Bound Algorithms for the Test Cover Problem", an extended abstract, with K.M.J. de Bontridder, B. J. Lageweg, J.K. Lenstra, and L. Stougie, June 2002.

 

[WP 13]   "Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem", with Ravi Ahuja, Krishna Jha, and Dushyant Sharma. July, 2002.

 

[WP 14]  "Creating Very Large Scale Neighborhoods out of Smaller Ones by Compounding Moves: A Study on the Vehicle Routing Problem" with Ozlem Ergun and Abran Steele-Feldman, September 2002.

 

[WP 15]  “Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem” with Ravi Ahuja, A. Kumar, K.C. Jha.  Technical Report.  2003.

 

[WP 16]  “Approximate Local Search in Combinatorial Optimization” with Abraham Punnen and Andreas Schulz.  Technical Report.  An extended abstract appeared in the Proceedings of the 2004 Symposium on Discrete Algorithms (SODA).

 

[WP 17]  “Two Dynamic Programming Methodologies in Very Large Scale Neighborhood Search Applied to the Traveling Salesman Problem” with Özlem Ergun.  MIT Technical Report.  August, 2003