Efficiently solving linear bilevel programming problems using off-the-shelf optimization software.

*(English)*Zbl 1391.90004Summary: Many optimization models in engineering are formulated as bilevel problems. Bilevel optimization problems are mathematical programs where a subset of variables is constrained to be an optimal solution of another mathematical program. Due to the lack of optimization software that can directly handle and solve bilevel problems, most existing solution methods reformulate the bilevel problem as a mathematical program with complementarity conditions (MPCC) by replacing the lower-level problem with its necessary and sufficient optimality conditions. MPCCs are single-level non-convex optimization problems that do not satisfy the standard constraint qualifications and therefore, nonlinear solvers may fail to provide even local optimal solutions. In this paper we propose a method that first solves iteratively a set of regularized MPCCs using an off-the-shelf nonlinear solver to find a local optimal solution. Local optimal information is then used to reduce the computational burden of solving the Fortuny-Amat reformulation of the MPCC to global optimality using off-the-shelf mixed-integer solvers. This method is tested using a wide range of randomly generated examples. The results show that our method outperforms existing general-purpose methods in terms of computational burden and global optimality.

##### MSC:

90-04 | Software, source code, etc. for problems pertaining to operations research and mathematical programming |

90C30 | Nonlinear programming |

90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |

90C11 | Mixed integer programming |

##### Keywords:

bilevel programming; mathematical programming with complementarity conditions; nonlinear programming; mixed-integer programming; optimization solvers
PDF
BibTeX
XML
Cite

\textit{S. Pineda} et al., Optim. Eng. 19, No. 1, 187--211 (2018; Zbl 1391.90004)

Full Text:
DOI

##### References:

[1] | Bard, JF, Some properties of the bilevel programming problem, J Optim Theory Appl, 68, 371-378, (1991) · Zbl 0696.90086 |

[2] | Bard JF (1998) practical bilevel optimization: algorithms and applications. Springer, Berlin · Zbl 0943.90078 |

[3] | Bard, JF; Falk, JE, An explicit solution to the multi-level programming problem, Comput Oper Res, 9, 77-100, (1982) |

[4] | Bard, J; Moore, J, A branch and bound algorithm for the bilevel programming problem, SIAM J Sci Stat Comput, 11, 281-292, (1990) · Zbl 0702.65060 |

[5] | Baringo, L; Conejo, AJ, Wind power investment within a market environment, Appl Energy, 88, 3239-3247, (2011) |

[6] | Baringo, L; Conejo, AJ, Wind power investment: a benders decomposition approach, IEEE Trans Power Syst, 27, 433-441, (2012) |

[7] | Baringo, L; Conejo, AJ, Risk-constrained multi-stage wind power investment, IEEE Trans Power Syst, 28, 401-411, (2013) |

[8] | Baringo, L; Conejo, AJ, Strategic wind power investment, IEEE Trans Power Syst, 29, 1250-1260, (2014) |

[9] | Ben-Ayed, O; Blair, CE, Computational difficulties of bilevel linear programming, Oper Res, 38, 556-560, (1990) · Zbl 0708.90052 |

[10] | Bialas, WF; Karwan, MH, Two-level linear programming, Manag Sci, 30, 1004-1020, (1984) · Zbl 0559.90053 |

[11] | Calvete, HI; Galé, C; Mateo, PM, A new approach for solving linear bilevel problems using genetic algorithms, Eur J Oper Res, 188, 14-28, (2008) · Zbl 1135.90023 |

[12] | Candler, W; Townsley, R, A linear two-level programming problem, Comput Oper Res, 9, 59-76, (1982) |

[13] | Colson, B; Marcotte, P; Savard, G, Bilevel programming: a survey, 4OR, 3, 87-107, (2005) · Zbl 1134.90482 |

[14] | Colson, B; Marcotte, P; Savard, G, An overview of bilevel optimization, Ann Oper Res, 153, 235-256, (2007) · Zbl 1159.90483 |

[15] | Dempe S (2002) Foundations of bilevel programming. Springer, Berlin · Zbl 1038.90097 |

[16] | Dempe, S, Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52, 333-359, (2003) · Zbl 1140.90493 |

[17] | Dempe, S; Dutta, J, Is bilevel programming a special case of a mathematical program with complementarity constraints?, Math Program, 131, 37-48, (2010) · Zbl 1235.90145 |

[18] | Dempe, S; Franke, S, Solution algorithm for an optimistic linear Stackelberg problem, Comput Oper Res, 41, 277-281, (2014) · Zbl 1348.91081 |

[19] | Dempe, S; Zemkoho, AB, The bilevel programming problem: reformulations, constraint qualifications and optimality conditions, Math Program, 138, 447-473, (2012) · Zbl 1272.90086 |

[20] | Dempe, S; Dutta, J; Mordukhovich, BS, New necessary optimality conditions in optimistic bilevel programming, Optimization, 56, 577-604, (2007) · Zbl 1172.90481 |

