A co-evolutionary decomposition-based algorithm for Bi-Level combinatorial optimization

Several optimization problems encountered in practice have two levels of optimization instead of a single one. These BLOPs (Bi-Level Optimization Problems) are very computationally expensive to solve since the evaluation of each upper level solution requires finding an optimal solution for the lower level. Recently, a new research field, called EBO (Evolutionary Bi-Level Optimization) has appeared thanks to the promising results obtained by the use of EAs (Evolutionary Algorithms) to solve such kind of problems. Most of these promising results are restricted to the continuous case. Motivated by this observation, we propose a new bi-level algorithm, called CODBA (CO-Evolutionary Decomposition based Bi-level Algorithm), to tackle combinatorial BLOPs. The basic idea of our CODBA is to exploit decomposition, parallelism, and co-evolution within the lower level in order to cope with the high computational cost. CODBA is assessed on a set of instances of the bi-level MDVRP (MultiDepot Vehicle Routing Problem) and is confronted to two recently proposed bi-level algorithms. The statistical analysis of the obtained results shows the merits of CODBA from effectiveness and efficiency viewpoints.

I. Introduction

Bi-level optimization is an important field of mathematical programming. It represents a special kind of optimization problems where one problem is nested within another. This kind of problem allows modeling a large number of real-life applications such as supply chain management [1], security and defense [2], reliability-based design optimization [3], just to cite a few. In such kind of problems, we find a hierarchy between two optimization problems. The outer optimization task is usually referred as the upper level problem or the leader one. The nested inner optimization task is referred as the lower level problem or the follower. The follower appears as a constraint of the leader such that only an optimal solution to the follower is a possible feasible candidate to the leader [4]. Such a requirement makes BLOPs difficult to handle and have kept researchers and practitioners busy alike. Resolution methods could be classified into two main families: (1) classical methods and (2) evolutionary ones. The first family includes the Karush-Kuhn-Tucker approach [5], extreme point-based approaches [6], branch-and-bound [7], complementary pivoting [8], descent methods [9], penalty function methods [10], trust region methods [11], etc. The main shortcoming of these methods is that they heavily depend on the mathematical characteristics of the BLOP, which makes them unsuitable to handle real world problems' difficulties such dimensionality, non-linearity, etc. For this reason, most classical methods studied for a long time tackle the linear case (i.e., the simplest case) in which all objective functions and constraints are linear with respect to the decision variables. The second family includes EAs that are a class of approximate algorithms focusing on finding good-quality solutions for large-size and complex problems in a reasonable amount of time. Some examples of works using EAs to solve BLOPs are Sinha et al. [12], Legillon et al. [17], and Koh [13]. The main challenge faced when solving a BLOP using an EA is the high computational cost. Indeed, the evaluation of each upper level solution requires executing another EA to find the lower level (near-)optimal solution. Assuming a lower level population of 50 individuals that is evolved for 50 generations, the evaluation of an upper level solution requires 2500 evaluations, which is very computationally expensive. For this reason, Sinha et al. [12] proposed a bi-level algorithm based on quadratic approximation which has shown a significant effectiveness in reducing the number of lower level evaluations. From a performance assessment viewpoint, several test problems has been recently proposed by Sinha et al. [15] that include several difficulties such as difficulty in convergence at upper/lower level, interaction between both levels (conflict or cooperation), constraints at upper/lower level, etc. An interesting observation regarding the EBO literature consists in that most works are solving the continuous case. The number of EBO works for the discrete (combinatorial case) is so scarce. Thus, the main goal of our paper is to propose an efficient EBO approach for combinatorial optimization, where ideas like exploiting quadratic approximation could not be used. The principal contributions of this paper are the following: