×

SUSPECT: MINLP special structure detector for Pyomo. (English) Zbl 1444.90081

Summary: We present SUSPECT, an open source toolkit that symbolically analyzes mixed-integer nonlinear optimization problems formulated using the Python algebraic modeling library Pyomo. We present the data structures and algorithms used to implement SUSPECT. SUSPECT works on a directed acyclic graph representation of the optimization problem to perform: bounds tightening, bound propagation, monotonicity detection, and convexity detection. We show how the tree-walking rules in SUSPECT balance the need for a lightweight computation with effective special structure detection. SUSPECT can be used as a standalone tool or as a Python library to be integrated in other tools or solvers. We highlight the easy extensibility of SUSPECT with several recent convexity detection tricks from the literature. We also report experimental results on the MINLPLib 2 dataset.

MSC:

90C11 Mixed integer programming
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adjiman, CS; Androulakis, IP; Floudas, CA, Global optimization of mixed-integer nonlinear problems, AIChE J., 46, 9, 1769-1797 (2000)
[2] An, Le Thi Hoai, D.C. Programming for Solving a Class of Global Optimization Problems via Reformulation by Exact Penalty, Global Optimization and Constraint Satisfaction, 87-101 (2003), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1255.90097
[3] Belotti, P., Bound reduction using pairs of linear inequalities, J. Glob. Optim., 56, 3, 787-819 (2013) · Zbl 1272.90033
[4] Belotti, Pietro; Cafieri, Sonia; Lee, Jon; Liberti, Leo, Feasibility-Based Bounds Tightening via Fixed Points, Combinatorial Optimization and Applications, 65-76 (2010), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1311.90189
[5] Belotti, P.; Kirches, C.; Leyffer, S.; Linderoth, J.; Luedtke, J.; Mahajan, A., Mixed-integer nonlinear optimization, Acta Numer., 22, 1-131 (2013) · Zbl 1291.65172
[6] Belotti, P.; Lee, J.; Liberti, L.; Margot, F.; Wächter, A., Branching and bounds tightening techniques for non-convex MINLP, Optim. Met. Softw., 24, 4-5, 597-634 (2009) · Zbl 1179.90237
[7] Benhamou, F.; Older, WJ, Applying interval arithmetic to real, integer, and boolean constraints, J. Log. Program., 32, 1, 1-24 (1997) · Zbl 0882.68032
[8] Boukouvala, F.; Misener, R.; Floudas, CA, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, Eur. J. Oper. Res., 252, 3, 701-727 (2016) · Zbl 1346.90677
[9] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049
[10] Ceccon, F.: SUSPECT: 10.5281/zenodo.1216808 (2018)
[11] Ceccon, F.; Kouyialis, G.; Misener, R., Using functional programming to recognize named structure in an optimization problem: application to pooling, AIChE J., 62, 9, 3085-3095 (2016)
[12] Chinneck, JW, Analyzing mathematical programs using MProbe, Ann. Oper. Res., 104, 1-4, 33-48 (2001) · Zbl 1007.90064
[13] Cormen, TH, Introduction to Algorithms (2009), New York: MIT Press, New York · Zbl 1187.68679
[14] Diamond, S.; Boyd, S., Cvxpy: a python-embedded modeling language for convex optimization, J. Mach. Learn. Res., 17, 1, 2909-2913 (2016) · Zbl 1360.90008
[15] Floudas, CA, Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications (1995), Oxford: Oxford University Press, Oxford · Zbl 0886.90106
[16] Fourer, R.; Ma, J.; Martin, K., OSiL: an instance language for optimization, Comput. Optim. Appl., 45, 1, 181-203 (2010) · Zbl 1189.90007
[17] Fourer, R.; Maheshwari, C.; Neumaier, A.; Orban, D.; Schichl, H., Convexity and concavity detection in computational graphs: tree walks for convexity assessment, INFORMS J. Comput., 22, 1, 26-43 (2010) · Zbl 1243.90004
[18] Fourer, R.; Orban, D., DrAmpl: a meta solver for optimization problem analysis, Comput. Manag. Sci., 7, 4, 437-463 (2010) · Zbl 1243.90005
[19] Gau, CY; Schrage, LE, Implementation and Testing of a Branch-and-Bound Based Method for Deterministic Global Optimization: Operations Research Applications, 145-164 (2004), Boston: Springer, Boston · Zbl 1165.90687
[20] Gleixner, AM; Berthold, T.; Müller, B.; Weltge, S., Three enhancements for optimization-based bound tightening, J. Glob. Optim., 67, 4, 731-757 (2017) · Zbl 1369.90106
[21] Goldberg, D., What every computer scientist should know about floating-point arithmetic, ACM Comput. Surv., 23, 1, 5-48 (1991)
[22] Grant, M., Boyd, S.: Graph implementations for nonsmooth convex programs. In: Recent Advances in Learning and Control, pp. 95-110. Springer (2008) · Zbl 1205.90223
[23] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx (2014)
[24] Grant, M.C.: Disciplined convex programming. Ph.D. thesis, Stanford University (2004). Accessed May 2018 · Zbl 1130.90382
[25] Grossmann, IE, Global Optimization in Engineering Design (1996), New York: Springer, New York · Zbl 0869.00021
[26] Grossmann, Ignacio E.; Kravanja, Zdravko, Mixed-Integer Nonlinear Programming: A Survey of Algorithms and Applications, Large-Scale Optimization with Applications, 73-100 (1997), New York, NY: Springer New York, New York, NY · Zbl 0884.65058
[27] Hart, WE; Laird, CD; Watson, JP; Woodruff, DL; Hackebeil, GA; Nicholson, BL; Siirola, JD, Pyomo-Optimization Modeling in Python (2017), Berlin: Springer, Berlin · Zbl 1370.90003
[28] Hart, WE; Watson, JP; Woodruff, DL, Pyomo: modeling and solving mathematical programs in Python, Math. Program. Comput., 3, 3, 219-260 (2011)
[29] Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude, Conjugacy in Convex Analysis, Grundlehren der mathematischen Wissenschaften, 35-90 (1993), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 0795.49001
[30] Hoad, TC; Zobel, J., Methods for identifying versioned and plagiarised documents, J. Assoc. Inf. Sci. Technol., 54, 3, 203-215 (2003)
[31] Hooker, JN, Integrated Methods for Optimization, International Series in Operations Research & Management Science (2012), Boston: Springer, Boston · Zbl 1263.90002
[32] Kulisch, Ulrich W., Complete Interval Arithmetic and Its Implementation on the Computer, Numerical Validation in Current Hardware Architectures, 7-26 (2009), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg
[33] Lobo, MS; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear Algebra Appl., 284, 1-3, 193-228 (1998) · Zbl 0946.90050
[34] Lougee-Heimer, R., The common optimization INterface for operations research: promoting open-source software in the operations research community, IBM J. Res. Dev., 47, 1, 57-66 (2003)
[35] Mahajan, A., Leyffer, S., Linderoth, J., Luedtke, J., Munson, T.: Minotaur: A Mixed-Integer Nonlinear Optimization Toolkit (2017) · Zbl 1476.65099
[36] Millman, KJ; Aivazis, M., Python for scientists and engineers, Comput. Sci. Eng., 13, 2, 9-12 (2011)
[37] Misener, R.; Floudas, CA, Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, Math. Program., 136, 1, 155-182 (2012) · Zbl 1257.90079
[38] Misener, R.; Floudas, CA, GloMIQO: global mixed-integer quadratic optimizer, J. Glob. Optim., 57, 1, 3-50 (2013) · Zbl 1272.90034
[39] Misener, R.; Floudas, CA, A framework for globally optimizing mixed-integer signomial programs, J. Optim. Theory Appl., 161, 3, 905-932 (2014) · Zbl 1303.90074
[40] Misener, R.; Floudas, CA, ANTIGONE: Algorithms for coNTinuous/Integer Global Optimization of Nonlinear Equations, J. Glob. Optim., 59, 2-3, 503-526 (2014) · Zbl 1301.90063
[41] Mistry, M.; Misener, R., Optimising heat exchanger network synthesis using convexity properties of the logarithmic mean temperature difference, Comput. Chem. Eng., 94, 1-17 (2016)
[42] Mönnigmann, M., Efficient calculation of bounds on spectra of Hessian matrices, SIAM J. Sci. Comput., 30, 5, 2340-2357 (2008) · Zbl 1181.65055
[43] Moore, RE; Kearfott, RB; Cloud, MJ, Introduction to Interval Analysis (2009), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 1168.65002
[44] Nenov, I.P., Fylstra, D.H., Kolev, L.: Convexity determination in the Microsoft Excel Solver using automatic differentiation techniques. In: Fourth International Workshop on Automatic Differentiation (2004)
[45] Neun, Winfried; Sturm, Thomas; Vigerske, Stefan, Supporting Global Numerical Optimization of Rational Functions by Generic Symbolic Convexity Tests, Computer Algebra in Scientific Computing, 205-219 (2010), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1290.65053
[46] Nowak, I.; Vigerske, S., LaGO: a (heuristic) Branch and Cut algorithm for nonconvex MINLPs, Central Eur. J. Oper. Res., 16, 2, 127-138 (2008) · Zbl 1152.90665
[47] Schichl, H.; Neumaier, A., Interval analysis on directed acyclic graphs for global optimization, J. Glob. Optim., 33, 4, 541-562 (2005) · Zbl 1094.65061
[48] Stubbs, RA; Mehrotra, S., A branch-and-cut method for 0-1 mixed convex programming, Math. Program., 86, 3, 515-532 (1999) · Zbl 0946.90054
[49] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 2, 225-249 (2005) · Zbl 1099.90047
[50] Tuy, H., A General Deterministic Approach to Global Optimization VIA D.C. Programming, 273-303 (1986), Amsterdam: North-Holland Mathematics Studies, Amsterdam · Zbl 0623.65067
[51] Udell, M., Mohan, K., Zeng, D., Hong, J., Diamond, S., Boyd, S.: Convex optimization in Julia. In: Proceedings of the 1st First Workshop for High Performance Technical Computing in Dynamic Languages, pp. 18-28. IEEE Press (2014)
[52] Van Voorhis, T.; Al-Khayyal, FA, Difference of convex solution of quadratically constrained optimization problems, Eur. J. Oper. Res., 148, 2, 349-362 (2003) · Zbl 1035.90066
[53] Vigerske, S.: (MI)NLPLib 2. Tech. Rep. July (2015)
[54] Vigerske, S.; Heinz, S.; Gleixner, A.; Berthold, T., Analyzing the computational impact of MIQCP solver components, Numer. Algebra Control Optim., 2, 4, 739-748 (2012) · Zbl 1269.90066
[55] Vu, XH; Schichl, H.; Sam-Haroud, D., Interval propagation and search on directed acyclic graphs for numerical constraint solving, J. Glob. Optim., 45, 4, 499-531 (2009) · Zbl 1179.90267
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.