Search

Combinatorial bi-level optimization remains a challenging topic, especially when the lower-level is an ${\mathcal {NP}}$ -hard problem. In this paper, we tackle large-scale and combinatorial bi-level problems using GP hyper-heuristics, i.e., an approach that permits to train heuristics like a machine learning model. Our contribution aims at targeting the intensive and complex lower-level optimizations that occur when solving a large-scale and combinatorial bi-level problem. For this purpose, we consider hyper-heuristics through heuristic generation. Using a GP hyper-heuristic approach, we train greedy heuristics in order to make them more reliable when encountering unseen lower-level instances that could be generated during bi-level optimization. To validate our approach referred to as GA+AGH, we tackle instances from the bi-level cloud pricing optimization problem (BCPOP) that model the trading interactions between a cloud service provider and cloud service customers. Numerical results demonstrate the abilities of the trained heuristics to cope with the inherent nested structure that makes bi-level optimization problems so hard. Furthermore, it has been shown that training heuristics for lower-level optimization permits to outperform human-based heuristics and metaheuristics which constitute an excellent outcome for bi-level optimization.

In this paper, we focus on the coloration approach and estimation of chromatic number. First, we propose an upper bound of the chromatic number based on the orientation algorithm described in previous studies. This upper bound is further improved by developing a novel coloration algorithm. Second, we make a theoretical and empirical comparison of our bounds with Brooks’s bound and Reed’s conjecture for class of triangle-free graphs. Third, we propose an adaptation of our algorithm to deal with the team building problem respecting several hard and soft constraints. Finally, a real case study from healthcare domain is considered for illustration.

International audience; Communication satellites have the crucial role to forward signals to customers. They filter and amplify uplink signals coming from Earth stations to improve the signal quality before reaching customers. These operations are performed by the payload component of the satellite that embeds reconfigurable components (e.g., switches). These components route signals to appropriate signal processing components (e.g., amplifiers, filters) and lead amplified signals to the output antenna. In order to route the channels that compose signals, satellite engineers can remotely modify switch states. These are typically updated when one or more new channels must be connected or when failures occur. However, satellites embed always more switches to answer customer demands, which makes their reconfiguration time consuming and error prone without appropriate decision aid tools. Power transmission is a crucial objective to ensure a maximum quality of service at reasonable cost. This is why satellite operators aim at minimizing incoming power signals while guaranteeing a maximum factor of amplification at the output antenna. This problem is referred to as the “satellite payload power problem.” Previous works have outlined the difficulty to solve exactly large instances of this problem. This work proposes to improve the existing mathematical formulation of the switch network. We show that it can be modeled as a static network and switch states can be deduced after optimization, thus limiting the combinatorial explosion. Computational experiments on different sizes of realistic instances using the adaptive ε‐constraint method demonstrate the computational time gain with this new model and the possibility to solve larger instances.

This paper proposes a new method to determine the clique of maximum cardinality in a graph. More precisely, we propose a contraction-based approach, which uses the orientation algorithm and the labeling order scheme of vertices. This method allows to effeciently compute both upper and lower bounds of the clique number. The experimental results on instances of the library DIMACS are validated against our method.

In this paper, we address the problem of humanitarian aids distribution across refugee camps in war-ridden areas from a network design perspective. We show that the problem can be modeled as a variant of multi-period hub location problem with a particular demand pattern resulted by the user’s behavior. The problem has been motivated by a case study of Lebanese experience in Syrian war refugee accommodation. We elaborate on the complexity and real-life constraints and, propose a compact formulation of a mathematical model of the problem. We then show that modeling the problem using a Benders paradigm drives O ( n 3 ) variables of the original compact model unnecessary in addition to the constraints that are being projected out in a typical Benders decomposition. Additionally, we identify several classes of valid inequalities together with efficient separation procedures leading to a cut-and-Benders approach. Our extensive computational experiments on the case study with real data as well as randomly generated instances proves the performance of proposed solution methods.

Real-life problems often involve several decision makers whose decisions impact each other. When two decision makers decides sequentially, these problems are referred to as bi-level optimization problems. Generally modeled as nested optimization problems, they are NP-hard even for two linear and continuous levels. Such problems often occur in situations were only a part of the decision variables is controlled by each decision makers. Their final objective value is thus subject to each other's decision. From the first decision maker point of view, it is necessary to predict the rational reaction of the second decision maker which may have a conflicting objective function. The first decision maker should therefore ensure that this reaction will not have a disastrous effect on its own final objective value. The inherent complexity of bi-level optimization problems led researchers to consider metaheuristics. Among the most promising metaheuristics, co-evolutionary algorithms proved their abilities to tackle large scale problems. Unfortunately, BOPs are naturally strongly epistatic. In this work, we propose an hybrid competitive co-evolutionary algorithm (CARBON) to tackle this pitfall. We compare CARBON against another co-evolutionary approach for bi-level optimization problems, i.e., COBRA. Experimental results demonstrate the abilities of CARBON to break the inherent nested structure that makes bi-level optimization problems so difficult.

