حل مسأله برنامه ریزی دو سطحی خطی با استفاده از الگوریتم ژنتیک
محورهای موضوعی : مدیریت صنعتی
Hashem Omrani
1
(
Department of Industrial Engineering, Urmia University of Technology, Urmia, Iran
)
کلید واژه: Genetic Algorithm, الگوریتم ژنتیک, برنامه ریزی دو سطحی, تئوری تصمیم گیری, Bi-level programming, Decision theory,
چکیده مقاله :
مسأله برنامه ریزی دو سطحی (BLP) یکی از مسائل مهم در تئوری تصمیم گیری می باشد که زیر مجموعه مسائل برنامه ریزی چند سطحی به شمار می رود. این مسأله دارای دو سطح بیرونی و داخلی می باشد که فضای جواب مسأله بیرونی یا سطح اول توسط مسأله داخلی یا سطح دوم معین می شود. با توجه به اینکه BLP یک مسأله NP-hard می باشد، حل آن توسط روشهای سنتی به راحتی امکان پذیر نیست. در این مقاله ابتدا مسأله BLP و کاربردهای آن بررسی و سپس برای یافتن نقطه بهینه مسأله از روش شمارش نقاط رأسی استفاده می شود. در این مقاله برای جستجوی فضای اطراف نقاط رأسی و یافتن جواب بهینه از الگوریتم ژنتیک استفاده می گردد. همچنین با استفاده از یک پارامتر کنترلی، شعاع فضایی را که باید جستجو شود کنترل می شود تا از افزایش زمان حل مسأله اجتناب گردد. نتایج خروجی نشان می دهد که جواب بدست آمده از الگوریتم ژنتیک پیشنهادی در مقایسه با مطالعات قبلی قابل قبول می باشد.
Bi-level programming (BLP), is one of the important problems in the decision-making theory, is multilevel programming with two levels. It involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. Since the BLP problem is NP-hard, it is impossible solving it by traditional methods. This paper reviews the BLP problem and applies enumeration techniques for finding extreme points. It uses the genetic algorithm for the searching region and finding the optimum solution. Also, the search region is controlled by a parameter in order to avoid the increased time. The results show that the solutions are acceptable in comparison with previous studies.
Anandalingam, G., and White, D.J. (1990). A solution for the linear static Stackelberg problem using penalty functions. IEEE Transactions on Automatic Control, 35: 1170–1173.
2. Bard, J.F. (1990). Some properties of the bilevel linear programming. Journal of Optimization Theory and Applications, 68: 371-378.
3. Bard, J.F., Plummer, J., and Sourie, J.C. (2000). A bilevel programming approach to determining tax credits for biofuel production. European Journal of Operational Research, 120(1): 30-46.
4. Ben-Ayed, O., and Blair, C.E. (1990). Computational difficulties of bilevel linear programming. Operations Research, 38: 556-560.
5. Ben-ayed, O., Boyce, D.E., and Blair, C.E. (1988). A general bilevel linear programming formulation of the network design problem. Transportation Research Part B: Methodological, 22: 311-318.
6. Ben-ayed, O., Boyce, D.E., Blair, C.E. (1988). Solving a real world highway design problem using bilevel linear programming. Faculty Working Paper No. 1463, College of Commerce and Business Administration, University of Illinois, Urbana-Champaign. 1988.
7. Bialas, W.F., and Karwan, M.H. (1982). On two-level optimization. IEEE Transactions on Automatic Control, 27: 211-214.
8. Bialas, W.F., and Karwan, M.H. (1983). Two-level linear programming. Managment Sciences, 30: 1004-1020.
9. Bracken, J., and McGill, J.T. (1973). Mathematical programs with optimization problems in the constraints. Operations Research, 21: 37-44.
10. Bracken, J., and McGill, J.T. (1974). A method for solving mathematical programs with nonlinear programs in the constraints. Operations Research, 22: 1097-1101.
11. Bracken, J., and McGill, J.T. (1974). Defense application of mathematical programs with optimization problems in the constraints. Operations Research, 22: 1086-1096.
12. Bracken, J., Falk, J. E., and Miercort, F.A. (1977). A strategic weapons exchange allocation model. Operations Research, 25: 968-976.
13. Brad, J.F. (1983). An efficient point algorithm for a linear two-stage optimization problem. Operations Research, 31: 670-684.
14. Brad, J.F. (1985). Geometric and algorithmic developments for a hierarchical planning problem. European Journal of Operational Research, 19: 372-383.
15. Brad, J.F., and Falk, J.E. (1982). An explicit solution to the multi-level programming problem. Computers & Operations Research, 9: 77-100.
16. Brad, J.F., and Moore, J.T. (1988). A branch and bound algorithm for the bilevel programming problem. Presented at the TIMSIORSA Joint National Meeting, Washington, DC, April.
17. Calvete, H.I., Gale´, C., and Mateo, P.M. (2008). A new approach for solving linear bilevel problems using genetic algorithms. European Journal of Operational Research, 188 (1), 14-28.
18. Candler, W., and McCarl, B. (1981). The potential role of multilevel programming in agricultural economics. American Journal of Agricultural. Economics, 63: 521-531.
19. Candler, W., and Norton, R.D. (1977). Multi-level programming. World Bank Development Research Center Discussion Paper No. 20, Washington, DC.
20. Candler, W., and Townsley, R. (1982). A linear two-level programming problem. Computers & Operations Research, 9: 59-76.
21. Cassidy, R.G., Kirby, M.J.L., anRaike, W.M. (1971). Efficient distribution of resources through three levels of government. Managment Sciences, 17: 462-473.
22. Clegg, J., Smith, M., Xiang, Y., and Yarrow, R. (2001). Bilevel programming applied to optimising urban transportation Transportation Research Part B: Methodological, 35(1): 41-70.
23. Desilva, A.H. (1978). Sensitivity formulas for nonlinear factorable programming and their application to the solution of an implicitly defined optimization model of US crude oil production. DSc. Dissertation, George Washington University, Washington, DC.
24. Falk, J.E. (1973). A linear max-min problem. Mathematical Programming, 5: 169-188.
25. Fortuny-amat, J., and McCarl, B. 1981. A representation and economic interpretation of a two-level programming problem. Journal of Operation Research Society, 32: 783-792.
26. Friedman, J. (1983). Oligopoly Theory. Cambridge University Press, Cambridge.
27. Gendreau, M., Marcotte, P., and Savard, G. (1996). A hybridTabu-Ascent algorithm for the linear bilevel programming problem. Journal of Global Optimization, 8: 217–33.
28. Gupta, A., and Maranas, C.D. (2002). Managing demand uncertainty in supply chain planning. Computers & Chemical Engineering 27: 1219-1227.
29. Hansen, P., Jaumard, B., and Savard, G. (1992). New branch-and-bound rules for linear bilevel programming.SIAM Journal on Science and Statistical Computing, 13(5): 1194-1217.
30. Hejazi, S.R., Memariani, A. Jahanshahloo, G., and Sepehri, M.M. (2002). Linear bilevel programming solution by genetic algorithm. Computers & Operations Research, 29: 1913–1925
31. Ji, X., and Shao, Z. (2006). Model and algorithm for bilevel newsboy problem with fuzzy demands and discounts Applied Mathematics and Computation, 172(1): 163-174.
32. Karlof, J., K., and Wang, W. (1996). Bilevel programming applied to the flow shop scheduling problem. Computers & Operations Research, 23(5): 443-451.
33. Kyland, F. (1975). Hierarchical decomposition in linear economic model. Management Sciences, 21: 1029-1039.
34. Lana, K.M., Wena, U.P., Shihb, H-S., and Leec, E.S. (2007). A hybrid neural network approach to bilevel programming problems. Applied Mathematics Letters, 20: 880–884.
35. Lukač, Z., Šorić, K., and Rosenzweig, V.V. (2008). Production planning problem with sequence dependent setups as a bilevel programming problem European Journal of OperationalResearch, 187(3): 1504-1512.
36. Marcotte, P. (1986). Network design problem with congestion effects: a case of bilevel programming. Mathematical Programming, 34: 142-162.
37. Marcotte, P., Savard, G., and Semet, F. 2004. A bilevel programming approach to the travelling salesman problem Operations Research Letters, 32(3): 240-248.
38. Miljkovic, D. (2002). Privatizing state farms in Yugoslavia. Journal of Policy Modeling, 24(2): 169-179.
39. Parraga, F.A. (1981). Hierarchical programming and applications to economic policy. PhD. Dissertation, Department of Systems and Industrial Engineering, University of Arizona, Tucson.
40. Sahin, KH, and Cirit, AR. (1998). A dual temperature simulated annealing approach for solving bilevel programming problems. Computers and Chemical engineering, 23: 11–25.
41. Sakava, M., Nishizaki, I., and Uemura, Y. (1997). Interactive fuzzy programming for multilevel linear programming problem. Computers & Mathematics with Applications, 36(2), 71–86.
42. Unlu, G. (1987). A linear bilevel programming algorithm based on bicriteria programming. Computers & Operations Research, 14: 173-1 79.
43. Wang, G., Wan, Z., and Wang, X. (2003). Solving Method for a Class of Bi-level Linear Programming based on Genetic Algorithms. In www. Optimization Online.org/DB-HTML/2003/03/617.html.
44. Wen, U. P. (1981). Mathematical methods for multilevel linear programming. PhD. Dissertation, Depaltment of Industrial Engineering, State University of New York at Buffalo, New York.
45. Wen, U. P., and Hsu, S. T. (1989). A note on a linear bilevel programming algorithm based on bicriteria programming. Computers & Operations Research, 16: 79-83.
46. Wen, U. P., and Hsu, S. T. (1991). Linear bi-level programming problems- a review. Journal of Operation Research Society, 42(2): 125-133.
47. Wen, U. P., and Jiang, C.F. (1988). A multilevel programming approach in commission rate setting problem. Journal of the Chinese Institute of Industrial Engineers, 5: 43-49.
48. Wen, U. P., Hsu, S. T. (1991). Efficient solutions for the linear bi-level programming problem. European Journal of Operational Research, 62: 354-362.
49. Yang, H., and Yagar, S. (1994). Traffic assignment and traffic control in general freeway-arterial corridor systems. Transportation Research Part B: Methodological, 28(6): 463-486.
50. Yang, H., and Yagar, S. (1995). Traffic assignment and signal control in saturated road networks. Transportation Research Part A: Policy and Practice, 29(2): 125-139.
_||_1. Anandalingam, G., and White, D.J. (1990). A solution for the linear static Stackelberg problem using penalty functions. IEEE Transactions on Automatic Control, 35: 1170–1173.
2. Bard, J.F. (1990). Some properties of the bilevel linear programming. Journal of Optimization Theory and Applications, 68: 371-378.
3. Bard, J.F., Plummer, J., and Sourie, J.C. (2000). A bilevel programming approach to determining tax credits for biofuel production. European Journal of Operational Research, 120(1): 30-46.
4. Ben-Ayed, O., and Blair, C.E. (1990). Computational difficulties of bilevel linear programming. Operations Research, 38: 556-560.
5. Ben-ayed, O., Boyce, D.E., and Blair, C.E. (1988). A general bilevel linear programming formulation of the network design problem. Transportation Research Part B: Methodological, 22: 311-318.
6. Ben-ayed, O., Boyce, D.E., Blair, C.E. (1988). Solving a real world highway design problem using bilevel linear programming. Faculty Working Paper No. 1463, College of Commerce and Business Administration, University of Illinois, Urbana-Champaign. 1988.
7. Bialas, W.F., and Karwan, M.H. (1982). On two-level optimization. IEEE Transactions on Automatic Control, 27: 211-214.
8. Bialas, W.F., and Karwan, M.H. (1983). Two-level linear programming. Managment Sciences, 30: 1004-1020.
9. Bracken, J., and McGill, J.T. (1973). Mathematical programs with optimization problems in the constraints. Operations Research, 21: 37-44.
10. Bracken, J., and McGill, J.T. (1974). A method for solving mathematical programs with nonlinear programs in the constraints. Operations Research, 22: 1097-1101.
11. Bracken, J., and McGill, J.T. (1974). Defense application of mathematical programs with optimization problems in the constraints. Operations Research, 22: 1086-1096.
12. Bracken, J., Falk, J. E., and Miercort, F.A. (1977). A strategic weapons exchange allocation model. Operations Research, 25: 968-976.
13. Brad, J.F. (1983). An efficient point algorithm for a linear two-stage optimization problem. Operations Research, 31: 670-684.
14. Brad, J.F. (1985). Geometric and algorithmic developments for a hierarchical planning problem. European Journal of Operational Research, 19: 372-383.
15. Brad, J.F., and Falk, J.E. (1982). An explicit solution to the multi-level programming problem. Computers & Operations Research, 9: 77-100.
16. Brad, J.F., and Moore, J.T. (1988). A branch and bound algorithm for the bilevel programming problem. Presented at the TIMSIORSA Joint National Meeting, Washington, DC, April.
17. Calvete, H.I., Gale´, C., and Mateo, P.M. (2008). A new approach for solving linear bilevel problems using genetic algorithms. European Journal of Operational Research, 188 (1), 14-28.
18. Candler, W., and McCarl, B. (1981). The potential role of multilevel programming in agricultural economics. American Journal of Agricultural. Economics, 63: 521-531.
19. Candler, W., and Norton, R.D. (1977). Multi-level programming. World Bank Development Research Center Discussion Paper No. 20, Washington, DC.
20. Candler, W., and Townsley, R. (1982). A linear two-level programming problem. Computers & Operations Research, 9: 59-76.
21. Cassidy, R.G., Kirby, M.J.L., anRaike, W.M. (1971). Efficient distribution of resources through three levels of government. Managment Sciences, 17: 462-473.
22. Clegg, J., Smith, M., Xiang, Y., and Yarrow, R. (2001). Bilevel programming applied to optimising urban transportation Transportation Research Part B: Methodological, 35(1): 41-70.
23. Desilva, A.H. (1978). Sensitivity formulas for nonlinear factorable programming and their application to the solution of an implicitly defined optimization model of US crude oil production. DSc. Dissertation, George Washington University, Washington, DC.
24. Falk, J.E. (1973). A linear max-min problem. Mathematical Programming, 5: 169-188.
25. Fortuny-amat, J., and McCarl, B. 1981. A representation and economic interpretation of a two-level programming problem. Journal of Operation Research Society, 32: 783-792.
26. Friedman, J. (1983). Oligopoly Theory. Cambridge University Press, Cambridge.
27. Gendreau, M., Marcotte, P., and Savard, G. (1996). A hybridTabu-Ascent algorithm for the linear bilevel programming problem. Journal of Global Optimization, 8: 217–33.
28. Gupta, A., and Maranas, C.D. (2002). Managing demand uncertainty in supply chain planning. Computers & Chemical Engineering 27: 1219-1227.
29. Hansen, P., Jaumard, B., and Savard, G. (1992). New branch-and-bound rules for linear bilevel programming.SIAM Journal on Science and Statistical Computing, 13(5): 1194-1217.
30. Hejazi, S.R., Memariani, A. Jahanshahloo, G., and Sepehri, M.M. (2002). Linear bilevel programming solution by genetic algorithm. Computers & Operations Research, 29: 1913–1925
31. Ji, X., and Shao, Z. (2006). Model and algorithm for bilevel newsboy problem with fuzzy demands and discounts Applied Mathematics and Computation, 172(1): 163-174.
32. Karlof, J., K., and Wang, W. (1996). Bilevel programming applied to the flow shop scheduling problem. Computers & Operations Research, 23(5): 443-451.
33. Kyland, F. (1975). Hierarchical decomposition in linear economic model. Management Sciences, 21: 1029-1039.
34. Lana, K.M., Wena, U.P., Shihb, H-S., and Leec, E.S. (2007). A hybrid neural network approach to bilevel programming problems. Applied Mathematics Letters, 20: 880–884.
35. Lukač, Z., Šorić, K., and Rosenzweig, V.V. (2008). Production planning problem with sequence dependent setups as a bilevel programming problem European Journal of OperationalResearch, 187(3): 1504-1512.
36. Marcotte, P. (1986). Network design problem with congestion effects: a case of bilevel programming. Mathematical Programming, 34: 142-162.
37. Marcotte, P., Savard, G., and Semet, F. 2004. A bilevel programming approach to the travelling salesman problem Operations Research Letters, 32(3): 240-248.
38. Miljkovic, D. (2002). Privatizing state farms in Yugoslavia. Journal of Policy Modeling, 24(2): 169-179.
39. Parraga, F.A. (1981). Hierarchical programming and applications to economic policy. PhD. Dissertation, Department of Systems and Industrial Engineering, University of Arizona, Tucson.
40. Sahin, KH, and Cirit, AR. (1998). A dual temperature simulated annealing approach for solving bilevel programming problems. Computers and Chemical engineering, 23: 11–25.
41. Sakava, M., Nishizaki, I., and Uemura, Y. (1997). Interactive fuzzy programming for multilevel linear programming problem. Computers & Mathematics with Applications, 36(2), 71–86.
42. Unlu, G. (1987). A linear bilevel programming algorithm based on bicriteria programming. Computers & Operations Research, 14: 173-1 79.
43. Wang, G., Wan, Z., and Wang, X. (2003). Solving Method for a Class of Bi-level Linear Programming based on Genetic Algorithms. In www. Optimization Online.org/DB-HTML/2003/03/617.html.
44. Wen, U. P. (1981). Mathematical methods for multilevel linear programming. PhD. Dissertation, Depaltment of Industrial Engineering, State University of New York at Buffalo, New York.
45. Wen, U. P., and Hsu, S. T. (1989). A note on a linear bilevel programming algorithm based on bicriteria programming. Computers & Operations Research, 16: 79-83.
46. Wen, U. P., and Hsu, S. T. (1991). Linear bi-level programming problems- a review. Journal of Operation Research Society, 42(2): 125-133.
47. Wen, U. P., and Jiang, C.F. (1988). A multilevel programming approach in commission rate setting problem. Journal of the Chinese Institute of Industrial Engineers, 5: 43-49.
48. Wen, U. P., Hsu, S. T. (1991). Efficient solutions for the linear bi-level programming problem. European Journal of Operational Research, 62: 354-362.
49. Yang, H., and Yagar, S. (1994). Traffic assignment and traffic control in general freeway-arterial corridor systems. Transportation Research Part B: Methodological, 28(6): 463-486.
50. Yang, H., and Yagar, S. (1995). Traffic assignment and signal control in saturated road networks. Transportation Research Part A: Policy and Practice, 29(2): 125-139.
