Abstract
In this paper, we present a novel global optimisation approach for the general solution of multi-parametric mixed integer linear programs (mp-MILPs). We describe an optimisation procedure which iterates between a (master) mixed integer nonlinear program and a (slave) multi-parametric program. Moreover, we explain how to overcome the presence of bilinearities, responsible for the non-convexity of the multi-parametric program, in two classes of mp-MILPs, with (i) varying parameters in the objective function and (ii) simultaneous presence of varying parameters in the objective function and the right-hand side of the constraints. Examples are provided to illustrate the solution steps.
Similar content being viewed by others
References
Acevedo J., Pistikopoulos E.N.: A multiparametric programming approach for linear process engineering problems under uncertainty. Ind. Eng. Chem. Res. 36, 717–728 (1997)
Acevedo J., Salgueiro M.: An efficient algorithm for convex multiparametric nonlinear programming problems. Ind. Eng. Chem. Res. 42(23), 5883–5890 (2003)
Adjiman C.S., Androulakis I.P., Floudas C.A.: A global optimization method, αbb, for general twice-differentiable constrained nlps. ii. implementation and computational results. Comput. Chem. Eng. 22(9), 1159–1179 (1998)
Adjiman C.S., Dallwig S., Floudas C.A., Neumaier A.: A global optimization method, αbb, for general twice-differentiable constrained nlps. i. theoretical advances. Comput. Chem. Eng. 22(9), 1137–1158 (1998)
Armacost R.L.: Computational experience in sensitivity analysis for nonlinear programming. Math. Program. 6, 301–326 (1974)
Armacost, R.L.: Sensitivity analysis in parametric nonlinear programming. PhD thesis, School of Engineering and Applied Science, George Washington University, Washington, USA (1976)
Arnold V.I.: Catastrophe Theory. Springer-Verlag, Berlin (1984)
Baotić M., Christophersen F.J., Morari M.: Constrained optimal control of hybrid systems with linear performance index. IEEE Trans. Autom. Control 51(12), 1903–1919 (2006)
Bazaraa M.S., Shetty C.M.: Nonlinear Programming—Theory and Algorithms. Wiley, New York (1979)
Bemporad A., Filippi C.: Suboptimal explicit receding horizon control via approximate multiparametric quadratic programming. J. Optim. Theory Appl. 117(1), 9–38 (2003)
Bemporad A., Morari M., Dua V., Pistikopoulos E.N.: The explicit linear quadratic regulator for constrained systems. Automatica 38, 3–20 (2002)
Bemporad A., Borrelli F., Morari M.: Min–max control of constrained uncertain discrete-time linear systems. IEEE Trans. Autom. Control 48(9), 1600–1606 (2003)
Biegler L.T., Grossman I.E., Westerberg A.W.: Systematic Methods of Chemical Process Design. Prentice Hall, New Jersey (1997)
Borrelli F., Bemporad A., Morari M.: Geometric algorithm for multiparametric linear programming. J. Optim. Theory Appl. 118(3), 515–540 (2003)
Borrelli F., Baotić M., Bemporad A., Morari M.: Dynamic programming for constrained optimal control of discrete-time linear hybrid systems. Automatica 41, 1709–1721 (2005)
Dua, V.: Parametric programming techniques for process engineering problems under uncertainty. PhD thesis. Department of Chemical Engineering and Chemical Technology, Imperial College of Science, Technology and Medicine London, London, UK (2000)
Dua V., Pistikopoulos E.N.: Algorithms for the solution of multiparametric mixed-integer nonlinear optimization problems. Ind. Eng. Chem. Res 38, 3976–3987 (1999)
Dua V., Pistikopoulos E.N.: An algorithm for the solution of multiparametric mixed integer linear programming problems. Ann. Oper. Res. 99, 123–139 (2000)
Dua P., Pistikopoulos E.N.: Modelling and control of drug delivery systems. Comput. Chem. Eng. 29(11–12), 2290–2296 (2005)
Dua V., Bozinis N.A., Pistikopoulos E.N.: A multiparametric programming approach for mixed-integer quadratic engineering problems. Comput. Chem. Eng. 26, 715–733 (2002)
Dua V., Papalexandri K.P., Pistikopoulos E.N.: Global optimization issues in multiparametric continuous and mixed-integer optimization problems. J. Glob. Optim. 30, 59–89 (2004)
Dua P., Doyle F.J., Pistikopoulos E.N.: Model-based blood glucose control for type 1 diabetes via parametric programming. IEEE Trans. Biomed. Eng. 53(8), 1478–1491 (2006)
Faísca, N.P., Saraiva, P.M., Rustem, B., Pistikopoulos, E.N.: A multi-parametric programming approach for multi-level hierarchical and decentralised optimisation problems. Comput. Manag. Sci. (published electronically) (2007)
Faísca N.P., Dua V., Saraiva P.M., Rustem B., Pistikopoulos E.N.: Parametric global optimisation for bilevel programming. J. Glob. Optim. 38(4), 609–623 (2007)
Faísca N.P., Kouramas K.I., Saraiva P.M., Rustem B., Pistikopoulos E.N.: A multi-parametric programming approach for constrained dynamic programming problems. Optim. Lett. 2(2), 267–280 (2008)
Fiacco A.V.: Sensitivity analysis for nonlinear programming using penalty methods. Math. Program. 10, 287–311 (1976)
Fiacco A.V.: Introduction to Sensitivity and Stability Analysis in Nonlinear Programming. Academic Press, New York (1983)
Fiacco A.V., Kyparisis J.: Computable bounds on parametric solutions of convex problems. Math. Program. 40, 213–221 (1988)
Filippi C.: An algorithm for approximate multiparametric linear programming. J. Optim. Theory Appl. 120(1), 73–95 (2004)
Floudas C.A.: Deterministic Global Optimization. Kluwer, Dordrecht (2000)
Gal T.: Rim multiparametric linear programming. Manag. Sci. 21(5), 567–575 (1975)
Gal T., Nedoma J.: Multiparametric linear programming. Math. Program. Stud. 18, 406–422 (1972)
Gass S.I., Saaty T.L.: Parametric objective function (part 2). J. Oper. Res. Soc. Am. 3(4), 395–401 (1954)
Kosmidis, V.S.: Multiparametric analysis of mixed integer linear programming problems. Master’s thesis, Imperial College London, University of London, London, UK (1999)
Kouramas, K.I., Faísca, N.P., Rustem, B., Pistikopoulos, E.N.: Design of robust multi-parametric controllers for constrained multi-stage optimization problems. Automatica (submitted)(2008)
Kyparisis J., Fiacco A.V.: Generalized convexity and concavity of the optimal value function in nonlinear programming. Math. Program. 39, 285–304 (1987)
Li Z., Ierapetritou M.G.: A new methodology for the general mixed-integer linear programming (milp) problems. Ind. Eng. Chem. Res. 46, 5141–5151 (2007)
Li Z., Ierapetritou M.G.: Process scheduling under uncertainty using multiparametric programming. AIChE J 53(12), 3183–3203 (2007)
Lundberg B.N., Poore A.B.: Numerical continuation and singularity detection methods for parametric nonlinear programming. SIAM J. Optim. 3(1), 134–154 (1993)
Mangasarian O.L., Fromovitz S.: The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl. 17, 37–47 (1967)
McCormick, G.P.: Optimality criteria in nonlinear programming. In: SIAM-AMS Proceedings 1975, vol. 9, p. 27 (1976)
Morari M., Barić M.: Rcent developments in the control of constrained hybrid systems. Comput. Chem. Eng. 30(10–12), 1619–1631 (2006)
Pertsinidis, A.: On the parametric optimization of mathematical programs with binary variables and its application in the chemical engineering process synthesis. PhD thesis, Department of Chemical Engineering, Carnegie-Mellon University, Pittsburg, USA (1992)
Pertsinidis A., Grossman I.E., McRae G.J.: Parametric optimization of milp programs and a framework for the parametric optimization of minlps. Comput. Chem. Eng. 22, S205–S212 (1998)
Pistikopoulos E.N., Dua V., Bozinis N.A., Bemporad A., Morari M.: On-line optimization via off-line parametric optimization tools. Comput. Chem. Eng. 24, 183–188 (2000)
Pistikopoulos E.N., Georgiadis M.C., Dua V.: Multi-Parametric Programming: Theory, Algorithms, and Applications, vol. 1. Wiley-VCH, Weinheim (2007)
Pistikopoulos E.N., Georgiadis M.C., Dua V.: Multi-Parametric Model-Based Control: Theory and Applications, vol. 2. Wiley-VCH, Weinheim (2007)
Pistikopoulos, E.N., Faísca, N.P., Georgiadis, M.C.: Advanced optimization techniques in the supply chain management of manufacturing industries. In: PulPaper 2007. Finish Paper Engineers’ Association, Helsinki, Finland (2007)
Poore A.B., Tiahrt C.A.: Bifurcation problems in nonlinear parametric programming. Math. Program. 39, 189–205 (1987)
Ryu J.H., Pistikopoulos E.N.: A novel approach to scheduling of zero-wait batch processes under processing time variations. Comput. Chem. Eng. 31(3), 101–106 (2007)
Ryu J.H., Dua V., Pistikopoulos E.N.: A bilevel programming framework for enterprise-wide process networks under uncertainty. Comput. Chem. Eng. 28, 1121–1129 (2004)
Saaty T.L., Gass S.I.: Parametric objective function (part 1). J. Oper. Res. Soc. Am. 2(3), 316–319 (1954)
Sahinidis N.V.: BARON: User’s Manual Version 4.0. Department of Chemical Engineering, University of Illinois, Urbana-Campaign (2000)
Sakizlis, V., Dua, V., Perkins, J.D., Pistikopoulos E.N.: The explicit control law for hybrid systems via parametric programming. In: Proceedings of the American Control Conference, Anchorage, AK, pp. 674–679 (2002)
Sakizlis V., Perkins J.D., Pistikopoulos E.N.: Parametric controllers in simultaneous process and control design optimization. Ind. Eng. Chem. Res. 42, 4545–4563 (2003)
Sakizlis V., Perkins J.D., Pistikopoulos E.N.: Recent advances in optimization-based simulataneous process and control design. Comput. Chem. Eng. 28, 2069–2086 (2004)
Sakizlis V., Kakalis M.P., Dua V., Perkins J.D., Pistikopoulos E.N.: Design of robust controllers via parametric programming. Automatica 40, 189–201 (2004)
Sakizlis V., Kakalis N.M.P., Dua V., Perkins J.D., Pistikopoulos E.N.: Design of robust model-based controllers via parametric programming. Automatica 40(2), 189–201 (2004)
Sakizlis V., Perkins J.D., Pistikopoulos E.N.: Explicit solutions to optimal control problems for constrained continuous-time linear systems. IEE Proc. Control Theory Appl. 152(4), 443–452 (2005)
Sakizlis, V., Kouramas, K.I., Faisca, N.P., Pistikopoulos, E.N.: Towards the design of parametric model predictive controllers for non-linear constrained systems. In: Assessment and Future Directions of Nonlinear Model Predictive Control. Lecture Notes in Control and Information Sciences, vol. 358. Springer, Berlin (2007)
Smith E.M.B., Pantelides C.C.: A symbolic reformulation: spatial branch-and-bound algorithm for the global optimisation of nonconvex minlps. Comput. Chem. Eng. 23, 457–478 (1999)
Tøndel P., Johansen T.A., Bemporad A.: An algorithm for multi-parameffic quadratic programming and explicit mpc solutions. Automatica 39(3), 489–497 (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Faísca, N.P., Kosmidis, V.D., Rustem, B. et al. Global optimization of multi-parametric MILP problems. J Glob Optim 45, 131–151 (2009). https://doi.org/10.1007/s10898-008-9398-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-008-9398-3