A tutorial on solving single‐leader‐multi‐follower problems using SOS1 reformulations

Aussel, Didier; Egea, Cécile; Schmidt, Martin Article — Published Version A tutorial on solving single‐leader‐multi‐follower problems using SOS1 reformulations International Transactions in Operational Research Provided in Cooperation with: John Wiley & Sons Suggested Citation: Aussel, Didier; Egea, Cécile; Schmidt, Martin (2024) : A tutorial on solving single‐leader‐multi‐follower problems using SOS1 reformulations, International Transactions in Operational Research, ISSN 1475-3995, Wiley Periodicals, Inc., Hoboken, NJ, Vol. 32, Iss. 3, pp. 1227-1250, https://doi.org/10.1111/itor.13466 This Version is available at: https://hdl.handle.net/10419/313686 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by-nc-nd/4.0/ Intl. Trans. in Op. Res. 32 (2025) 1227–1250 DOI: 10.1111/itor.13466 INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH A tutorial on solving single-leader-multi-follower problems using SOS1 reformulations Didier Aussela,∗, Cécile Egeaband Martin Schmidtc aLaboratoire PROMES UPR CNRS 8521, University of Perpignan, Tecnosud, Perpignan 66100, France bINSA Rouen Normandie, 685 Avenue de l’Université, Saint-Etienne-du-Rouvray 76800, France cDepartment of Mathematics, Trier University, Universitätsring 15, 54296, Trier, Germany E-mail: [email protected][Aussel]; [email protected][Egea]; [email protected][Schmidt] Received 25 July 2023; received in revised form 6 February 2024; accepted 13 April 2024 Abstract In this tutorial, we consider single-leader-multi-follower games in which the models of the lower-level players have polyhedral feasible sets and convex objective functions. This situation allows for classic Karush–Kuhn– Tucker reformulations of the separate lower-level problems, which lead to challenging single-level reformulations of Mathematical Programing with Complementarity Constraints (MPCC) type. The main contribution of this tutorial is to present a ready-to-use reformulation of this MPCC using special-ordered-sets of type 1 (SOS1) conditions. These conditions are readily available in all modern mixed-integer linear optimization solvers that solve the single-leader-multi-follower problem to optimality. After formally stating the problem class under consideration as well as deriving its reformulations, we present explicit Python code that shows how these techniques can be realized using the solver Gurobi. Finally, we also show the effect of the SOS1based reformulation using the real-world example of industrial eco-park modeling. 1. Introduction For many practical applications, it is necessary to model the noncooperative behavior of multiple agents, which usually leads to a Nash game (see Nash, 1950) or to its generalized version; see, for example, Facchinei and Kanzow (2010). However, these game-theoretic models are only applicable in situations in which the competitive agents act simultaneously. If the agents are ordered in a hierarchical way, the resulting model is a so-called multi-leader-multi-follower (MLMF) game—a problem class that dates back to the seminal publications by von Stackelberg (1934, 1952). In such games, the set of agents is split into two groups, the leaders and the followers, both interacting in a noncooperative way. The leaders, who usually represent the authorities or the most influencing agents, need to take into account the reactions of the followers, whose problems and, thus, decisions depend on those of the leaders. This setup is also often referred to as a bilevel game, and the general solution concept on both levels is that of a (generalized) Nash equilibrium. In other words, ∗Corresponding author. © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. This is an open access article under the terms of the Creative Commons Attribution-NonCommercial-NoDerivs License, which permits use and distribution in any medium, provided the original work is properly cited, the use is non-commercial and no modifications or adaptations are made. 1228 D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 the MLMF game is a (generalized) Nash game among Stackelberg leaders. Note that alternative approaches to Nash equilibrium interactions have been recently considered in Allevi et al. (2024) and Aussel and Chaipunya (2024). Obviously, these models are extremely challenging—both in theory and in practice. We refer to Aussel and Svensson (2020) for a recent overview. The easiest (but still challenging) instantiation of such models is a bilevel optimization problem, that is, a single-leader-single-follower (SLSF) model. This field made enormous progress in the last years and decades; see, for example, the recent books by Dempe and Zemkoho (2020), Dempe et al. (2015), and the recent survey by Kleinert et al. (2021a) for SLSF games, Aussel and Svensson (2020) for single-leader-multi-follower (SLMF) games, and Aussel and Svensson (2018) and Aussel et al. (2021) for MLMF games. In this tutorial, we focus on the intermediate setting in which there is a single leader but multiple followers, that is, we consider SLMF games. In particular, we present and explain a powerful technique to obtain a single-level reformulation of the SLMF game that uses the so-called specialordered-sets of type 1 (SOS1), which date back to Beale and Tomlin (1970) and which have been used for the first time in bilevel optimization in Fortuny-Amat and McCarl (1981). The key idea is to use the Karush–Kuhn–Tucker (KKT) conditions of the lower-level players and reformulate the nonlinear and nonconvex KKT complementarity conditions by using SOS1 conditions. This approach received increasing attention in the last years in bilevel optimization (Kleinert and Schmidt, 2023) since it does not require to determine correct big-Mvalues, which is needed if one rewrites the KKT complementarity conditions using additional binary variables; see, for example, Pineda and Morales (2019) and Kleinert et al. (2020) for the drawbacks of the big-Mapproach. An alternative approach, proposed in Leyffer and Munson (2010), consists of a penalization method based on the complementarity conditions of the followers. The advantages of the SOS1 approach are the following: (i) It is easy to implement. We will present Python code that shows how to implement the resulting single-level reformulation of a given SLMF game and then solve it with Gurobi. (ii) The SOS1 functionality is widely available. Not only Gurobi but also other solvers for mixedinteger optimization such as CPLEX or SCIP support this modeling technique. We choose one specific combination of programming language (Python) and solver (Gurobi)heretobeasspecific as possible. However, the mathematical concepts can, of course, also be implemented with other programming languages and solvers as well. (iii) There is no need for computing big-Mvalues or a penalization parameter. (iv) In combination with other ready-to-use techniques from bilevel optimization, the approach is competitive with other classic techniques such as the big-Mapproach; see, for example, Kleinert and Schmidt (2023) and Kleinert et al. (2021b). The remainder of this tutorial is structured as follows. In Section 2, we formally present the problem statement and derive a first single-level reformulation based on the KKT conditions of the lower-level players. The SOS1-based reformulation of the single-level KKT reformulation is then briefly discussed in Section 3. This technique is then applied in Section 4 to two academic examples. Here, we also present Python code that shows how easy the implementation is. Afterward, in Section 5, we apply the SOS1 technique to a real-world SLMF game in the area of a circular industrial economy to show the applicability of the technique also for more realistic and larger instances. © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 1229 A comparison with an implementation of the Leyffer–Munson method on this application is also provided. Finally, we conclude in Section 6. 2. Problem statement and single-level reformulation As announced in the introduction, our aim is to propose a reformulation scheme based on the SOS1 approach to solve SLMF games. These problems, in their optimistic version, are given by min x,y1,... ,yNF(x,y) (1a) s.t. G(x,y)≥0,(1b) y:=(yν)ν∈[N]solves GNEP(x),(1c) where x∈Rn0is the vector of the leader’s decisions and yν∈Rnνis the variable vector of follower ν∈[N]:={1,... ,N}. The vector y=(yν)ν∈[N]∈Rnfcollects all decisions of all followers, that is, nf=ν∈[N]nν. Hence, we have F:Rn0×Rnf→Rand G:Rn0×Rnf→Rm0,where m0is the number of upper-level constraints. In what follows, we use the classic notation y−ν= (yμ)μ∈[N]\{ν}from game theory that collects all followers’ decisions except for those of player ν. Let us comment a bit more in detail on two important aspects of Model (1). First, the optimistic version of the bilevel game is considered here, which is formalized by the fact that the upper-level player also optimizes over the lower-level variables yin case that there are any multiplicities in the lower-level’s set of equilibria GNEP(x). For a more detailed discussion of the differences between the optimistic and pessimistic versions of SLMF games, we refer to Aussel and Svensson (2020). Moreover, let us note that we allow for so-called coupling constraints G, which are upper-level constraints that explicitly depend on lower-level variables y. Furthermore, GNEP(x) stands for the set of generalized Nash equilibria of the noncooperative game among the Nfollowers, where the optimization problem of the νth player is given by min yνfν(yν,x,y−ν) (2a) s.t. Dνyν≥e−Dν,0x− μ=ν Dν,μyμ,(2b) E0x+ N  μ=1 Eμyμ≥g(2c) with Dν∈Rmν×nν,Dν,0∈Rmν×n0,andDν,μ ∈Rmν×nμfor all μ= ν,ande∈Rmν. Moreover, we have E0∈Rm×n0,Eν∈Rm×nν,andg∈Rm. Problems (2) define a GNEP because the feasible set of every player explicitly depends on the decisions of the other players. This is different from classic Nash games in which only the objective functions depend on the other players’ decisions. However, let us remark that the approach proposed in this tutorial is also applicable to Nash equilibrium problems in the lower level as well. In Problem (2), (2b) is the private constraint of player ν, which may depend on the leader’s decision xand the decisions of all other lower-level players μ∈[N]\{ν}, © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. 1230 D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 and (2c) is the shared constraint of the GNEP at the lower level. For later reference, we denote thefeasiblesetoftheνth lower-level player by ν(x,y−ν). In this spirit, we also define −ν= μ∈[N]\{ν}μ(x,y−μ). The so-called shared constraint set is then given by :=(x,y)∈Rn0×Rnf:G(x,y)≥0andyν∈ν(x,y−ν)forallν∈[N]. Its projection onto the space of the leader variables is denoted by x:=x∈Rn0:∃ywith (x,y)∈. The class of SLMF games we tackle is quite large since the only restrictions are the following: • The functions Fand Gare continuous on Rn0×Rnf. •Foranyν∈[N], any x∈x,andanyy−ν∈−ν, the function f(·,x,y−ν) is convex and continuously differentiable on Rnν. • The feasible set of each follower is polyhedral, that is, it is defined by affine-linear functions. For any follower ν∈[N], the corresponding KKT conditions are given by ∇νfν(yν,x,y−ν)−(Dν)λν−(Eν)δν=0,(3a) Dνyν−e+Dν,0x+ μ=ν Dν,μyμ≥0,(3b) E0x+ N  μ=1 Eμyμ−g≥0,(3c) λν,δν≥0,(3d) (λν)⎛ ⎝Dνyν−e+Dν,0x+ μ=ν Dν,μyμ⎞ ⎠=0,(3e) (δν)⎛ ⎝E0x+ N  μ=1 Eμyμ−g⎞ ⎠=0.(3f) The KKT conditions of the lower-level problems are both necessary and sufficient for all players. In particular, we do not need any further constraint qualifications for the lower-level problems since the constraint sets are all polyhedral. Moreover, we assume that all linear problems are stated so that the linear independence constraint qualification (LICQ) holds. In the linearly constrained case considered here, this means that the row vectors of all active constraints are linearly independent. This can be ensured a priori in the linear case by, without loss of generality, assuming that the respective constraint matrices have full row rank; see, for example, the seminal textbooks by Nocedal and Wright (2006) or Bertsekas (2016) for an introduction to constraint qualifications. As a further consequence of the LICQ, all Lagrangian multipliers of all KKT points are uniquely determined. © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 1231 Remark 1. Taking a closer look at Constraint (3f) reveals that every lower-level player νhas an own dual variable δνfor the shared primal constraint. For many applications, this is a problem since the dual variables of shared constraints often define prices, which leads to economic ambiguities if every player sees a different price. As a remedy, Rosen (1965) introduced the concept of normalized or variational equilibria of a GNEP in which all the dual variables of the shared constraint need to be the same—hence leading to a well-defined price in the respective economic applications. Here, we are interested in variational equilibria of the GNEP in the lower-level problem and we thus need to impose δν=δfor all ν∈[N]. Hence, (3f) needs to be replaced by δ⎛ ⎝E0x+ N  μ=1 Eμyμ−f⎞ ⎠=0. Replacing the GNEP in the lower level by the concatenation of all KKT conditions of the lowerlevel players, we obtain the single-level reformulation min x,y,λ,δ F(x,y) (4a) s.t. G(x,y)≤0,(4b) ∇νfν(yν,x,y−ν)−(Dν)λν−(Eν)δν=0,ν∈[N],(4c) Dνyν−e+Dν,0x+ μ=ν Dν,μyμ≥0,ν∈[N],(4d) E0x+ N  μ=1 Eμyμ−g≥0,(4e) λν,δν≥0,ν∈[N],(4f) (λν)⎛ ⎝Dνyν−e+Dν,0x+ μ=ν Aν,μyμ⎞ ⎠=0,ν∈[N],(4g) δ⎛ ⎝E0x− N  μ=1 Eμyμ−g⎞ ⎠=0.(4h) Here and in what follows, we use the abbreviations y:=(yν)ν∈[N],λ:=(λν)ν∈[N],andδ:=(δν)ν∈[N]. Note that the single-level reformulation leads to an optimistic solution to the single-leader-multifollower problem. Theorem 2. Let (x∗,y∗)be a global optimal solution of the SLMF game (1). Then, there exists λ∗ and δ∗so that (x∗,y∗,λ ∗,δ∗)is a global optimal solution of the single-level reformulation (4). On the other hand, if (x∗,y∗,λ ∗,δ∗)is a global optimal solution of the single-level reformulation (4), then (x∗,y∗)is a global optimal solution of the single-leader multi-follower game (1). The proof is straightforward or can be deduced from Theorem 3.3.8 in Aussel and Svensson (2020). © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. 1232 D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 Remark 3. We finally discuss some potential generalizations of the above setting. 1. The setup and the main result can be generalized to convex instead of polyhedral feasible sets if Slater’s constraint qualification is satisfied since the corresponding KKT conditions of the followers are still necessary and sufficient. However, in light of the results by Aussel and Svensson (2019) and Dempe and Dutta (2012), one needs to be careful with the respective Lagrangian multipliers to actually obtain the correctness of Theorem 2. 2. The constraints of the lower-level problems would stay linear if one allows for multilinear terms. Hence, the classic KKT reformulation can still be applied. However, the resulting single-level reformulation would then inherit these multilinear terms. Since one optimizes over all follower variables in the single-level reformulation, this would then lead to nonconvex nonlinearities. The analog applies to the lower-level objective functions, where we, however, lose one degree of the multilinear polynomial by taking the respective gradient in the KKT conditions. 3. SOS1-based reformulation The main burden in Problem (4) is the two complementarity constraints (4g) and (4h). These two nonlinear and nonconvex constraints can be modeled using SOS1-type constraints and can thus be solved using Gurobi or CPLEX to global optimality without choosing any big-Ms; see, for example, Kleinert and Schmidt (2023). To this end, we introduce auxiliary variables sν iν≥0forallν∈[N]andalliν∈[mν]andtj≥0for all j∈[m] as well as the following SOS1 conditions: λν iνand sν iν=⎛ ⎝Dνyν−e+Dν,0x+ μ=ν Aν,μyμ⎞ ⎠iν are SOS1 for all ν∈[N]andiν∈[mν]aswellas δjand tj=E0x− N  ν=1 Eνyν−gj are SOS1 for all j∈[m]. Let us recall that a SOS1-type constraint defines a set of variables for which at most one variable in the set may take a value other than zero. Remark 4. If for some of these components, we have good (and, of course, provably correct) upper bounds (“big-Ms”) for the dual variables λν iνand δjas well as for the corresponding primal expressions, we can also use the classic big-M-like reformulation for these components. © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 1233 4. Academic examples Our aim in this section is to show, via two simple examples, how simple the implementation of the SOS1 approach is for the computation of solutions of SLMF games. While the first example is completely linear, the second one also contains nonlinearities. In the spirit of a tutorial and for each example, the single-level/MPCC (Mathematical Programing with Complementarity Constraits) reformulation of the SLMF game will be given, then the Python code corresponding to the numerical resolution of the MPCC will be fully described, and the optimization results will be presented. 4.1. Example #1 Let us start with a very simple and completely linear example of a SLMF game. Three agents are considered here. Thus, we have one leader and two followers. The leader’s problem is given by min x,y1,y2,y3 2x+y1+y2−y3 s.t. x≥1, ysolves GNEP(x), where the GNEP in the lower level consists of two players—the first follower has a two-dimensional optimization problem while the second follower solves the one-dimensional problem: Player 1 Player 2 miny1,y2x−2y1−y2miny3x+y1+y2+y3 s.t. y1≥y2+y3s.t. y3≥x y1≤x This bilevel problem admits only one optimal solution ( ¯ x,¯ y1,¯ y2,¯ y3)=(1,1,0,1). The corresponding KKT conditions of the first and second followers are given as follows: KKTs of Player 1 KKTs of Player 2 −2−λ1 1+λ1 2=01−λ2 1=0 −1+λ1 1=0y3−x≥0 y1−y2−y3≥0λ2 1(y3−x)=0 x−y1≥0λ2 1≥0 λ1 1(y1−y2−y3)=0 λ1 2(x−y1)=0 λ1 1,λ 1 2≥0 © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. 1234 D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 Thanks to Theorem 2, the single-level reformulation is equivalent to the SLMF game and reads min x,y1,y2,y3 2x+y1+y2−y3 s.t. x≥1, −2−λ1 1+λ1 2=0, −1+λ1 1=0, y1−y2−y3≥0, x−y1≥0, λ1 1(y1−y2−y3)=0, λ1 2(x−y1)=0, λ1 1,λ 1 2≥0, 1−λ2 1=0, y3−x≥0, λ2 1(y3−x)=0, λ2 1≥0. Finally, if we use the nonnegative slack variables s1 1=y1−y2−y3,s1 2=x−y1,s2 1=y3−x, we obtain the SOS1-based single-level reformulation min x,y,λ,s2x+y1+y2−y3 s.t. x≥1, −2−λ1 1+λ1 2=0, −1+λ1 1=0, y1−y2−y3≥0, x−y1≥0, SOS1(λ1 1,s1 1), SOS1(λ1 2,s1 2), s1 1=y1−y2−y3,s1 1≥0, s1 2=x−y1,s1 2≥0, © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 1241 Table 1 Meaning and unit of all constants Symbol Meaning Unit MiContaminant load of process ig/h βPolluted water discharge cost $/ton δPolluted water pumping cost $/ton Ci,out Maximum contaminant concentration allowed in the outlet of processes ippm Ci,in Maximum contaminant concentration allowed in the inlet of processes ippm Further following Salas et al. (2020), each company controls the amount of polluted water it will send to the other companies or the sink node of the water network. Recall that the production level of each company is assumed to be constant. Thus, the model is built for a single hour. For any (i,j)∈I2 P, let us denote by •Fi,jthe water flux going from company ito company jand by •Fi,0the water flux going from company ito sink node. Thus, the variable of company iis the vector Fi,•composed of all the fluxes exiting from company i. Now, the manager of the IEP, that is, the leader, decides about the implementation of connections between companies and this decision is represented by the binary matrix ygiven by yi,j=1,the implementation of a pipe between iand jis decided, 0,otherwise, for all (i,j)∈I2 P. Note that we will later always set yi,i=0foralli∈IP. The optimization problem of each company i∈IPcan then be expressed as a parameterized linear problem in which the parameters are the binary design variables yof the leader and the fluxes F−i,•of the other companies. The meaning and the unit of each of the constant terms used in the following model that are not explained explicitly in the text are given in Table 1. Formally, the problem of company ireads © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. 1242 D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 Here and in what follows, cis the cost of freshwater. Note that the objective functions of the followers as well as all their constraints are linear. Moreover, note that in the variables defined above, the amount of freshwater reaching each process/company is not given. Indeed, as observed by Salas et al. (2020), taking into account the contaminant mass balance and since the production level is fixed, the amount of freshwater needed for company ican be described as a function of the other variables: zi(F−i)=1 Ci,out ⎛ ⎝Mi+ k∈IP (Ck,out −Ci,out)Fk,i⎞ ⎠.(5) For more details on the formulas used, we refer the interested reader to Ramos et al. (2016) and Salas et al. (2020). However, let us explain a bit more that the constant value Kis chosen in such a way that Fi,jis forced to be zero if yi,jis zero, and such that it guarantees the nonnegativity of Fi,j otherwise. Thus Khas to be larger than all of the feasible values of Fi,jand a natural choice is K= i∈IP Mi Ci,out , which corresponds to the sum of the natural resources used by companies if none of them participates in the eco-park. The leader aims to design the eco-park, that is, the leader decides on the topology of the IEP network in order to minimize the total amount of freshwater used by the companies, which is a proper measure of the overall ecological impact. This leads to the following optimistic SLMF game: min y,F i∈IP 1 Ci,out ⎛ ⎝Mi+ k∈IP (Ck,out −Ci,out)Fk,i⎞ ⎠ s.t. βFi,0−Mi Ci,out + k∈IPδ−c+cC k,out Ci,out Fk,i+δFi,k≤0,i∈IP, yi,i=0,i∈IP, F∈GNEP(y). The leader only has to guarantee that the production cost of each company will not increase when participating in the IEP, that is, the resulting production cost in case the IEP is implemented is not larger than the one the company would face in a “stand-alone situation”, that is, if not participating in the eco-park. Here, as above, GNEP(y) stands for the set of generalized Nash equilibria between the companies acting as followers in the lower level. This set is nonempty for at least one binary design matrix y—namely, the one corresponding to the stand-alone situation, which is given yi,j=0 for all (i,j)∈I2 P. © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 1243 5.2. MPCC reformulation As already explained in Section 2, the first step to solve an SLMF game is to build a reformulation as an MPCC by replacing the computation of a parameterized Nash equilibrium between the followers with the computation of solutions to the associated and concatenated KKT conditions. For thecaseoftheIEP,let =⎛ ⎜ ⎜ ⎜ ⎜ ⎝ (ηi,j)j∈I,i∈IP (θi,j)j∈I,i∈IP (κi)i∈IP (λi)i∈IP (μi)i∈IP ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ be the vector of the Lagrangian multipliers. With this notation at hand, the MPCC reformulation is thus given by min y,F,  i∈IP zi(F−i) s.t. β(Fi,0−Mi Ci,out )+ k∈IPδ−c+cCk,out Ci,out Fk,i+δFi,k≤0,i∈IP, yi,i=0,i∈IP, (F,)∈(KKT)i,i∈IP, where, for any i∈IP, the set (KKT)iis given by all points satisfying δ−ηi,j+θi,j−κiCi,out −λiCi,in =0,j∈IP, β−ηi,0+θi,0−κiCi,out −λiCi,in =0, ηi,jFi,j=0,j∈I, θi,j(Kyi,j−Fi,j)=0,j∈I, λi⎛ ⎝Ci,in  j∈I Fi,j− k∈IP Ck,outFk,i⎞ ⎠=0, μi⎛ ⎝Mi− k∈IP (Ci,out −Ck,out)Fk,i⎞ ⎠=0, ηi,j≥0,j∈I, θi,j≥0,j∈I, λi≥0, © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. 1244 D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 μi≥0, Fi,j≥0,j∈I, Kyi,j−Fi,j≥0,j∈I, Mi+ k∈IP Ck,outFk,i−Ci,out  j∈I Fi,j=0, Ci,in  j∈I Fi,j− k∈IP Ck,outFk,i≥0, Mi− k∈IP (Ci,out −Ck,out)Fk,i≥0. Our aim in the forthcoming Subsections 5.3 and 5.4 is to see how the SOS1 as well as the Leyffer– Munson approach can be compared on a reasonably large application case of designing an IEP. The test IEP used in these two subsections is composed of 15 companies and the values of the constant terms of the model are given in the Appendix A. All models have been implemented using Python 3.10.9 and have been solved using Gurobi version 10.0.2 on a DELL 5310 Latitude with an i5 Intel Core CPU with 16 GB RAM, and an Intel(R) UHD Graphics GPU. 5.3. The SOS1 approach We now reformulate the MPCC to get rid of the nonlinear and nonconvex KKT complementarity constraints. The idea is, as shown in Section 3, to rewrite them using SOS1 constraints. Thus, for each inequality constraint gi,k(y,F)≥0 of the optimization problem of company i, one introduces a new real-valued variable si,kand the additional constraint si,k=gi,k(y,F). Moreover, the corresponding KKT complementarity constraint μi,kgi,k(y,F)=0 of the system (KKT)iis replaced by the SOS1 condition SOS1(si,k,μ i,k). As an example, in (KKT)i, the complementarity constraint μi⎛ ⎝Mi− k∈IP (Ci,out −Ck,out)Fk,i⎞ ⎠=0 is replaced by si,k=Mi− k∈IP (Ci,out −Ck,out)Fk,iand SOS1(si,k,μ i). © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 1245 Fig. 2. The optimal IEP design for 15 participating companies. The resulting optimization problem with 15 companies has 1275 continuous and 240 binary variables as well as 1530 constraints—including 510 SOS1 conditions. Gurobi solves the problem of global optimality in three seconds. The resulting IEP design is given in Fig. 2. The white nodes represent the companies participating in the eco-park and the red node is the sink node (SN). The edges represent the built connections between the respective companies in the IEP. The amount of fresh, that is, unpolluted, resource is not displayed. However, the optimal value for the designed IEP shows that, compared to the stand-alone situation, 32.72 % of the freshwater resource is saved thanks to the implementation of the IEP structure. 5.4. The penalization method by Leyffer and Munson and a comparison To assess the performance of the SOS1 reformulation, we solve the same IEP problem using the Leyffer–Munson reformulation; see Leyffer and Munson (2010). This method is based on a © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. 1246 D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 penalization technique in which the original objective function is also extended to penalize the violation of the KKT complementarity constraints, which are then deleted from the set of constraints. By doing so, the new objective function is nonlinear while the new constraint set is now convex. Starting from the MPCC reformulation of Subsection 5.2, the notation qi(y,Fi,F−i)=⎛ ⎜ ⎜ ⎝ (Fi,j)j∈I Kyi,j−Fi,jj∈I Ci,in j∈IFi,j−k∈IPCk,outFk,i Mi−k∈IP(Ci,out −Ck,out)Fk,i ⎞ ⎟ ⎟ ⎠ is used for i∈IP. We introduce slack variables s:=(si)i∈IPand reformulate the KKT complementarity conditions as qi(y,Fi,F−i)−si=0, 0≤i⊥si≥0, where iis the subvector of referring to company iand only containing Lagrangian multipliers for inequality constraints. Using the Leyffer–Munson approach, the IEP problem is now formulated as min y,,s i∈IP zi(F−i)+ρ i∈I s ii s.t. β(Fi,0−Mi Ci,out )+ k∈IPδ−c+cCk,out Ci,out Fk,i+δFi,k≤0,i∈IP, yi,i=0,i∈IP, qi(y,Fi,F−i)=si,i∈IP, i≥0,i∈IP, si≥0,i∈IP, δ−ηi,j+θi,j−κiCi,out −λiCi,in =0,i,j∈IP, β−ηi,0+θi,0−κiCi,out −λiCi,in =0,i∈IP, Mi+ k∈IP Ck,outFk,i−Ci,out  j∈I Fi,j=0,i∈IP, which can then be solved with state-of-the-art solvers for mixed-integer nonlinear optimization problems (MINLPs). We do this by using Gurobi again, for which we have to change its NonConvex parameter to 2 so that Gurobi is able to handle the given nonconvex MINLP. It is now important to notice that the penalization coefficient ρplays a fundamental role since it must be chosen sufficiently large for the violation to be forced to be zero in an optimum, ensuring the equivalence between the above model and the initial formulation of the IEP problem. Since a © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 1247 Table 2 Gaps and total runtime (in minutes) of solving depending on ρand warmstart. We set the penalty parameter ρ=10n Warmstart n=1n=2n=3n∈{4,5,6}n=7Totaltime Yes 1.98 % 3.02 % 1.32 % 1.32 % ✔48 No 1.98 % 4.24 % 4.77 % 1.32 % ✗52 provably correct threshold for the parameter being large enough is usually not known in advance, one often tries to increase the penalty parameter ρiteratively. This, however, requires the solution of multiple MINLPs and can thus be computationally expensive. For the specific IEP problem at hand, we conducted a sensitivity analysis on the value of ρ,that is, we tested values ρ=10nfor some n∈N. Table 2 lists the total runtimes for all problems. We set the maximum runtime to eight minutes for each ρand try to solve the model without and with warmstart, that is, we then use the solution of the last run as an initialization for the current run. For almost all runs, we are not able to solve the problem of global optimality within the time limit. In these cases, the respective optimality gaps are given in the table. We note that, with or without the warmstart, the solver takes around 50 minutes to solve all problems, which is significantly longer than the runtime of the SOS1 method. Moreover, not using warmstarts leads to points for n=7 that violate KKT complementarity conditions. Hence, the sum of the KKT complementarity constraints in the extended objective function is positive and the obtained point is, consequently, not a solution of the SLMF game. Using warmstarts, we get a solution of the SLMF game for n=7. It is also interesting to note that the Leyffer–Munson reformulation of the IEP with 15 companies generates a problem with 1515 real-valued variables and 240 binary variables, thus around 250 continuous variables more than for the SOS1 formulation. Of course, it does not contain any SOS1 conditions. The comparison of the SOS1 and the Leyffer–Munson method on this specific IEP example shows that the SOS1 can be more efficient and, more importantly, does not need the determination of a specific parameter, which is required for ρfor the penalty approach. Hence, the penalization approach faces a similar difficulty as the determination of the M-parameter in the “big-M” method. 6. Conclusion SLMF games naturally appear in many decision-making processes including noncooperative and hierarchical aspects. Recent results from bilevel optimization paved the way for a ready-to-use single-level and SOS1-based reformulation of these models that can be solved to global optimality by modern branch-and-cut solvers such as Gurobi. We present two academic examples including Python code that exemplify the usage of the SOS1 technique. Moreover, we discussed the application of this reformulation for solving a real-world problem from IEP modeling. One of the main advantages of the SOS1-based reformulation is that there is no need for deriving provably correct big-Mvalues or a sufficiently large penalty parameter, which is required if KKT complementarity constraints are rewritten using further binary variables for modeling the © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. 1248 D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 corresponding disjunction or if the Leyffer–Munson penalty approach is used. However, the SOS1based reformulation might lead to slower performance. Hence, an important topic for future research is how to strengthen the resulting single-level reformulation, for example, by generalizing the valid inequalities given in Kleinert et al. (2021b) and Audet et al. (2007a, 2007b) to the case of SLMF games. For the eco-park example, however, we see that the SOS1 approach leads to a mixed-integer linear model (instead of a mixed-integer nonlinear one that needs to be solved in the Leyffer–Munson approach), and the runtimes are thus significantly faster for the SOS1 approach for this specific application. Acknowledgments The first author would like to thank the Fondation Mathématique Jacques Hadamard for the financial support through the PGMO project “Numerical methods for bilevel problems: theory, numerical analysis and energy management applications (NuMeBi).” References Allevi, E., Aussel, D., Riccardi, R., Scopelliti, D., 2024. Single-leader-radner-equilibrium: a new approach for a class of bilevel problems under uncertainty. Journal of Optimization Theory and Applications 200, 344–370. Audet, C., Haddad, J., Savard, G., 2007a. Disjunctive cuts for continuous linear bilevel programming. Optimization Letters 1, 3, 259–267. Audet, C., Savard, G., Zghal, W., 2007b. New branch-and-cut algorithm for bilevel linear programming. Journal of Optimization Theory and Applications 134, 2, 353–370. Aussel, D., Bouza, G., Dempe, S., Lepaul, S., 2021. Genericity analysis of multi-leader-disjoint-followers game. SIAM Journal on Optimization 31, 3, 2055–2079. Aussel, D., Cao Van, K., Salas, D., 2023. Optimal design of exchange water networks with control inputs in eco-industrial parks. Energy Economics 120, 106480. Aussel, D., Chaipunya, P., 2024. Variational and quasi-variational inequalities under local reproducibility: solution concept and applications. Aussel, D., Svensson, A., 2018. Some remarks about existence of equilibria, and the validity of the EPCC reformulation for multi-leader-follower games. Journal of Nonlinear and Convex Analysis 19, 7, 1141–1162. Aussel, D., Svensson, A., 2019. Towards tractable constraint qualifications for parametric optimisation problems and applications to generalised Nash games. Journal of Optimization Theory and Applications 182, 404–416. Aussel, D., Svensson, A., 2020. A short state of the art on multi-leader-follower games. In Dempe, S., Zemkoho, A. (eds) Bilevel Optimization. Springer International Publishing, Cham. pp. 53–76. Beale, E.M.L., Tomlin, J.A., 1970. Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. In Lawrence, J. (ed.), Proceedings of the Fifth International Conference on Operational Research. Tavistock Publications, London, pp. 447–454. Bertsekas, D.P., 2016. Nonlinear Programming. Athena Scientific Belmont, Nashua, NH. Boix, M., Montastruc, L., Catherine, A.P., Domenech, S., 2015. Optimization methods applied to the design of ecoindustrial parks: a literature review. Journal of Cleaner Production 87, 303–317. Boix, M., Montastruc, L., Pibouleau, L., Azzaro-Pantel, C., Serge, D., 2012. Industrial water management by multiobjective optimization: from individual to collective solution through eco-industrial parks. Journal of Cleaner Production 22(1), 85–97. Dempe, S., Dutta, J., 2012. Is bilevel programming a special case of a mathematical program with complementarity constraints? Mathematical Programming 131, 1–2, 37–48. © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 1249 Dempe, S., Kalashnikov, V., Pérez-Valdés, G.A., Kalashnykova, N., 2015. Bilevel Programming Problems. Springer, Berlin. Dempe, S., Zemkoho, A., 2020. Bilevel Optimization: Advances and Next Challenges. Springer International Publishing, Cham. Ehrgott, M., 2005. Multicriteria Optimization. Springer, Berlin. Facchinei, F., Kanzow, C., 2010. Generalized Nash equilibrium problems. Annals of Operations Research 175, 1, 177–211. Fortuny-Amat, J., McCarl, B., 1981. A representation and economic interpretation of a two-level programming problem. The Journal of the Operational Research Society 32, 9, 783–792. Kleinert, T., Labbé, M., Ljubi´ c, I., Schmidt, M., 2021a. A survey on mixed-integer programming techniques in bilevel optimization. EURO Journal on Computational Optimization 9, 100007. Kleinert, T., Labbé, M., Plein, F., Schmidt, M., 2020. There’s no free lunch: on the hardness of choosing a correct Big-M in bilevel optimization. Operations Research 68, 6, 1716–1721. Kleinert, T., Labbé, M., Plein, F., Schmidt, M., 2021b. Closing the gap in linear bilevel optimization: a new valid primaldual inequality. Optimization Letters 15, 1027–1040. Kleinert, T., Schmidt, M., 2023. Why there is no need to use a Big-Min linear bilevel optimization: a computational study of two ready-to-use approaches. Computational Management Science 20, 3. Leyffer, S., Munson, T., 2010. Solving multi-leader-common-follower games. Optimization Methods & Software 25, 4-6, 601–623. Nash, J.F., 1950. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36, 1, 48–49. Nocedal, J., Wright, S.J., 2006. Numerical Optimization (2nd edn.). Springer, Berlin. Pineda, S., Morales, J.M., 2019. Solving linear bilevel problems using big-ms: Not all that glitters is gold. IEEE Transactions on Power Systems 34, 3, 2469–2471. Ramos, M., Boix, M., Aussel, D., Montastruc, L., Domenech, S., 2016. Water integration in eco-industrial parks using a multi-leader-follower approach. Computers & Chemical Engineering 87, 190–207. Rosen, J.B., 1965. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33, 3, 520– 534. Salas, D., Van, K.C., Aussel, D., Montastruc, L., 2020. Optimal design of exchange networks with blind inputs and its application to Eco-industrial parks. Computers & Chemical Engineering 143, 107053. von Stackelberg, H., 1934. Marktform und Gleichgewicht. Springer, Berlin. von Stackelberg, H., 1952. Theory of the Market Economy. Oxford University Press, Oxford, UK. Appendix A: Calibration of the IEP text example The meaning, unit, and values of the constants in the test example for the IEP model with 15 companies are given in Table A1. Table A1 Specific data for the IEP problem used in the numerical experiments Meaning Unit Value PNumber of companies — 15 MiContaminant load of process ig/h (A1) cfreshwater cost $/ton 0.01 βPolluted water discharge cost $/ton 0.22 δPolluted water pumping cost $/ton 0.01 Ci,out Maximum contaminant concentration allowed in the outlet of processes ippm (A3) Ci,in Maximum contaminant concentration allowed in the inlet of processes ippm (A2) © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies. 1250 D. Aussel et al. / Intl. Trans. in Op. Res. 32 (2025) 1227–1250 The values of the contaminant load are given by M=(7500,6000,5000,30000,4000,2500,2200, 500,30000,4000,2000,2000,5000,30000,13000) (A1) and the maximum contaminant concentrations are given by (A2) as well as by (A3) © 2024 The Authors. International Transactions in Operational Research published by John Wiley & Sons Ltd on behalf of International Federation of Operational Research Societies.