×

Computing in operations research using Julia. (English) Zbl 1331.90001

Summary: The state of numerical computing is currently characterized by a divide between highly efficient yet typically cumbersome low-level languages such as C, C++, and Fortran and highly expressive yet typically slow high-level languages such as Python and MATLAB. This paper explores how Julia, a modern programming language for numerical computing that claims to bridge this divide by incorporating recent advances in language and compiler design (such as just-in-time compilation), can be used for implementing software and algorithms fundamental to the field of operations research, with a focus on mathematical optimization. In particular, we demonstrate algebraic modeling for linear and nonlinear optimization and a partial implementation of a practical simplex code. Extensive cross-language benchmarks suggest that Julia is capable of obtaining state-of-the-art performance.{ }Data, as supplemental material, are available at http://dx.doi.org/10.1287/ijoc.2014.0623.

MSC:

90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90C05 Linear programming
90C30 Nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andersson J (2013) A general-purpose software framework for dynamic optimization. Ph.D. thesis, Arenberg Doctoral School, KU Leuven, Department of Electrical Engineering (ESAT/SCD) and Optimization in Engineering Center, Heverlee, Belgium.
[2] Belotti P, Lee J, Liberti L, Margot F, Wächter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Software 24(4-5):597-634. CrossRef · Zbl 1179.90237
[3] Bezanson J, Karpinski S, Shah VB, Edelman A (2012) Julia: A fast dynamic language for technical computing. Accessed January 29, 2015, http://arxiv.org/abs/1209.5145.
[4] Bixby RE (2002) Solving real-world linear programs: A decade and more of progress. Oper. Res. 50(1):3-15. Abstract, · Zbl 1163.90643
[5] Bolz CF, Cuni A, Fijalkowski M, Rigo A (2009) Tracing the meta-level: PyPy’s tracing JIT compiler. Proc. 4th Workshop Implementation, Compilation, Optim. Object-Oriented Languages Programming Systems, ICOOOLPS ’09 (ACM, New York), 18-25. CrossRef
[6] Brooke A, Kendrick D, Meeraus A, Raman R (1988) GAMS: A User’s Guide (Scientific Press, Redwood City, CA).
[7] Duff IS, Grimes RG, Lewis JG (1989) Sparse matrix test problems. ACM Trans. Math. Software 15(1):1-14. CrossRef · Zbl 0667.65040
[8] Fourer R, Orban D (2010) DrAmpl: A meta solver for optimization problem analysis. Comput. Management Sci. 7(4):437-463. CrossRef · Zbl 1243.90005
[9] Fourer R, Gay DM, Kernighan BW (1993) AMPL: A Modeling Language for Mathematical Programming, 2nd ed. (Brooks/Cole, Pacific Grove, CA).
[10] Gay DM (1985) Electronic mail distribution of linear programming test problems. Math. Programming Soc. COAL Newsletter 13:10-12.
[11] Gay DM (1996) More AD of nonlinear AMPL models: Computing Hessian information and exploiting partial separability. Berz M, Bischof C, Corliss G, Griewank A, eds. Computational Differentiation: Applications, Techniques, and Tools (SIAM, Philadelphia), 173-184.
[12] Gay DM (1997) Hooking your solver to AMPL. Technical report, Bell Laboratories, Murray Hill, NJ.
[13] Grant MC, Boyd SP (2013) The CVX users’ guide (release 2.0). Accessed May 1, 2013, http://cvxr.com/cvx/doc/CVX.pdf.
[14] Hall J (2010) Towards a practical parallelisation of the simplex method. Comput. Management Sci. 7(2):139-170. CrossRef · Zbl 1185.90149
[15] Hall J, McKinnon K (2005) Hyper-sparsity in the revised simplex method and how to exploit it. Comput. Optim. Appl. 32(3):259-283. CrossRef · Zbl 1125.90033
[16] Harris PMJ (1973) Pivot selection methods of the DEVEX LP code. Math. Programming 5(1):1-28. CrossRef · Zbl 0261.90031
[17] Hart WE, Watson J-P, Woodruff DL (2011) Pyomo: Modeling and solving mathematical programs in Python. Math. Programming Comput. 3(3):219-260. CrossRef
[18] Koberstein A (2005) The dual simplex method, techniques for a fast and stable implementation. Unpublished doctoral thesis, Universität Paderborn, Paderborn, Germany. · Zbl 1198.90010
[19] Lattner C, Adve V (2004) LLVM: A compilation framework for lifelong program analysis and transformation. Code Generation Optim., 2004. Internat. Sympos., Palo Alto, CA, 75-86. CrossRef
[20] Lofberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. Comput. Aided Control Systems Design, 2004 IEEE Internat. Sympos., Taipai, Taiwan, 284-289. CrossRef
[21] Maros I (2003) Computational Techniques of the Simplex Method (Kluwer Academic Publishers, Norwell, MA). CrossRef
[22] Mitchell S, O’Sullivan M, Dunning I (2011) Pulp: A linear programming toolkit for python. Accessed May 1, 2013, https://code.google.com/p/pulp-or/.
[23] Mittelmann H (2013) Benchmarks for optimization software. Accessed April 28, 2013, http://plato.la.asu.edu/bench.html.
[24] Suhl UH, Suhl LM (1990) Computing sparse LU factorizations for large-scale linear programming bases. ORSA J. Comput. 2(4):325-335. Abstract, · Zbl 0755.90059
[25] van der Walt S, Colbert SC, Varoquaux G (2011) The NumPy array: A structure for efficient numerical computation. Comput. Sci. Engrg. 13(2):22-30. CrossRef
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.