جواب تقریبی مسائل mp-MILP با استفاده از آزادسازی مک کورمیک قطعه ای تظریف شده
الموضوعات :مریم محمودی 1 , عقیله حیدری 2 , علی کریم پور 3
1 - گروه ریاضی، دانشگاه پیام نور، ص.پ. 19395-4697، تهران، ایران.
2 - گروه ریاضی، دانشگاه پیام نور، ص.پ. 19395-4697، تهران، ایران.
3 - گروه مهندسی برق، دانشگاه فردوسی مشهد، مشهد، ایران.
الکلمات المفتاحية: Mixed Integer Linear programming (MILP), McCormick relaxation, multi-parametric programming (mp-p),
ملخص المقالة :
نظریه برنامه‌ریزی چندپارامتریک ابزار ارزشمندی برای تصمیم‌گیری تحت عدم قطعیت می‌باشد و حیطه فعالی از تحقیقات را به خود اختصاص داده است. اگرچه بهینه‌سازی چندپارامتریک با عدم قطعیت در ضرایب تابع هدف و مقادیر سمت راست محدودیت‌ها بسیار مورد توجه واقع شده و روش‌های گوناگونی برای حل آن‌ها تاکنون ارائه شده است، عدم قطعیت در ماتریس ضرایب (به عبارتی سمت چپ) کمتر مورد توجه قرار گرفته است. در این کار یک روش جدید برای حل مسائل چندپارمتریک عدد صحیح مختلط (mp-MILP) با عدم قطعیت در محدودیت‌ها ارائه شده است. این روش شامل دو مرحله است که در مرحله اول با استفاده از آزادسازی مک‌کورمیک تظریف شده کران‌های جملات دوخطی بهبود می‌یابد و در مرحله دوم برپایه این کران‌های بهبود یافته و تخمین جملات دوخطی، مدل تقریبی از mp-MILP بدست آمده است. در انتها کارایی روش تقریبی ارائه شده توسط دو مثال مورد بررسی قرار گرفته است. برای انجام این کار در افزارهای متفاوت تقریب مساله انجام شده و میزان محاسبات لازم برای حل آن‌ها مقایسه گردیده است.
[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.
