Evolutionary Bilevel Optimization

Bilevel programming problems are a special class of optimization problems with two levels of optimization task. These problems have been widely studied in the literature (Sinha et al. 2018; Colson et al. 2007; Vicente and Calamai 2004; Dempe et al. 2006) and often appear in many practical problem solving tasks (Bard 1998). Bilevel problems are different from the common optimization problems, as they contain a nested optimization task within the constraints of another optimization problem. The outer optimization problem is referred as the upper level task and the inner optimization problem is referred as the lower level task. The nested structure of the overall problem requires that a solution to the upper level problem may be feasible only if it is an optimal solution to the lower level problem. This requirement makes bilevel optimization problems very difficult to solve.

A generic bilevel optimization problem can be formulated as follows:

$$\begin{align*} \min_{x_u,x_l}\quad & F(x_u,x_l) \\ \hbox{such that} & \\ & x_l\in \hbox{argmin}_{x_l} \lbrace \hspace{1mm} f(x_u,x_l):g_j(x_u,x_l)\leq 0, j=1,\dots,J \hspace{1mm} \rbrace\\ & G_k(x_u,x_l)\leq 0, k=1,\dots,K \\ & x_u\in X_U,x_l\in X_L \end{align*}$$

where $x_u$ represents the upper level decision vector and $x_l$ represents the lower level decision vector. The objective functions at the upper and lower level are represented by $F$ and $f$ respectively. Inequality constraints at the upper and lower levels are represented by $G_k$ and $g_j$ respectively. For brevity, equality constraints have not been shown in the formulation. $X_U$ and $X_L$ are the bound constraints for the upper level decision vector and lower level decision vector.

In practice, a bilevel scenario commonly occurs when a set of decision variables in an (upper level) optimization task is considered physically or functionally acceptable, only when it is a stable point or a point in equilibrium or a point satisfying certain conservation principles, etc. Satisfaction of one or more of these conditions is usually posed as another (lower level) optimization task. The bilevel optimization problems are known to be challenging, and often (Bianco et al. 2009; Dempe 2002; Pakala 1994) such problems are not treated as bilevel programming problems. Instead, some approximate methodologies are used to replace the lower level problem and convert the problem into a single-level optimization task.

The origin of bilevel programming can be traced to two roots. The first root is the domain of game theory, where such problems were first realized by Stackelberg (Stackelberg 1952) and came to be known as Stackelberg problems. The second root is the domain of mathematical programming, where the problems appeared as bilevel optimization problems containing an optimization problem within the constraints of another optimization problem (Bracken and McGill 1973). Bilevel problems have since then been widely studied by researchers, in the field of classical as well as evolutionary optimization. Most of the classical methods for handling bilevel problems require assumptions of smoothness, linearity or convexity. This includes the Karush-Kuhn-Tucker approach (Herskovits et al. 2000; Bianco et al. 2009), Branch-and-bound approach (Bard and Falk 1982) and the use of penalty functions (Aiyoshi 1981). A number of evolutionary techniques have also been developed (Mathieu et al. 1994; Yin 2000, Sinha et al. 2013; Angelo et al. 2013) to handle complex bilevel problems, which do not adhere to the simplifying assumptions required by the classical methods. However, most of the evolutionary bilevel optimization methods are computationally intensive nested strategies, and there is a need for approaches that can handle the task more efficiently. Studies on test problems and generators (Mitsos 2006; Sinha et al. 2014; Deb and Sinha 2010) are also available for evaluating the bilevel solution procedures.

There also exist multi-objective extensions of the bilevel optimization problems, which contain multiple objectives at one or both levels. However, apart from a few recent studies in classical (Eichfelder 2008) and evolutionary optimization (Halter and Mostaghim 2006; Shi and Xia 2001; Sinha and Deb 2009; Deb and Sinha 2010), little has been done in this direction. Multiple objectives in bilevel optimization adds an additional stratum of difficulty to the problem.