Real-life problems including transportation, planning and management often involve several decision makers whose actions depend on the interaction between each other. When involving two decision makers, such problems are classified as bi-level optimization problems. In terms of mathematical programming, a bi-level program can be described as two nested problems where the second decision problem is part of the first problem's constraints. Bi-level problems are NP-hard even if the two levels are linear. Since each solution implies the resolution of the second level to optimality, efficient algorithms at the first level are mandatory. In this work we propose BOBP, a Bayesian Optimization algorithm to solve Bi-level Problems, in order to limit the number of evaluations at the first level by extracting knowledge from the solutions which have been solved at the second level. Bayesian optimization for hyper parameter tuning has been intensively used in supervised learning (e.g., neural networks). Indeed, hyper parameter tuning problems can be considered as bi-level optimization problems where two levels of optimization are involved as well. The advantage of the bayesian approach to tackle multi-level problems over the BLEAQ algorithm, which is a reference in evolutionary bi-level optimization, is empirically demonstrated on a set of bi-level benchmarks.

Handling constraints is not a trivial task in evolutionary computing. Even if different techniques have been proposed in the literature, very few have considered co-evolution which tends to decompose problems into easier sub-problems. Existing co-evolutionary approaches have been mainly used to separate the decision vector. In this article we propose a different co-evolutionary approach, referred to as co-evolutionary constraint decomposition algorithm (CCDA), that relies on a decomposition of the constraints. Indeed, it is generally the conjunction of some specific constraints which hardens the problems. The proposed CCDA generates one sub-population for each constraint and optimizes its own local fitness. A sub-population will first try to satisfy its assigned constraint, then the remaining constraints from other sub-populations using a cooperative mechanism, and finally the original objective function. Thanks to this approach, sub-populations will have different behaviors and solutions will approach the feasible domain from different sides. An exchange of information is performed using crossover between individuals from different sub-populations while mutation is applied locally. Promising mutated features are then transmitted through mating. The proposed CCDA has been validated on 8 well-known benchmarks from the literature. Experimental results show the relevance of constraint decomposition in the context of co-evolution compared to state-of-the-art algorithms.

Over the last years, the activities related to unmanned aerial vehicle have seen an exponential growth in several application domains. In that context, a great interest has been devoted to search and tracking scenarios, which require the development of novel UAV mobility management solutions. Recent works on mobility models have shown that bio-inspired algorithms such as ant colonies, have a real potential to tackle complex scenarios. Nevertheless, most of these algorithms are either modified path planning algorithms or dynamical algorithms with no a priori knowledge. This paper proposes H3MP, a hybrid model based on Markov chains and pheromones to take advantage of both static and dynamic methods. Markov chains are evolved to generate a global behavior guiding UAVs to promising areas while pheromones allow local and dynamical mobility management thanks to information sharing between UAVs via stigmergy. Experimental results demonstrate the ability of H3MP to rapidly detect and keep watch on targets compared to random and pheromone based models.

In this paper, a novel type of co-evolutionary algorithm based on constraints decomposition (CHCGA) is proposed. Its principle consists in dividing an initial constrained problem into a sufficient number of sub-problems with weak constrained domains where feasible solutions can be easily determined. One sub-population for each sub-problems are then evolved independently and merged when they become compatible with each other, i.e. they contain enough mutually feasible solutions. Experimental results on the Cloud Brokering optimization problem have demonstrated a strong solution quality gain compared to a standard genetic algorithm.

International audience; This paper presents a new variation of the packing problem, where the dimensions of the objects belong to intervals instead of being fixed. This problem is solved with linear optimization and applied to the automated computation of a dwelling layout. The proposed layout, besides meeting some elementary building rules, also takes into account wishes expressed by the future occupant.

