An Alternative Approach for Solving Bi-Level Programming Problems

Rashmi Birla¹, Vijay K. Agarwal², Idrees A. Khan³, Vishnu Narayan Mishra^4*

¹Department of Mathematics, Sir Padampat Singhania University, Bhatewar, India.
²Department of Mathematics, Mody University of Science and Techonology Lakshmangarh, India.
³Department of Mathematics, Integral University, Lucknow, India.
⁴Applied Mathematics & Humanities Department, Sardar Vallabhbhai National Institute of Technology, Surat, India.

DOI: 10.4236/ajor.2017.73016                

Abstract

An algorithm is proposed in this paper for solving two-dimensional bi-level linear programming problems without making a graph. Based on the classification of constraints, algorithm removes all redundant constraints, which eliminate the possibility of cycling and the solution of the problem is reached in a finite number of steps. Example to illustrate the method is also included in the paper.

Keywords

Linear Programming Problem, Bi-Level Programming Problem, Graph, Algorithm

1. Introduction

Multilevel programming is developed to solve the decentralized planning pro- blem in which decision makers are often arranged within a hierarchical ad- ministrative structure. The bi-level programming problem is a hierarchical optimization problem in which a subset of the variables are constrained to be solution of a given optimization problem parameterized by the remaining vari- ables. The linear bi-level programming problem, which is a specific case of the Multilevel programming problem with a two levels structure is a set of nested linear optimization over a single polyhedral region. Two decision makers are located at different hierarchical levels, each independently controlling only one set of decision variables, and with different and perhaps conflicting objectives. The hierarchical optimization structure appears normally in plenty of appli- cation when lower level moves are controlled by upper level decisions. Transpor- tation, management, planning and optimal design are the few application fields of bi-level programming problems.

In mathematical terms, in bi-level programming problems it is required to find a solution to the upper level problem

${\min }_{x,y}F\left(x,y\right)$

such that $g\left(x\mathrm{,}y\right)\le 0$ ,

where y for each value of x, is the solution of the lower level problem:

${\min }_{y}f\left(x,y\right)$

such that $h\left(x\mathrm{,}y\right)\le 0$ .

The lower level problem is also referred as the follower’s problem. In a similar way, the upper level problem is also called the leader’s problem. The original formulation for bi-level programming problem appeared in 1973, in a paper authored by J. Bracken and J. McGill [1] , although it was W. Candler and R. Norton [2] that first used the designation bi-level or multilevel programming. However, it was not until the early eighties that these problems started receiving the attention they deserve [3] [4] [5] [6] . Motivated by the game theory of H. Stackelberg [7] , several authors studied bi-level programming problems in- tensively and contributed to its proliferation in the mathematical programming community. Since 1980, a significant efforts have been devoted to understanding the fundamental concepts associated with bi-level programming. Various ver- sions of the linear bi-level programming problem are presented by [8] [9] [10] [11] . At the same time, various algorithms have been proposed for solving these problems. One class of techniques inherent of extreme point algorithms and has been largely applied to the linear bi-level programming problems because for this problem, if there is a solution, then there is at least one global minimizer that is an extreme point [12] . Two other classes of algorithms are branch and bound algorithm and complementarily pivot algorithms [13] [14] . A survey on the linear bi-level programming problems has been written by O. Ben-Ayed [15] . The complexity of the problem has been addressed by a number of authors [16] [17] [18] . It has been proved that even the linear bi-level programming problem where all the involved functions are affine, is a strongly NP-hard problem [19] [20] .

In this paper, an attempt has been made to develop a method in which constraints are analyzed, and used for solving two-dimensional linear bi-level programming problems. Constraints have been classified broadly in two cate- gories; we have named them as concave constraints and convex constraints.

2. Fundamental Principles

We define two types of constraint classes for the proposed method, which lay the foundation of this algorithm. Considering the normal to be towards the half plane region not satisfied by constraints, we define the following:

