Sauder School of Business

University of British Columbia Logo

Opening Worlds

THE UNIVERSITY OF BRITISH COLUMBIA

 

 

 

S. Thomas (Tom) McCormick

AB (Penn), PhD (Stanford)

WJ Van Dusen Professor in Management

Professor, Operations and Logistics Division

 

Contact Information

 

Office:  Henry Angus 463

Tel:     (604) 822-8426

Fax:     (604) 822-9574

Email: Tom.McCormick [at-sign] sauder [dot] ubc [dot] ca

 
 
 

 

 


Thomas McCormick

 

 

 

 

Research Interests

 

My research looks at optimizing mathematical models of business processes.  I am particularly interested in models of flows of various commodities through networks, and problems of scheduling.  I am also interested in problems where submodularity and/or parametric optimization come into play.  Some of this work is around “computational complexity”: which problems are NP Hard, and which are computationally tractable?  When a problem is tractable, what is the fastest algorithm for it?  Lately I have been interested in some real-world problems in supply chains and block cave mining.

 

 

Teaching Interests

 

I have taught at many levels: undergraduate, masters, PhD, executive programs, and in both engineering and business schools.  I have given short courses in optimization in Berlin, and in Padua and Rimini in Italy.  Recently most of my teaching has been in the MBA Core course at UBC, where I teach Supply Chain Management and Optimization as part of an interdisciplinary team.  I won the UBC CGA Master Teaching Award for Graduate Teaching in 1997.

 

 

Publications

 

[1] P. Pesneau, B. Fortz, A.R. Mahjoub, and S. T. McCormick (2006). The 2-Edge Connected

Subgraph Problem with Bounded Rings. Math. Prog., 105, 85–111.

 

[2] S. Iwata, S. T. McCormick, and M. Shigeno (2005). A Strongly Polynomial Cut Canceling Algorithm for the Submodular Flow Problem. SIAM J. on Discrete Math., 19, 304–320; a preliminary version appeared in Proceedings of the Seventh MPS Conference on Integer Programming and Combinatorial Optimization (1999), G. Cornu΄ejols, R. E. Burkard, and G. J. Woeginger, eds., 259–272.

 

[3] S. Iwata, S. T. McCormick, and M. Shigeno (2003). Fast Cycle Canceling Algorithms for Minimum Cost Submodular Flow. Combinatorica 23, 503–525; an extended abstract of a preliminary version appears as A Faster Algorithm for Minimum Cost Submodular Flows Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (1998), 167–174.

 

[4] S.T. McCormick, G. Rinaldi, and M.R. Rao (2003). Easy and Difficult Objective Functions for Max Cut. Math. Prog. B, 94, 459–466.

 

[5] Lisa K. Fleischer, S. Iwata, and S. T. McCormick (2002). A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow. Math. Prog., 92, 119–139.

 

[6] S.T. McCormick, S.R. Smallwood and F.C.R. Spieksma (2001).A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths. Math. of OR, 26, 31–49. An extended abstract appears in Proceedings of Eighth SODA (1997), 509–517.

 

[7] S. Iwata, S. T. McCormick, and M. Shigeno (2000). A Fast Cost Scaling Algorithm for Submodular Flow. Information Processing Letters, 74, 123–128.

 

[8] M. Shigeno, S. Iwata, and S.T. McCormick (2000).Relaxed most negative cycle and most positive cut canceling algorithms for minimum cost flow. Math. of OR, 25, 76–104.

 

[9] S.T. McCormick and A. Shioura (2000). Minimum Ratio Canceling is Oracle Polynomial for Linear Programming, but Not Strongly Polynomial, Even for Networks. OR Letters, 27, 199– 207. An extended abstract appeared in Proceeding of SODA 2000, 944–952.

 

[10] S.T. McCormick (1995).A Polynomial Algorithm for Abstract Maximum Flow. An extended abstract appears in Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 490–497.

 

