Approximate Answer to MP-MILP Problems Using McCormic Release of Modified Components
Subject Areas : StatisticsMaryam Mahmoudi 1 , aghileh heydari 2 , Ali Karimpour 3
1 - Department of Mathematics, Payame Noor University, tehran, Iran.
2 - Department of Mathematics, Payame Noor University, tehran, Iran.
3 - Department of Electrical Engineering, /Faculty of Engineering/ Ferdowsi University of Mashhad/Mashhad/ Iran
Keywords: آزادسازی مک‌کورمیک, برنامه‌ریزی عدد صحیح مختلط (MILP), برنامه‌ریزی چندپارامتری (mp-p),
Abstract :
Multi-parametric programming theory is a valuable tool for decision making under uncertainty and has been an active area of research. Although multi-parametric programming with uncertainty in the objective function coefficients and right-hand side of constraints has been extensively discussed and various methods have been proposed for this, uncertainty in the coefficients matrix (i.e. left-hand side uncertainty) have been less considered. In this work, a new method for solving multi-parametric mixed-integer linear problems (mp-MILP) with uncertainty in constraints is presented. This procedure consists of two steps, which in the first step, the bounds of the bilinear terms are improved by using tightening piecewise McCormick relaxations and secondly, based on these improved bounds and estimating bilinear terms, an approximate model of mp-MILP is obtained. The performance of the presented method is investigated by two examples. To do this, the approximation of the problem has been done in different partitioning factors and computational requirements to solve them have been compared.
[1] Öncü Hazır and Ulusoy, Gündüz. A classification and review of approaches and methods for modeling uncertainty in projects. International Journal of Production Economics, p. 107522, 2019.
[2] Jordehi, A. Rezaee. How to deal with uncertainties in electric power systems? a review. Renewable and Sustainable Energy Reviews, 96:145 – 155, 2018.
[3] طیب نسب، سیده فرخنده، حمیدی، فرهاد، و اله دادی، مهدی. یک روش جدید برای حل مسئله برنامه ریزی خطی دو ترازه تماما بازهای با قیود تساوی پژوهشهای نوین در ریاضی، 4 (14): 51-60، 1397.
[4] رعایت پناه، محمدعلی و آقایی، نازیلا. اندازهگیری کارایی سود کلی استوار با در نظر گرفتن عدم قطعیت در بردارهای قیمت ورودی و خروجی، پژوهشهای نوین در ریاضی، 4 (15): 5-18، 1397.
[5] آقایی، نازیلا. رتبهبندی واحدهای تصمیمگیرنده با استفاده از کارایی متقاطع در حضور خروجیهای نامطلوب و عدم قطعی دادهها پژوهشهای نوین در ریاضی، 3 (11): 19-30، 1396.
[6] Oberdieck, R., Diangelakis, N. A., and Pistikopoulos, E. N. Explicit model predictive control: A connected- graph approach. Automatica, 76:103 – 112, 2017.
[7] Oberdieck, R. and Pistikopoulos, E. N. Explicit hybrid model-predictive control: The exact solution. Automatica, 58:152- 159, 2015.
[8] Sakizlis, V., Kakalis, N. M.P., Dua, V., Perkins, J. D., and Pistikopoulos, E. N. Design of robust model-based controllers via parametric programming. Automatica, 40(2): 189 – 201, 2004.
[9] Pistikopoulos, E. N., Dua, V., Bozinis, N. A., Bemporad, A., and Morari, M. On-line optimization via off-line parametric optimization tools. Computers & Chemical Engineering, 24(2):183 – 188, 2000.
[10] Lu, K., Du, P., Cao, J., Zou, Q., He, T., and Huang, W. A novel traffic signal split approach based on explicit model predictive control. Mathematics and Computers in Simulation, 155:105 – 114, 2019.
[11] Hao, Z., Boel, R., and Li, Z. Model based urban traffic control, part i: Local model and local model predictive controllers. Transportation Research Part C: Emerging Technologies, 97:61-81, 2018.
[12] Hao, Z., Boel, R., and Li, Z. Model based urban traffic control, part ii: Coordinated model predictive controllers. Transportation Research Part C: Emerging Technologies, 97:23 – 44, 2018.
[13] Le, T., Vu, H. L., Nazarathy, Y., Vo, Quoc Bao, and Hoogendoorn, Serge. Linear-quadratic model predictive control for urban traffic networks. Transportation Research Part C: Emerging Technologies, 36:498 - 512, 2013.
[14] Ryu, J., Dua, V., and Pistikopoulos, E. N. Proactive scheduling under uncertainty: a parametric optimization approach. Industrial & Engineering Chemistry Research, 46(24):8044–8049, 2007.
[15] Li, Z. and Ierapetritou, M. Process scheduling under uncertainty: Review and challenges. Computers & Chemical Engineering, 32(4):715 – 727, 2008.
[16] Avraamidou, S. and Pistikopoulos, E. N. A multiparametric mixed-integer bi-level optimization strategy for supply chain planning under demand uncertainty. IFAC-PapersOnLine, 50(1):10178 – 10183, 2017.
[17] Avraamidou, S. and Pistikopoulos, E. N. A multi-parametric optimization approach for bilevel mixed-integer linear and quadratic programming problems. Computers & Chemical Engineering, 125:98 – 113, 2019.
[18] Avraamidou, S. and Pistikopoulos, E. N. Multi-parametric global optimization approach for tri-level mixed-integer linear optimization problems. Journal of Global Optimization, 74(3):443–465, 2019.
[19] Faísca, N. P., Kouramas, K. I., Saraiva, P. M., Rustem, B., and Pistikopoulos, E. N. A multi-parametric programming approach for constrained dynamic programming problems. Optimization Letters, 2:267–280, 2008.
[20] Gal, T. Postoptimal analyses, parametric programming, and related topics: degeneracy, multicriteria decision making, redundancy. 1994.
[21] Crema, A. The multiparametric 0–1-integer linear programming problem: A unified approach. European Journal of Operational Research, 139(3):511- 520, 2002.
[22] Li, Z. and Ierapetritou, G. M. A new methodology for the general multiparametric mixedinteger linear programming (milp) problems. Industrial & Engineering Chemistry Research, 46(15):5141- 5151, 2007.
[23] Avis, D. and Fukuda, K. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete & Computational Geometry, 8(3):295-313, 1992.
[24] Wittmann-Hohlbein, M. and Pistikopoulos, E. N. Approximate solution of mp-milp problems using piecewise affine relaxation of bilinear terms. Computers & Chemical Engineering, 61:136-155, 2014.
[25] Wittmann-Hohlbein, M. and Pistikopoulos, E. N. A two-stage method for the approximate solution of general multiparametric mixed-integer linear programming problems. Industrial & Engineering Chemistry Research, 51(23):8095–8107, 2012.
[26] Khalilpour, R. and Karimi, I.A. Parametric optimization with uncertainty on the left hand side of linear programs. Computers & Chemical Engineering, 60:31 – 40, 2014.
[27] Flavell, R. and Salkin, G. R. An approach to sensitivity analysis. Journal of the Operational Research Society, 26(4): 857-866, 1975.
[28] Searle, H. Hendersonand S. On deriving the inverse of a sum of matrices. SIAM Review, 23(1):53–60, 1981.
[29] Charitopoulos, V. M., Papageorgiou, L. G., and Dua, V. Multi-parametric mixed integer linear programming under global uncertainty. Computers & Chemical Engineering, 116:279 - 295, 2018.
[30] Winkler, Burchberger. Gröbner Bases and Applications. London Mathematical Society Lecture Note Series. Cambridge University Press, 1998.
[31] Castro, P.M. Tightening piecewise mccormick relaxations for bilinear problems. Computers & Chemical Engineering, 72:300-311, 2015.
[32] Gounaris, Ch. E., Misener, R., and Floudas, CH. A. Computational comparison of piecewise-linear relaxations for pooling problems. Industrial & Engineering Chemistry Research, 48 (12):5742–5766, 2009.
[33] McCormick, G. P. Computability of global solutions to factorable nonconvex programs: Part i — convex underestimating problems. Mathematical Programming, 10(1):147-175, 1976.
[34] Dua, V. and Pistikopoulos, E. N. An algorithm for the solution of multiparametric mixed integer linear programming problems. Annals of Operations Research, 99:123–139, 2000.
[35] Borrelli, F. Constrained Optimal Control of Linear and Hybrid Systems, vol. 290. SpringerVerlag Berlin Heidelberg, 2003.
[36] Acevedo, J. and Pistikopoulos, E. N. An algorithm for multiparametric mixed-integer linear programming problems. Operations Research Letters, 24(3):139 – 148, 1999.
[37] Jia, Z. and Ierapetritou, M. Uncertainty analysis on the righthand side for milp problems. AIChE Journal, 52:2486 – 2495, 07 2006.
[38] Oberdieck, Richard, Diangelakis, Nikolaos, Papathanasiou, Maria, Nascu, Ioana, and Pistikopoulos, Efstratios. Pop - parametric optimization toolbox. Industrial & Engineering Chemistry Research, 55, 07 2016.
[39] Herceg, Martin, Kvasnica, Michal, Jones, Colin, and Morari, Manfred. Multi parametric toolbox 3.0. pp. 502–510, 07 2013.