[21] | Dempe, S; Mordukhovich, BS; Zemkoho, AB, Necessary optimality conditions in pessimistic bilevel programming, Optimization, 63, 505-533, (2014) · Zbl 1302.90206 |

[22] | Dempe S, Kalashnikov V, Pérez-Valdés GA, Kalashnikova N (2015) Bilevel programming problems: theory, algorithms and applications to energy networks. Energy systems. Springer, Berlin · Zbl 1338.90005 |

[23] | Fletcher R, Leyffer S (2002) Numerical experience with solving MPECs as NLPs. Technical report, Department of Mathematics and Computer Science, University of Dundee, Dundee |

[24] | Fletcher, R; Leyffer, S, Solving mathematical programs with complementarity constraints as nonlinear programs, Optim Methods Softw, 19, 15-40, (2004) · Zbl 1074.90044 |

[25] | Fortuny-Amat, J; McCarl, B, A representation and economic interpretation of a two-level programming problem, J Oper Res Soc, 32, 783-792, (1981) · Zbl 0459.90067 |

[26] | Gabriel, SA; Leuthold, FU, Solving discretely-constrained MPEC problems with applications in electric power markets, Energy Econ, 32, 3-14, (2010) |

[27] | Garces, LP; Conejo, AJJ; Garcia-Bertrand, R; Romero, R; Garcés, LP, A bilevel approach to transmission expansion planning within a market environment, IEEE Trans Power Syst, 24, 1513-1522, (2009) |

[28] | Hansen, P; Jaumard, B; Savard, G, New branch-and-bound rules for linear bilevel programming, SIAM J Sci Stat Comput, 13, 1194-1217, (1992) · Zbl 0760.65063 |

[29] | Hasan, E; Galiana, FD; Conejo, AJ, Electricity markets cleared by merit order—part I: finding the market outcomes supported by pure strategy Nash equilibria, IEEE Trans Power Syst, 23, 361-371, (2008) |

[30] | Hejazi, SR; Memariani, A; Jahanshahloo, G; Sepehri, MM, Linear bilevel programming solution by genetic algorithm, Comput Oper Res, 29, 1913-1925, (2002) · Zbl 1259.90120 |

[31] | Hu, XM; Ralph, D, Convergence of a penalty method for mathematical programming with complementarity constraints, J Optim Theory Appl, 123, 365-390, (2004) |

[32] | Jenabi, M; Ghomi, SM; Smeers, Y, Bi-level game approaches for coordination of generation and transmission expansion planning within a market environment, IEEE Trans Power Syst, 28, 2639-2650, (2013) |

[33] | Jeroslow, RG, The polynomial hierarchy and a simple model for competitive analysis, Math Program, 32, 146-164, (1985) · Zbl 0588.90053 |

[34] | Jiang, Y; Li, X; Huang, C; Xianing, W, Application of particle swarm optimization based on CHKS smoothing function for solving nonlinear bilevel programming problem, Appl Math Comput, 219, 4332-4339, (2013) · Zbl 1401.90273 |

[35] | Kazempour, SJ; Conejo, AJ, Strategic generation investment under uncertainty via benders decomposition, IEEE Trans Power Syst, 27, 424-432, (2012) |

[36] | Kazempour, SJ; Conejo, AJ; Ruiz, C, Strategic generation investment using a complementarity approach, IEEE Trans Power Syst, 26, 940-948, (2011) |

[37] | Kazempour, SJ; Conejo, AJ; Ruiz, C, Strategic generation investment considering futures and spot markets, IEEE Trans Power Syst, 27, 1467-1476, (2012) |

[38] | Li, H; Fang, L, An evolutionary algorithm for solving bilevel programming problems using duality conditions, Math Probl Eng, (2012) · Zbl 1264.90153 |

[39] | Lorenczik S, Malischek R, , Trüby J (2014) Modeling strategic investment decisions in spatial markets. Technical Report 14/09, Köln · Zbl 1394.91314 |

[40] | Lv, Y; Tiesong, H; Wang, G; Wan, Z, A penalty function method based on Kuhn-Tucker condition for solving linear bilevel programming, Appl Math Comput, 188, 808-813, (2007) · Zbl 1137.90617 |

[41] | Maurovich-Horvat, L; Boomsma, TK; Siddiqui, AS, Transmission and wind investment in a deregulated electricity industry, IEEE Trans Power, 30, 1633-1643, (2014) |

[42] | Mersha, AG; Dempe, S, Linear bilevel programming with upper level constraints depending on the lower level solution., Appl Math Comput, 180, 247-254, (2006) · Zbl 1102.90070 |

[43] | Moiseeva, E; Hesamzadeh, MR; Biggar, DR, Exercise of market power on ramp rate in wind-integrated power systems, IEEE Trans Power Syst, 30, 1614-1623, (2015) |

[44] | Morales, JM; Zugno, M; Pineda, S; Pinson, P, Electricity market clearing with improved scheduling of stochastic production, Eur J Oper Res, 235, 765-774, (2014) · Zbl 1305.91193 |