References

• E. Aiyoshi and K. Shimizu. Hierarchical decentralized systems and its new solution by a barrier method. IEEE Transactions on Systems, Man, and Cybernetics, 11:444–449, 1981.
• J. Angelo, E. Krempser and H. Barbosa. Differential Evolution for Bilevel Programming. In 2013 IEEE Congress on Evolutionary Computation (CEC-2013). IEEE Press, 2013.
• J. Bard. Practical Bilevel Optimization: Algorithms and Applications. The Netherlands: Kluwer, 1998.
• J. Bracken and J. McGill. Mathematical programs with optimization problems in the constraints. Operations Research 21: 37–44, 1973.
• L. Bianco, M. Caramia, and S. Giordani. A bilevel flow model for hazmat transportation network design. Transportation Research Part C: Emerging technologies, 17(2):175–196, 2009.
• J.F. Bard and J. Falk. An explicit solution to the multi-level programming problem. Computers and Operations Research, 9:77–100, 1982.
• B. Colson, P. Marcotte, and G. Savard. An overview of bilevel optimization. Annals of Operational Research, 153:235–256, 2007.
• K. Deb and A. Sinha. An efficient and accurate solution methodology for bilevel multi-objective programming problems using a hybrid evolutionary-local-search algorithm. Evolutionary Computation Journal, 18(3):403–449, 2010.
• S. Dempe. Foundations of bilevel programming. Kluwer: Dordrecht, 2002.
• S. Dempe, J. Dutta, S. Lohse. Optimality conditions for bilevel programming problems. Optimization, 55(5–6):505–524, 2006.
• G. Eichfelder. Multiobjective bilevel optimization. Mathematical Programming. DOI 10.1007/s10107-008-0259-0, 2008.
• W. Halter and S. Mostaghim. Bilevel optimization of multi-component chemical systems using particle swarm optimization. In Proceedings of World Congress on Computational Intelligence (WCCI-2006), pages 1240–1247, 2006.
• J. Herskovits, A. Leontiev, G. Dias, and G. Santos. Contact shape optimization: A bilevel programming approach. Struct Multidisc Optimization, 20:214–221, 2000.
• R. Mathieu, L. Pittard, and G. Anandalingam. Genetic algorithm based approach to bi-level linear programming. Operations Research, 28(1):1–21, 1994.
• A. Mitsos and P. I. Barton. A test set for bilevel programs, 2006. http://yoric.mit.edu/download/Reports/bileveltestset.pdf.
• R. R. Pakala. A study on applications of stackelberg game strategies in concurrent design models. University of Houston, 1994.
• X. Shi. and H. S. Xia. Model and interactive algorithm of bi-level multi-objective decision-making with multiple interconnected decision makers. Journal of Multi-Criteria Decision Analysis, 10(1):27–34, 2001.
• A. Sinha and K. Deb. Towards understanding evolutionary bilevel multi-objective optimization algorithm. In IFAC Workshop on Control Applications of Optimization (IFAC-2009), volume 7. Elsevier, 2009.
• A. Sinha, P. Malo, and K. Deb. Test problem construction for single-objective bilevel optimization. Evolutionary Computation Journal, 22(3):439-477, 2014.
• A. Sinha, P. Malo, and K. Deb. A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22(2):276-295, 2018.
• A. Sinha, P. Malo, A. Frantsev, and K. Deb. Finding optimal strategies in multi-period multi- leader-follower stackelberg games using an evolutionary framework. Computers and Operations Research. Elsevier, 2013 (In Press).
• Heinrich von Stackelberg. The theory of the market economy. Oxford University Press, New York, 1952.
• L. N. Vicente and P. H. Calamai. Bilevel and multilevel programming: A bibliography review. Journal of Global Optimization, 5(3):291–306, 2004.
• Y. Yin. Genetic algorithm based approach for bilevel programming models. Journal of Transportation Engineering, 126(2):115–120, 2000.