×

Customizing the solution process of COIN-OR’s linear solvers with python. (English) Zbl 1392.90078

Summary: Implementations of the simplex method differ mostly in specific aspects such as the pivot rule. Similarly, most relaxation methods for mixed-integer programming differ mostly in the type of cuts and the exploration of the search tree. We provide a scripting mechanism to easily implement and experiment with primal and dual pivot rules for the simplex method, by building upon COIN-OR’s open-source linear programming package CLP, without explicitly interacting with the underlying C++ layers of CLP. In the same manner, users can customize the solution process of mixed-integer linear programs using the CBC and CGL COIN-OR packages by coding branch-and-cut strategies and cut generators in Python. The Cython programming language ensures communication between Python and C++ libraries and activates user-defined customizations as callbacks. Our goal is to emphasize the ease of development in Python while maintaining acceptable performance. The resulting software, named CyLP, has become a part of COIN-OR and is available under open-source terms. For illustration, we provide an implementation of the positive edge rule – a recently proposed rule that is particularly efficient on degenerate problems – and demonstrate how to customize branch-and-cut node selection in the solution of a mixed-integer program.

MSC:

90C05 Linear programming
90C10 Integer programming
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aides, A.: Cython wrapper for IPOPT. http://code.google.com/p/cyipopt. Accessed 2 Nov 2011 (Online)
[2] Berkelaar, M.: lpsolve, A Mixed Integer Linear Programming Software. http://lpsolve.sourceforge.net. Accessed 2 Nov 2011 (Online) · Zbl 0793.90034
[3] Bland, R.G.: New finite pivoting rules for the Simplex method. Math. Oper. Res. 2(2), 103-107 (1977). (ISSN 0364765X) · Zbl 0408.90050 · doi:10.1287/moor.2.2.103
[4] Carolan, W., Hill, J., Kennington, J., Niemi, S., Wichmann, S.: Empirical evaluation of the KORBX algorithms for military airlift applications. Oper. Res. 38, 240-248 (1990) · doi:10.1287/opre.38.2.240
[5] CBC: COIN-OR Branch-and-Cut. http://projects.coin-or.org/Cbc. Accessed 2 Nov 2011 (Online) · Zbl 0734.90060
[6] CGL: COIN-OR Cut Generation Library. http://projects.coin-or.org/Cgl. Accessed 2 Nov 2011 (Online)
[7] Cipra, B.A.: The best of the 20th century: editors name top 10 algorithms. SIAM News 33(4), 1-2 (2000)
[8] CLP: COIN-OR Linear Programming. https://projects.COIN-OR.org/Clp. Accessed 2 Nov 2011 (Online)
[9] CPLEX: http://www.cplex.com. Accessed 2 Nov 2011 (Online)
[10] Cython: http://www.cython.org. Accessed 1 Sept 2013 (Online)
[11] Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, NJ (1963) · Zbl 0108.33103 · doi:10.1515/9781400884179
[12] Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. B 91, 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[13] Dongarra, J., Sullivan, F.: Guest editors’ introduction: the top 10 algorithms. Comput. Sci. Eng. 2, 22-23 (2000). doi:10.1109/MCISE.2000.8146052. (ISSN 1521-9615) · doi:10.1109/MCISE.2000.8146052
[14] Forrest, J.J., Goldfarb, D.: Steepest-edge simplex algorithms for linear programming. Math. Program. 57, 341-374 (1992). doi:10.1007/BF01581089. (ISSN 0025-5610) · Zbl 0787.90047 · doi:10.1007/BF01581089
[15] Goldfarb, D., Reid, J.K.: A practicable steepest-edge simplex algorithm. Math. Program. 12, 361-371 (1977). doi:10.1007/BF01593804. (ISSN 0025-5610) · Zbl 0443.90058 · doi:10.1007/BF01593804
[16] Greenberg, H.J.: An analysis of degeneracy. Naval Res. Log. Q. 33, 635-655 (1986) · Zbl 0644.90058 · doi:10.1002/nav.3800330409
[17] Gurobi: http://www.gurobi.com. Accessed 2 Nov 2011 (Online)
[18] Harris, P.M.J.: Pivot selection methods of the Devex LP code. In: Cottle, R.W., et al., (eds.) Computational Practice in Mathematical Programming, Mathematical Programming Studies, vol. 4, pp. 30-57. Springer, Berlin (1975). doi:10.1007/BFb0120710 (ISBN 978-3-642-00766-8) · Zbl 0395.90046
[19] Hoffman, K.L., Padberg, M.: Solving airline crew scheduling problems by branch-and-cut. Manag. Sci. 39, 675-682 (1993). doi:10.1287/mnsc.39.6.657 · Zbl 0783.90051 · doi:10.1287/mnsc.39.6.657
[20] Koepke, H.: Cython wrapper for CPLEX. http://www.stat.washington.edu/ hoytak/code/pycpx/index.html. Accessed 2 Nov 2011 (Online)
[21] Koepke, H.: Cython wrapper for lpsolve. http://www.stat.washington.edu/ hoytak/code/pylpsolve/index.html. Accessed 2 Nov 2011 (Online)
[22] Larman, C.: Applying UML and Patterns: An Introduction to Object-Oriented Analysis and Design and the Unified Process, 2nd edn. Prentice Hall, Upper Saddle River (2001)
[23] Lougee-Heimer, R.: The common optimization interface for operations research. IBM J. Res. Dev. 47(1), 57-66 (2003). doi:10.1147/rd.471.0057. http://www.COIN-OR.org
[24] Makhorin, A.: GLPK, GNU Linear Programming Kit. http://www.gnu.org/s/glpk. Accessed 2 Nov 2011 (Online) · Zbl 0644.90058
[25] Netlib: http://www.netlib.org/lp/data. Accessed 2 Nov 2011 (Online)
[26] Numpy: http://www.numpy.org. Accessed 1 Sept 2013 (Online)
[27] Padberg, M., Rinaldi, G.: A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33, 60-100 (1991). doi:10.1137/1033004. (ISSN 0036-1445) · Zbl 0734.90060 · doi:10.1137/1033004
[28] PuLP: An LP modeler written in Python. http://code.google.com/p/pulp-or. Accessed 2 Nov 2011
[29] Python. http://www.python.org. Accessed 1 Sept 2013 (Online) · Zbl 0644.90058
[30] Raymond, V.,Soumis, F., Metrane, A., Desrosiers, J.: Positive edge: a pricing criterion for the identification of non-degenerate simplex pivots. In: Cahier du GERAD G-2010-61. GERAD, Montreal (2010) · Zbl 0443.90058
[31] Raymond, V., Soumis, F., Orban, D.: A new version of the improved primal simplex for degenerate linear programs. Comput. OR 37(1), 91-98 (2010). doi:10.1016/j.cor.2009.03.020 · Zbl 1176.90646 · doi:10.1016/j.cor.2009.03.020
[32] Scipy: http://www.scipy.org. Accessed 1 Sept 2013 (Online)
[33] Silva, P.J.S.: Pycoin, interface to some COIN packages (2005). http://www.ime.usp.br/ pjssilva/software.html. Accessed 2 Nov 2011 (Online) · Zbl 1176.90646
[34] SoPlex: An open-source LP solver. http://soplex.zib.de. Accessed 1 Sept 2013 (Online)
[35] Terlaky, T., Zhang, S.: Pivot rules for linear programming: a survey on recent theoretical developments. Ann. Oper. Res. 46-47, 203-233 (1993). doi:10.1007/BF02096264. (ISSN 0254-5330) · Zbl 0793.90034 · doi:10.1007/BF02096264
[36] Towhidi, M., Orban, D.: Customizing the solution process of coin-or’s linear solvers with python. In: Cahier du GERAD G-2012-07. GERAD, Montreal (2012) · Zbl 1392.90078
[37] Wächter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Programm. 106, 25-57 (2006). doi:10.1007/s10107-004-0559-y. https://projects.COIN-OR.org/Ipopt · Zbl 1134.90542
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.