Abstract
In this work, we propose a two-stage approach to strengthen piecewise McCormick relaxations for mixed-integer nonlinear programs (MINLP) with multi-linear terms. In the first stage, we exploit Constraint Programing (CP) techniques to contract the variable bounds. In the second stage we partition the variables domains using a dynamic multivariate partitioning scheme. Instead of equally partitioning the domains of variables appearing in multi-linear terms, we construct sparser partitions yet tighter relaxations by iteratively partitioning the variable domains in regions of interest. This approach decouples the number of partitions from the size of the variable domains, leads to a significant reduction in computation time, and limits the number of binary variables that are introduced by the partitioning. We demonstrate the performance of our algorithm on well-known benchmark problems from MINLPLIB and discuss the computational benefits of CP-based bound tightening procedures.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
This approach is easily extended to multi-linear terms using successive bilinear relaxations as discussed in Sect. 2.1.
- 2.
In the case of higher order monomials, i.e., \(x_i^5\), we apply a reduction of the form \(x_i^2x_i^2x_i \Rightarrow \tilde{x_i}^2x_i \Rightarrow \tilde{\tilde{x_i}}x_i\).
- 3.
In the “blend” instances, there were few binary variables that appeared in most of the bilinear terms. These are the variables chosen for partitioning.
References
Belotti, P., Cafieri, S., Lee, J., Liberti, L.: On feasibility based bounds tightening (2012). https://hal.archives-ouvertes.fr/file/index/docid/935464/filename/377.pdf
Bergamini, M.L., Grossmann, I., Scenna, N., Aguirre, P.: An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms. Comput. Chem. Eng. 32(3), 477–493 (2008)
Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib—a collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15(1), 114–119 (2003)
Cafieri, S., Lee, J., Liberti, L.: On convex relaxations of quadrilinear terms. J. Global Optim. 47(4), 661–685 (2010)
Castro, P.M.: Normalized multiparametric disaggregation: an efficient relaxation for mixed-integer bilinear problems. J. Global Optim., 1–20 (2015)
Castro, P.M.: Tightening piecewise McCormick relaxations for bilinear problems. Comput. Chem. Eng. 72, 300–311 (2015)
Castro, P.M., Grossmann, I.E.: Optimality-based bound contraction with multiparametric disaggregation for the global optimization of mixed-integer bilinear problems. J. Global Optim. 59(2–3), 277–306 (2014)
Coffrin, C., Hijazi, H.L., Van Hentenryck, P.: Strengthening convex relaxations with bound tightening for power network optimization. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 39–57. Springer, Heidelberg (2015)
Faria, D.C., Bagajewicz, M.J.: Novel bound contraction procedure for global optimization of bilinear minlp problems with applications to water management problems. Comput. Chem. Eng. 35(3), 446–455 (2011)
Grossmann, I.E., Trespalacios, F.: Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming. AIChE J. 59(9), 3276–3295 (2013)
Hasan, M., Karimi, I.: Piecewise linear relaxation of bilinear programs using bivariate partitioning. AIChE J. 56(7), 1880–1893 (2010)
Hock, W., Schittkowski, K.: Test examples for nonlinear programming codes. J. Optim. Theory Appl. 30(1), 127–129 (1980)
Jamil, M., Yang, X.S.: A literature survey of benchmark functions for global optimisation problems. Int. J. Math. Model. Numer. Optim. 4(2), 150–194 (2013)
Karuppiah, R., Grossmann, I.E.: Global optimization for the synthesis of integrated water systems in chemical processes. Comput. Chem. Eng. 30(4), 650–673 (2006)
Kolodziej, S.P., Grossmann, I.E., Furman, K.C., Sawaya, N.W.: A discretization-based approach for the optimization of the multiperiod blend scheduling problem. Comput. Chem. Eng. 53, 122–142 (2013)
Liberti, L., Lavor, C., Maculan, N.: A branch-and-prune algorithm for the molecular distance geometry problem. Int. Trans. Oper. Res. 15(1), 1–17 (2008)
McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: part I—convex underestimating problems. Math. Program. 10(1), 147–175 (1976)
Meyer, C.A., Floudas, C.A.: Global optimization of a combinatorially complex generalized pooling problem. AIChE J. 52(3), 1027–1037 (2006)
Mouret, S., Grossmann, I.E., Pestiaux, P.: Tightening the linear relaxation of a mixed integer nonlinear program using constraint programming. In: van Hoeve, W.-J., Hooker, J.N. (eds.) CPAIOR 2009. LNCS, vol. 5547, pp. 208–222. Springer, Heidelberg (2009)
Ryoo, H.S., Sahinidis, N.V.: Global optimization of nonconvex NLPs and minlps with applications in process design. Comput. Chem. Eng. 19(5), 551–566 (1995)
Sahinidis, N.V.: Baron: a general purpose global optimization software package. J. Global Optim. 8(2), 201–205 (1996)
Smith, E.M., Pantelides, C.C.: A symbolic reformulation/spatial B&B algorithm for the global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 23(4), 457–478 (1999)
Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)
Teles, J.P., Castro, P.M., Matos, H.A.: Univariate parameterization for global optimization of mixed-integer polynomial problems. Eur. J. Oper. Res. 229(3), 613–625 (2013)
Wicaksono, D.S., Karimi, I.: Piecewise MILP under-and overestimators for global optimization of bilinear programs. AIChE J. 54(4), 991–1008 (2008)
Acknowledgements
The work was funded by the Center for Nonlinear Studies (CNLS) and was carried out under the auspices of the NNSA of the U.S. DOE at LANL under Contract No. DE-AC52-06NA25396.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Nagarajan, H., Lu, M., Yamangil, E., Bent, R. (2016). Tightening McCormick Relaxations for Nonlinear Programs via Dynamic Multivariate Partitioning. In: Rueher, M. (eds) Principles and Practice of Constraint Programming. CP 2016. Lecture Notes in Computer Science(), vol 9892. Springer, Cham. https://doi.org/10.1007/978-3-319-44953-1_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-44953-1_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44952-4
Online ISBN: 978-3-319-44953-1
eBook Packages: Computer ScienceComputer Science (R0)