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.

Given a bipartite graph G = ( U ∪ V , E ) , | U | ⩽ | V | , the surplus of G is defined by the maximum number k such that a matching covering all vertices of U still exists upon removal of any k vertices from V . Given a partition U = { U 1 , … , U m } of U , the Multiple Bipartite Complete Matching Vertex Blocker Problem (MBCMVBP) consists in finding a partition V = { V 1 , … , V m } of V such that the smallest surplus among those of the induced subgraphs G [ U i ∪ V i ] is maximized. The removed vertices are related to the blocker notion. We show the strong NP-hardness of the MBCMVBP by using a reduction from the stable set problem. We also propose two integer linear programs for solving this problem. After comparing these two models, we introduce some valid inequalities for the model that outperforms the other one, and we analyze its facial structure. We then derive a Branch-and-Cut algorithm based on these results and conclude by an analysis of the experimental results.

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.

In this paper we address unbalanced spatial distribution of hub-level flows in an optimal hub-and-spoke network structure of median-type models. Our study is based on a rather general variant of the multiple allocation hub location problems with fixed setup costs for hub nodes and hub edges in both capacitated and uncapacitated variants wherein the number of hub nodes traversed along origin-destination pairs is not constrained to one or two as in the classical models.. From the perspective of an infrastructure owner, we want to make sure that there exists a choice of design for the hub-level sub-network (hubs and hub edges) that considers both objectives of minimizing cost of transportation and balancing spatial distribution of flow across the hub-level network. We propose a bi-objective (transportation cost and hub-level flow variance) mixed integer non-linear programming formulation and handle the bi-objective model via a compromise programming framework. We exploit the structure of the problem and propose a second-order conic reformulation of the model along with a very efficient matheuristics algorithm for larger size 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.

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.

National audience

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.

World Congress on Computer Applications and Information Systems (WCCAIS), Hammamet, TUNISIA, JAN 17-19, 2014; International audience; In this paper, we consider the single machine scheduling problem with an unexpected non-availability interval. The objective is to minimize the maximum lateness. We have to decide the scheduling of jobs without any knowledge of the machine non-availability interval. Hence, we consider two possible models related to this constraint: breakdown model and emergent-job model. In both cases, the starting time of the non-availability interval and the length of the interval are unknown. We show that no root 37+1/6=competitive online algorithm exists for the breakdown model and no 9/2+root 31-competitive online algorithm exists for the emergent model and we show the Jackson's rule can give a 2-approximation for the two models and this ratio is tight.