ارائه یک الگوریتم محورگیری برای برنامه‌ریزی خطی با قیدهای مکمل خطی

نویسندگان
خاطره قربانی مقدم 1
رضا قنبری 2
جواد محمدنیا 2
1 موسسه تحقیقات ریاضی دکتر مصاحب، دانشگاه خوازمی
2 دانشکده علوم ریاضی، دانشگاه فردوسی مشهد
چکیده
مساله‌های برنامه‌ریزی خطی با قیدهای مکمل خطی[1] ‎‎‎‎(LPCC) ‎ جز مساله‌های پرکاربرد در رشته تحقیق در عملیات هستند و حل آن‌ها به‌دلیل ماهیت غیرخطی و پیچیده قیدهای مکملی، در رده مسائل NP-hard قرار می‌گیرد. در این مقاله، یک حالت خاص از LPCC مورد بررسی قرار گرفته است که در آن قید مکملی از نوع x p x m =0 ظاهر می‌شود. این نوع قید در بسیاری از مسائل کاربردی بهینه‌سازی، به‌ویژه در مدل‌هایی که شامل عباراتی نظیر قدرمطلق هستند، دیده می‌شود. نوآوری اصلی این پژوهش در ارائه یک الگوریتم شاخه و کران اختصاصی برای حل این نوع خاص از LPCC است، بدون نیاز به استفاده از روش‌های مرسوم خطی‌سازی مانند معرفی متغیرهای دودویی و قیدهای M-بزرگ[2] ، که معمولاً موجب افزایش بعد مدل، ضعیف شدن کران پایین و کاهش دقت حل در مسائل با قید مکملی می‌شوند. مزیت روش پیشنهادی در بهره‌گیری مستقیم از ساختار حالت خاص قید مکملی است که باعث کاهش حجم محاسبات، حفظ فرم خطی اصلی، و عملکرد بهتر در مسائل با ابعاد کوچک و متوسط نسبت به روش‌های کلاسیک مانند خطی‌سازی و الگوریتم‌های عمومی شاخه و کران می‌شود. الگوریتم پیشنهادی به‌صورت کامل توسعه داده شده و عملکرد آن از طریق حل مثال‌های عددی و مقایسه با روش‌های مرسوم موجود مورد ارزیابی قرار گرفته است. نتایج نشان می‌دهد که رویکرد پیشنهادی از نظر دقت و کارایی نسبت به روش‌های رایج برتری دارد.


[1] Linear Programming ‎with ‎Linear‎ Complementarity Constraints

[2] Big-M
کلیدواژه‌ها
برنامه‌ریزی خطی
قیدهای مکمل خطی
برنامه‌ریزی صفر و یک
الگوریتم شاخه و کران

عنوان مقاله English

A pivoting algorithm for linear programming with linear complementarity constraints

نویسندگان English

Khatere Ghorbani-Moghadam 1
Reza Ghanbari 2
Javad Mohammadnia 2
1 Mosaheb Institute of Mathematics, Kharazmi University, Tehran, Iran
2 Ferdowsi University of Mashhad
چکیده English

Linear programming problems with complementary linear constraints (LPCC) are widely studied in operations research and are known to be NP-hard. This paper explores a specific case of LPCC where the product of two variables must be zero, i.e., xp xm=0. This scenario frequently arises in optimization problems, particularly those involving absolute values that cannot be expressed as linear or integer programming problems. To tackle this, we will present a branch-and-bound algorithm, and we will implement the algorithm on numerical examples and compare its performance with existing methods.

کلیدواژه‌ها English

Linear Programming Problems
Linear‎ Complementarity Constraints
Zero-one constraint
Branch and Bound Algorithm
1. C. Chen, H. Yang, X. Li L. Chen and M. Shi, Optimization of solar and heat pump complementary powered desiccant air conditioning system, Journal of Building Engineering, 87 (2024), https://doi.org/10.1016/j.jobe.2024.109084.

2. H. Fang, S. Leyffer, and T. Munson. A pivoting algorithm for linear programming with linear complementary constraint, Optimization Methods Software, 27 (2012) 89-114.

3. R. Fletcher, S. Leyffer, D. Ralph and S. Scholtes, Local convergence of SQP methods for mathematical programs with equilibrium constraints, SIAM Journal of Optimization, 17 (2006) 259-289.

4. Z. Guo, J. Wang, F. Dong and H. Xu, Multi-objective optimization of multi-energy complementary system based on cascade utilization of heat storage, Energy Conversion and Management, 299 (2024), https://doi.org/10.1016/j.enconman.2023.117864.

5. J. Hu, J. E. Mitchelly, J. S. Pangz and B. Yu. On Linear programs with Linear Complementary Constraints, Journal of Global Optimization, 53 (2012) 29-51.

6. J. Hu, J. E. Mitchell, J. S. Pang, K. P. Bennett, and G. Kunapuli, On the global solution of linear programs with linear complementary constraints, SIAM Journal on Optimization, 19 (2008) 445-471.

7. T. Ibaraki, Complementary programming, Operations Research, 19 (1971) 1523-1529.

8. Z. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, U. K. 1996.

9. H. Scheel and S. Scholtes, Mathematical program with complementarity constraints: Stationarity, optimality and sensitivity, Mathematics of Operations Research, 25 (2000) 1-22.

10. S. Leyffer, G. Lopez-Calva and J. Nocedal, Interior methods for mathematical programs with complementarity constraints, SIAM Journal on Optimization, 17 (2006) 52-77.

11. S. Leyffer, T. Munson, A globally convergent filter method for MPECs, Mathematics and Computer Science Division, 2007.

12. S. Leyffer, Mathematical programs with complementarity, SIAG/OPT Views and News, 14 (2003) 15-18.

13. J. Hu, J. E. Mitchell, J. S. Pang, K. P. Bennet and G. Kunapuli, On the Global solution of linear programs with linear complementarity constraints, SIAM Journal on Optimization, 19 (2008) 445-471.

14. J. F. Bard and J. T. Moore, A branch and bound algorithm for the bi-level programming problem, SIAM Journal on Scientific Computing (1990) 281-292.

15. H. Onal, A Modified simplex approach for solving bi-level linear programming problems, European Journal of Operational Reseach, 67 (1993) 126-133.

16. J. Hu, J. E. Mitchelly, J. S. Pangz and B. Yu, On Linear Programs with Linear Complementarity Constraints, Journal of Global Optimization, 53 (2012) 29-51.