An Alternative Approach for Solving Bi-Level Programming Problems ()
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
such that
,
where y for each value of x, is the solution of the lower level problem:
such that
.
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
.
Convex Constraints: -constraints whose normal make angles with the x-axis in the range
.
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:
(1)
(2)
(3)
(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,
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,
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
is RCC with respect to concave constraint having line
if
and
. After removal of such RCC let the concave constraints sustained are those whose lines are represented by
, where
and
.
From Figure 2 we can observe that
and
are three lines of constraint such that their slopes
and
respectively and their intercepts with y- axis
and
respectively follow relation
and
and none of the three are RCC but under the same condition constraint with the line
is RCC with respect to constraint having lines
and
. Such RCC can be removed by finding out the x-coordinates for point of intersection of the line of concave constraints. x coordinate
for point of intersection of
and
is given by
, similarly the x coordinate
of point of intersection of
and
is given by
, for constraint having the
line
not to be RCC with respect to constraint having lines
and
we
must have
. In case constraint having the line
is redundant with respect to constraint having lines
and
, replace constraint having the line
by constraint having the line
and constraint having the line
by
constraint having the line
and find out
and
,
thus one by one all the redundant concave constraints can be removed. Here it is assumed that
and corresponding y coordinate
are non-negative otherwise constraint having the line
become RCC and we replace constraint having the line
by constraint having the line
and so on. While finding
to check redundancy for concave constraints we also find corresponding y coordinates
. In this process after
is obtained if we come across
for a positive
, the concave constraint having
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
is encountered then point of intersection
of the line of concave constraint just before
and
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
and
be two lines of convex constraint, such that
and
then constraint having line
is RCX with respect to convex constraint having line
. After removal of such RCX let the convex constraint left are those having lines
,
,
,
,
,
, where
and
.
Such RCX can be removed by finding out the x-coordinates of the point of intersection of lines of convex constraint, x-coordinate
for point of
intersection of
and
is given by
, similarly x coordinate
of point of intersection of
and
is given by
, for con-
straint having the line
not to be RCX with respect to constraint having the line
and constraint having line
we must have
. In case constraint having the line
is redundant with respect to constraint having the line
and constraint having the line
, replace constraint having the line
by constraint having the line
and constraint having the line
by constraint
having the line
and find out
and
, 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
is nearer to y-axis than constraint having line
if
. 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
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
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
for all
obtained during the process of removal. Find RCX from all convex constraints.
Step 2: Find starting point
of first non-redundant concave constraint line, and the terminal point
of last non-redundant concave constraint line which may be part of inducible region.
Step 3: Check if end points
and
of first non-redundant concave con- straint line
satisfy all non-redundant convex constraint lines or not, if they do so go for
and
of
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
and
in this case constraint having line
become RCC1 otherwise
become part of boundary of the feasible region, and we move to constraint having lines
2) There is at least one non-redundant convex constraint not satisfied by
but satisfied by
. Let
be one such line of convex constraint, then find the intersection point of
and
and shift
to this point of intersection, with this new
and
if
is again line of such constraint do the same, and so on, till all such constraints are exhausted, then move to constraint having line
3) There is at least one non-redundant convex constraint not satisfied by
but satisfied by
. Let constraint having line
be one such convex constraint, then find the intersection point of
and
and shift
to this point of intersection, with this new
and
if constraint having line
is again such constraint do the same, and so on, till all such constraints are exhausted, in this case
become the last point to be considered for solution.
Step 4: The points
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
then there is a case of no feasible solution.
4. Example
where y solves
(5)
(6)
(7)
(8)
(9)
(10)
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
and
.
None of the concave constraint is RCC and none of the convex constraint is RCX.
and
.
Step 2:
and
.
Step 3:
and
satisfy both (8) and (9).
Step 4: z1 for all the
and
are
and
.
Therefore solution is
.
where y solves
(11)
(12)
(13)
(14)
(15)
(16)
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
and
.
None of the concave constraint is RCC and none of the convex constraint is RCX.
and
.
Step 2:
and
.
Step 3:
and
satisfy both (8) and (9).
Step 4:
for all the
and P4 are
and
.
Therefore solution is
.
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.