[45] | Motto, ALL; Arroyo, JMM; Galiana, FDD, A mixed-integer LP procedure for the analysis of electric grid security under disruptive threat, IEEE Trans Power Syst, 20, 1357-1365, (2005) |

[46] | Outrata, J, On mathematical programs with complementarity constraints, Optim Methods Softw, 14, 117-137, (2000) · Zbl 0979.49027 |

[47] | Pisciella, P; Bertocchi, M; Vespucci, MT, A leader-followers model of power transmission capacity expansion in a market driven environment, Comput Manag Sci, 13, 87-118, (2016) · Zbl 1397.90079 |

[48] | Pozo, D; Contreras, J, Finding multiple Nash equilibria in pool-based markets: a stochastic EPEC approach, IEEE Trans Power Syst, 26, 1744-1752, (2011) |

[49] | Pozo, D; Sauma, E; Contreras, J, A three-level static MILP model for generation and transmission expansion planning, IEEE Trans Power Syst, 28, 202-210, (2013) |

[50] | Ralph, D; Wright, SJ, Some properties of regularization and penalization schemes for mpecs, Optim Methods Softw, 19, 527-556, (2004) · Zbl 1097.90054 |

[51] | Ruiz, C; Conejo, AJ, Pool strategy of a producer with endogenous formation of locational marginal prices, IEEE Trans Power Syst, 24, 1855-1866, (2009) |

[52] | Ruiz, C; Conejo, AJ, Robust transmission expansion planning, Eur J Oper Res, 242, 390-401, (2014) |

[53] | Ruiz, C; Conejo, AJ; Smeers, Y, Equilibria in an oligopolistic electricity pool with stepwise offer curves, IEEE Trans Power Syst, 27, 752-761, (2012) |

[54] | Scheel, H; Scholtes, S, Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity, Math Oper Res, 25, 1-22, (2000) · Zbl 1073.90557 |

[55] | Scholtes, S, Convergence properties of a regularization scheme for mathematical programs with complementarity constraints, SIAM J Optim, 11, 918-936, (2001) · Zbl 1010.90086 |

[56] | Shi, C; Jie, L; Zhang, G, An extended Kuhn-Tucker approach for linear bilevel programming, Appl Math Comput, 162, 51-63, (2005) · Zbl 1090.90175 |

[57] | Shi, C; Jie, L; Zhang, G, An extended kth-best approach for linear bilevel programming, Appl Math Comput, 164, 843-855, (2005) · Zbl 1072.65085 |

[58] | Shi, C; Zhang, G; Jie, L, On the definition of linear bilevel programming solution, Appl Math Comput, 160, 169-176, (2005) · Zbl 1084.91007 |

[59] | Shi, C; Jie, L; Zhang, G; Zhou, H, An extended branch and bound algorithm for linear bilevel programming, Appl Math Comput, 180, 529-537, (2006) · Zbl 1102.65071 |

[60] | Siddiqui, S; Gabriel, SA, An SOS1-based approach for solving MPECs with a natural gas market application, Netw Spat Econ, 13, 205-227, (2012) · Zbl 1332.91075 |

[61] | Sinha A, Malo P, Deb K (2013) Efficient evolutionary algorithm for single-objective bilevel optimization. arXiv:1303.3901 |

[62] | Strekalovsky, AS; Orlov, AV; Malyshev, AV, On computational search for optimistic solutions in bilevel problems, J Glob Optim, 48, 159-172, (2010) · Zbl 1202.90219 |

[63] | Strekalovsky, AS; Orlov, AV; Malyshev, AV, Numerical solution of a class of bilevel programming problems, Numer Anal Appl, 3, 165-173, (2010) |

[64] | The ILOG CPLEX (2015) http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/index.html · Zbl 0559.90053 |

[65] | Valinejad, J; Barforoushi, T, Generation expansion planning in electricity markets: a novel framework based on dynamic stochastic MPEC, Int J Electr Power Energy Syst, 70, 108-117, (2015) |

[66] | Von Stackelberg H (1952) The theory of the market economy. Oxford University Press, Oxford |

[67] | White, DJ; Anandalingam, G, A penalty function approach for solving bi-level linear programs, J Glob Optim, 3, 397-419, (1993) · Zbl 0791.90047 |

[68] | Wogrin, S; Centeno, E; Barquín, J, Generation capacity expansion in liberalized electricity markets: a stochastic MPEC approach, IEEE Trans Power Syst, 26, 2526-2532, (2011) |

[69] | Wogrin, S; Barquin, J; Centeno, E, Capacity expansion equilibria in liberalized electricity markets: an EPEC approach, IEEE Trans Power Syst, 28, 1531-1539, (2013) |

[70] | Zhang G, Lu J, Gao Y (2015) Multi-level decision making: models, methods and applications. Intelligent systems reference library. Springer, Berlin · Zbl 1308.91006 |

[71] | Zugno, M; Morales, JM; Pinson, P; Madsen, H, Pool strategy of a price-maker wind power producer, IEEE Trans Power Syst, 28, 3440-3450, (2013) |

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.