# An Exact Algorithm Based on the Kuhn–Tucker Conditions for Solving Linear Generalized Semi-Infinite Programming Problems

Authors: Abraham Barragán; José-Fernando Camacho-Vallejo
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Optimization problems containing a finite number of variables and an infinite number of constraints are called semi-infinite programming problems. Under certain conditions, a class of these problems can be represented as bi-level programming problems. Bi-level problems are a particular class of optimization problems, in which there is another optimization problem embedded in one of the constraints. We reformulate a semi-infinite problem into a bi-level problem and then into a single-level nonlinear one by using the Kuhn–Tucker optimality conditions. The resulting reformulation allows us to employ a branch and bound scheme to optimally solve the problem. Computational experimentation over well-known instances shows the effectiveness of the developed method concluding that it is able to effectively solve linear semi-infinite programming problems. Additionally, some linear bi-level problems from literature are used to validate the robustness of the proposed algorithm.


---

## Body

## 1. Introduction

The more general case of semi-infinite programming (SIP) problems occurs when a finite number of semi-infinite constraints are considered. Each constraint consists in a set of constraints indexed by a set of infinite cardinality, in this case, a generalized semi-infinite programming (GSIP) problem arises. Previous work has been reported for problems that involve continuous and differentiable functions [1–3]. Therefore, linear generalized semi-infinite programming (LGSIP) problems can be considered as a particular case of GSIPs, where all the defining functions are sufficiently smooth. In [4], an inverse optimization approach is proposed to solve a LGSIP. In general, semi-infinite programming is a very challenging field and keeps attracting the attention of researchers. For instance, a review of solution methods and different applications appear in [5]. Similarly, GSIPs have been proposed to model a wide variety of real-life applications, such as design centering, optimization of assembly lines, time minimal control, and robust optimization [6].A basic reference on this topic is [7], and a review of classical methods in GSIP appears in [8]. When the set Yx=Y does not depend on the variable x, we have a standard semi-infinite programming (SSIP) problem which is another especial case in GSIP. Regarding the latter problems, in [9], an extensive study on their main characteristics is presented, and, in [10, 11], some algorithmic aspects are reviewed. Recent results for a linear case are presented in [12–15]. For a wide overview of SSIP applications, we refer to [7]. Some applications of GSIP can be found in the maneuverability problem in robotics (see [16]) and the reverse Chebyshev approximation (see [17, 18]).Theory and solution methods for SIPs are strongly related to their corresponding bi-level formulation. The connection between both classes of problems relies in the fact that, under certain conditions, semi-infinite problems can be reformulated as bi-level programming ones [1, 3]. Bi-level programming (BLP) problems have been used to model applications widely, for example, in location, network design, pricing, humanitarian logistics, and telecommunication systems, among others [19, 20]. BLP can be seen as a hierarchized situation in which the decision maker with a higher hierarchy (leader) aims to optimize his/her own objective function depending on its decisions and the decisions taken by the decision maker with a lower hierarchy (follower). In this case, the follower considers his/her own optimization problem but parameterized according to the leader’s decision. It is essential to mention that BLP cannot be seen as two-stage optimization problems, since the leader’s decision restricts the follower’s problem, and then, the follower’s decision impacts the leader’s objective function. Hence, both decisions are interrelated but respecting a predefined hierarchy among the decision makers.As it is mentioned above, there exist few methods for solving generalized semi-infinite optimization that exploit the closely relationship obtained from the bi-level structure of the problems [8]. Despite the abovementioned, the proposed methods that solve GSIPs are scarce and the computational experimentations are limited. The latter motivated us to conduct this research. Hence, in order to benefit from the relationship between GSIPs and BLPs, the following idea could be followed: reformulate the lower-level problem by some of the well-known methods. For instance, in the convex case, the Kuhn–Tucker optimality conditions are commonly used. After that, some of the classical algorithms used to solve linear bi-level problems, such as the Kth-best algorithm, Kuhn–Tucker approach, complementarity approach, variable elimination algorithm, and penalty function approach [21, 22], could be implemented to solve the reformulated GSIP. In this case, we decided to implement a different exact approach, which is based on the branch and bound method, which have been used to successfully solve nonlinear SIPs (see [23]).Other methods that have been used to solve GSIPs via the bi-level formulation differ from each other on the lower-level reformulations. For instance, Stein [2] uses equilibrium constraints to model the lower level. In [8], complementarity constraints are employed to replace the lower level. Numerical methods to approximate the original problem are generated by substituting these complementarity constraints by smooth ones [3, 24]. That method has been applied to solve centering design and lapidary cutting problems (see [1, 25], respectively). Another approach is to reformulate the lower level by its corresponding dual problem. In [24], Wolfe’s dual problem is considered. It is shown that, under additional conditions, the resulting problem is numerically tractable. Theoretically, feasible direction methods and discretization algorithms [6] have been also proposed to solve GSIPs. However, the computational experimentation is complicated when having multidimensional set of indices. Most of these methods are developed to solve particular class of GSIPs or made significant assumptions preventing their reproducibility, in general. On the contrary, the algorithm herein proposed is motivated by the ideas given in [3] for solving a general case of semi-infinite programming problems but neither a detailed description nor results are reported there. Hence, a detailed step-by-step description of the algorithm is included to facilitate its implementation and reproducibility.The main contribution of this research is the proposal of an algorithm that can be used to solve a particular class of generalized semi-infinite programming problems. In particular, linear problems consider a semi-infinite constraint. The proposed method exploits the conditions that allow a generalized semi-infinite problem to be handled as a bi-level programming one. In order to apply this method, the representation of the semi-infinite problem as a bi-level one is required. Then, its Kuhn–Tucker optimality conditions are used to reformulate the bi-level problem into a single-level one, which is solved via a branch-and-bound scheme. The effectiveness of the algorithm is shown through computational experimentation. To validate the obtained results, we analytically solve the tested linear semi-infinite programming problems, showing the algebraic and graphical solutions coincide with the solution obtained by the algorithm.The remainder of this study is organized as follows. In Section2, some preliminaries and the notation considered throughout this research is presented. In Section 3, the developed algorithm is described. Therefore, the computational experimentation, in which the effectiveness of the algorithm is validated, is presented in Section 4. Additionally, some examples are solved in a geometric and algebraic way to corroborate the obtained solution. Conclusions that include important remarks regarding the topic investigated in this study and further research directions are presented in Section 5.