Concave Constraints: -constraints whose normal make angles with the x-axis in the range $[\mathrm{0,}\text{π}]$ .

Convex Constraints: -constraints whose normal make angles with the x-axis in the range $[\text{π}\mathrm{,2}\text{π}]$ .

Concave and Convex constraints defined here are other than non-negativity constraints.Various types of constraints on the basis of the above definition are given in the table below:

The form of bi-level linear programming problem considered here is of the following type:

$\underset{x}{\max }\text{or}\underset{x}{\min }{f}_1\left(x,y\right)\text{where}y\text{solves}$ (1)

$\underset{y}{\max }\text{or}\underset{y}{\min }{f}_2\left(x\mathrm{,}y\right)$ (2)

$a_{i}x+b_{i}y\le c_i$ (3)

$x\mathrm{,}y\ge 0$ (4)

It can be observed easily that inducible region, for the finite solution is one among following two cases: 1) a part of the line of concave constraints; 2) a part of the line of convex constraints or part of the x-axis. Reason behind this observation is the fact that in (2), the control is only on the y variable, therefore for a given x, if (2) is to be maximized in the positive direction of the y-axis, then the extreme point will be a point on a line of concave constraint as shown in Figure 1, and if (2) is to be minimized in the positive direction of the y-axis, then the extreme point will be a point on the line of convex constraint or on the x-axis as shown in Figure 1.

While dealing with this method of solving problems we come across two types of redundant concave constraint and one type of redundant convex constraint. A concave constraint which is redundant when no convex constraints are con- sidered is one type of redundant concave constraints, ${l^{\prime }}_2$ is a line of such type of

Figure 1. Location of extreme point in case of maximization or minimization problems.

redundant constraint as shown in Figure 2, hereafter represented as RCC. A concave constraints which is redundant when convex constraints are also con- sidered with concave constraints is another type of redundant concave con- straints, $l_1$ is a line of such type of redundant concave constraint as shown in Figure 2, hereafter represented as RCC1. One type of redundant convex con- straints used for the proposed method is redundant when no concave constraint are considered, hereafter represented as RCX.

RCC are removed in two steps, at the first step those RCC are removed which can be identified just by inspection, it can be easily seen that a concave con- straint having line $l_i\equiv y=m_{i}x+c_i$ is RCC with respect to concave constraint having line $l_j\equiv y=m_{j}x+c_j$ if $m_i>m_j$ and $c_i>c_j$ . After removal of such RCC let the concave constraints sustained are those whose lines are represented by $l_1\equiv y=m_{1}x+c_1,$ $l_2\equiv y=m_{2}x+c_2,$ $\cdots ,$ $l_j\equiv y=m_{j}x+c_j,$ $\cdots ,$ $l_{p1}\equiv y=m_{p1}x+c_{p1}$ , where $m_1>m_2>\cdots >m_j>\cdots >m_{p1}$ and $c_1<c_2<\cdots <c_j<\cdots <c_{p1}$ .

From Figure 2 we can observe that $l_1\mathrm{,}{l}_2$ and $l_3$ are three lines of constraint such that their slopes $m_1\mathrm{,}{m}_2$ and $m_3$ respectively and their intercepts with y- axis $c_1\mathrm{,}{c}_2$ and $c_3$ respectively follow relation $m_1>m_2>m_3$ and $c_1<c_2<c_3$ and none of the three are RCC but under the same condition constraint with the line ${l^{\prime }}_2$ is RCC with respect to constraint having lines $l_1$ and $l_3$ . Such RCC can be removed by finding out the x-coordinates for point of intersection of the line of concave constraints. x coordinate $x_{12}$ for point of intersection of $l_1$ and

$l_2$ is given by $x_{12}=\frac{c_1-c_2}{m_2-m_1}$ , similarly the x coordinate $x_{23}$ of point of intersection of $l_2$ and $l_3$ is given by $x_{23}=\frac{c_2-c_3}{m_3-m_2}$ , for constraint having the

line $l_2$ not to be RCC with respect to constraint having lines $l_1$ and $l_3$ we