The 0-1 quadratic knapsack problem consists of maximizing a quadratic objective function subject to a linear capacity constraint. To exactly solve large instances of this problem with a tree search algorithm (e.g., a branch and bound method), the knowledge of good lower and upper bounds is crucial for pruning the tree but also for fixing as many variables as possible in a preprocessing phase. The upper bounds used in the best known exact approaches are based on Lagrangian relaxation and decomposition. It appears that the computation of these Lagrangian dual bounds involves the resolution of numerous 0-1 linear knapsack subproblems. Thus, taking this huge number of resolutions into account, we propose to embed reoptimization techniques for improving the efficiency of the preprocessing phase of the 0-1 quadratic knapsack resolution. Namely, reoptimization is introduced to accelerate each independent sequence of 0-1 linear knapsack problems induced by the Lagrangian relaxation as well as the Lagrangian decomposition. Numerous numerical experiments validate the relevance of our approach.

We propose a Mixed-Integer Linear Programming model for a class of multi-period crop rotation optimization problems with demand constraints and incompatibility constraints between cultivation and fallow state on a land plot. This model is applied to a case study on Madagascan farms in the scope of a sustainable development campain against deforestation, where the objective is to better control agricultural space while covering seasonal needs of farmer. We propose an efficient upper bound computation and study the variation of the minimum number of plots and total space needed in function of the unitary surface area of a plot. Numerical results associated with the Madagascan case are reported.

First, this paper deals with lagrangean heuristics for the 0–1 bidimensional knapsack problem. A projected subgradient algorithm is performed for solving a lagrangean dual of the problem, to improve the convergence of the classical subgradient algorithm. Secondly, a local search is introduced to improve the lower bound on the value of the biknapsack produced by lagrangean heuristics. Thirdly, a variable fixing phase is embedded in the process. Finally, the sequence of 0–1 one-dimensional knapsack instances obtained from the algorithm are solved by using reoptimization techniques in order to reduce the total computational time effort. Computational results are presented.

The shortest path problem with resource constraints consists of finding the minimum cost path between two specified points while respecting constraints on resource consumption. Its solving by a dynamic programming algorithm requires a computation time increasing with the number of resources. With the aim of producing rapidly a good heuristic solution we propose to reduce the state space by aggregating resources. Our approach consists of projecting the resources on a vector of smaller dimension and then to dynamically adjust the projection matrix to get a better approximation of the optimal solution. We propose an adjustment based on Lagrangian and surrogate relaxations in a column generation framework, in which the sub-problems are shortest path problems with resource constraints. We adjust the multipliers only one time at each column generation iteration. This permit to obtain good solutions of the scheduling problem in few time.

This paper deals with a new algorithm for a 0-1 bidimensional knapsack Lagrangean dual which relaxes one of the two constraints. Classical iterative algorithms generate a sequence of multipliers which converges to an optimal one. In this way, these methods generate a sequence of 0-1 one-dimensional knapsack instances. Generally, the procedure for solving each instance is considered as a black box. We propose to design a new iterative scheme in which the computation of the step size takes into account the algorithmic efficiency of each instance. Our adapted step size iterative algorithm is compared favorably with several other algorithms for the 0-1 biknapsack Lagrangean dual over difficult instances for CPLEX 7.0.