## 2. Preliminaries

Let us introduce the necessary notation for this study, as well as some concepts, and necessary results on GSIP and BLP that will be used.Throughout this study, we considera,c,c1,c2⊂ℝn, b,d1,d2⊂ℝm, b0∈ℝ, b1∈ℝp, b2∈ℝq, A1 is a p×n-matrix, B1 is a p×m-matrix, A2 is a q×n-matrix, and B2 is a q×m-matrix.We consider linear generalized semi-infinite programming (LGSIP) problems which are defined as(1)SIP:minxcTxs.t.aTx+bTy≤b0,for allyinYx,where(2)Yx=y|A2x+B2y≤b2.Unless otherwise stated, we will considerx∈X and y∈Y0, where the sets X and Y0 will represent additional restrictions on the decision variables. In particular, X⊆ℝ+n and Y0⊆ℝ+m, that is, xi≥0 and yj≥0, for all i=1,…,n and j=1,…,m, respectively. Furthermore, we will consider that X=domY, where domY=x|Yx≠∅; this condition can always be satisfied by adding in X appropriate extra conditions (such as xi≤δ or others depending only on the variables xi).Following the notation presented in [21], a linear bi-level programming (LBLP) problem is defined as(3)BL:minxc1Tx+d1Ty,s.t.A1x+B1y≤b1,andysolves,Qx:minyc1Tx+d1Ty,s.t.y∈Yx,where Yx is defined as in SIP.With the conditions onX, the problem SIP can be considered as a LBLP problem with the special structure that lower-level objective function is obtained with the upper-level constraint. The problem that results is presented next (see [3]):(4)BLSIP:minxcTx,s.t.aTx+bTy≤b0,andysolves,Qx:minx−aTx−bTy,s.t.y∈Yx.In order to have well-defined considered problem, we assume that the set-valued mappingY:ℝn⟶2ℝm is uniformly compact on ℝn. In other words, there exists a ball Bεx¯=x∈ℝn|x−x¯≤ε with ε>0 for any x¯∈ℝn such that cl∪Bεx¯Yx is compact, where clX denotes the topological closure of X. Therefore, under these assumptions, the mapping Y is closed and upper semicontinuous in the sense of Berge, and X is a closed set. It is important to remark that, by considering the latter condition, the lower-level problems Qx, x∈X, always has an optimal solution.The following sets are associated with a bi-level problem. LetSx=y|yis a solution global ofQx be the set of solutions of Qx. Consider S=x,y|y∈Sx as the solution graph of Q, and G=x,y|aTx+bTy≤b0 as the constrained set for the upper level. Also, let MBL=x,y|x,y∈G,y∈Sx be the feasible set of BLP.Now, the concepts associated with the semi-infinite problem defined in the introduction are presented. First, its feasible set is defined as follows:(5)MSIP=x∈X|aTx+bTy≤b0,y∈Yx.Under the assumptions made on the setX, we have (see [3]) MSIP=prxMBLSIP, where prx denotes the orthogonal projection onto the space ℝn.The latter equality allows the use of methods proposed to solve LBLP problems to obtain the solution of LGSIP problems.As it is mentioned in the introduction, the main idea of the algorithms designed to solve linear bi-level problems is to reformulate the bi-level problem into an equivalent single-level one. The latter can be achieved by using the important result described next.Consideru∈ℝq and v∈ℝm as the corresponding dual variables of the constraints associated with the lower-level problem, that is, constraints represented by equation (3). Using the notation of problem BLSIP, we adapt the following proposition given in [21].Proposition 1.
A necessary condition forx∗,y∗ to solve BLSIP is that there exist (column) vectors u∗ and v∗ such that x∗,y∗,u∗,v∗ solves(6)minxcTx,(7)s.t.aTx+bTy≤b0,(8)uTB2−v=b,(9)uTb2−A2x−B2y+vTy=0,(10)A2x+B2y≤b2,(11)x≥0,y≥0,u≥0,v≥0.This single-level reformulation is valid in bi-level programming when the lower-level problem is convex. Hence, it not always exists for all the classes of BLP problems. However, in this study, we are considering the linear case, so the problems can be reformulated under this scheme.