Figure 2. Redundant constraint.

must have $x_{12}<x_{23}$ . In case constraint having the line $l_2$ is redundant with respect to constraint having lines $l_1$ and $l_3$ , replace constraint having the line

$l_2$ by constraint having the line $l_3$ and constraint having the line $l_3$ by

constraint having the line $l_4$ and find out $x_{13}=\frac{c_1-c_3}{m_3-m_1}$ and $x_{34}=\frac{c_3-c_4}{m_4-m_3}$ ,

thus one by one all the redundant concave constraints can be removed. Here it is assumed that $x_{12}$ and corresponding y coordinate $y_{12}$ are non-negative otherwise constraint having the line $l_1$ become RCC and we replace constraint having the line $l_2$ by constraint having the line $l_1$ and so on. While finding $x_{ij}$ to check redundancy for concave constraints we also find corresponding y coordinates $y_{ij}$ . In this process after $l_1$ is obtained if we come across $y_{ij}\le 0$ for a positive $x_{ij}$ , the concave constraint having $\left(x_{ij}\mathrm{,}{y}_{ij}\right)$ as terminal point is considered to be the last non-redundant concave constraint. It is to be noted that a line segment parallel to y-axis cannot be a part of inducible region, therefore while removing RCC, if a concave constraint parallel to the y-axis having line $l_p$ is encountered then point of intersection $P_l$ of the line of concave constraint just before $l_p$ and $l_p$ is considered to be the terminal point of the last non- redundant concave constraint making the reaction set.

RCX can be removed in the similar way as RCC, for this let ${l^{\prime }}_i\equiv y={m^{\prime }}_{i}x+{c^{\prime }}_i$ and ${l^{\prime }}_j\equiv y={m^{\prime }}_{j}x+{c^{\prime }}_j$ be two lines of convex constraint, such that ${m^{\prime }}_i<{m^{\prime }}_j$ and ${c^{\prime }}_i<{c^{\prime }}_j$ then constraint having line ${l^{\prime }}_i$ is RCX with respect to convex constraint having line ${l^{\prime }}_j$ . After removal of such RCX let the convex constraint left are those having lines ${l^{\prime }}_1\equiv y={m^{\prime }}_{1}x+{c^{\prime }}_1$ , ${l^{\prime }}_2\equiv y={m^{\prime }}_{2}x+{c^{\prime }}_2$ , $\cdots$ , ${l^{\prime }}_j\equiv y={m^{\prime }}_{j}x+{c^{\prime }}_j$ , $\cdots$ , ${l^{\prime }}_{p1}\equiv y={m^{\prime }}_{p1}x+{c^{\prime }}_{p1}$ , where ${m^{\prime }}_1<{m^{\prime }}_2<\cdots <{m^{\prime }}_j<\cdots <{m^{\prime }}_{p1}$ and ${c^{\prime }}_1>{c^{\prime }}_2>\cdots >{c^{\prime }}_j>\cdots >{c^{\prime }}_{p1}$ .

Such RCX can be removed by finding out the x-coordinates of the point of intersection of lines of convex constraint, x-coordinate ${x^{\prime }}_{12}$ for point of

intersection of ${l^{\prime }}_1$ and ${l^{\prime }}_2$ is given by ${x^{\prime }}_{12}=\frac{{c^{\prime }}_1-{c^{\prime }}_2}{{m^{\prime }}_2-{m^{\prime }}_1}$ , similarly x coordinate ${x^{\prime }}_{23}$ of point of intersection of ${l^{\prime }}_2$ and ${l^{\prime }}_3$ is given by ${x^{\prime }}_{23}=\frac{{c^{\prime }}_2-{c^{\prime }}_3}{{m^{\prime }}_3-{m^{\prime }}_2}$ , for con-