Les programmes fractionnaires consistent a optimiser un objectif mis sous la forme d'un rapport de deux fonctions lineaires ou non, soumis a un ensemble de contraintes. Differentes versions de ce modele, lineaires ou non lineaires, en nombres entiers ou en continu, ont une multitude d'applications que ce soit en optimisation combinatoire, en programmation stochastique, en bases de donnees ou en economie. Trois grandes strategies de resolution d'un programme fractionnaire emergent dans la litterature. la resolution directe, la resolution par parametrisation et la resolution d'un probleme equivalent a objectif simplifie. Un catalogue de ces modeles et applications mettant en jeu des programmes fractionnaires precede une synthese des methodes de resolution incluant en particulier celles dediees aux programmes hyperboliques (optimisation d'un rapport de deux fonctions affines soumis a des contraintes lineaires) en variables 0-1.

10th IEEE International Conference on Networking, Sensing and Control (ICNSC), Evry Val Essonne Univ, FRANCE, APR 10-12, 2013; International audience; In this paper we describe a new approach to model and to solve the job shop scheduling problem using a strip packing formulation. The formulation is enhanced by introducing some valid inequalities in order to compute an efficient lower bound.

This work deals with different strategies of cooperations between a greedy heuristic and a column generation scheme for exponential size covering integer programs. Computational experiments are proposed on a real-case transportation problem.

Cet article est un travail de synthese autour de l'analyse de sensibilite pour les problemes lineaires en variables 0-1. De nombreux aspects sont ainsi abordes: historique et formes d'analyse de sensibilite, exemples d'application, complexite, conditions d'optimalite, algorithmes et approches. Nous dressons par ailleurs quelques perspectives de recherche actuelles dans ce domaine.

International audience; In this paper we consider the total completion time minimization in a job-shop. We propose a new mathematical formulation based on a strip packing model. This formulation is enhanced by introducing some valid inequalities in order to compute an efficient lower bound. It is also exploited to derive an exact method; branch-and-bound algorithm which uses an improved solution of a genetic algorithm. The proposed algorithms are tested on standard benchmarks and the results are satisfactory in term of solution quality and the distance to the optimal solution.

National audience

International audience; The 0-1 quadratic knapsack problem consists in maximizing a quadratic objective function subject to a linear capacity constraint. To solve exactly large instances of this problem with a tree search algorithm (e.g. a branch and bound method), the knowledge of good lower and upper bounds is crucial for pruning the tree but also for fixing as many variables as possible in a preprocessing phase. The upper bounds used in the best known exact approaches are based on Lagrangian relaxation and decomposition. It appears that the computation of these Lagrangian dual bounds involves the resolution of numerous 0-1 linear knapsack subproblems. Thus, taking this huge number of solvings into account, we propose to embed reoptimization techniques for improving the efficiency of the preprocessing phase of the 0-1 quadratic knapsack resolution. Namely, reoptimization is introduced to accelerate each independent sequence of 0-1 linear knapsack problems induced by the Lagrangian relaxation as well as the Lagrangian decomposition. Numerous numerical experiments validate the relevance of our approach.

29 pages; The use of the method of column generation was intensified during the last decades, in particular for the resolution of huge discrete problems in order to obtain a lagrangian bound. It is also integrated in a branch and bound method (branch-and-price) where it is used for the computation of the evaluation function at each node of the research tree. The efficiency of this method is very related to the resolution of the subproblems and to the quality of the columns generated at each iteration. Like iterative methods, it suffers from the long tail effect, particularly when it is used to solve degenerated problems. The scheme of column generation offers several possibilities for improvements. We present in this report some of these possibilities suggested in the literature, which are based on varied principles according to whether one operates on the primal or dual plan, or that acceleration relates to the resolution of the master problem, the subproblem or the whole process, or his hybridization with other resolution methods. At the end of this report, we focus our study on reoptimization techniques, which prove to be promising for the acceleration of column generation, particularly when the total time of resolution is dominated by that of the subproblems.

International audience; Column generation algorithms have been specially designed for solving mathematical programs with a huge number of variables. Unfortunately, this method suffers from slow convergence that limits its efficiency and usability. Several accelerating approaches are proposed in the literature such as stabilization-based techniques. A more classical approach, known as "intensification, consists in inserting a set of columns instead of only the best one. Unfortunately, this intensication typically overloads the master problem, and generates a huge number of useless variables. This article covers some characteristics of the generated columns from theoretical and experimental points of view. Two selection criteria are compared. The first one is based on column reduced cost and the second on column structure. We conclude our study with computational experiments on two kinds of problems: the acyclic vehicle routing problem with time windows and the one-dimensional cutting stock. problem.

International audience; This paper focuses on accelerating strategies in a Column Generation (CG) algorithm. In order to decrease the total number of generated columns and then, master problems resolution time, pricing problems solutions are made of task-disjoint columns. This can be achieved by diversification methods. Another way to improve CG computing time is to use reoptimization approaches to solve efficiently the pricing problems. We show in this work that diversification approaches are more efficient when applied on the first iterations to build efficiently a good approximation of pricing problems convex hull and that reoptimization methods are more efficient when applied on the last iterations when the dual variables are close. We combine a diversification technique and a reoptimization procedure in a CG scheme to improve the global resolution time. This study is validated on the Vehicle Routing Problem with Time Windows (VRPTW), defined on acyclic networks.

International audience

International Conference on Control, Decision and Information Technologies (CoDIT), Ecole Natl Ingenieurs Metz, Metz, FRANCE, NOV 03-05, 2014; International audience; In this paper, we focus on the coloration approach and estimation of chromatic number. We propose an upper bound of a chromatic number based on the orientation algorithm described in [4]. This upper bound is improved by developing a novel coloration algorithm. Finally, we make a theoretical and empirical comparison of our bounds with Brooks's bound and Reed's conjecture [15] for class of triangle-free graphs.

In this paper, we consider the single machine scheduling problem with a fixed non-availability interval. The objective is to minimize the makespan. Our work aims at the comparison of Jackson's schedule to the optimal and the worst solutions in order to establish the differential approximation ratio for this problem. The analysis of Jackson's rule shows that this rule cannot yield a constant differential approximation in the general case.