×

zbMATH — the first resource for mathematics

Capacity planning with competitive decision-makers: trilevel MILP formulation, degeneracy, and solution approaches. (English) Zbl 1375.90149
Summary: Capacity planning addresses the decision problem of an industrial producer investing on infrastructure to satisfy future demand with the highest profit. Traditional models neglect the rational behavior of some external decision-makers by assuming either static competition or captive markets. We propose a mathematical programing formulation with three levels of decision-makers to capture the dynamics of duopolistic markets. The trilevel model is transformed into a bilevel optimization problem with mixed-integer variables in both levels by replacing the third-level linear program with its optimality conditions. We introduce new definitions required for the analysis of degeneracy in multilevel models, and develop two novel algorithms to solve these challenging problems. Each algorithm is shown to converge to a different type of degenerate solution. The computational experiments for capacity expansion in industrial gas markets show that no algorithm is strictly superior in terms of performance.

MSC:
90B50 Management decision making, including multiple objectives
90C11 Mixed integer programming
90C27 Combinatorial optimization
90C90 Applications of mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alekseeva, E.; Kochetov, Y.; Plyasunov, A., An exact method for the discrete (r-p)-centroid problem, Journal of Global Optimization, 63, 445-460, (2015) · Zbl 1329.90076
[2] Alguacil, N.; Delgadillo, A.; Arroyo, J. M., A trilevel programming approach for electric grid defense planning, Computers and Operations Research, 41, 1, 282-290, (2014) · Zbl 1348.90378
[3] Anandalingam, G.; Apprey, V., Multi-level programming and conflict resolution, European Journal of Operational Research, 51, 2, 233-247, (1991) · Zbl 0743.90127
[4] Bard, J. F.; Moore, J. T., An algorithm for the discrete bilevel programming problem, Naval Research Logistics, 39, 3, 419-435, (1992) · Zbl 0751.90111
[5] Bard, J. F.; Plummer, J.; Sourie, J. C., A bilevel programming approach to determining tax credits for biofuel production, European Journal of Operational Research, 120, 30-46, (2000) · Zbl 0976.90099
[6] Ben-Ayed, O.; Blair, C. E., Computational difficulties of bilevel linear programming, Operations Research, 38, 3, 556-560, (1990) · Zbl 0708.90052
[7] Berglund, P. G.; Kwon, C., Solving a location problem of a Stackelberg firm competing with Cournot-Nash firms, Networks and Spatial Economics, 14, 1, 117-132, (2014) · Zbl 1339.91021
[8] Chang, S.-G.; Gavish, B., Telecommunications network topological design and capacity expansion: formulations and algorithms, Telecommuncation systems, 1, 1, 99-131, (1993)
[9] Delgadillo, A.; Arroyo, J. M.; Alguacil, N., Analysis of electric grid interdiction with line switching, IEEE Transactions on Power Systems, 25, 2, 633-641, (2010)
[10] Dempe, S., Foundations of bilevel programming, (2002), Springer Science & Business · Zbl 1038.90097
[11] Dempe, S.; Mardukhovich, B. S.; Zemkoho, A. B., Necessary optimality conditions in pessimistic bilevel programming, Optimization, 63, 4, 505-533, (2014) · Zbl 1302.90206
[12] DeNegre, S. T.; Ralphs, T. K., A branch-and-cut algorithm for integer bilevel linear programs, Operations Research and Computer Science Interfaces Series, 47, 65-78, (2009)
[13] Faísca, N. P.; Dua, V.; Rustem, B.; Saraiva, P. M.; Pistikopoulos, E. N., Parametric global optimisation for bilevel programming, Journal of Global Optimization, 38, 4, 609-623, (2006) · Zbl 1145.91016
[14] Friesz, T. L.; Rigdon, M. A.; Mookherjee, R., Differential variational inequalities and shipper dynamic oligopolistic network competition, Transportation Research Part B, 40, 480-503, (2006)
[15] Garcia-Herreros, P.; Zhang, L.; Misra, P.; Arslan, E.; Mehta, S.; Grossmann, I. E., Mixed-integer bilevel optimization for capacity planning with rational markets, Computers and Chemical Engineering, 86, 33-47, (2016)
[16] Glover, F., Improved linear integer programming formulations of nonlinear integer problems, Management Science, 22, 4, 455-460, (1975) · Zbl 0318.90044
[17] Grossmann, I. E., Advances in mathematical programming models for enterprise-wide optimization, Computers and Chemical Engineering, 47, 2-18, (2012)
[18] Gümüs, Z. H.; Floudas, C. A., Global optimization of mixed-integer bilevel programming problems, Computational Management Science, 2, 3, 181-212, (2005) · Zbl 1112.90061
[19] Hakimi, L. S., On locating new facilities in a competitive environment, European Journal of Operational Research, 12, 1, 29-35, (1983) · Zbl 0499.90026
[20] Han, J.; Lu, J.; Hu, Y.; Zhang, G., Tri-level decision-making with multiple followers: model, algorithm and case study, Information Sciences, 311, 182-204, (2015)
[21] Jeroslow, R. G., The polynomial hierarchy and a simple model for competitive analysis, Mathematical Programming, 32, 2, 146-164, (1985) · Zbl 0588.90053
[22] Karakitsiou, A., Modeling discrete competitive facility location, (2015), Springer · Zbl 1336.90061
[23] Karakitsiou, A.; Migdalas, A., Locating facilities in a competitive environment, Optimization Letters, (2015) · Zbl 1368.90095
[24] Kleniati, P.-M.; Adjiman, C. S., Branch-and-sandwich: A deterministic global optimization algorithm for optimistic bilevel programming problems. part II: convergence analysis and numerical results, Journal of Global Optimization, 60, 3, 459-481, (2014) · Zbl 1310.90092
[25] Kress, D.; Pesch, E., Sequential competitive location on networks, European Journal of Operational Research, 217, 483-499, (2012) · Zbl 1244.90128
[26] Luh, P. B.; Chang, S.-C.; Chang, T.-S., Solutions and properties of multi-stage stackeiberg games, Automatica, 20, 2, 251-256, (1984) · Zbl 0529.90105
[27] Migdalas, A., Bilevel programming in traffic planning: models, methods and challenge, Journal of Global Optimization, 7, 381-405, (1995) · Zbl 0844.90050
[28] Miller, T. C.; Friesz, T. L.; Tobin, R. L.; Kwon, C., Reaction function based dynamic location modeling in Stackelberg-Nash-Cournot competition, Networks and Spatial Economics, 7, 77-97, (2007) · Zbl 1137.91336
[29] Mitsos, A.; Bollas, G. M.; Barton, P. I., Bilevel optimization formulation for parameter estimation in liquid-liquid phase equilibrium problems, Chemical Engineering Science, 64, 548-559, (2009)
[30] Moore, J. T.; Bard, J. F., The mixed integer linear bilevel programming problem, Operations Research, 38, 5, 911-921, (1990) · Zbl 0723.90090
[31] Murphy, F. H.; Smeers, Y., Generation capacity expansion in imperfectly competitive restructured electricity markets, Operations Research, 53, 4, 646-661, (2005) · Zbl 1165.91342
[32] Poirion, P.-L., Toubaline, S., D’ambrosio, C., & Liberti, L. (2015). Bilevel mixed-integer linear programs and the zero forcing set. Optimization-online.org: 5210.
[33] Roboredo, M. C.; Pessoa, A. A., A branch-and-cut algorithm for the discrete (r-p)-centroid problem, European Journal of Operational Research, 224, 1, 101-109, (2013) · Zbl 1292.90172
[34] Sherali, H. D.; Soyster, A. L.; Murphy, F. H., Stackelberg-Nash-Cournot equilibria: characterizations and computations, Operations Research, 31, 2, 253-276, (1983) · Zbl 0506.90011
[35] Smith, J.C., Lim, C., & Alptekinoglu, A. (2009). Optimal mixed-Integer programming and heuristic methods for a bilevel Stackelberg product introduction game. Naval Research Logistics, 56 (8), 714-729.
[36] Wiesemann, W., Tsoukalas, A., & Kleniati, P.-M. (2013). Pessimistic bilevel optimization. SIAM Journal on Optimization, 23(1), 353-380. · Zbl 1270.90088
[37] Xu, P., & Wang, L. (2014). An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Computers and Operations Research, 41, 309-318. · Zbl 1348.90496
[38] Yao, Y., Edmunds, T., Papageorgiou, D., & Alvarez, R. (2007). Trilevel optimization in power network defense. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, 37(4), 712-718.
[39] Zemkoho, A. B. (2016). Solving Ill-posed bilevel programs. Set-Valued and Variational Analysis, 24(3), 423-448. · Zbl 1362.90346
[40] Zeng, B. (2015). Easier than we thought : A practical scheme to compute pessimistic bilevel optimization problem. Available at SSRN 2658342.
[41] Zeng, B., & An, Y. (2014). Solving bilevel mixed integer program by reformulations and decomposition. Optimization On-line.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.