## 3. An Algorithm that Uses the Kuhn–Tucker Optimality Conditions and a Branch-and-Bound Scheme for Solving LGSIPs

It is well known that one of the most common approaches to solve a linear bi-level problem is by using its equivalent single-level reformulation, which is given in equation (5)–(10). It can be appreciated that the resulting single-level model is a nonlinear one (see equation (9)), which complicates the optimization process. Noting that equation (9) is the only nonlinear constraint, it is common to try to handle the reformulation without that equation instead of solving the reformulated nonlinear single-level model.One option to address the nonlinearity of the reformulated model is by omitting the nonlinear term (this results in a relaxation of the problem) and solve the resulting relaxed problem. For achieving this, let us consider all the inequalities that appear in the lower-level problem in the following manner:gix,y≥0, i=1,…,q+m. Also, it is identified that the nonlinear constraints uigix,y=0 (i=1,…,q+m, where uq+j=vj, j=1,…,m) imply the complementarity slackness constraints. Recall that the relaxed reformulation yields to a linear subproblem.After the resulting linear subproblem has been solved, it is checked if equation (9) holds. If so, the optimal solution obtained is a feasible solution of problem given by equation (5)–(10), which implies that it is a feasible solution for the bi-level problem derived from the SIP; if not, an approach based on a branch and bound scheme is implemented to try to satisfy the complementarity slackness constraints. To achieve the latter, an examination of all the possible combinations’ values that guarantee the complementarity slackness implicitly is conducted. A complete cycle of this procedure is called an iteration.The notation introduced in [21], which is the classical notation for an implicit enumeration, is used to describe the solution method herein considered. Let W=1,…,q+m be the set of indexes associated with the complementarity slackness terms (see equation (9)). Consider F⋅ as the objective function of the single-level reformulation, which corresponds to the upper-level’s objective function of the bi-level problem, and consider F¯ as the incumbent upper bound on the upper-level’s objective function. A subset of indexes Wk⊂W is considered at the kth level of the search tree, and also, a path Pk is used. The path indicates if either ui=0 or gi=0, for i∈Wk. The common sets Sk+, Sk−, and Sk0 of the implicit branch and bound are used. Therefore,(12)Sk+=i|i∈Wkandui=0,Sk−=i|i∈Wkandgi=0,Sk0=i|i∉Wk.The variablesui and gi, for which i∈Sk0, are considered as nonnegative when solving the relaxation of the single-level reformulated problem defined by equations (6)–(11). Recall that, in the aforementioned relaxation, equation (9) is omitted. Hence, the complementarity slackness constraint may be satisfied or not.The description of the algorithm based on a branch-and-bound scheme that considers the complementarity slackness constraints is presented next. It is important to emphasize that this algorithm is based in the Kuhn–Tucker approach for solving linear bi-level problems (see [21]). In nonlinear problems, Kuhn–Tucker conditions are used in globalization [26].(i)
Initialization: setk=0, Sk+=∅, Sk−=∅, Sk0=1,…,q+m, and F¯=∞.(ii)
Main step (in thekth iteration): set ui=0, for i∈Sk+, and gi=0, for i∈Sk−. Try to solve the relaxed single-level problem, that is, the problem defined by problem defined in equations (6)–(11) omitting equation (9). If an optimal solution is obtained, do k←k+1, record the solution xk,yk,uk, and continue to the Fathom step; otherwise, go to the Backtrack step.Fathom: if the obtained solution yields an objective function value worst that the incumbent, a backtrack is needed. That is, ifFxk,yk≥F¯, go to the Backtrack step; otherwise, continue to the Branch step.Branch: ifuikgixk,yk=0, i=1,…,q+m, go to the next step; otherwise, select the ith for which the product uikgixk,yk is the largest one and label it as i1. Update the sets as follows: Sk+←Sk+∪i1, Sk0←Sk0∖i1, and Sk−←Sk−. Append i1 to the current path Pk, and return to the main step.Update: set the incumbent objective function value asF¯=Fxk,yk.Backtrack: if all the nodes in the current pathPk has been explored already, go to the next step; otherwise, branch to the ith component most recently introduced in the path Pk and update Sk+, Sk−, and Sk0. Return to the main step.Termination: if the initial incumbent value remains the same (F¯=∞), hence, there is no feasible solution to the bi-level problem. Otherwise, consider the feasible solution associated with F¯ as the optimal one.This algorithm based in the branch-and-bound scheme solves exactly the equivalent single-level reformulation of the linear bi-level programming problem. The latter arises from linear generalized semi-infinite problems. Therefore, this algorithm is used to solve LGSIPs optimally.


