{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T07:03:38Z","timestamp":1767855818389,"version":"3.49.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T00:00:00Z","timestamp":1679270400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T00:00:00Z","timestamp":1679270400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Thessaly Central Library"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We develop an exact cutting plane solution algorithm for a special class of bilevel programming models utilized for optimal price-bidding of energy producers in day-ahead electricity markets. The proposed methodology utilizes a suitable reformulation in which a key prerequisite for global optimality, termed bilevel feasibility, is relaxed. Solving the problem to global optimality involves finding the price-offers of the strategic producer (upper-level decision variables) which maximize his self-profit upon clearing of the market and identification of the optimal energy quantity distribution (lower-level decision variables). To exclude from consideration the encountered bilevel infeasible solutions, the algorithm employs a special type of valid cuts drawn from the theory of integer parametric programming. The generation of these cuts involves finding the truly optimal lower-level solution using the strategic price-offers at the bilevel infeasible solution subject to exclusion and devising range intervals for these offers such that the optimality of this solution is retained when each of them lies in its corresponding interval. Each cut imposes a suitable part of this solution, under the condition that each price-offer belongs to its associated interval, which renders the bilevel infeasible solution invalid. We establish the theoretical framework for the development of the proposed algorithm, we illustrate its application on a small case study, and we present extensive computational results demonstrating its behavior and performance on random problem instances. These results indicate that the algorithm is capable of solving to global optimality considerably larger problems than those that a previous elementary version of the same algorithm could solve. This constitutes significant research contribution, considering the lack of generic optimization software for bilevel programming, as well as the fact that the applicability of specialized algorithms on problems of realistic size is rather limited.<\/jats:p>","DOI":"10.1007\/s10957-023-02166-8","type":"journal-article","created":{"date-parts":[[2023,3,20]],"date-time":"2023-03-20T08:03:55Z","timestamp":1679299435000},"page":"573-607","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Exact Solution Algorithm for Integer Bilevel Programming with Application in Energy Market Optimization"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4325-2975","authenticated-orcid":false,"given":"George","family":"Kozanidis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eftychia","family":"Kostarelou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,20]]},"reference":[{"key":"2166_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-030-36979-8_2","volume-title":"Electricity Markets","author":"A Akbari-Dibavar","year":"2020","unstructured":"Akbari-Dibavar, A., Mohammadi-Ivatloo, B., Zare, K.: Electricity market pricing: Uniform pricing vs pay-as-bid pricing. In: Nojavan, S., Zare, K. (eds.) Electricity Markets, pp. 19\u201335. Springer, Cham. (2020). https:\/\/doi.org\/10.1007\/978-3-030-36979-8_2"},{"key":"2166_CR2","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1109\/TPWRS.2012.2207920","volume":"28","author":"P Andrianesis","year":"2013","unstructured":"Andrianesis, P., Liberopoulos, G., Kozanidis, G., Papalexopoulos, A.: Recovery mechanisms in day-ahead electricity markets with non-convexities\u2014Part I: design and evaluation methodology. IEEE Trans. Power Syst. 28, 960\u2013968 (2013). https:\/\/doi.org\/10.1109\/TPWRS.2012.2207920","journal-title":"IEEE Trans. Power Syst."},{"key":"2166_CR3","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1109\/TPWRS.2012.2207921","volume":"28","author":"P Andrianesis","year":"2013","unstructured":"Andrianesis, P., Liberopoulos, G., Kozanidis, G., Papalexopoulos, A.: Recovery mechanisms in day-ahead electricity markets with non-convexities\u2014Part II: implementation and numerical evaluation. IEEE Trans. Power Syst. 28, 969\u2013977 (2013). https:\/\/doi.org\/10.1109\/TPWRS.2012.2207921","journal-title":"IEEE Trans. Power Syst."},{"key":"2166_CR4","doi-asserted-by":"publisher","first-page":"1804","DOI":"10.1109\/TPWRS.2007.907536","volume":"22","author":"AG Bakirtzis","year":"2007","unstructured":"Bakirtzis, A.G., Ziogos, N.P., Tellidou, A.C., Bakirtzis, G.A.: Electricity producer offering strategies in day-ahead energy market with step-wise offers. IEEE Trans. Power Syst. 22, 1804\u20131818 (2007). https:\/\/doi.org\/10.1109\/TPWRS.2007.907536","journal-title":"IEEE Trans. Power Syst."},{"key":"2166_CR5","doi-asserted-by":"publisher","unstructured":"Bard, J.F.: Practical Bilevel Optimization. Nonconvex Optimization and Its Applications, vol 30. Springer, Boston, MA (1998). https:\/\/doi.org\/10.1007\/978-1-4757-2836-1_4","DOI":"10.1007\/978-1-4757-2836-1_4"},{"key":"2166_CR6","unstructured":"Bylling, H.C.: Bilevel optimization with applications in energy. Ph.D. thesis, University of Copenhagen, Faculty of Science, Department of Mathematical Sciences, Copenhagen, Denmark (2018)"},{"issue":"5","key":"2166_CR7","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1080\/01605682.2019.1590132","volume":"71","author":"HC Bylling","year":"2020","unstructured":"Bylling, H.C., Gabriel, S.A., Boomsma, T.K.: A parametric programming approach to bilevel optimisation with lower-level variables in the upper level. J. Oper. Res. Soc. 71(5), 846\u2013865 (2020). https:\/\/doi.org\/10.1080\/01605682.2019.1590132","journal-title":"J. Oper. Res. Soc."},{"key":"2166_CR8","unstructured":"Candler, W., Norton R.: Multi-level programming and development policy. World Bank Staff Working Paper No 258, Washington, DC (1977)"},{"key":"2166_CR9","doi-asserted-by":"publisher","first-page":"1447","DOI":"10.1007\/s11590-015-0872-9","volume":"9","author":"M Caramia","year":"2015","unstructured":"Caramia, M., Mari, R.: Enhanced exact algorithms for discrete bilevel linear problems. Optim. Lett. 9, 1447\u20131468 (2015). https:\/\/doi.org\/10.1007\/s11590-015-0872-9","journal-title":"Optim. Lett."},{"key":"2166_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/b101970","volume-title":"Foundations of Bilevel Programming","author":"S Dempe","year":"2002","unstructured":"Dempe, S.: Foundations of Bilevel Programming. Kluwer Academic, New York (2002). https:\/\/doi.org\/10.1007\/b101970"},{"key":"2166_CR11","doi-asserted-by":"publisher","unstructured":"DeNegre, S.T., Ralphs, T.K.: A branch-and-cut algorithm for integer bilevel linear programs. In: Operations research and cyber-infrastructure, pp. 65\u201378. Springer, Boston, MA (2009) https:\/\/doi.org\/10.1007\/978-0-387-88843-9_4","DOI":"10.1007\/978-0-387-88843-9_4"},{"key":"2166_CR12","doi-asserted-by":"publisher","first-page":"2097","DOI":"10.1016\/j.compchemeng.2010.07.032","volume":"34","author":"LF Dom\u00ednguez","year":"2010","unstructured":"Dom\u00ednguez, L.F., Pistikopoulos, E.N.: Multiparametric programming based algorithms for pure integer and mixed-integer bilevel programming problems. Comput. Chem. Eng. 34, 2097\u20132106 (2010). https:\/\/doi.org\/10.1016\/j.compchemeng.2010.07.032","journal-title":"Comput. Chem. Eng."},{"key":"2166_CR13","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s10589-007-9066-4","volume":"39","author":"M Fampa","year":"2008","unstructured":"Fampa, M., Barroso, L.A., Candal, D., Simonetti, L.: Bilevel optimization applied to strategic pricing in competitive electricity markets. Comput. Optim. Appl. 39, 121\u2013142 (2008). https:\/\/doi.org\/10.1007\/s10589-007-9066-4","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"2166_CR14","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1109\/PTC.2017.7980796","volume":"32","author":"R Fern\u00e1ndez-Blanco","year":"2017","unstructured":"Fern\u00e1ndez-Blanco, R., Arroyo, J.M., Alguacil, N.: On the solution of revenue-and network-constrained day-ahead market clearing under marginal pricing\u2014Part I: an exact bilevel programming approach. IEEE Trans. Power Syst. 32(1), 208\u2013219 (2017). https:\/\/doi.org\/10.1109\/PTC.2017.7980796","journal-title":"IEEE Trans. Power Syst."},{"key":"2166_CR15","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1287\/opre.2017.1650","volume":"65","author":"M Fischetti","year":"2017","unstructured":"Fischetti, M., Ljubi\u0107, I., Monaci, M., Sinnl, M.: A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper. Res. 65, 1615\u20131637 (2017). https:\/\/doi.org\/10.1287\/opre.2017.1650","journal-title":"Oper. Res."},{"key":"2166_CR16","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1287\/mnsc.23.5.453","volume":"23","author":"AM Geoffrion","year":"1977","unstructured":"Geoffrion, A.M., Nauss, R.: Parametric and postoptimality analysis in integer linear programming. Manage. Sci. 23, 453\u2013466 (1977). https:\/\/doi.org\/10.1287\/mnsc.23.5.453","journal-title":"Manage. Sci."},{"key":"2166_CR17","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1023\/A:1009677326718","volume":"6","author":"G Gross","year":"2000","unstructured":"Gross, G., Finlay, D.: Generation supply bidding in perfectly competitive electricity markets. Comput. Math. Organ. Theory 6, 83\u201398 (2000). https:\/\/doi.org\/10.1023\/A:1009677326718","journal-title":"Comput. Math. Organ. Theory"},{"key":"2166_CR18","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10287-005-0025-1","volume":"2","author":"ZH G\u00fcm\u00fcs","year":"2005","unstructured":"G\u00fcm\u00fcs, Z.H., Floudas, C.A.: Global optimization of mixed-integer bilevel programming problems. Comput. Manag. Sci. 2, 181\u2013212 (2005). https:\/\/doi.org\/10.1007\/s10287-005-0025-1","journal-title":"Comput. Manag. Sci."},{"key":"2166_CR19","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1109\/59.867153","volume":"15","author":"BF Hobbs","year":"2000","unstructured":"Hobbs, B.F., Metzler, C.B., Pang, J.-S.: Strategic gaming analysis for electric power systems: an MPEC approach. IEEE Trans. Power Syst. 15, 638\u2013645 (2000). https:\/\/doi.org\/10.1109\/59.867153","journal-title":"IEEE Trans. Power Syst."},{"key":"2166_CR20","unstructured":"IBM ILOG CPLEX: CPLEX Callable Library v. 12.9.0 (2019) https:\/\/www.ibm.com\/docs\/en\/icos\/12.9.0 Last accessed 14 Jan. 2023"},{"key":"2166_CR21","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/j.compchemeng.2014.06.004","volume":"72","author":"P-M Kleniati","year":"2015","unstructured":"Kleniati, P.-M., Adjiman, C.S.: A generalization of the branch-and-sandwich algorithm: From continuous to mixed-integer nonlinear bilevel problems. Comput. Chem. Eng. 72, 373\u2013386 (2015). https:\/\/doi.org\/10.1016\/j.compchemeng.2014.06.004","journal-title":"Comput. Chem. Eng."},{"issue":"1","key":"2166_CR22","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s11081-020-09521-y","volume":"22","author":"E Kostarelou","year":"2021","unstructured":"Kostarelou, E., Kozanidis, G.: Bilevel programming solution algorithms for optimal price-bidding of energy producers in multi-period day-ahead electricity markets with non-convexities. Optim. Eng. 22(1), 449\u2013484 (2021). https:\/\/doi.org\/10.1007\/s11081-020-09521-y","journal-title":"Optim. Eng."},{"issue":"8","key":"2166_CR23","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1080\/02331934.2013.801473","volume":"62","author":"G Kozanidis","year":"2013","unstructured":"Kozanidis, G., Kostarelou, E., Andrianesis, P., Liberopoulos, G.: Mixed integer parametric bilevel programming for optimal strategic bidding of energy producers in day-ahead electricity markets with indivisibilities. Optimization 62(8), 1045\u20131068 (2013). https:\/\/doi.org\/10.1080\/02331934.2013.801473","journal-title":"Optimization"},{"key":"2166_CR24","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s10957-010-9668-3","volume":"146","author":"M K\u00f6ppe","year":"2010","unstructured":"K\u00f6ppe, M., Queyranne, M., Ryan, C.T.: Parametric integer programming algorithm for bilevel mixed integer programs. J. Optim. Theory Appl. 146, 137\u2013150 (2010). https:\/\/doi.org\/10.1007\/s10957-010-9668-3","journal-title":"J. Optim. Theory Appl."},{"key":"2166_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-23193-3_2","volume-title":"Handbook of Networks in Power Systems I. Energy Systems","author":"RH Kwon","year":"2012","unstructured":"Kwon, R.H., Frances, D.: Optimization-based bidding in day-ahead electricity auction markets: a review of models for power producers. In: Sorokin, A., Rebennack, S., Pardalos, P., Iliadis, N., Pereira, M. (eds.) Handbook of Networks in Power Systems I. Energy Systems, pp. 41\u201359. Springer, Berlin (2012). https:\/\/doi.org\/10.1007\/978-3-642-23193-3_2"},{"key":"2166_CR26","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1109\/TPWRS.2004.840378","volume":"20","author":"T Li","year":"2005","unstructured":"Li, T., Shahidehpour, M.: Strategic bidding of transmission-constrained GENCOs with incomplete information. IEEE Trans. Power Syst. 20, 437\u2013447 (2005). https:\/\/doi.org\/10.1109\/TPWRS.2004.840378","journal-title":"IEEE Trans. Power Syst."},{"key":"2166_CR27","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1016\/j.ejor.2020.10.002","volume":"291","author":"S Liu","year":"2021","unstructured":"Liu, S., Wang, M., Kong, N., Hu, X.: An enhanced branch-and-bound algorithm for bilevel integer linear programming. Eur. J. Oper. Res. 291, 661\u2013679 (2021). https:\/\/doi.org\/10.1016\/j.ejor.2020.10.002","journal-title":"Eur. J. Oper. Res."},{"key":"2166_CR28","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF00121269","volume":"8","author":"P Loridan","year":"1996","unstructured":"Loridan, P., Morgan, J.: Weak via strong Stackelberg problem: New results. J. Global Optim. 8, 263\u2013287 (1996). https:\/\/doi.org\/10.1007\/BF00121269","journal-title":"J. Global Optim."},{"key":"2166_CR29","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1287\/opre.2017.1589","volume":"65","author":"L Lozano","year":"2017","unstructured":"Lozano, L., Smith, J.C.: A value-function-based exact approach for the bilevel mixed-integer programming problem. Oper. Res. 65, 768\u2013786 (2017). https:\/\/doi.org\/10.1287\/opre.2017.1589","journal-title":"Oper. Res."},{"key":"2166_CR30","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s10898-009-9479-y","volume":"47","author":"A Mitsos","year":"2010","unstructured":"Mitsos, A.: Global solution of nonlinear mixed-integer bilevel programs. J. Global Optim. 47, 557\u2013582 (2010). https:\/\/doi.org\/10.1007\/s10898-009-9479-y","journal-title":"J. Global Optim."},{"key":"2166_CR31","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1287\/opre.38.5.911","volume":"38","author":"JT Moore","year":"1990","unstructured":"Moore, J.T., Bard, J.F.: The mixed integer linear bilevel programming problem. Oper. Res. 38, 911\u2013921 (1990). https:\/\/doi.org\/10.1287\/opre.38.5.911","journal-title":"Oper. Res."},{"key":"2166_CR32","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1109\/TPWRS.2004.840397","volume":"20","author":"MV Pereira","year":"2005","unstructured":"Pereira, M.V., Granville, S., Fampa, M.H.C., Dix, R., Barroso, L.A.: Strategic bidding under uncertainty: a binary expansion approach. IEEE Trans. Power Syst. 20, 180\u2013188 (2005). https:\/\/doi.org\/10.1109\/TPWRS.2004.840397","journal-title":"IEEE Trans. Power Syst."},{"key":"2166_CR33","doi-asserted-by":"publisher","first-page":"1855","DOI":"10.1109\/TPWRS.2009.2030378","volume":"24","author":"C Ruiz","year":"2009","unstructured":"Ruiz, C., Conejo, A.J.: Pool strategy of a producer with endogenous formation of locational marginal prices. IEEE Trans. Power Syst. 24, 1855\u20131866 (2009). https:\/\/doi.org\/10.1109\/TPWRS.2009.2030378","journal-title":"IEEE Trans. Power Syst."},{"key":"2166_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-1683-1","volume-title":"Spot Pricing of Electricity","author":"FC Schweppe","year":"1988","unstructured":"Schweppe, F.C., Caramanis, M.C., Tabors, R.D., Bohn, R.E.: Spot Pricing of Electricity. Kluwer, Boston (1988). https:\/\/doi.org\/10.1007\/978-1-4613-1683-1"},{"key":"2166_CR35","doi-asserted-by":"publisher","first-page":"1403","DOI":"10.1137\/15M1051592","volume":"27","author":"L Wang","year":"2017","unstructured":"Wang, L., Xu, P.: The watermelon algorithm for the bilevel integer linear programming problem. SIAM J. Optim. 27, 1403\u20131430 (2017). https:\/\/doi.org\/10.1137\/15M1051592","journal-title":"SIAM J. Optim."},{"key":"2166_CR36","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/120864015","volume":"23","author":"W Wiesemann","year":"2013","unstructured":"Wiesemann, W., Tsoukalas, A., Kleniati, P.-M., Rustem, B.: Pessimistic bilevel optimization. SIAM J. Optim. 23, 353\u2013380 (2013). https:\/\/doi.org\/10.1137\/120864015","journal-title":"SIAM J. Optim."},{"key":"2166_CR37","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/j.cor.2013.07.016","volume":"41","author":"P Xu","year":"2014","unstructured":"Xu, P., Wang, L.: An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions. Comput. Oper. Res. 41, 309\u2013318 (2014). https:\/\/doi.org\/10.1016\/j.cor.2013.07.016","journal-title":"Comput. Oper. Res."},{"key":"2166_CR38","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s10898-018-0679-1","volume":"73","author":"D Yue","year":"2019","unstructured":"Yue, D., Gao, J., Zeng, B., You, F.: A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs. J. Global Optim. 73, 27\u201357 (2019). https:\/\/doi.org\/10.1007\/s10898-018-0679-1","journal-title":"J. Global Optim."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02166-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-023-02166-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02166-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T13:07:53Z","timestamp":1684415273000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-023-02166-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,20]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["2166"],"URL":"https:\/\/doi.org\/10.1007\/s10957-023-02166-8","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,20]]},"assertion":[{"value":"6 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}