Benders decomposition algorithm for robust aggregate production planning considering pricing decisions in competitive environment: A case study

Document Type : Article


Department of Industrial Engineering, Iran University of Science and Technology, University Ave., Narmak, Tehran, P.O. Box 1684613114, Iran


In operations research, bi-level programming is a mathematical modeling which has another optimization problem as a constraint. In the present research, regarding the current intense competition among large manufacturing companies for achieving a greater market share, a bi-level robust optimization model is developed as a leader-follower problem using Stackelberg game in the field of aggregate production planning (APP). The leader company with higher influence intends to produce new products, which can replace the existing products. The follower companies, as rivals, are also seeking more sales, but they do not have the intention and ability to produce such new products. The price of the new products is determined by the presented elasticity relations between the uncertain demand and price. After linearization, using the KKT conditions, the bi-level robust model is transformed into an ordinary uni-level model. Due to the NP-hard nature of the problem, Benders decomposition algorithm (BDA) is proposed for overcoming the computational complexities in large scale. Finally, using the real data of Sarvestan Sepahan Co as a leader company, the validity of the developed model as well as efficiency and convergence of the BDA are investigated. The computational results clearly show the efficiency and effectiveness of the proposed BDA.


Main Subjects

1. Xiao, T. and Yang, D. "Price and service competition of supply chains with risk-averse retailers under demand uncertainty", Int. J. Prod. Econ., 114(1), pp. 187-200 (2008).
2. Rezapour, S., Farahani, R.Z., Ghodsipour, S.H., et al. "Strategic design of competing supply chain networks with foresight", Adv. Eng. Softw., 42(4), pp. 130-141 (2011).
3. Zhang, D. "A network economic model for supply chain versus supply chain competition", Omega, 34(3), pp. 283-295 (2006).
4. Boyaci, T. and Gallego, G. "Supply chain coordination in a market with customer service competition", Prod. Oper. Manag., 13(1), pp. 3-22 (2004).
5. Anderson, E.J. and Bao, Y. "Price competition with integrated and decentralized supply chains", Eur. J. Oper. Res., 200(1), pp. 227-234 (2010).
6. Fallah, H., Eskandari, H., and Pishvaee, M.S. "Competitive closed-loop supply chain network design under uncertainty" , J. Manuf. Syst., 37, pp. 649-661 (2015).
7. Makui, A., Heydari, M., Aazami, A., et al. "Accelerating benders decomposition approach for robust aggregate production planning of products with a very limited expiration date", Comput. Ind. Eng., 100, pp. 34-51 (2016).
8. Nam, S. and Logendran, R. "Aggregate production planning-a survey of models and methodologies", Eur. J. Oper. Res., 61(3), pp. 255-272 (1992).
9. Saharidis, G.K. and Ierapetritou, M.G. "Resolution method for mixed integer bi-level linear problems based on decomposition technique", J. Glob. Optim., 44(1), pp. 29-51 (2009).
10. Mulvey, J.M., Vanderbei, R.J., and Zenios, S.A. "Robust optimization of large-scale systems", Oper. Res., 43(2), pp. 264-281 (1995).
11. Bernstein, F. and Federgruen, A. "A general equilibrium model for industries with price and service competition", Oper. Res., 52(6), pp. 868-886 (2004).
12. Zhang, L. and Rushton, G. "Optimizing the size and locations of facilities in competitive multi-site service systems", Comput. Oper. Res., 35(2), pp. 327-338 (2008).
13. Bracken, J. and McGill, J.T. "Mathematical programs with optimization problems in the constraints", Oper. Res., 21(1), pp. 37-44 (1973).
14. Candler, W. and Norton, R., Multi-Level Programming and Development Policy, The World Bank (1977).
15. Stackelberg, H.V., The Theory of The Market Economy, Oxford University Press (1952).
16. Vicente, L.N. and Calamai, P.H. "Bilevel and multilevel programming: a bibliography review", Journal of Global Optimization, 5(3). pp. 291-306 (1994).
17. Candler, W., Fortuny-Amat, J., and McCarl, B. "The potential role of multilevel programming in agricultural economics", Am. J. Agric. Econ., 63(3), pp. 521- 531 (1981).
18. Fortuny-Amat, J. and McCarl, B. "A representation and economic interpretation of a two-level programming problem", J. Oper. Res. Soc., 32(9), pp. 783-792 (1981).
19. Shimizu, K. and Aiyoshi, E. "A new computational method for stackelberg and min-max problems by use of a penalty method", IEEE Transactions on Automatic Control, 26(2). pp. 460-466 (1981).
20. Bard, J.F. and Falk, J.E. "An explicit solution to the multi-level programming problem", Comput. Oper. Res., 9(1), pp. 77-100 (1982).
21. Colson, B., Marcotte, P., and Savard, G. "Bilevel programming: a survey", 4OR, 3(2). pp. 87-107 (2005).
22. Colson, B., Marcotte, P., and Savard, G. "An overview of bilevel optimization", Ann. Oper. Res., 153(1), pp. 235-256 (2007).
23. Bard, J.F., Practical Bilevel Optimization: Algorithms and Applications, Springer Science & Business Media (1998).
24. Farahani, R.Z., Rezapour, S., Drezner, T., et al. "Competitive supply chain network design: an overview of classifications, models, solution techniques and applications", Omega, 45, pp. 92-118 (2014).
25. Ben-Ayed, O., Boyce, D.E., and Blair, C.E. "A general bilevel linear programming formulation of the network design problem", Transp. Res. Part B Methodol., 22(4), pp. 311-318 (1988).
26. Bard, J.F. and Moore, J.T. "A branch and bound algorithm for the bilevel programming problem", SIAM J. Sci. Stat. Comput., 11(2), pp. 281-292 (1990).
27. Bard, J.F. and Moore, J.T. "An algorithm for the discrete bilevel programming problem", Nav. Res. Logist., 39(3), pp. 419-435 (1992).
28. Edmunds, T.A. and Bard, J.F. "An algorithm for the mixed-integer nonlinear bilevel programming problem", Ann. Oper. Res., 34(1), pp. 149-162 (1992).
29. Yang, H. "Heuristic algorithms for the bilevel origindestination matrix estimation problem", Transp. Res. Part B, 29(4), pp. 231-242 (1995).
30. Maher, M.J., Zhang, X., and Vliet, D.V. "A bilevel programming approach for trip matrix estimation and traffic control problems with stochastic user equilibrium link  flows", Transp. Res. Part B Methodol., 35(1), pp. 23-40 (2001).
31. Burgard, A.P., Pharkya, P., and Maranas, C.D. "OptKnock: a bilevel programming framework for identifying gene knockout strategies for microbial strain optimization", Biotechnol. Bioeng., 84(6), pp. 647-657 (2003).
32. Gao, Z., Wu, J., and Sun, H. "Solution algorithm for the bi-level discrete network design problem", Transp. Res. Part B Methodol., 39(6), pp. 479-495 (2005).
33. Shi, C., Lu, J., Zhang, G., and Zhou, H. "An extended branch and bound algorithm for linear bilevel programming", Appl. Math. Comput., 180(2), pp. 529- 537 (2006).
34. Sun, H., Gao, Z., and Wu, J. "A bi-level programming model and solution algorithm for the location of logistics distribution centers", Appl. Math. Model., 32(4), pp. 610-616 (2008).
35. Zhang, T., Zhao, Q., and Wu, W. "Bi-level programming model of container port game in the container transport supernetwork", J. Appl. Math. Comput., 31(1-2), pp. 13-32 (2009).
36. Gelareh, S., Nickel, S., and Pisinger, D. "Liner shipping hub network design in a competitive environment", Transp. Res. Part E Logist. Transp. Rev., 46(6), pp. 991-1004 (2010).
37. Kucukaydin, H., Aras, N., and Kuban Altinel, I. "Competitive facility location problem with attractiveness adjustment of the follower: a bilevel programming model and its solution", Eur. J. Oper. Res., 208(3), pp. 206-220 (2011).
38. Naimi Sadigh, A., Mozafari, M., and Karimi, B. "Manufacturer-retailer supply chain coordination: a bi-level programming approach", Adv. Eng. Softw., 45(1), pp. 144-152 (2012).
39. Kristianto, Y., Helo, P., and Jiao, R.J. "Mass customization design of engineer-to-order products using benders' decomposition and bi-level stochastic programming", J. Intell. Manuf., 24(5), pp. 961-975 (2013).
40. Rezapour, S. and Zanjirani Farahani, R. "Supply chain network design under oligopolistic price and service level competition with foresight", Comput. Ind. Eng., 72, pp. 129-142 (2014).
41. Rezapour, S., Farahani, R.Z., Dullaert, W., et al. "Designing a new supply chain for competition against an existing supply chain", Transp. Res. Part E Logist. Transp. Rev., 67, pp. 124-140 (2014).
42. Rezapour, S., Farahani, R.Z., Fahimnia, B., et al. "Competitive closed-loop supply chain network design with price-dependent demands", J. Clean. Prod., 93, pp. 251-272 (2015).
43. Rashidi, E., Parsafard, M., Medal, H., et al. "Optimal traffic calming: a mixed-integer bi-level programming model for locating sidewalks and crosswalks in a multimodal transportation network to maximize pedestrians' safety and network usability", Transp. Res. Part E Logist. Transp. Rev., 91, pp. 33-50 (2016).
44. Han, J., Zhang, G., Hu, Y., et al. "A solution to  i/trilevel programming problems using particle swarm optimization", Inf. Sci., 370, pp. 519-537 (2016).
45. Saranwong, S. and Likasiri, C. "Bi-level programming model for solving distribution center problem: a case study in northern Thailand's sugarcane management", Comput. Ind. Eng., 103, pp. 26-39 (2017).
46. Shamekhi Amiri, A., Torabi, A., and Ghodsi, R. "An iterative approach for a bi-level competitive supply chain network design problem under foresight competition and variable coverage", Transp. Res. Part E Logist. Transp. Rev., 109, pp. 99-114 (2018).
47. Ghazanfari, M. and Murtagh, B.A. "A multi-objective hierarchical production planning model under stochastic demand", Sci. Irancia, 9(3), pp. 203-214 (2002).
48. Mula, J., Poler, R., Garcia-Sabater, J.P., et al. "Models for production planning under uncertainty: a review", Int. J. Prod. Econ., 103(1), pp. 271-285 (2006).
49. Leung, S.C.H. and Ng, W. "A goal programming model for production planning of perishable products with postponement", Comput. Ind. Eng., 53(3), pp. 531- 541 (2007).
50. Leung, S.C.H. and Chan, S.S.W. "A goal programming model for aggregate production planning with resource utilization constraint", Comput. Ind. Eng., 56(3), pp. 1053-1064 (2009).
51. Mirzapour Al-E-Hashem, S.M.J., Malekly, H., and Aryanezhad, M.B. "A multi-objective robust optimization model for multi-product multi-site aggregate production planning in a supply chain under uncertainty", Int. J. Prod. Econ., 134(1), pp. 28-42 (2011).
52. Zhang, G., Shang, J., and Li, W. "Collaborative production planning of supply chain under price and demand uncertainty", Eur. J. Oper. Res., 215(3), pp. 590-603 (2011).
53. Ghasemi Yaghin, R., Torabi, S.A., and Fatemi Ghomi, S.M.T. "Integrated markdown pricing and aggregate production planning in a two echelon supply chain: a hybrid fuzzy multiple objective approach", Appl. Math. Model., 36(12), pp. 6011-6030 (2012).
54. Ramezanian, R., Rahmani, D., and Barzinpour, F. "An aggregate production planning model for two phase production systems: solving with genetic algorithm and tabu search", Expert Syst. Appl., 39(1), pp. 1256-1263 (2012).
55. Awudu, I. and Zhang, J. "Stochastic production planning for a biofuel supply chain under demand and price uncertainties", Appl. Energy, 103, pp. 189-196 (2013).
56. Rahmani, D., Youse i, A., and Ramezanian, R. "A new robust fuzzy approach for aggregate production planning", Sci. Iran. Trans. E, Ind. Eng., 21(6), p. 2307 (2014).
57. Da Silva, A.F. and Marins, F.A.S. "A fuzzy goal programming model for solving aggregate productionplanning problems under uncertainty: a case study in a Brazilian sugar mill", Energy Econ., 45, pp. 196-204 (2014).
58. Chakrabortty, R.K., Hasin, M.A.A., Sarker, R.A., et al. "A possibilistic environment based particle swarm optimization for aggregate production planning", Comput. Ind. Eng., 88, pp. 366-377 (2015).
59. Jabbarzadeh, A., Fahimnia, B., and Sheu, J.-B. "An enhanced robustness approach for managing supply and demand uncertainties", Int. J. Prod. Econ., 183, pp. 620-631 (2015).
60. Ramyar, M., Mehdizadeh, E., and Hadji Molana, M. "Optimizing reliability and cost of system for aggregate production planning in supply chain", Sci. Iran., 24(6), pp. 3394-3408 (2017).
61. Entezaminia, A., Heidari, M., and Rahmani, D. "Robust aggregate production planning in a green supply chain under uncertainty considering reverse logistics: a case study", Int. J. Adv. Manuf. Technol., 90(5-8), pp. 1507-1528 (2017).
62. Mokhtari, H. and Hasani, A. "A multi-objective model for cleaner production-transportation planning in manufacturing plants via fuzzy goal programming", J. Manuf. Syst., 44, pp. 230-242 (2017).
63. Hahn, G.J. and Brandenburg, M. "A sustainable aggregate production planning model for the chemical process industry", Comput. Oper. Res., 94, pp. 154- 168 (2018).
64. Leung, S.C.H., Tsang, S.O.S., Ng, W.L., et al. "A robust optimization model for multi-site production planning problem in an uncertain environment", Eur. J. Oper. Res., 181(1), pp. 224-238 (2007).
65. Gorissen, B.L., Yankoglu, _I., and Hertog, D. "A practical guide to robust optimization", Omega, 53, pp. 124-137 (2015).
66. Zhen, J., Hertog, D., and Sim, M. "Adjustable robust optimization via Fourier-Motzkin elimination", Oper. Res., 66(4), pp. 1086-1100 (2018).
67. Bertsimas, D., Gupta, V., and Kallus, N. "Data-driven robust optimization", Math. Program., 167(2), pp. 235-292 (2018).
68. Pishvaee, M.S., Rabbani, M., and Torabi, S.A. "A robust optimization approach to closed-loop supply chain network design under uncertainty", Appl. Math. Model., 35(2), pp. 637-649 (2011).
69. Gabrel, V., Murat, C., and Thiele, A. "Recent advances in robust optimization: an overview", Eur. J. Oper. Res., 235(3), pp. 471-483 (2014).
70. Beyer, H.-G. and Sendho , B. "Robust optimization-a comprehensive survey", Comput. Methods Appl. Mech. Eng., 196(33-34), pp. 3190-3218 (2007). 
71. Bertsimas, D., Brown, D.B., and Caramanis, C. "Theory and applications of robust optimization", SIAM Rev., 53(3), pp. 464-501 (2011).
72. Vidal, C.J. and Goetschalckx, M. "A global supply chain model with transfer pricing and transportation cost allocation", Eur. J. Oper. Res., 129(1), pp. 134- 158 (2001).
73. Benders, J.F. "Partitioning procedures for solving mixed-variables programming problems", Numer. Math., 4(1), pp. 238-252 (1962).
74. MacRae, C.A.G., Ernst, A.T., and Ozlen, M. "A benders decomposition approach to transmission expansion planning considering energy storage", Energy, 112, pp. 795-803 (2016).
75. Pishvaee, M.S., Razmi, J., and Torabi, S.A. "An accelerated benders decomposition algorithm for sustainable supply chain network design under uncertainty: a case study of medical needle and syringe supply chain", Transp. Res. Part E Logist. Transp. Rev., 67, pp. 14-38 (2014).
76. Bagger, N.-C.F., Srensen, M., and Stidsen, T.R. "Benders' decomposition for curriculum-based course timetabling", Comput. Oper. Res., 91, pp. 178-189 (2017).