## 4. Numerical Experimentation

In this section, the algorithm described above is used to solve a set of ten linear semi-infinite problems with different characteristics. Its effectiveness and suitability to solve LGSIPs are shown. Since various examples will be shown, the semi-infinite problem, its feasible set, the optimal value, and the optimal set are distinguished asPi, MSIPi, vi, and Fi∗, respectively, where i denotes the number of example. Moreover, for the bi-level form, we also distinguish its corresponding sets Six, Si, Gi, and MBLSIPi.The aim of this section is to exhibit that the proposed algorithm is able to solve LGSIPs in an efficient manner. The optimal solution of the tested problems is compared with the optimal solution obtained analytically. Also, eight additional linear bi-level problems are tested to robust the computational section showing that the algorithm is able to efficiently solve these problems. Since the majority of the semi-infinite problems herein tested are proposed by us, we do not compare the efficiency results of our algorithm against other methods. However, a comparison regarding the quality of the solution is made.The first three examples show the particular case whenYx=Y. Although the study is only of interest in the general case (since in standard SIPs, they are inherently finite by the vertex theorem), standard SIPs are considered to show that the algorithm is effective in both cases.Example 1.
Consider the following problem:(13)P1:minxx1+2x2,s.t.x1+x2≥y,y∈Y=0,1.
Figure1 shows that the problem has feasible solution, v1=1 and F1∗=1,0'.
The bi-level formulation ofP1 is(14)minxx1+2x2s.t.x1+x2≥y,andysolves,Qx:miny−ys.t.0≤y≤1.
The solution obtained by the algorithm coincides with the solution obtained geometrically.Figure 1
Feasible set ofP1.Example 2.
Consider the following problem:(15)P2:minx2x1+x2s.t.x1+x2≥y1+y2,y∈Y=0,1×0,1.
The corresponding bi-level formulation is(16)minx2x1+x2s.t.x1+x2≥y1+y2,andysolves,Qx:miny−y1−y2s.t.0≤y1≤1,0≤y2≤1.
The algorithm shows thatF2∗=0,2' and v2=2.Example 3.
Consider the following problem:(17)P3:minx2x1+x2s.t.x1+x2≥y1+y2,y∈Y,where(18)Y=y|0≤y1+y2≤1.
The bi-level formulation is(19)minx2x1+x2s.t.x1+x2≥y1+y2,andysolves,Qx:miny−y1−y2s.t.0≤y1+y2≤1.
The results obtained by the algorithm areF3∗=0,1' and v3=1.
The following examples show that the proposed algorithm is also effective to solve semi-infinite problems in the general case.Example 4.
Consider the following problem:(20)P4:maxxxs.t.2y+x−1≤0,y∈Yx,where(21)Yx=y|0≤y≤x2.
This example is presented in [23], where the bi-level problem has optimal set F∗=1/2,1/4' and its optimal value is v4=1/2.
To solve the semi-infinite problem using the algorithm herein proposed, its bi-level formulation is deduced:(22)P4BL:minx−xs.t.x+2y≤1,andysolves,Qx:miny−2ys.t.0≤y≤x2.
Then, its equivalent single-level reformulation is as follows:(23)minx−xs.t.x+2y≤1,u−v=2,ux2−y+vy=0,−x2+y≤0,x≥0,y≥0,u≥0,v≥0.
To solve that problem, the nonlinear constraint (complementarity slackness constraint) is omitted and the relaxed linear problem is solved:(24)min−xxs.t.x+2y≤1,u−v=2,−x2+y≤0,x≥0,y≥0,u≥0,v≥0.
The optimal solution of the relaxed problem isx,y,u,v'=1,0,2,0', with an optimal value of F¯=−1. Now, the relaxed complementarity slackness constraints are verified. The algorithm first explores the branch when u=0. In this case, the resulting problem is infeasible, and that branch is fathomed. Then, the branch that considers x/2−y=0 is explored. In this case, the optimal solution x,y,u,v'=0.5,0.25,2,0' is obtained, yielding to F¯=−0.5. The search to the global optimum continues, and v=0 is imposed. By doing this, the same solution of the latter problem is obtained. At this point, the obtained solution is a candidate to be the global optimum of the semi-infinite problem since all the complementarity slackness constraints are hold. To finish the search, the constraint v=0 is substituted by y=0 and the resulting problem is solved. The obtained solution is x,y,u,v'=0,0,2,0' and the objective function value of F¯=0. The algorithm stops and the optimal solution of the bi-level problem is x,y,u,v'=0.5,0.25,2,0' with F¯=−0.5. Hence, the optimal solution for the semi-infinite problem is x=0.5yv4=0.5.
In Figure2, the representation of the search tree is shown.Figure 2
Search tree for Example4.Example 5.
Consider the following problem:(25)P5:minxxs.t.x−y≤0,y∈Yx,where(26)Yx=y|−x−y≤−3,x−y≤3,x2+y≤3.
The corresponding bi-level formulation is(27)minxxs.t.x−y≤0,andysolves,Qx:minyys.t.−x−y≤−3,x−y≤3,x2+y≤3.
Its single-level reformulation is as follows:(28)minxx,s.t.x−y≤0,u1+u2−u3+v=1,u1−3+x+y+u23−x+y+u33−x2−y+vy=0,−x−y≤−3,x−y≤3,x2+y≤3,x,y,u1,u2,u3,v≥0.
Similarly, as in the previous example, the branch and bounding scheme explores the search tree depicted in Figure3 to achieve the optimal solution.
The solution that the algorithm obtains is0,3' as optimal set and 0 as optimal value, which shows that F5∗=0 and v5=0. The results are validated by solving P5 in a geometric way. We have(29)S5x=3−xif0≤x≤3,x−3if3<x≤4.
The solution graph ofQ is shown in Figure 4. On the contraru, in Figure 5, we show that(30)MBLSIP5=x,y′|y=3−x,0≤x≤32.
AsMSIP5=prxMBLSIP5, the feasible set is(31)MSIP5=0,32.
The optimal solution of theSIP problem obtained from the above described feasible set is the same as the one obtained by the algorithm.Figure 3
Search tree for Example5.Figure 4
Solution graph ofQ which results of P5.Figure 5
Feasible set ofBLSIP which is results of P5.Example 6.
Consider the following problem:(32)P6:minxxs.t.x+y≤0,y∈Yx,where(33)Yx=y|−x−y≤−3,x−y≤3,x2+y≤3.
The bi-level formulation is(34)minxxs.t.x+y≤0,andysolves,Qx:miny−y,s.t.−x−y≤−3,x−y≤3,x2+y≤3.
The algorithm shows that the problem does not have feasible solution (from the Backtrack step goes to the Termination one). The result is justified geometrically because the intersection ofG6 and S6 is empty.Example 7.
Consider the following problem:(35)P7:minxxs.t.−x+y≤0,y∈Yx,where(36)Yx=y|x+y≤3.
The bi-level form is(37)minxxs.t.−x+y≤0,andysolves,Qx:miny−ys.t.x+y≤3.
The solution graph ofQ is shown in Figure 6. On the contrary, in Figure 7, we show that(38)MBLSIP7=x,y′|y=3−x,1.5≤x≤3.
SinceMSIP7=pxxMBLSIP7, the feasible set is MSIP7=1.5,3. The optimal solution is x=1.5. We have the same result with the algorithm.Figure 6
Solution graph ofQ which results of P7.Figure 7
Feasible set ofBLSIP which results of P7.Example 8.
Consider the following problem:(39)P8:minx−x1+x2s.t.y≥0,y∈Yx,where(40)Yx=y|y≥x1,y≥x2,y≤1.
The corresponding bi-level formulation is(41)minx−x1+x2s.t.y≥0,andysolves,Qx:minyys.t.y≥x1,y≥x2,y≤1.
The solution obtained by the algorithm isx1,x2'=1,0' and v8=−1.
If the restrictiony≤1 is omitted in the problem P8, then the problem is unbounded. Moreover, if x1 and x2 have no sign constraints, the feasible set exhibits a so-called re-entrant corner point at the origin (see [2]).Example 9.
Consider the following problem:(42)P9:minxx1−x2s.t.y≥0,y∈Yx,where(43)Yx=y|x1−y≤−1,x2−y≤1,y≤2.
The corresponding bi-level formulation is(44)minxx1−x2s.t.y≥0andysolves,Qx:minyys.t.x1−y≤−1,x2−y≤1,y≤2.
The solution obtained by the algorithm isx1,x2'=0,3' and v9=−3.Example 10.
Consider the following problem:(45)P10:minx2≤3−x1−x2s.t.y≥0,y∈Yx,where(46)Yx=y|y≥x1,y≤x2.
The corresponding bi-level formulation is(47)minx2≤3−x1−x2s.t.y≥0andysolves,Qx:minyys.t.y≥x1,y≤x2.
The solution obtained by the algorithm isx1,x2'=3,3' and v10=−6.
If the restrictionx2≤3 is omitted in the problem P10, then the problem is unbounded. Moreover, if x1 and x2 have no sign constraints, the feasible set is not closed (see [2]).
The examples and computational results are summarized in Table1, in which the problem is shown in the first column, the optimal solution is reported in the second one, the number of mathematical programming problems solved until the optimal solution obtained is presented in the third column, the total number of mathematical programming problems solved to guarantee optimality is shown in the fourth column, and the total CPU required time is reported in the last column. All tests were performed using a personal computer having an Intel (R) Core processor with 8 GB of RAM, and the proposed algorithm was coded and run using the FICO XPRESS 8.5 commercial software. Also, as mentioned in each example, the optimal solutions are taken from the cited references in which each problem is proposed.
The effectiveness of the algorithm is shown by solving an additional set of problems that appears in [3, 21, 22, 27]. Here, bi-level problems are considered to show the robustness of the developed method. The algorithm starts from the point in which a bi-level reformulation of the linear generalized semi-infinite programming problem is obtained. As it is explained above, the algorithm aims to find the optimal solution, but then, global optimality must be guaranteed. As a consequence, additional iterations are required. However, the required time to solve the tested problems is very short. The obtained results are presented in Table 2 in which we follow the notation of the authors.Table 1
Results in linear semi-infinite programming.
ExampleOptimalsolutionMath Progsolved tofind theoptimalsolutionMath Progsolved toguaranteeoptimalityRequiredtimesecP1:minxx1+2x2s.t.x1+x2≥y,y∈Y=0,1v1=1v1=1x1=1x2=0330.031P2:minx2x1+x2s.t.x1+x2≥y1+y2,y∈Y=0,1×0,1v2=2x1=0x2=2550.047P3:minx2x1+x2s.t.x1+x2≥y1+y2,y∈Y, where Y=y|0≤y1+y2≤1v3=1x1=0x2=1330.031P4:maxxxs.t.2y+x−1≤0,y∈Yx, where Yx=y|0≤y≤x/2v4=1/2x=1/2330.031P5:minxxs.t.x−y≤0,y∈Yx, where Yx=y|−x−y≤−3x−y≤3x/2+y≤3v5=0x=0230.031P6:minxxs.t.x+y≤0,y∈Yx, where Yx=y|−x−y≤−3x−y≤3x/2+y≤3infeasible110.016P7:minxxs.t.−x+y≤0,y∈Yx where Yx=y|x+y≤3v7=1.5x=1.5330.031P8:minx−x1+x2s.t.y≥0,y∈Yx where Yx=yy≥x1y≥x2y≤1v8=−1x1=1x2=0230.031P9:minxx1−x2s.t.y≥0,y∈Yx, where Yx=y|x1−y≤−1x2−y≤1y≤2v9=−3x1=0x2=3350.047P10:minx2≤3−x1−x2s.t.y≥0,y∈Yx, where Yx=y|y≥x1,y≤x2v10=−6x1=3x2=3230.031Table 2
Results in linear bi-level programming.
ExampleOptimalsolutionMath Progsolved tofind theoptimalsolutionMath Progsolved toguaranteeoptimalityRequiredtimesecBL1:minx≥0−8x1−4x2+4y1−40y2−4y3s.t.miny≥0x1+2x2+y1+y2+2y3s.t.−y1+y2+y3≤12x1−y1+2y2−0.5y3≤12x2+2y1−y2−0.5y3≤1v1=−29.2x1=0x2=0.9y1=0y2=0.6y3=0.45150.14BL2:minx−x−10ys.t.minyys.t.−25x+20y≤30x+2y≤102x−y≤152x+10y≥15v2=−18x=8y=1570.078BL3:minx≥0x+ys.t.miny≥0−5x−ys.t.−x−y2≤−2−x4+y≤2x+y/2≤8x−2y≤4v3=28/9x=8/9y=20/9550.047BL4:minxx+2ys.t.miny−ys.t.−x+2.5y≤3.75x+2.5y≥3.752.5x+y≤8.75v4=3x=0y=1.5110.016BL5:min3x+ys.t.1≤y≤6minx−xs.t.x+y≤84x+y≥82x+y≤13v5=12x=2y=6550.047BL6:miny2x2−y,s.t.0≤y≤3minx−x1s.t.100x1−x2≤1x2≤yx≥0v6=0x1=0.01x2=0y=0330.031BL7:maxx+ys.t.ysolvesQx:maxy2ys.t.2y+x−1≤00≤y≤12xv7=1x=1y=0230.031BL8:maxx+ys.t.x+2y≤8andyis a solution ofQx:maxx+ys.t.0≤y≤4v8=4x=0y=4330.031BL9:minx12x1−11x2s.t.minx2x1+3x2s.t.x1−2x2≤42x1−x2≤243x1+4x2≤96x1+7x2≤126−4x1+5x2≤65−x1−4x2≤−8x1,x2≥0v9=−85.09x1=17.45x2=10.90690.08BL10:minx1−x2s.t.minx2x2s.t.−x1−2x2≤10x1−2x2≤62x1−x2≤21x1+2x2≤38−x1+2x2≤18x1,x2≥0v10=−11x1=16x2=11690.064BL11:minx1−x1−3x2s.t.minx2x2s.t.−x1+x2≤3x1+2x2≤124x1−x2≤12x1,x2≥0v11=−16x1=4x2=4450.049