straint having the line ${l^{\prime }}_2$ not to be RCX with respect to constraint having the line ${l^{\prime }}_1$ and constraint having line ${l^{\prime }}_3$ we must have ${x^{\prime }}_{12}<{x^{\prime }}_{23}$ . In case constraint having the line ${l^{\prime }}_2$ is redundant with respect to constraint having the line ${l^{\prime }}_1$ and constraint having the line ${l^{\prime }}_3$ , replace constraint having the line ${l^{\prime }}_2$ by constraint having the line ${l^{\prime }}_3$ and constraint having the line ${l^{\prime }}_3$ by constraint

having the line ${l^{\prime }}_4$ and find out ${x^{\prime }}_{13}=\frac{{c^{\prime }}_1-{c^{\prime }}_3}{{m^{\prime }}_3-{m^{\prime }}_1}$ and ${x^{\prime }}_{34}=\frac{{c^{\prime }}_3-{c^{\prime }}_4}{{m^{\prime }}_4-{m^{\prime }}_3}$ , thus one by

one all the redundant convex constraints can be removed.

Non-redundant concave constraints obtained after removal of RCC as dis- cussed above are such that constraint having line $l_k$ is nearer to y-axis than constraint having line $l_m$ if $k<m$ . Also during this process we have obtained, coordinates of corners made by all non-redundant concave constraint lines, after removal of RCC, except the starting point of first non-redundant concave con- straint line and the terminal point of last non-redundant concave constraint line in general.

To obtain the starting point of first non-redundant concave constraint line, find its intersection first with the y-axis if the coordinate so obtained is $\left(0,y\ge 0\right)$ then this is the required point, otherwise we find its intersection with x-axis. To obtain the terminal point of last non-redundant concave constraint line we find its intersection with the x-axis, if the coordinate so obtained is $\left(x\ge \mathrm{0,0}\right)$ then this is the required point, otherwise terminal point is un- bounded.

3. Algorithm

Method and algorithm in case inducible region is a part of concave constraints line is given below. A similar method and algorithm can be given in case in- ducible region is a part of convex constraints line.

Step 1: Remove RCC from all concave constraints and find $y_{ij}$ for all $x_{ij}$ obtained during the process of removal. Find RCX from all convex constraints.

Step 2: Find starting point $P_1$ of first non-redundant concave constraint line, and the terminal point $P_l$ of last non-redundant concave constraint line which may be part of inducible region.

Step 3: Check if end points $P_1$ and $P_2$ of first non-redundant concave con- straint line $l_1$ satisfy all non-redundant convex constraint lines or not, if they do so go for $P_2$ and $P_3$ of $l_2$ and so on, to check the same, otherwise there may be one of the following three cases:

1) There is at least one non-redundant convex constraint not satisfied by both $P_1$ and $P_2$ in this case constraint having line $l_1$ become RCC1 otherwise $l_1$ become part of boundary of the feasible region, and we move to constraint having lines $l_2,l_3,\cdots .$

2) There is at least one non-redundant convex constraint not satisfied by $P_1$ but satisfied by $P_2$ . Let ${l^{\prime }}_1$ be one such line of convex constraint, then find the intersection point of ${l^{\prime }}_1$ and $l_1$ and shift $P_1$ to this point of intersection, with this new $P_1$ and $P_2$ if ${l^{\prime }}_j$ is again line of such constraint do the same, and so on, till all such constraints are exhausted, then move to constraint having line $l_2,l_3,\cdots .$

3) There is at least one non-redundant convex constraint not satisfied by $P_2$ but satisfied by $P_1$ . Let constraint having line ${l^{\prime }}_p$ be one such convex constraint, then find the intersection point of ${l^{\prime }}_p$ and $l_1$ and shift $P_2$ to this point of intersection, with this new $P_2$ and $P_1$ if constraint having line ${l^{\prime }}_q$ is again such constraint do the same, and so on, till all such constraints are exhausted, in this case $P_2$ become the last point to be considered for solution.

Step 4: The points $P_1,P_2,\cdots$ satisfying all non-redundant convex constraints, obtained from step 3 are used to find optimal solution by putting its value in the objective function (1).

