smart.lab.tunisia@gmail.com +216 71 588 443
Connexion

Bi-level optimization

Description

Aucune description disponible pour cet axe de recherche.

Membres

Ameni Azzouz Ameni Azzouz
Safa Mahouachi Safa Mahouachi
Meriem Ennigrou Meriem Ennigrou
Mouna Karaja Mouna Karaja
Rihab Said Rihab Said
Chaouki Bayoudhi Chaouki Bayoudhi

Publications

  • 2025
    Safa Mahouachi, Maha Elarbi, Slim Bechikh

    Bi-level Evolutionary Model Tree Chain Induction for Multi-output Regression

    Neurocomputing, 646, 130280, 2025

    Résumé

    Multi-output Regression (MOR) is a machine learning technique that aims to predict several values simultaneously. Some existing approaches addressed this problem by decomposing the MOR problem into separate single-target ones. However, in real-world applications, it is more advantageous to exploit the inter-target correlations in the prediction task. Some other approaches proposed simultaneous prediction but they are based on greedy algorithms and are prone to fall easily into local optima. In order to solve these issues, we propose a novel approach called Bi-level Evolutionary Model TreeChain Induction (BEMTCI) which is able to deal with multi-output datasets using a bi-level evolutionary algorithm. BEMTCI evolves a population of Model Tree Chains (MTCs) where each Model Tree (MT) focuses on the prediction of one single target. The upper-level explores different orderings of the MTs of each MTC to find the best chaining order which is able to express the relationships among the output variables. A further optimization is performed in the lower-level of BEMTCI which concerns the linear models at the leaves of the MTs. The experimental study showed the effectiveness of our approach compared to the existing ones when applied on sixteen MOR datasets. The genetic operators employed in our BEMTCI ensure the variation of the population and guarantee a fair and a precise prediction due to the evaluation process. The obtained results prove the performance of our BEMTCI in solving MOR problems.

  • Safa Mahouachi, Maha Elarbi, Khaled Sethom, Slim Bechikh, Carlos A. Coello Coello

    A Bi-Level Evolutionary Model Tree Induction Approach for Regression

    2024 IEEE Congress on Evolutionary Computation (CEC). June 30 - July 5, 2024. YOKOHAMA, JAPAN, 2024

    Résumé

    Supervised machine learning techniques include classification and regression. In regression, the objective is to map a real-valued output to a set of input features. The main challenge that existing methods for regression encounter is how to maintain an accuracy-simplicity balance. Since Regression Trees (RTs) are simple to interpret, many existing works have focused on proposing RT and Model Tree (MT) induction algorithms. MTs are RTs with a linear function at the leaf nodes rather than a numerical value are able to describe the relationship between the inputs and the output. Traditional RT induction algorithms are based on a top-down strategy which often leads to a local optimal solution. Other global approaches based on Evolutionary Algorithms (EAs) have been proposed to induce RTs but they can require an important calculation time which may affect the convergence of the algorithm to the solution. In this paper, we introduce a novel approach called Bi-level Evolutionary Model Tree Induction algorithm for regression, that we call BEMTI, and which is able to induce an MT in a bi-level design using an EA. The upper-level evolves a set of MTs using genetic operators while the lower-level optimizes the Linear Models (LMs) at the leaf nodes of each MT in order to fairly and precisely compute their fitness and obtain the optimal MT. The experimental study confirms the outperformance of our BEMTI compared to six existing tree induction algorithms on nineteen datasets.

  • Rihab Said, Slim Bechikh, Carlos A. Coello Coello, Lamjed Ben Said

    Solving the Discretization-based Feature Construction Problem using Bi-level Evolutionary Optimization

    2023 IEEE Congress on Evolutionary Computation (CEC), Chicago, IL, USA, 2023, pp. 1-8, 2023

    Résumé

    Feature construction represents a crucial data preprocessing technique in machine learning applications because it ensures the creation of new informative features from the original ones. This fact leads to the improvement of the classification performance and the reduction of the problem dimensionality. Since many feature construction methods require discrete data, it is important to perform discretization in order to transform the constructed features given in continuous values into their corresponding discrete versions. To deal with this situation, the aim of this paper is to jointly perform feature construction and feature discretization in a synchronous manner in order to benefit from the advantages of each process. Thus, we propose here to model the discretization-based feature construction task as a bi-level optimization problem in which the constructed features are evaluated based on their optimized sequence of cut-points. The resulting algorithm is termed Discretization-Based Feature Construction (Bi-DFC) where the proposed model is solved using an improved version of an existing co-evolutionary algorithm, named I-CEMBA that ensures the variation of concatenation trees. Bi-DFC performs the selection of original attributes at the upper level and ensures the creation and the evaluation of constructed features at the upper level based on their optimal corresponding sequence of cut-points. The obtained experimental results on ten high-dimensional datasets illustrate the ability of Bi-DFC in outperforming relevant state-of-the-art approaches in terms of classification results.

    Mouna Karaja, Abir Chaabani, Ameni Azzouz, Lamjed Ben Said

    Dynamic bag-of-tasks scheduling problem in a heterogeneous multi-cloud environment: a taxonomy and a new bi-level multi-follower modeling

    J Supercomput 79, 17716–17753 (2023), 2023

    Résumé

    Since more and more organizations deploy their applications through the cloud, an increasing demand for using inter-cloud solutions is noticed. Such demands could inherently result in overutilization of resources, which leads to resource starvation that is vital for time-intensive and life-critical applications. In this paper, we are interested in the scheduling problem in such environments. On the one hand, a new taxonomy of criteria to classify task scheduling problems and resolution approaches in inter-cloud environments is introduced. On the other hand, a bi-level multi-follower model is proposed to solve the budget-constrained dynamic Bag-of-Tasks (BoT) scheduling problem in heterogeneous multi-cloud environments. In the proposed model, the upper-level decision maker aims to minimize the BoT’ makespan under budget constraints. While each lower-level decision maker minimizes the completion time of tasks it received. Experimental results demonstrated the outperformance of the proposed bi-level algorithm and revealed the advantages of using a bi-level scheme with an improvement rate of 32%, 29%, and 21% in terms of makespan for the small, medium, and big size instances, respectively.

  • Mouna Karaja, Abir Chaabani, Ameni Azzouz, Lamjed Ben Said

    Efficient bilevel multi-objective approach for budget-constrained dynamic Bag-of-Tasks scheduling problem in heterogeneous multi-cloud environment

    Applied Intelligence, 1-29, 2022

    Résumé

    Bag-of-Tasks is a well-known model that processes big-data applications supporting embarrassingly parallel jobs with independent tasks. Scheduling Bag-of-Tasks in a dynamic multi-cloud environment is an NP-hard problem that has attracted a lot of attention in the last years. Such a problem can be modeled using a bi-level optimization framework due to its hierarchical scheme. Motivated by this issue, in this paper, an efficient bi-level multi-follower algorithm, based on hybrid metaheuristics, is proposed to solve the multi-objective budget-constrained dynamic Bag-of-Tasks scheduling problem in a heterogeneous multi-cloud environment. In our proposed model, the objective function differs depending on the scheduling level: The upper level aims to minimize the makespan of the whole Bag-of-Tasks under budget constraints; while each follower aims to minimize the makespan and the execution cost of tasks belonging to the Bag-of-Tasks. Since multiple conflicting objectives exist in the lower level, we propose an improved variant of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) called Efficient NSGA-II (E-NSGA-II), applying a recently proposed quick non-dominated sorting algorithm (QNDSA) with quasi-linear average time complexity. By performing experiments on proposed synthetic datasets, our algorithm demonstrates high performance in terms of makespan and execution cost while respecting budget constraints. Statistical analysis validates the outperformance of our proposal regarding the considering metrics.

    Malek Abbassi, Abir Chaabani, Lamjed Ben Said

    An efficient chemical reaction algorithm for multi-objective combinatorial bi-level optimization

    Engineering Optimization, 54(4), 665-686, 2022

    Résumé

    The Bi-Level Optimization Problem (BLOP) is defined as a mathematical program with two nested optimization tasks. Although many applications fit the bi-level framework, however, existing resolution methods were most proposed to solve single-objective bi-level problems. Regarding Multi-objective BLOPs (MBLOPs), there do not exist too many previous studies because of the difficulties associated with solving these complex problems. Additionally, a recently proposed metaheuristic, called Non-dominated sorting Chemical Reaction Optimization (NCRO), has been successfully applied to solve single-level Multi-Objective Problems (MOPs). NCRO applies a quick-non-dominated sorting technique that makes it one of the most powerful search algorithms in solving MOPs. Based on these observations, a new Bi-level Multi-objective CRO method, called BMCRO, is proposed in this article for solving MBLOPs. The main idea behind BMCRO is to come up with good solutions in an acceptable execution time within the bi-level framework. Experimental results on well-established benchmarks reveal the outperformance of the proposed algorithm against a bi-level variant of the Non-dominated Sorting Genetic Algorithm (NSGA-II) which is developed for this purpose.

    Malek Abbassi, Abir Chaabani, Lamjed Ben Said

    An elitist cooperative evolutionary bi-level multi-objective decomposition-based algorithm for sustainable supply chain

    International Journal of Production Research, 60(23), 7013-7032, 2022

    Résumé

    Many real-life applications are modelled using hierarchical decision-making in which: an upper-level optimisation task is constrained by a lower-level one. Such class of optimisation problems is referred in the literature as Bi-Level Optimisation Problems (BLOPs). Most of the proposed methods tackled the single-objective continuous case adhering to some regularity assumptions. This is at odds with real-world problems which involve mainly discrete variables and expensive objective function evaluations. Besides, the optimisation process becomes exorbitantly time-consuming, especially when optimising several objectives at each level. For this reason, the Multi-objective variant (MBLOP) remains relatively less explored and the number of methods tackling the combinatorial case is much reduced. Motivated by these observations, we propose in this work an elitist decomposition-based evolutionary algorithm to solve MBLOPs, called ECODBEMA. The basic idea of our proposal is to handle, decomposition, elitism and multithreading mechanisms to cope with the MBLOP's high complexity. ECODBEMA is applied to the production–distribution problem and to a sustainable end-of-life products disassembly case-study based on real-data of Aix-en-Provence French city. We compared the optimal solutions of an exact method using CPLEX solver with near-optimal solutions obtained by ECODBEMA. The statistical results show the significant outperformance of ECODBEMA against other multi-objective bi-level optimisation algorithms.

    Rihab Said, Maha Elarbi, Slim Bechikh, Carlos Artemio Coello Coello, Lamjed Ben Said

    Interval-based Cost-sensitive Classification Tree Induction as a Bi-level Optimization Problem

    In 2022 IEEE Congress on Evolutionary Computation (CEC) (pp. 1-8). IEEE., 2022

    Résumé

    Cost-sensitive learning is one of the most adopted approaches to deal with data imbalance in classification. Unfortunately, the manual definition of misclassification costs is still a very complicated task, especially with the lack of domain knowledge. To deal with the issue of costs' uncertainty, some researchers proposed the use of intervals instead of scalar values. This way, each cost would be delimited by two bounds. Nevertheless, the definition of these bounds remains as a very complicated and challenging task. Recently, some researches proposed the use of genetic programming to simultaneously build classification trees and search for optimal costs' bounds. As for any classification tree there is a whole search space of costs' bounds, we propose in this paper a bi-level evolutionary approach for interval-based cost-sensitive classification tree induction where the trees are constructed at the upper level while misclassification costs intervals bounds are optimized at the lower level. This ensures not only a precise evaluation of each tree but also an effective approximation of optimal costs intervals bounds. The performance and merits of our proposal are shown through a detailed comparative experimental study on commonly used imbalanced benchmark data sets with respect to several existing works.

    Rihab Said, Maha Elarbi, Slim Bechikh, Carlos Artemio Coello Coello

    Cost-sensitive classification tree induction as a bi-level optimization problem

    In Proceedings of the Genetic and Evolutionary Computation Conference Companion (pp. 284-287), 2022

    Résumé

    Data imbalance is still so far a challenging issue in data classification. In literature, cost-sensitive approach has been used to deal with such a challenge. Despite its interesting results, the manual design of cost matrices is still the main shortcoming of this approach. The data engineer is still facing a great difficulty in defining the misclassification costs, especially with the absence of domain specific knowledge. Recent works suggest the use of genetic programming as an effective tool to design classification trees with automatically learned costs. Although promising results were obtained, evaluating a classification tree with a single cost matrix is not a wise choice. Indeed, the tree quality evaluation requires trying several misclassification cost matrices to be more precise and fair. Motivated by this observation, we propose in this paper a bi-level modeling of the cost-sensitive classification tree induction problem where the upper level evolves the classification trees, while the cost matrix of each tree is optimized at the lower level. Our bi-level modeling is solved using an existing co-evolutionary algorithm, and the resulting method is named Bi-COS. The obtained comparative experimental results on several imbalanced benchmark datasets show the merits of Bi-COS with respect to the state-of-the art.

    Rihab Said, Maha Elarbi, Slim Bechikh, Lamjed Ben Said

    Solving combinatorial bi-level optimization problems using multiple populations and migration schemes

    Operational Research, 22(3), 1697-1735, 2022

    Résumé

    In many decision making cases, we may have a hierarchical situation between different optimization tasks. For instance, in production scheduling, the evaluation of the tasks assignment to a machine requires the determination of their optimal sequencing on this machine. Such situation is usually modeled as a Bi-Level Optimization Problem (BLOP). The latter consists in optimizing an upper-level (a leader) task, while having a lower-level (a follower) optimization task as a constraint. In this way, the evaluation of any upper-level solution requires finding its corresponding lower-level (near) optimal solution, which makes BLOP resolution very computationally costly. Evolutionary Algorithms (EAs) have proven their strength in solving BLOPs due to their insensitivity to the mathematical features of the objective functions such as non-linearity, non-differentiability, and high dimensionality. Moreover, EAs that are based on approximation techniques have proven their strength in solving BLOPs. Nevertheless, their application has been restricted to the continuous case as most approaches are based on approximating the lower-level optimum using classical mathematical programming and machine learning techniques. Motivated by this observation, we tackle in this paper the discrete case by proposing a Co-Evolutionary Migration-Based Algorithm, called CEMBA, that uses two populations in each level and a migration scheme; with the aim to considerably minimize the number of Function Evaluations (FEs) while ensuring good convergence towards the global optimum of the upper-level. CEMBA has been validated on a set of bi-level combinatorial production-distribution planning benchmark instances. The statistical analysis of the obtained results shows the effectiveness and efficiency of CEMBA when compared to existing state-of-the-art combinatorial bi-level EAs.

    Mouna Karaja, Abir Chaabani, Ameni Azzouz, Lamjed Ben Said

    Efficient bi-level multi objective approach for budget-constrained dynamic Bag-of-Tasks scheduling problem in heterogeneous multi-cloud environment.

    Appl Intell 53, 9009–9037 (2023), 2022

    Résumé

    Bag-of-Tasks is a well-known model that processes big-data applications supporting embarrassingly parallel jobs with independent tasks. Scheduling Bag-of-Tasks in a dynamic multi-cloud environment is an NP-hard problem that has attracted a lot of attention in the last years. Such a problem can be modeled using a bi-level optimization framework due to its hierarchical scheme. Motivated by this issue, in this paper, an efficient bi-level multi-follower algorithm, based on hybrid metaheuristics, is proposed to solve the multi-objective budget-constrained dynamic Bag-of-Tasks scheduling problem in a heterogeneous multi-cloud environment. In our proposed model, the objective function differs depending on the scheduling level: The upper level aims to minimize the makespan of the whole Bag-of-Tasks under budget constraints; while each follower aims to minimize the makespan and the execution cost of tasks belonging to the Bag-of-Tasks. Since multiple conflicting objectives exist in the lower level, we propose an improved variant of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) called Efficient NSGA-II (E-NSGA-II), applying a recently proposed quick non-dominated sorting algorithm (QNDSA) with quasi-linear average time complexity. By performing experiments on proposed synthetic datasets, our algorithm demonstrates high performance in terms of makespan and execution cost while respecting budget constraints. Statistical analysis validates the outperformance of our proposal regarding the considering metrics.

  • Mouna Karaja, Meriem Ennigrou, Lamjed Ben Said

    Solving Dynamic Bag-of-Tasks Scheduling Problem in Heterogeneous Multi-cloud Environment Using Hybrid Bi-Level Optimization Model.

    In: Abraham A., Hanne T., Castillo O., Gandhi N., Nogueira Rios T., Hong TP. (eds) Hybrid Intelligent Systems. HIS 2020. Advances in Intelligent Systems and Computing, vol 1375. Springer, Cham., 2021

    Résumé

    Task scheduling problem has attracted a lot of attention since it plays a key role to improve the performance of any distributed system. This is again more challenging, especially for multi-cloud computing environment, mainly based on the nature of the multi-cloud to scale dynamically and due to heterogeneity of resources which add more complexity to the scheduling problem. In this paper, we propose, for the first time, a new Hybrid Bi-level optimization model named HB-DBoTSP to solve the Dynamic Bag-of-Tasks Scheduling Problem (DBoTSP) in heterogeneous multi-cloud environment. The proposed model aims to minimize the makespan and the execution cost while taking into consideration budget constraints and guaranteeing load balancing between Cloud’s Virtual Machines. By performing experiments on synthetic data sets that we propose, we demonstrate the effectiveness of the algorithm.

  • Ameni Azzouz, Abir Chaabani, Meriem Ennigrou, Lamjed Ben Said

    Handling Sequence-dependent Setup Time Flexible Job Shop Problem with Learning and Deterioration Considerations using Evolutionary Bi-level Optimization

    Applied Artificial Intelligence, 34(6), 433-455, 2020

    Résumé

    Bi-level optimization is a challenging research area that has received significant attention from researchers to model enormous NP-hard optimization problems and real-life applications. In this paper, we propose a new evolutionary bi-level algorithm for Flexible Job Shop Problem with Sequence-Dependent Setup Time (SDST-FJSP) and learning/deterioration effects. There are two main motivations behind this work. On the one hand, learning and deterioration effects might occur simultaneously in real-life production systems. However, there are still ill posed in the scheduling area. On the other hand, bi-level optimization was presented as an interesting resolution scheme easily applied to more complex problems without additional modifications. Motivated by these issues, we attempt in this work to solve the FJSP variant using the bi-level programming framework. We suggest firstly a new bi-level mathematical formulation for the considered FJSP; then we propose a bi-level evolutionary algorithm to solve the problem. The experimental study on well-established benchmarks assesses and validates the advantage of using a bi-level scheme over the compared approaches in this research area to solve such NP-hard problem.

    Abir Chaabani, Slim Bechikh, Lamjed Ben Said

    A co-evolutionary hybrid decomposition-based algorithm for bi-level combinatorial optimization problems.

    Soft Computing, 24(10), 7211-7229, 2020

    Résumé

    Bi-level programming problems are a special class of optimization problems with two levels of optimization tasks. These problems have been widely studied in the literature and often appear in many practical problem solving tasks. Although many applications fit the bi-level framework, however, real-life implementations are scarce, due mainly to the lack of efficient algorithms able to handle effectively this NP-hard problem. Several solution approaches have been proposed to solve these problems; however, most of them are restricted to the continuous case. Motivated by this observation, we have recently proposed a Co-evolutionary Decomposition-based Algorithm (CODBA) to solve bi-level combinatorial problems. CODBA scheme has been able to bring down the computational expense significantly as compared to other competitive approaches within this research area. In this paper, we further improve CODBA approach by incorporating a local search procedure to make the search process more efficient. The proposed extension called CODBA-LS includes a variable neighborhood search to the lower-level task to help in faster convergence of the algorithm. Further experimental tests based on the bi-level production–distribution problems in supply chain management model on a set of artificial and real-life data turned out to be effective on both computation time and solution quality.

    Abir Chaabani, Lamjed Ben Said

    A co-evolutionary decomposition-based algorithm for the bi-level knapsack optimization problem

    International Journal of Computational Intelligence Studies, 2020

    Résumé

    Bi-level optimisation problems (BOPs) are a class of challenging problems with two levels of optimisation tasks. These problems allow to model a large number of real-life situations in which a first decision maker, hereafter the leader, optimises his objective by taking the follower's response to his decisions explicitly into account. In this context, a new proposed algorithm called CODBA-II was suggested to solve combinatorial BOPs. The latter was able to improve the quality of generated bi-level solutions regarding to recently proposed methods. In fact, a wide range of applications fit the bi-level programming framework and real-life implementations still scarce. For this reason, we propose in this paper a co-evolutionary decomposition-based bi-level algorithm for the bi-level knapsack optimisation problem. The computational algorithm turned out to be quite efficient on both computation time and solution quality regarding to other competitive EAs.

    Malek Abbassi, Abir Chaabani, Lamjed Ben Said, Nabil Absi

    Bi-level multi-objective combinatorial optimization using reference approximation of the lower-level reaction.

    International conference on Knowledge Based and Intelligent information and Engineering Systems (On Line), 2098-2107, 2020

    Résumé

    Bi-level optimization has gained a lot of interest during the last decade. This framework is suitable to model several real-life situations. Bi-level optimization problems refer to two related optimization tasks, each one is assigned to a decision level (i.e., upper and lower levels). In this way, the evaluation of an upper level solution requires the evaluation of the lower level. This hierarchical decision making necessitates the execution of a significant number of Function Evaluations (FEs). When dealing with a multi-objective optimization context, new complexities are added and imposed by the conflicting objectives and their evaluation techniques. In this paper, we aim to reduce the induced complexity using approximation techniques in order to obtain the lower level optimality. To this end, ideas from multi-objective optimization have been extracted, improved, and hybridized with evolutionary methods to build an efficient approach for Multi-objective Bi-Level Optimization Problems (MBLOPs). In this work, three techniques are suggested: (1) a complete lower level approximation Pareto front procedure, (2) a reference-based approximation selection procedure, and (3) a sub-set reference-based approximation selection one. The proposed variants are applied to a new multi-objective formulation of a well-known combinatorial problem integrating two systems in the supply chain management, namely, the Bi-level Multi Depot Vehicle Routing Problem (Bi-MDVRP). The statistical analysis demonstrates the efficiency of each algorithm according to a set of metrics. Indeed, a large number of savings are detected which confirms the efficiency of our proposals for solving combinatorial optimization problems.

    Malek Abbassi, Abir Chaabani, Lamjed Ben Said, Nabil Absi

    An improved bi-level multi-objective evolutionary algorithm for the production distribution planning system

    In International Conference on Modeling Decisions for Artificial Intelligence, MDAI’20,, 2020

    Résumé

    Bi-level Optimization Problem (BOP) presents a special class of challenging problems that contains two optimization tasks. This nested structure has been adopted extensively during recent years to solve many real-world applications. Besides, a number of solution methodologies are proposed in the literature to handle both single and multi-objective BOPs. Among the well-cited algorithms solving the multi-objective case, we find the Bi-Level Evolutionary Multi-objective Optimization algorithm (BLEMO). This method uses the elitist Non-dominated Sorting Genetic Algorithm (NSGA-II) with the bi-level framework to solve Multi-objective Bi-level Optimization Problems (MBOPs). BLEMO has proved its efficiency and effectiveness in solving such kind of NP-hard problem over the last decade. To this end, we aim in this paper to investigate the performance of this method on a new proposed multi-objective variant of the Bi-level Multi Depot Vehicle Routing Problem (Bi-MDVRP) which is a well-known problem in combinatorial optimization. The proposed BLEMO adaptation is further improved combining jointly three techniques in order to accelerate the convergence rate of the whole algorithm. Experimental results on well-established benchmarks reveal a good performance of the proposed algorithm against the baseline version.

    Rihab Said, Slim Bechikh, Ali Louati, Abdulaziz Aldaej, Lamjed Ben Said

    Solving Combinatorial Multi-Objective Bi-Level Optimization Problems Using Multiple Populations and Migration Schemes

    IEEE Access, vol. 8, pp. 141674-141695, 2020

    Résumé

    Many decision making situations are characterized by a hierarchical structure where a lower-level (follower) optimization problem appears as a constraint of the upper-level (leader) one. Such kind of situations is usually modeled as a BLOP (Bi-Level Optimization Problem). The resolution of the latter usually has a heavy computational cost because the evaluation of a single upper-level solution requires finding its corresponding (near) optimal lower-level one. When several objectives are optimized in each level, the BLOP becomes a multi-objective task and more computationally costly as the optimum corresponds to a whole non-dominated solution set, called the PF (Pareto Front). Despite the considerable number of recent works in multi-objective evolutionary bi-level optimization, the number of methods that could be applied to the combinatorial (discrete) case is much reduced. Motivated by this observation, we propose in this paper an Indicator-Based version of our recently proposed Co-Evolutionary Migration-Based Algorithm (CEMBA), that we name IB-CEMBA, to solve combinatorial multi-objective BLOPs. The indicator-based search choice is justified by two arguments. On the one hand, it allows selecting the solution having the maximal marginal contribution in terms of the performance indicator from the lower-level PF. On the other hand, it encourages both convergence and diversity at the upper-level. The comparative experimental study reveals the outperformance of IB-CEMBA on a multi-objective bi-level production-distribution problem. From the effectiveness viewpoint, the upper-level hyper-volume values and inverted generational distance ones vary in the intervals [0.8500, 0.9710] and [0.0072, 0.2420], respectively. From the efficiency viewpoint, IB-CEMBA has a good reduction rate of the Number of Function Evaluations (NFEs), lying in the interval [30.13%, 54.09%]. To further show the versatility of our algorithm, we have developed a case study in machine learning, and more specifically we have addressed the bi-level multi-objective feature construction problem.

  • Abir Chaabani, Lamjed Ben Said

    Transfer of learning with the coevolutionary decomposition-based algorithm-II: a realization on the bi-level production-distribution planning system.

    Applied Intelligence, 49(3), 963- 982, 2019

    Résumé

    Bi-Level Optimization Problem (BLOP) is a class of challenging problems with two levels of optimization tasks. The main goal is to optimize the upper level problem, which has another optimization problem as a constraint. In this way, the evaluation of each upper level solution requires finding an optimal solution to the corresponding lower level problem, which is computationally so expensive. For this reason, most proposed bi-level resolution methods have been restricted to solve the simplest case (linear continuous BLOPs). This fact has attracted the evolutionary computation community to solve such complex problems. Besides, to enhance the search performance of Evolutionary Algorithms (EAs), reusing knowledge captured from past optimization experiences along the search process has been proposed in the literature, and was demonstrated much promise. Motivated by this observation, we propose in this paper, a memetic version of our proposed Co-evolutionary Decomposition-based Algorithm-II (CODBA-II), that we named M-CODBA-II, to solve combinatorial BLOPs. The main motivation of this paper is to incorporate transfer learning within our recently proposed CODBA-II scheme to make the search process more effective and more efficient. Our proposed hybrid algorithm is investigated on two bi-level production-distribution problems in supply chain management formulated to: (1) Bi-CVRP and (2) Bi-MDVRP. The experimental results reveal a potential advantage of memes incorporation in CODBA-II. Most notably, the results emphasize that transfer learning allows not only accelerating the convergence but also finding better solutions.

  • Abir Chaabani, Slim Bechikh, Lamjed Ben Said

    A new co-evolutionary decomposition-based algorithm for bi-level combinatorial optimization

    Applied Intelligence, 48(9), 2847-2872, 2018

    Résumé

    Bi-Level Optimization Problems (BLOPs) are a class of challenging problems with two levels of optimization tasks. The main goal is to optimize the upper level problem which has another optimization problem as a constraint. The latter is called the lower level problem. In this way, the evaluation of each upper level solution requires finding an (near) optimal solution to the corresponding lower level problem, which is computationally very expensive. Many real world applications are bi-level by nature, ranging from logistics to software engineering. Further, proposed bi-level approaches have been restricted to solve linear BLOPs. This fact has attracted the evolutionary computation community to tackle such complex problems and many interesting works have recently been proposed. Unfortunately, most of these works are restricted to the continuous case. Motivated by this observation, we propose in this paper a new Co-evolutionary Decomposition Algorithm inspired from Chemical Reaction Optimization algorithm, called E-CODBA (Energy-based CODBA), to solve combinatorial bi-level problems. Our algorithm is based on our previous works within this research area. The main idea behind E-CODBA is to exploit co-evolution, decomposition, and energy laws to come up with good solution(s) within an acceptable execution time. The statistical analysis of the experimental results on the Bi-level Multi-Depot Vehicle Routing Problem (Bi-MDVRP) show the out-performance of our E-CODBA against four recently proposed works in terms of effectiveness and efficiency.

    Abir Chaabani, Lamjed Ben Said

    Hybrid CODBA-II Algorithm Coupling a Co-Evolutionary Decomposition-Based Algorithm with Local Search Method to Solve Bi-Level Combinatorial Optimization

    International Conference on Tools with Artificial Intelligence ICTAI’18, Volos, 2018

    Résumé

    Bi-level optimization problems (BLOPs) are a class of challenging problems with two levels of optimization tasks. The usefulness of bi-level optimization in designing hierarchical decision processes prompted several researchers, in particular the evolutionary computation community, to pay more attention to such kind of problems. Several solution approaches have been proposed to solve these problems; however, most of them are restricted to the continuous case. Motivated by this observation, we have recently proposed a Co-evolutionary Decomposition-based Algorithm (CODBA-II) to solve combinatorial bi-level problems. CODBA-II scheme has been able to improve the bi-level performance and to bring down the computational expense significantly as compared to other competitive approaches within this research area. In this paper, we present an extension of the recently proposed CODBA-II algorithm. The improved version, called CODBA-IILS, further improves the algorithm by incorporating a local search process to both upper and lower levels in order to help in faster convergence of the algorithm. The improved results have been demonstrated on two different sets of test problems based on the bi-level production-distribution problems in supply chain management, and comparison results against the contemporary approaches are also provided.

    Abdelkader Dekdouk, Ameni Azzouz, Hiba Yahyaoui, Saoussen Krichen

    Solving energy ordering problem with multiple supply-demand using Bilevel optimization approach

    Procedia Computer Science, 130, 753-759., 2018

    Résumé

    We develop in this paper an energy ordering problem with multiple energy supplying sources and multiple traders trying to satisfy customers’ demands. Such a supply chain network is split of three main layers: the set of energy generation plants (suppliers), a set of traders trying to expect and satisfy customer’s demands dispatched. Following the new investment in renewable energy, customers have the option to choose the nature of its electricity. Customer choice has an impact on the future energy supply chain. For that, we deal with the customer choice in our considered problem. Motivated by this architecture, we propose an evolutionary algorithm-based on bi-level optimization model is developed to handle this problem. The performance of the proposed model is evaluated by numerical experiments based on real-world data.

  • Abir Chaabani, Slim Bechikh, Lamjed Ben Said

    A co-evolutionary decomposition-based chemical reaction algorithm for bi-level combinatorial optimization problems.

    International conference on Knowledge Based and Intelligent information and Engineering Systems KES’17, France, 112, 780-789, 2017

    Résumé

    Bi-level optimization problems (BOPs) are a class of challenging problems with two levels of optimization tasks. The main goal is to optimize the upper level problem which has another optimization problem as a constraint. In these problems, the optimal solutions to the lower level problem become possible feasible candidates to the upper level one. Such a requirement makes the optimization problem difficult to solve, and has kept the researchers busy towards devising methodologies, which can efficiently handle the problem. 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. However, most of these promising results are restricted to the continuous case. The number of existing EBO works for the discrete (combinatorial case) bi-level problems is relatively small when compared to the field of evolutionary continuous BOP. Motivated by this observation, we have recently proposed a Co-evolutionary Decomposition-Based Algorithm (CODBA) to solve combinatorial bi-level problems. The recently proposed approach applies a Genetic Algorithm to handle BOPs. Besides, a new recently proposed meta-heuristic called CRO has been successfully applied to several practical NP-hard problems. To this end, we propose in this work a CODBA-CRO (CODBA with Chemical Reaction Optimization) to solve BOP. The experimental comparisons against other works within this research area on a variety of benchmark problems involving various difficulties show the effectiveness and the efficiency of our proposal.

    Hajer Ben Younes, Ameni Azzouz, Meriem Ennigrou

    Solving flexible job shop scheduling problem using hybrid bilevel optimization model

    In: Madureira, A., Abraham, A., Gandhi, N., Varela, M. (eds) Hybrid Intelligent Systems. HIS 2018. Advances in Intelligent Systems and Computing, vol 923. Springer, Cham., 2017

    Résumé

    Flexible Job Shop Problem (FJSP) has an important significance in both fields of production management and combinatorial optimization. This problem is decomposed into two sub-problems: the assignment problem and the scheduling problem. Following this structure, we consider in this work the FJSP as a bilevel problem. For that, we are interested to solve this problem with bilevel optimization method in which the upper level optimizes the assignment problem and the lower level optimizes the scheduling problem. Therefore, we propose, for the first time, an hybrid bilevel optimization model named HB-FJSP based on both exact and approximate methods to solve the FJSP in order to minimize the makespan. The computational results confirm that our model HB-FJSP provides better solutions than other models.

  • Abir Chaabani, Slim Bechikh, Lamjed Ben Said

    A memetic evolutionary algorithm for bi-level combinatorial optimization: a realization between Bi-MDVRP and Bi-CVRP

    IEEE Congress on Evolutionary Computation CEC’16, Canada, 1666-1673, 2016

    Résumé

    Bi-level optimization problems are a class of challenging optimization problems, that contain two levels of optimization tasks. In these problems, the optimal solutions to the lower level problem become possible feasible candidates to the upper level problem. Such a requirement makes the optimization problem difficult to solve, and has kept the researchers busy towards devising methodologies, which can efficiently handle the problem. In recent decades, it is observed that many efficient optimizations using modern advanced EAs have been achieved via the incorporation of domain specific knowledge. In such a way, the embedment of domain knowledge about an underlying problem into the search algorithms can enhance properly the evolutionary search performance. Motivated by this issue, we present in this paper a Memetic Evolutionary Algorithm for Bi-level Combinatorial Optimization (M-CODBA) based on a new recently proposed CODBA algorithm with transfer learning to enhance future bi-level evolutionary search. A realization of the proposed scheme is investigated on the Bi-CVRP and Bi-MDVRP problems. The experimental studies on well established benchmarks are presented to assess and validate the benefits of incorporating knowledge memes on bi-level evolutionary search. Most notably, the results emphasize the advantage of our proposal over the original scheme and demonstrate its capability to accelerate the convergence of the algorithm.