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.

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.

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.

International audience; The well-known column generation scheme is often an efficient approach for solving the linear relaxation of large-size Covering Integer Programs (CIP). In this paper, this technique is hybridized with an extension of the best-known CIP approximation heuristic, taking advantage of distinct criteria of columns selection. This extension uses fractional optimization for solving pricing subproblems. Numerical results on a real-case transportation planning problem show that the hybrid scheme accelerates the convergence of column generation both in terms of number of iterations and computational time. The integer solutions generated at the end of the process can also be improved for a significant proportion of instances, highlighting the potential of diversification of the approximation heuristic.

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.

The Job Shop Scheduling Problem is one of the most intractable NP-Hard combinatorial optimization problems. To solve optimally this problem in a reasonable computational time, we have to improve the lower and the upper bounds. In this paper we introduce a new lower bound to the job shop scheduling problem with min-sum criteria and compare two different genetic algorithms. The gap is computed by comparing the best upper bound with the lower bound.

The Column Generation approach is generally a high-performing approach to solve the linear relaxation of Covering Integer Programs (CIP).In this communication, we propose a hybrid column generation approach for large-size CIP that runs a greedy heuristic at appropriate iterations of the column generation process to complete subsets of columns accordingly to a given coverage threshold. This heuristic is an extension of the best-known CIP approximation heuristic of Dobson to the case when explicit enumeration of the set of columns is infeasible. This extension uses fractional optimization, namely the Dinkelback's algorithm, for solving combinatorial pricing subproblems.Numerical results on a real-case transportation planning problem show that the hybrid scheme improves the three main performance criteria of Column Generation: computational time, convergence in terms of number of iterations, and quality of integer solutions found from the last Restricted Master Program. A research paper associated to this talk is to appear in Computers and OR

This paper deals with generalizations of Dobson approximation algorithm and proposes its cooperation with Column Generation for large-size Covering Interger Programs

International audience; L'optimisation des ressources agricoles est une préoccupation croissante dans le contexte du développement durable. En effet, une mauvaise utilisation de ces ressources peut avoir un impact négatif sur le plan écologique. C'est dans ce contexte que nous nous intéressons à un problème de planification de production agricole dont l'objectif est de construire, sur un horizon de temps donné, des rotations culturales couvrant des demandes saisonnières en diverses cultures et minimisant la surface totale des parcelles utilisées. Nous considérons particulièrement l'aspect stratégique de la planification sur un horizon long jusqu'à 60 saisons et nous proposons une approche de modélisation implicite engendrant un programme mathématique de grande taille. Un schéma de résolution hybride combinant l'approche de génération de colonnes et une heuristique est alors considéré. Les résultats numériques prouvent l'efficacité de ce schéma comparativement à une approche de résolution exacte du modèle explicite équivalent.

The NP-hard Covering Integer Programming minimization problem models manyreal-case applications. Covering Integer Programs can appear as basic models in someapplications like location problems, but also as master problemsresulting from a Dantzig-wolfe decomposition in other applications liketransportation problems, cutting stock problems, etc. In this work, we focus on the second category of large-size covering integer programs, for which the column generation method isgenerally an appropriate solving approach. However, as it provides only a lowerbound of the optimal solution, it is often combined with other solving approaches toobtain integer solutions. The main contribution of this work is a hybridization of an approximation heuristic and a classical approach based on column generation.Two real-case transportation and production applications are considered. The goal is not to design the best possible method for each problem but to show the added value of hybridization of given components. Experimental results on the two practical applications show that this combination improves the classical approach on three major criteria : average CPU time, number of iterations and quality of the integer value.

International audience; We propose in this paper a new Dantzig-Wolfe master model based on Lagrangian decomposition. We establish the relationship with classical Dantzig-Wolfe decomposition master problem and propose an alternative proof of the dominance of Lagrangian decomposition on Lagrangian relaxation dual bound. As illustration, we give the corresponding models and numerical results for two standard mathematical programs: the 0-1 bidimensional knapsack problem and the generalized assignment problem.

We deal in this paper with an agricultural production planning problem where crops must be scheduled on land plots so as to satisfy crop demands every period of time and to minimize the overall surface of land used for cultivation. This problem can be formulated as a covering integer program with a huge number of variables. A resolution scheme based on column generation is thus proposed, where the resulting pricing problem is efficiently solved by dynamic programming. The numerical experiments show that the method is all the more so efficient and robust as the planning horizon is long and plot sizes are small.

International audience; An efficient use of dynamic programming requires a substantial reduction of the number of labels. We propose in this paper an efficient way of reducing the number of labels saved and dominance computing time. Our approach is validated by experiments on shortest path problem with time windows instances.

International audience

International audience

We want to solve exactly large instances of the 0-1 quadratic knapsack problem with a branch-and-bound algorithm. Thus we need to obtain good lower and upper bounds in order to fix variables in the preprocessing phase at the root node of the search tree. We introduce reoptimization technics in this preprocessing phase using the lagrangian relaxation of Caprara, Pisinger and Toth and the lagrangian decomposition of Billionnet and Soutif. Reoptimization technics are used to reduce importantly (up to 60%) the number of iterations in the linear knapsack resolutions done in both lagrangian methods.

30 pages; Many practical problems are modelled by integer programs. The difficulty of their resolution lies in the characterization of the feasible domain. Face to this difficulty, the researchers directed themselves towards approximations of this domain by decomposing the problem. The decomposition generally results in the relaxation of the integrality conditions on a subset of constraints. Decomposition methods differ from the bound quality and from the resolution methods used like their complexity. We present in this report some of these methods, analyze their strong and weak points and finally, establish a synthesis showing the relation between some methods considered to be different.

Problèmes paradigmatiques , Optimisation Combinatoire, volume 4

The 0-1 quadratic knapsack problem consists in maximizing a quadratic function subject to a linear capacity constraint. To solve exactly this problem with a branch and bound algorithm, we need to obtain good lower an upper bounds in order to fix a lot of variables in the pre-treatment phase at the root node of the branch and bound tree if we want to solve large instances. We introduce reoptimization technics in this pre-treatment phase using the lagrangean relaxation of Caprara, Pisinger and Toth and the lagrangean decomposition of Billionnet and Soutif that give the best upper bounds known today. Reoptimization technics are used to reduce importantly (until 60%) the number of iterations in the linear knapsack resolutions done in both lagrangean methods.