[11] McCormick, S.T. (2000).Fast Algorithms for Parametric Scheduling come from Extensions to Parametric Maximum Flow. Operations Research, 47, 744–756; an extended abstract appears in Proceedings of Symposium on the Theory of Computing (1996) 319– 328.

 

[12] S. Iwata, T. Matsui, and S.T. McCormick (1998). A Fast Bipartite Network Flow Algorithm for Selective Assembly. OR Letters, 22, 137–143.

 

[13] S.T. McCormick (1997). How to Compute Least Infeasible Flows. Math Programming B, 78, 179–194. An extended abstract appears in the program book of NETFLOW93, 160–164.

 

[14] A.V. Karzanov and S.T. McCormick (1997).Polynomial Methods for Separable Convex Optimization in Totally Unimodular Linear Spaces with Applications to Circulations and Cocirculations in Networks. SIAM J. on Computing, 26, 1245–1275. An extended abstract appears in Proceedings of the Sixth SODA, (1995), 78–87.

 

[15] S.T. McCormick (1996). Submodular Containment is Hard, Even for Networks. OR Letters, 19, 95–99.

 

[16] S.T. McCormick and M.L. Pinedo (1995). Scheduling n Independent Jobs on m Uniform Machines with both Flow Time and Makespan Objectives: A Parametric Approach. ORSA Journal on Computing, 7, 63–77.

 

[17] S.T. McCormick and U.S. Rao (1994). Some Complexity Results in Cyclic Scheduling. Mathematical and Computer Modelling, 20, 107–122.

 

[18] S.T. McCormick and T.R. Ervolina (1994). Computing Maximum Mean Cuts. Discrete Applied Math, 52, 53–70.

 

[19] T.R. Ervolina and S.T. McCormick (1993). Two Strongly Polynomial Cut Cancelling Algorithms for Minimum Cost Network Flow. Discrete Applied Math, 46, pp. 133–165.

 

[20] S.T. McCormick (1993). Approximate Binary Search Algorithms for Mean Cuts and Cycles. OR Letters, 14, 129–132.

 

[21] T.R. Ervolina and S.T. McCormick (1993). Cancelling Most Helpful Total Cuts for Minimum Cost Network Flow. Networks, 23, pp. 41–52.

 

[22] S.F. Chang and S.T. McCormick (1993). Computational Results for the Hierarchical Algorithm for Making Sparse Matrices Sparser. ACM Transactions on Mathematical Software, 19, 419–441.

 

[23] S.T. McCormick and S.F. Chang (1993). The Weighted Sparsity Problem: Complexity and Algorithms. SIAM Journal on Discrete Mathematics, 6, pp. 57–69.

 

[24] S.F. Chang and S.T. McCormick (1992). A Hierarchical Algorithm for Making Sparse Matrices Sparser. Mathematical Programming, 56, pp. 1–30.

 

[25] C-L. Li, S.T. McCormick and D. Simchi-Levi (1992). On the Minimum-Cardinality-Bounded- Diameter and the Fixed-Budget-Minimum-Diameter Edge Addition Problems. OR Letters, 11, pp. 303–308.

 

[26] C-L. Li, S.T. McCormick and D. Simchi-Levi (1992). Finding Disjoint Paths with Different Path Costs: Complexity and Algorithms. Networks, 22, pp. 653–667.

 

[27] C-L. Li, S.T. McCormick and D. Simchi-Levi (1992). The Point-to-Point Delivery and Connection Problems: Complexity and Algorithms. Discrete Applied Mathematics, 36, pp. 267–292.  [the pdf file is missing the lines in the figures, but they should be clear from the text]

 

[28] D.L. Applegate, W.J. Cook and S.T. McCormick (1991). Integral Infeasibility and Testing Total Dual Integrality. OR Letters, 10, pp. 37–41.

 

[29] S.T. McCormick, M.L. Pinedo, S. Shenker and B. Wolf (1991). Transient Behavior in a Flexible Assembly System, International Journal of Flexible Manufacturing Systems, 3, pp. 27–44.

 