## 5. Application to a Real-Life Problem

In this section, a case study regarding a supply chain, in which distribution centers and manufacturers are involved, is used to demonstrate the applicability of the developed algorithm. The problem herein considered is proposed in [28] and considered in [27]. At the upper level, the distribution centers aim to maximize the overall profit, while at the lower level, the manufacturer aims to minimize the costs.Letyij be the upper-level decision variables, which denote the amount of products that will be available at distribution center i. Also, let xij be the lower-level decision variables and represent the demand of customer j supplied from the distribution center i. Therefore, the upper-level objective function is given by the benefit obtained from selling xij products at price pij minus the production costs ui. The lower-level objective function is given by the manufacturing costs oij and the acquisition cost from other manufacturers. The imposed constraints are typical on a problem of this type; that is, there is a capacity ci at the distribution centers, the demand of the customers cannot be supplied from distribution centers that are closed, and at least the minimum demand of customers must be fulfilled.Considering the particular case study, the obtained data are assumed and the resulting bi-level model is as follows:(48)maxy1,y2110x11+120x21−40y1−50y2,minx11,x21130x11+145x21,x11≤y1,x21≤y2,y1≤1000,y2≤500,y1+y2≥750,x11,x21,y1,y2≥0.In order to apply the proposed algorithm, its single-level reformulation obtained by applying its Kuhn–Tucker conditions is as follows:(49)maxy1,y2,x11,x21.zk110x11+120x21−40y1−50y2,z1−z6=−130,z2−z7=−145,x11≤y1,x21≤y2,y1≤1000,y2≤500,y1+y2≥750,y1−x11z1=0,y2−x21z2=0,1000−y1z3=0,500−y2z4=0,−750+y1+y2z4=0,x11z6=0,x21z7=0,x11,x21,y1,y2≥0,zk≥0,k=1,…,7.The obtained solution is the same as in [27, 28], that is, x11,x21=y1,y2=1000,500, with a corresponding objective function value of 105,000. The algorithm solves 5 mathematical problems, and the optimal solution was assured in the 5th iteration. It required 0.031 seconds to reach the optimal solution. It is important to mention that, in [27], hybrid genetic and particle swarm optimization algorithms solved the problem in 8 iterations, while 6 iterations of a population-based metaheuristic are required in [28]. Both references do not report the computational time, but for the type of algorithms, it is probably that our methodology is faster for solving this real-life application.


