Public Science Framework-Journals - Paper

Smoothing and Solving Linear Quad-Level Programming Problem Using Mathematical Theorems

Eghbal Hosseini^{1, *}, Isa Nakhai Kamalabadi²

¹Payamenur University of Tehran, Department of Mathematics, Tehran, Iran

²University of Kurdistan, Department of Industy, Sanandaj, Iran

Abstract

The multi-level programming problems are attractive for many researchers because of their application in several areas such as economic, traffic, finance, management, computer science, informatics, transportation and so on. Among these, the quad-level programming problem (QLPP) is an appropriate tool to model these real problems because many real problems have four levels. It has been proven that even the general bi-level programming problem is an NP-hard problem, so the multi-level problem are practical and complicated problems therefore solving these problem would be significant. The literature shows several algorithms to solve different forms of the bi-level programming problems (BLPP). Not only there is no any algorithm for solving QLPP, but also it has not been studied by any researcher. The most important part in this paper is presentation and studying of a new model (QLPP) of multi-level problems. Also we attempt for developing two applied problems which would be modeled to the linear QLPP, then we attempt for developing an effective approach based on analyze theorems for solving the linear QLPP. In this approach, by using the heuristic method the QLPP is converted to a linear single problem. Finally, the single level problem is solved using the enumeration algorithm. The presented approach achieves an efficient and feasible solution in an appropriate time which has been evaluated by solving test problems.

Keywords

Linear Quad-Level Programming Problem, Heuristic Method, Enumeration Algorithm

Received: April 9, 2015 / Accepted: April 19, 2015 / Published online: May 11, 2015

@ 2015 The Authors. Published by American Institute of Science. This Open Access article is under the CC BY-NC license. http://creativecommons.org/licenses/by-nc/4.0/

Contents

1. Introduction 1.1. Global Techniques 1.2. Enumeration Methods 1.3. Meta Heuristic Approaches 2. The Linear Bi-Level and Tri-Level Programming Problems 3. Heuristic Algorithm (HA) to Solve QLPP 3.1. Main Theoretical Concepts 3.2. Steps of the Algorithm 4. Computational Results 5. Conclusion and Future Work Nomenclature

1. Introduction

It has been proven that the bi-level programming problem (BLPP) is an NP-Hard problem [1,2]. Several algorithms have been proposed to solve BLPP [11,12,13,21,25,26,27,28,29,31,32,33]. These algorithms are divided into the following classes: global techniques, enumeration methods, transformation methods [3,4,22,23], meta heuristic approaches, fuzzy methods [5,6,7,8,24], primal-dual interior methods [13]. In the following, these techniques are shortly introduced.

1.1. Global Techniques

All optimization methods can be divided into two distinctive classes: local and global algorithms. Local ones depend on initial point and characteristics such as continuity and differentiability of the objective function. These algorithms search only a local solution, a point at which the objective function is smaller than at all other feasible points in vicinity. They do not always find the best minima, that is, the global solution. On the other hand, global methods can achieve global optimal solution. These methods are independent of initial point as well as continuity and differentiability of the objective function [9,10,11,12,34,35].

1.2. Enumeration Methods

Branch and bound is an optimization algorithm that uses the basic enumeration. But in these methods we employ clever techniques for calculating upper bounds and lower bounds on the objective function by reducing the number of search steps. In these methods, the main idea is that the vertex points of achievable domain for BLPP are basic feasible solutions of the problem and the optimal solution is among them [14].

1.3. Meta Heuristic Approaches

Meta heuristic approaches are proposed by many researchers to solve complex combinatorial optimization. Whereas these methods are too fast and known as suitable techniques for solving optimization problems, however, they can only propose a solution near to optimal. These approaches are generally appropriate to search global optimal solutions in very large space whenever convex or non-convex feasible domain is allowed. In these approaches, BLPP is transformed to a single level problem by using transformation methods and then meta- heuristic methods are utilized to find out the optimal solution [15,16,17,18,19,25,36,40].

However there are many approaches to solve BLPP and this model of multi-level has been studied by many researchers, but there is no any attempt for modeling and presentation of QLPP. In this paper, the authors have tried to propose a new model of multi-level programming problem, QLPP, and then two applied examples which are modeled in QLPP form are proposed. Finally a new heuristic approach is proposed which is based on enumeration method and important theorems for solving QLPP in general and two applied examples specially.

The remainder of the pages is structured as follows: problem formulation and smooth method to the QLPP are introduced in Section 2. The algorithm based on analytic theorems and enumeration method is proposed in Section 3. Computational results are presented for our approach in Section 4. As result, the paper is finished in Section 5 by presenting the concluding remarks.

2. The Linear Bi-Level and Tri-Level Programming Problems