[30] S.T. McCormick (1990). Making Sparse Matrices Sparser: Computational Results. Math. Programming, 49, pp. 91–111.

 

[31] C-L. Li, S.T. McCormick and D. Simchi-Levi (1990). The Complexity of Finding Two Disjoint Paths with Min-Max Objective Function, Discrete Applied Mathematics, 26, pp. 105–115.

 

[32] S.T. McCormick, M.L. Pinedo, S. Shenker and B. Wolf (1989). Sequencing in an Assembly Line with Blocking to Minimize Cycle Time, Operations Research, 37, pp. 925–935.

 

[33] S.S. Chaudhry, S.T. McCormick and J.D. Moon (1987). Conditional Covering: Greedy Heuristics and Computational Results, Computers in Operations Research, 14, pp. 11–18.

 

[34] S.S. Chaudhry, S.T. McCormick and J.D. Moon (1986). Locating Independent Facilities with Maximum Weight: Greedy Heuristics, OMEGA, 14, pp. 383–389.

 

[35] S.T. McCormick (1983). Optimal Approximation of Sparse Hessians and its Equivalence to a Graph Coloring Problem. Mathematical Programming, 26, pp. 153–171.

 

 

Articles Submitted to Refereed Journals

 

[36] F. Granot, S.T. McCormick, M.N. Queyranne, and F. Tardella (2008). Monotone parametric min cut revisited: structures and algorithms. Submitted to Math. of OR.

 

[37] S. T. McCormick and S. Fujishige (2008). Strongly Polynomial and Fully Combinatorial Algorithms for Bisubmodular Function Minimization. Revision submitted to Mathematical Programming.

 

[38] Maren Martens, S. T. McCormick, and Maurice Queyranne (2008). Separation, Dimension, and Facet Algorithms

for Node Flow Polyhedra.  Submitted to SODA.

 

[39] Jing Shao, Harish Krishnan, and S. T. McCormick (2008).  Distributing a Product Line in a Decentralized Supply

Chain.  Submitted to POMS.

 

 

Other Refereed Contributions

 

[40] S.T. McCormick and L. Liu (1993). An Experimental Implementation of the Dual Cancel and Tighten Algorithm for Minimum Cost Network Flow. In Network Flows and Matching, D.S. Johnson and C.S McGeoch, eds., American Mathematical Society DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 12, 247–266.

 

[41] S.T. McCormick, M.L. Pinedo and B. Wolf (1986). Sequencing in a Flexible Assembly Line with Blocking to Minimize Cycle Time. In Flexible Manufacturing Systems, K.E. Stecke and R. Suri, eds., Elsevier, Amsterdam.

 

[42] Alan J. Hoffman and S.T. McCormick (1984). A Fast Algorithm that Makes Matrices Optimally Sparse. In Progress in Combinatorial Optimization, W. Pulleyblank, ed., Academic Press, New York.

 

 

Book Chapters

 

The following book chapter was published by Elsevier as part of the Handbook on Discrete Optimization, and contains lots of good stuff.  I encourage you to buy the handbook at the following link:

www.elsevier.com/wps/find/bookdescription.cws_home/699541/description#description

 

However, since publication there have been exciting new developments in Submodular Function Minimization, such as Orlin’s Algorithm.  The link below is to an updated version (now Version 3a, updated 11 February 2008) which clarifies SFM on ring families, and updates the section on computational results.

 

S. T. McCormick (2006). Submodular Function Minimization.  Chapter 7 in the Handbook on

Discrete Optimization, Elsevier, K. Aardal, G. Nemhauser, and R. Weismantel, eds, 321–391.

 

S. T. McCormick (1999). Minimum Cost Single Commodity Flow. Chapter 9.4 in the

Handbook of Applied Optimization, Oxford University Press, P. Pardalos and M. Resende,

eds.

 

 

CV

 

Last updated: 4 July 2008