جواب تقریبی مسائل mp-MILP با استفاده از آزادسازی مک کورمیک قطعه ای تظریف شده

محورهای موضوعی : آمار

مریم محمودی ^{1 *} , عقیله حیدری ² , علی کریم پور ³

1 - گروه ریاضی، دانشگاه پیام نور، ص.پ. 19395-4697، تهران، ایران.
2 - گروه ریاضی، دانشگاه پیام نور، ص.پ. 19395-4697، تهران، ایران.
3 - گروه مهندسی برق، دانشگاه فردوسی مشهد، مشهد، ایران.

تاریخ دریافت : 1398/10/30 تاریخ پذیرش : 1399/02/31 تاریخ انتشار : 1400/09/01

کلید واژه: Mixed Integer Linear programming (MILP), McCormick relaxation, multi-parametric programming (mp-p),

چکیده مقاله :

نظریه برنامه‌ریزی چندپارامتریک ابزار ارزشمندی برای تصمیم‌گیری تحت عدم قطعیت می‌باشد و حیطه فعالی از تحقیقات را به خود اختصاص داده است. اگرچه بهینه‌سازی چندپارامتریک با عدم قطعیت در ضرایب تابع هدف و مقادیر سمت راست محدودیت‌ها بسیار مورد توجه واقع شده و روش‌های گوناگونی برای حل آن‌ها تاکنون ارائه شده است، عدم قطعیت در ماتریس ضرایب (به عبارتی سمت چپ) کمتر مورد توجه قرار گرفته است. در این کار یک روش جدید برای حل مسائل چندپارمتریک عدد صحیح مختلط (mp-MILP) با عدم قطعیت در محدودیت‌ها ارائه شده است. این روش شامل دو مرحله است که در مرحله اول با استفاده از آزادسازی مک‌کورمیک تظریف شده کران‌های جملات دوخطی بهبود می‌یابد و در مرحله دوم برپایه این کران‌های بهبود یافته و تخمین جملات دوخطی، مدل تقریبی از mp-MILP بدست آمده است. در انتها کارایی روش تقریبی ارائه شده توسط دو مثال مورد بررسی قرار گرفته است. برای انجام این کار در افزارهای متفاوت تقریب مساله انجام شده و میزان محاسبات لازم برای حل آن‌ها مقایسه گردیده است.

چکیده انگلیسی:

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.