## 6. Conclusions

In this study, the bi-level formulation of linear generalized semi-infinite programming problems is exploited to propose an easy-to-implement exact solution algorithm. The core of the method relies in the use of Kuhn–Tucker optimality conditions to reduce the bi-level formulation into a nonlinear programming problem with complementarity constraints. The main contribution of this study is the approach of satisfying the complementarity constraints via a branch-and-bound scheme. That strategy is utilized in bi-level programming, but the adaptation to solve linear generalized semi-infinite programming problems is a novel contribution in this research area.Additionally, computational experimentation is conducted to validate the proposed algorithm and its effectiveness. Diverse linear generalized semi-infinite programming problems with different characteristics are considered to validate the robustness of the implemented algorithm. An interesting real-life application is considered during the numerical experience, which demonstrates the convenience and applicability of the proposed approach.Therefore, the proposed method results in an alternative for solving this particular type of problems that avoid the inclusion of additional functions to regulate the complementarity constraints, as in [8]. Nevertheless, in both methods, similar assumptions are made before applying them.A generalization of the proposed method for the case when many semi-infinite constraints are considered is presented in [3]. Their proposal is described in a theoretical manner, but its application to specific semi-infinite problems and computational experiments are not reported. The latter may be a challenging further research direction. Another opportunity is to extend the presented algorithm for solving other variants of SIPs. Also, the generalization of the algorithm to the case with many semi-infinite constraints can also be considered as future work.



---

*Source: 1765385-2022-04-25.xml*