In this section models of bi-level and tri-level programming problems are introduced.

BLPP is used frequently by problems with decentralized planning structure. It is defined as [20]:

(1)

Where and and are the objective functions of the leader and the follower, respectively.

In general, BLPP is a non-convex optimization problem; therefore, there is no general algorithm to solve it. This problem can be non-convex even when all functions and constraints are bounded and continuous. Of course, the linear BLPP is convex and preserving this property is very important. A summary of important properties for convex problem are as follows, which and is a nonempty convex set in :

(1) The convex function f is continuous on the interior of .

(2) Every local optimal solution of over a convex set is the unique global optimal solution.

(3) If then is the unique global optimal solution of over .

In a tri-level programming problem (TLPP), each decision entity at one level has its objective and its variables in part controlled by entities at other levels. To describe a TLPP, a basic model can be written as follows:

(2)

Where and the variables x, y, z are called the top-level, middle-level, and bottom-level variables respectively, the top-level, middle-level, and bottom-level objective functions, respectively. In this problem each level has individual control variables, but also takes account of other levels’ variables in its optimization function.

We propose the QLPP model as following formulation:

(3)

Definition 2.1

The feasible region of the QLPP is

(4)

On the other hand, if x be fixed, the feasible region of the follower can be explained as

(5)

Based on the above assumptions, the follower rational reaction set is

(6)

Where the inducible region is as follows

(7)

Finally, the quad-level programming problem can be written as

(8)

Definition 2.2

Every point such as is a feasible solution to quad -level problem if

Definition 2.3

Every point such as is an optimal solution to the quad -level problem if

(9)

3. Heuristic Algorithm (HA) to Solve QLPP

3.1. Main Theoretical Concepts

In this section, main concepts and essential theorems in order to expansion of our algorithm

are discussed.

Definition 3.1:

If X be a bounded above set, then the least upper bound of X is called supreme and it is exhibited by Sup(X) and:

Definition 3.2:

If X be a bounded below set, then the greatest lower bound of X is called infmum and it is exhibited by Inf(X) and:

Theorme 3.1:

If X be a bounded above set and then for every small positive number such as

Proof :

The proof is simple. Let

Because is positive then and can not be supreme of X by defenition 1.

This is contradiction with supposition. Therfore this assumption that is false and then

Hence proof of theorem finished.

Theorme 3.2:

If X be a bounded below set and, then for every small positive number such as

Proof :

Let

Because is positive then and can not be supreme of X by defenition 1.

This is contradiction with supposition . Therfore this assumption that is false and then

Hence proof of theorem finished.

Theorme 3.3 [20]:

If X be a bounded and non- empty set then

Proof :

The proof of this theorem was given by [20].

Now consider the problem (3) and X, feasible space of (3), is a bounded set.

Let

, (10)

then:

(11)

And

(12)

Therefore

(13)

And

Therefore

(14)

Equation (11) is valid because x and y are fixed in the last level and they are controlled by the first and middle levels, therefore the last problem has only z as variable. By substituting equation (11) in (13), the problem (2) converts to the following single problem:

(15)

As mention that, in the above formulation using (14) is necessary to remove variable. Also are the last feasible values of and (minimum (Inf) of). It is easy to show that by removing these three constraints:

We can obtain a relaxation to the problem (15):

(16)

Let X and S are feasible spaces of (15), (16) respectively. The problem (16) is a single linear programming problem and the optimal solution of linear problems is a vertex point. To obtain optimal solution, problem (16) will be solved by the proposed algorithm and it calculates all the vertex points in S. We necessary vertex point in X and some of vertex points in S will be removed by theorems because , should be Minimum in other words .

According to the theorems 1, 2, 3 it is easy to see that the following relations are contradictory with to minimize .

Therefore if, then.

Using the proposed algorithm and theorems all the vertex points in X are obtained and the optimal solution is calculated by enumeration method.

3.2. Steps of the Algorithm

In this section, steps of presented algorithm are proposed.

Step 1: We suppose that the objective function of the follower be a new variable and replace it in the leader objective function. Therefore the QLPP is changed into a single level problem. By applying this step, problem (3) is converted into (15), which is in linear form.

Step 2: The constraints related to u, v and w, three new variables which equal to the second, third and the last objective functions, are removed to obtain problem (16) (a relaxation to (15)).

Step 3: Finding all vertex points in problem (16). A vertex point is found by solving at least two constraints for a problem which has two variables. Also solving three constraints give a vertex point for a problem which has three variables and so on. These vertex points can be infeasible in (15). Step 4 proposes all feasible vertex points to problem (15).

