Optimization Technology Center of Northwestern and Argonne National Laboratory, Linear Programming FAQ, here. CCAR simulation for folks with 1+ trillion USD balance sheets set up the possibility of running an LP to maximize the Net Interest Margin (NIM) NIM is the difference
interest rate(assets) – interest rate (liabilities)
via the internal Transfer Pricing curves used to allocate capital within the Firm. NIM for a large bank can be anywhere from 150 to 300 bps. The value of a bp of NIM to a large Balance sheet is around 10+mm USD annually. If the LP gets the Firm a 2% better NIM through periodic reallocation and optimization at say a 300 bp NIM the Firm realizes 100+ mm USD of annual revenue that would otherwise be foregone. That 100mm annuity costs the Firm, on top of the sunk CCAR costs, a little Balance Sheet Simulation Code Optimization, an iMac5K, the ICC compiler w MKL, LP production setup, and control theory infrastructure for Treasury.
Pink I, with Intel/AVX2 and Moore’s Law, and in association with the Federal Reserve CCAR program (reasonably thorough dissection of a large Balance Sheet), we bring you … the 2015 Billion Dollar Floating Point Hack.
A: Options for parallel computation of various kinds have become a common feature of software for linear and mixed-integer programming. Here are some examples:
IBM’s OSL Parallel Extensions implement interior-point methods for linear programming and branch-and-bound methods for mixed-integer programming on homogeneous networks under Windows NT, AIX 4.x (on IBM RS/6000 and SP systems), HP-UX, Sun Solaris, and SGI IRIX, using the Parallel Virtual Machine (PVM) System version 3.4 for communication.
The CPLEX Parallel Solvers include simplex, barrier, and branch-and-bound solvers for linear and mixed-integer programming on a number of multiple-CPU systems.
Dash’s Xpress-Parallel includes a branch-and-bound mixed-integer programming code designed to exploit both multi-processor computers and networks of workstations.
OOPS is an object-oriented parallel implementation of the interior point algorithm, developed by Jacek Gondzio (firstname.lastname@example.org), Andreas Grothey and Robert Sarkissian. The code can exploit any special structure of the problem. It runs on all parallel computing platforms that support MPI.
Two parallel branch-cut-price frameworks are available to those who want to program specialized solvers for hard combinatorial problems that can be approached via integer programming:
Symphony requires the user to supply model-specific preprocessing and separation functions, while other components including search tree, cut pool, and communication management are handled internally. Source code is included for basic applications to traveling salesman and vehicle routing problems. The distributed version runs in any environment supported by the PVM message passing protocol, and can also be compiled for shared-memory architectures using any OpenMP compliant compiler.
BCP is a component of the COIN open source initiative.
Performance evaluations of parallel solvers must be interpreted with care. One common measurement is the “speedup” defined as the time for solution using a single processor divided by the time using multiple processors. A speedup close to the number of processors is ideal in some sense, but it is only a relative measure. The greatest speedups tend to be achieved by the least efficient codes, and especially by those that fail to take advantage of the sparsity (predominance of zero coefficients) in the constraints. For problems having thousands of constraints, a sparse single-processor code will tend to be faster than a non-sparse multiprocessor code running on current-day hardware.
Nemhauser, Rinnooy Kan, & Todd, eds, Optimization: Handbooks in Operations Research and Management Science, Volume 1, North-Holland, 1989. (Very broad-reaching, with large bibliography; a good reference, and worth checking first. Expensive, though, and tough reading for beginners.)
Regarding the common question of the choice of textbook for a college LP course, it’s difficult to give a blanket answer because of the variety of topics that can be emphasized: brief overview of algorithms, deeper study of algorithms, theorems and proofs, complexity theory, efficient linear algebra, modelling techniques, solution analysis, and so on. A small and unscientific poll of ORCS-L mailing list readers in 1993 uncovered a consensus that [Chvatal] was in most ways pretty good, at least for an algorithmically oriented class; of course, some new candidate texts have been published in the meantime. For a class in modelling, a book about a commercial code would be useful (LINDO, AMPL, GAMS were suggested), especially if the students are going to use such a code; and many are fond of [Williams], which presents a considerable variety of modelling examples.
Bazaraa, Jarvis and Sherali. Linear Programming and Network Flows. Grad level.
Bertsimas, Dimitris and Tsitsiklis, John, Introduction to Linear Optimization. Athena Scientific, 1997 (ISBN 1-886529-19-1). Graduate-level text on linear programming, network flows, and discrete optimization.
Chvatal, Linear Programming, Freeman, 1983. Undergrad or grad.
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R. and Schrijver, A. Combinatorial Optimization, Wiley Interscience, 1997.
Daellenbach, Hans G., A User’s Guide to Linear Programming. Good for engineers. Currently out of print.
Fang, S.-C. & Puthenpura, S., Linear Optimization and Extensions: Theory and Algorithms. Prentice Hall, 1993.
Dantzig, George B., Linear Programming and Extensions, Princeton University Press, 1963.. The most widely cited early textbook in the field.
Dantzig, George B. and Thapa, Mukund N., Linear Programming 1: Introduction, Springer Verlag, 1997..
Gass, Saul I., Linear Programming: Methods and Applications, 5th edition. International Thomson Publishing, 1985.. The author received the 1997 INFORMS Expository Writing Award.
Ignizio, J.P. & Cavalier, T.M., Linear Programming, Prentice Hall, 1994. Covers usual LP topics, plus interior point, multi-objective and heuristic techniques.
Luenberger, Introduction to Linear and non-linear Programming, Addison Wesley, 1984. Updated version of an old standby. The author received the 1999 INFORMS Expository Writing Award.
Murtagh, B., Advanced Linear Programming: Computation and Practice. McGraw-Hill, 1981. Good one after you’ve read an introductory text. Currently out of print.
Murty, K., Linear and Combinatorial Programming.
Nash, S., and Sofer, A., Linear and non-linear Programming, McGraw-Hill, 1996.
Nazareth, J.L., Computer Solution of Linear Programs, Oxford University Press, New York and Oxford, 1987.
Nemhauser, G.L. and Wolsey, L.A., Integer and Combinatorial Optimization, Wiley Interscience, 1988. An advanced text that covers many theortical and computational topics.
Nering, E.D. & Tucker, A.W., Linear Programs and Related Problems, Academic Press, 1993.
Roos, Terlaky and Vial, Theory and Algorithms for Linear Optimization: An Interior Point Approach. John Wiley, Chichester, 1997
Saigal, R., Linear Programming: A Modern Integrated Analysis, Kluwer Academic Publishers, 1995.
Schrijver, A., Theory of Linear and Integer Programming, Wiley, 1986. Advanced.
Taha, H., Operations Research: An Introduction, 1987.
Thie, P.R., An Introduction to Linear Programming and Game Theory, Wiley, 1988.
Vanderbei, Robert J., Linear Programming: Foundations and Extensions. Kluwer Academic Publishers, 1996. Balanced coverage of simplex and interior-point methods. Source code available on-line for all algorithms presented.
Williams, H.P., Model Building in Mathematical Programming, Wiley 1993, 3rd edition. Little on algorithms, but excellent for learning what makes a good model.
Wright, Stephen J., Primal-Dual Interior-Point Methods. SIAM Publications, 1997. Covers theoretical, practical and computational aspects of the most important and useful class of interior-point algorithms. The web page for this book contains current information on interior-point codes for linear programming, including links to their websites.
Ye, Yinyu, Interior Point Algorithms: Theory and Analysis. Wiley, 1997.