If there are some feasible points than in either of the following two cases we may have unbounded solution 1) No concave constraint exist 2) No constraint of the type 1, 5 and 7 as given in the table is present in the problem. If there is at least one of the convex constraints not satisfied by any of the point $P_1,P_2,\cdots$ then there is a case of no feasible solution.

4. Example

$\underset{x}{\max }{z}_1=3x+2y$

where y solves

$\underset{y}{\max }{z}_2=2x+4y$

$-5x+5y\le 15$ (5)

$y\le 4.5$ (6)

$4x+3y\le 24$ (7)

$-2x-y\le -4$ (8)

$8x-4y\le 12$ (9)

$x\le 3$ (10)

$x\mathrm{,}y\ge 0$

Solution:

As per the classification (5), (6), (7) and (10) are concave constraints and (8) and (9) are convex constraints, inducible region is a part of concave constraints.

Step 1: Part of ration reaction set are $l_1\equiv y=x+3,$ $l_2\equiv y=0x+9/2$ and $l_3\equiv y=-4/3x+8$ .

None of the concave constraint is RCC and none of the convex constraint is RCX. $P_2\left(x_{12},y_{12}\right)=\left(3/2,9/2\right)$ and $P_3\left(x_{23},y_{23}\right)=\left(21/8,9/2\right)$ .

Step 2: $P_1=\left(0,3\right)$ and $P_4=\left(3,4\right)$ .

Step 3: $P_1\mathrm{,}{P}_2\mathrm{,}{P}_3$ and $P_4$ satisfy both (8) and (9).

Step 4: z₁ for all the $P_1\mathrm{,}{P}_2\mathrm{,}{P}_3$ and $P_4$ are $z_1\left(0,3\right)=6,$ $z_1\left(3/2,9/2\right)=27/2,$

$z_1\left(21/8,9/2\right)=135/8$ and $z_1\left(3,4\right)=17$ .

Therefore solution is $z_1\left(3,4\right)=17$ .

$\underset{x}{\max }{z}_1=3x+2y$

where y solves

$\underset{y}{\max }{z}_2=2x+4y$

$-5x+5y\le 15$ (11)

$y\le 4.5$ (12)

$4x+3y\le 24$ (13)

$-2x-y\le -4$ (14)

$8x-4y\le 12$ (15)

$x\le 3$ (16)

$x\mathrm{,}y\ge 0$

Solution:

As per the classification (5), (6), (7) and (10) are concave constraints and (8) and (9) are convex constraints, inducible region is a part of concave constraints.

Step 1: Part of ration reaction set are $l_1\equiv y=x+3,$ $l_2\equiv y=0x+9/2$ and $l_3\equiv y=-4/3x+8$ .

None of the concave constraint is RCC and none of the convex constraint is RCX. $P_2\left(x_{12},y_{12}\right)=\left(3/2,9/2\right)$ and $P_3\left(x_{23},y_{23}\right)=\left(21/8,9/2\right)$ .

Step 2: $P_1=\left(0,3\right)$ and $P_4=\left(3,4\right)$ .

Step 3: $P_1\mathrm{,}{P}_2\mathrm{,}{P}_3$ and $P_4$ satisfy both (8) and (9).

Step 4: $z_1$ for all the $P_1\mathrm{,}{P}_2\mathrm{,}{P}_3$ and P₄ are $z_1\left(0,3\right)=6,$ $z_1\left(3/2,9/2\right)=27/2,$

$z_1\left(21/8,9/2\right)=135/8$ and $z_1\left(3,4\right)=17$ .

Therefore solution is $z_1\left(3,4\right)=17$ .

5. Conclusion

The proposed method is based on the analysis of constraints. Unlike the tra- ditionally used method of finding optimum such as interior point method or simplex method in which search is made by moving along the boundary of the feasible region, an attempt made in this paper conveys that by properly exploiting the properties of constraints there is a possibility of developing a method which solves the problem in finite number of steps efficiently.