Step 4: According to the proposed theorems each vertex point such as in S (feasible space of the problem (16) is a vertex point to X (feasible space of the problem (15)) if only if for each small positive number

When the follower problems are minimization and

When the follower problems are maximization .

Objective functions correspond feasible vertex points in (15) are recorded.

Step 5: Finding the best objective function among recorded objective functions in step 4 as the best solution to BLPP.

4. Computational Results

To illustrate the algorithm, we first propose the practical following examples and then model them. Finally the proposed examples will be solved using our algorithm.

Example 1:

The supply-chain has four levels in decision: the first level is customs, the second level is products importer, the third level is products wholesaler and the last level is products badger. The decision maker at all four levels try to maximize their own benefits as their objective functions, and each has its own constraints and variables. The importer considers the decision-making process of the customs, the wholesaler considers the decision-making process of the importer, and the badger considers the decision-making process of the wholesaler. At the same time, the customs decisions take into account the reaction of the importer, the importer’s decisions take into account the reaction of the wholesaler, and the wholesaler likewise takes the reaction of the badger into account. The importer wants to maximize own profits and the wholesaler likes to maximize his (her) benefits and the badger wants to maximize own objective function. We establish this problem by a linear quad-level programming model to obtain the optimal solution to determine the cost and price. The model of the problem is simplified as follows:

Using (10-13) let

Then:

And

Therefore

And

Therefore

the above problem is changed to the following problem:

Which, are the smallest values of u, v, w. according to the proposed algorithm (step 2) three last constraints are removed and the following relaxation is obtained:

Using enumeration method some of the vertex points are:

Now we have:

According to the Step 4, all the recent vertex points are infeasible and:

Therefore the problem has just this feasible vertex points:

Some feasible vertex point and objective functions at optimal solution are presented according to Table 1,2. Behavior of the variables in Example 1 has been shown in figure 1.

Figure 1. Behavior of the variables in Example 1.

Table 1. The feasible vertex points in Example 1.


		30
		10
		10
		21

Using above Table the optimal solution by the proposed algorithm as follows:

Table 2. Objective functions at optimal solution by Heuristic algorithm – Example 1.

Optimal Solution	Objective function at best solution by HA
(	(4,6,0,2)
	30
	20
	-4
	18

Example 2

In congestion pricing problem which provides an optimal price for vehicles entering the bridges or specified areas a QLPP model is the best model which in first level the income of the government that in this case usually the municipal is maximized whenever in the second level the tollgate wants to maximization his in the third level the drivers are trying to minimize their route from origin to the destination and in the last level users or passengers want to minimizing their costs. People in tollgate fully consider the decision-making process of the first level, the drivers fully consider the decision-making process of the second level, and the passengers consider the decision-making process of the drivers. At the same time, the first level decisions take into account the reaction of the second level, the second level decisions take into account the reaction of the drivers, and the drivers likewise take the reaction of the passengers into account. We have simplified the model of this problem arriving at following linear QLPP model.

Feasible vertex point and objective functions at optimal solution are presented according to Table 3,4. Behavior of the variables in Example 2 has been shown in figure 2.

Figure 2. Behavior of the variables in Example 2.

Table 3. The feasible vertex points in Example 2.


		100
		27
		39
		45

Using above Table the optimal solution by the proposed algorithm as follows:

Table 4. Objective functions at optimal solution by Heuristic algorithm – Example 2.

Optimal Solution	Objective function at best solution by HA
(
	100


	94.5

5. Conclusion and Future Work

In this paper, a new model of multi-level programming problem which has four levels was been proposed. This model has not been studied already by any researcher. Also a new heuristic approach has been presented to convert the quad-level problem into a single level problem. Then, using the enumeration method all the vertex point of the linear single problem was been obtained. Utilizing the proposed mathematics analyze theorems the optimal solution was proposed. Our algorithm has acceptable numerical results and present good solutions. In the future works, the following should be researched:

(1) Examples in larger sizes can be supplied to illustrate the efficiency of the proposed algorithms.

(2) Showing the efficiency of the proposed algorithms for solving other kinds of QLPP such as quadratic and non-linear QLPP.

Nomenclature

	Objective function of the first level in the QLPP
	Objective function of the second level in the QLPP
	Objective function of the third level in the QLPP
	Objective function of the fourth level in the QLPP
	Slack variable
v	Slack variable
	Slack variable
	Objective function of the first level in the BLPP
	Objective function of the first level in the BLPP
	Constraints in the BLPP
	Feasible region of the QLPP
	Inducible region of the QLPP
	The last feasible values of u
	The last feasible values of v
	The last feasible values of w
	The least upper bound of X
	The greatest lower bound of X
	An arbitrary very small positive number
	Optimal solution for the QLPP
	Optimal solution for the TLPP
	Optimal solution for the BLPP