Application of Genetic Algorithm for Solving Bilevel Linear Programming Problems

Abstract

Bilevel linear programming problem is a special class of nonconvex optimization problems which involves two levels with a hierarchical organization structure. In this paper, we present a genetic algorithm (GA) based approach to solve the bilevel linear programming (BLP) problem. The efficiency of this approach is confirmed by comparing the results with Kuo and Han’s method HGAPSO consisting of a hybrid of GA and particle swarm optimization algorithm (PSO) in Kuo and Han (Applied Mathematical Modelling 35:3905–3917, 2011, [15]) using four problems in the literature and an example of supply chain model. These results show that the proposed approach provides the optimal solution and outperforms HGAPSO for most test problems adopted from the literature.

Appendix

Test problem 1

$$\begin{aligned} \begin{array}{lcl} \displaystyle \max _{x_{1}} \; F=-2x_{1}+11x_{2}\\ where \; x_{2}\; solves \\ \displaystyle \max _{x_{2}} \; f=-x_{1}-3x_{2} \\ \displaystyle \textit{s.t.} \quad x_{1}-2x_{2} \le 4 \\ \qquad 2x_{1}-x_{2} \le 24 \\ \qquad 3x_{1}+4x_{2} \le 96 \\ \qquad x_{1}+7x_{2} \le 126 \\ \qquad -4x_{1}+5x_{2} \le 65 \\ \qquad x_{1}+4x_{2} \ge 8 \\ \qquad x_{1},x_{2} \ge 0. \end{array} \end{aligned}$$

(8.8)

Test problem 2

$$\begin{aligned} \begin{array}{lcl} \displaystyle \max _{x_{1}} \; F=x_{2} \\ where \; x_{2}\; solves \\ \displaystyle \max _{x_{2}} \; f=-x_{2} \\ \displaystyle \textit{s.t.} \; -x_{1}-2x_{2} \le 10 \\ \qquad x_{1}-2x_{2} \le 6 \\ \qquad 2x_{1}-x_{2} \le 21 \\ \qquad x_{1}+2x_{2} \le 38 \\ \qquad -x_{1}+2x_{2} \le 18 \\ \qquad x_{1}, x_{2} \ge 0. \end{array} \end{aligned}$$

(8.9)

Test problem 3

$$\begin{aligned} \begin{array}{lcl} \displaystyle \max _{x_{1}} \; F=x_{1}+3x_{2} \\ where \; x_{2}\; solves \\ \displaystyle \max _{x_{2}} \; f=-x_{2} \\ \displaystyle \textit{s.t.} \; -x_{1}+x_{2} \le 3 \\ \qquad x_{1}+2x_{2} \le 12 \\ \qquad 4x_{1}-x_{2} \le 12 \\ \qquad x_{1}, x_{2} \ge 0. \end{array} \end{aligned}$$

(8.10)

Test problem 4

$$\begin{aligned} \begin{array}{lcl} \displaystyle \max _{x} \; F=8x_{1}+4x_{2}-4y_{1}+40y_{2}-4y_{3} \\ where \; y\; solves \\ \displaystyle \max _{y} \; f=-x_{1}-2x_{2}-y_{1}-y_{2}-2y_{3} \\ \displaystyle \textit{s.t.} \qquad y_{1}-y_{2}-y_{3} \ge -1 \\ \qquad -2x_{1}+y_{1}-2y_{2}+0.5y_{3}\ge -1 \\ \qquad -2x_{2}-2y_{1}+y_{2}+0.5y_{3}\ge -1 \\ \qquad \quad x_{1}, x_{2}, y_{1}, y_{2}, y_{3}\ge 0 \end{array} \end{aligned}$$

(8.11)

Test problem 5

$$\begin{aligned} \begin{array}{lcl} \displaystyle \max _{x_{1}}\; F=-x_{1}-x_{2} \\ where \; x_{2}\; solves \\ \displaystyle \max _{x_{2}} \; f=5x_{1}+x_{2} \\ \displaystyle \textit{s.t.}\quad -x_{1}- \frac{x_{2}}{2} \le -2 \\ \qquad -\frac{x_{1}}{4}+x_{2} \le 2 \\ \qquad \quad x_{1}+\frac{x_{2}}{2} \le 8 \\ \qquad \quad x_{1}-2x_{2} \le 4 \\ \qquad \quad \quad x_{1}, x_{2} \ge 0 \end{array} \end{aligned}$$

(8.12)

Test problem 6

$$\begin{aligned} \begin{array}{lcl} \displaystyle \max _{x}\; F=2x_{1}-x_{2}+0.5y_{1} \\ where \; y\; solves \\ \displaystyle \max _{y} \; f=-x_{1}-x_{2}+4y_{1}-y_{2} \\ \displaystyle \textit{s.t.}\quad 2x_{1}-y_{1}+y_{2}\ge 2.5 \\ \qquad -x_{1}+3x_{2}-y_{2} \ge -2 \\ \qquad -x_{1}-x_{2} \ge -2 \\ \qquad \quad \quad x, y \ge 0 \end{array} \end{aligned}$$

(8.13)