Acknowledgements

We thank the Editor and the referee for their comments. This support is greatly appreciated.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Bracken, J. and McGill, J. (1973) Mathematical Programs with Optimization Problems in the Constraints. Operation Research, 21, 37-44. https://doi.org/10.1287/opre.21.1.37
[2]	Candler, W. and Norton, R. (1977) Multilevel Programming and Development Policy. Technical Report 258, Word Bank Staff, Washington DC.
[3]	Wen, U. and Hsu, S. (1992) Efficient Solution for the Linear Bilevel Programming Problems. European Journal of Operation Research, 62, 354-362.
[4]	Jan, R. and Chern, M. (1994) Nonlinear Integer Bilevel Programming. European Journal of Operation Research, 72, 574-587.
[5]	Liu, Y. and hart, S. (1994) Characterizing an Optimal Solution to the Linear Bilevel Programming Problem. European Journal of Operation Research, 73, 164-166.
[6]	Liu, Y. and Spencert, T. (1995) Solving a Bilevel Linear Program When the Inner Decision Maker Controls Few Variables. European Journal of Operation Research, 81, 644-651.
[7]	Stackelberg, H. (1952) The Theory of Market Economy. Oxford University Press, Oxford.
[8]	Bialas, W.F. and Karwan, M.H. (1982) On Tow-Level Linear Optimization. IEEE Transactions on Automatic Control, AC-27, 211-214.
[9]	Bard, J.F. and Falk, J.E. (1982) An Explicit Solution to the Multi-Level Programming Problem. Computers and Operations Research, 9, 77-100.
[10]	Bialas, W.F. and Karwan, M.H. (1984) Two-Level Linear Programming. Management Science, 30, 1004-1020. https://doi.org/10.1287/mnsc.30.8.1004
[11]	Bard, J. (1985) Geometric and Algorithm Development for Hierarchical Planning Problem. European Journal of Operation Research, 19, 372-383.
[12]	Mishra, V.N. (2007) Some Problems on Approximations of Functions in Banach Spaces. PhD Thesis, Indian Institute of Technology, Roorkee, 247-667.
[13]	Hansen, P., Jaumard, B. and Sarvard, G. (1992) New Branch-and-Bound Rules for Linear Bilevel Programming. SIAM Journal of Scientific and Statistical Computing, 13, 1194-1217. https://doi.org/10.1137/0913069
[14]	Judice, J. and Faustino, A. (1994) The Linear Quadratic Bi-Level Programming Problem. INFOR, 32, 87-98. https://doi.org/10.1080/03155986.1994.11732240
[15]	Ben-Ayed, O. (1993) Bilevel Linear Programming. Computers and Operation Research, 20, 485-501.
[16]	Haurie, A., Savard, G. and White, J.C. (1990) A Note on an Efficient Point Algorithm for a Linear Two-Stage Optimization Problem. Operation Research, 38, 553-555. https://doi.org/10.1287/opre.38.3.553
[17]	Onal, H. (1993) A Modified Simplex Approach for Solving Bilevel Linear Programming Problems. European Journal of Operation Research, 67, 126-135.
[18]	Husain, S., Gupta, S. and Mishra, V.N. (2013) An Existence Theorem of Solutions for the System of Generalized Vector Quasi-Variational Inequalities. American Journal of Operations Research, 3, 329-336. https://doi.org/10.4236/ajor.2013.33029
[19]	Gupta, S., Dalal, U.D. and Mishra, V.N. (2014) Novel Analytical Approach of Non Conventional Mapping Scheme with Discrete Hartley Transform in OFDM System. American Journal of Operations Research, 4, 281-292. https://doi.org/10.4236/ajor.2014.45027
[20]	Ahmad, I., Mishra, V.N., Ahmad, R. and Rahaman, M. (2016) An Iterative Algorithm for a System of Generalized Implicit Variational Inclusions. Springer Plus, 5, 1283. https://doi.org/10.1186/s40064-016-2916-8