No description available.

No description available.

No description available.

No description available.

This thesis focuses on the construction of effective and efficient hybrid methods based on the integrations of Constraint Programming (CP), Integer Programming (IP) and local search (LS) to tackle two combinatorial optimisation problems from different application areas: the nurse rostering problems and the portfolio selection problems. The principle of designing hybrid methods in this thesis can be described as: for the combinatorial problems to be solved, the properties of the problems are investigated firstly and the problems are decomposed accordingly in certain ways; then the suitable solution techniques are integrated to solve the problem based on the properties of substructures/subproblems by taking the advantage of each technique. For the over-constrained nurse rostering problems with a large set of complex constraints, the problems are first decomposed by constraint. That is, only certain selected set of constraints is considered to generate feasible solutions at the first stage. Then the rest of constraints are tackled by a second stage local search method. Therefore, the hybrid methods based on this constraint decomposition can be represented by a two-stage framework “feasible solution + improvement”. Two integration methods are proposed and investigated under this framework. In the first integration method, namely a hybrid CP with Variable Neighourhood Search (VNS) approach, the generation of feasible initial solutions relies on the CP while the improvement of initial solutions is gained by a simple VNS in the second stage. In the second integration method, namely a constraint-directed local search, the local search is enhanced by using the information of constraints. The experimental results demonstrate the effectiveness of these hybrid approaches. Based on another decomposition method, Dantzig-Wolfe decomposition, in the third integration method, a CP based column generation, integrates the feasibility reasoning of CP with the relaxation and optimality reasoning of Linear Programming. The experimental results demonstrate the effectiveness of the methods as well as the knowledge of the quality of the solution. For the portfolio selection problems, two integration methods, which integrate Branch-and-Bound algorithm with heuristic search, are proposed and investigated. In layered Branch-and-Bound algorithm, the problem is decomposed into the subsets of variables which are considered at certain layers in the search tree according to their different features. Node selection heuristics, and branching rules, etc. are tailored to the individual layers, which speed up the search to the optimal solution in a given time limit. In local search branching Branch-and-Bound algorithm, the idea of local search is applied as the branching rule of Branch-and-Bound. The local search branching is applied to generate a sequence of subproblems. The procedure for solving these subproblems is accelerated by means of the solution information reusing. This close integration between local search and Branch-and-Bound improves the efficiency of the Branch-and-Bound algorithm according to the experimental results. The hybrid approaches benefit from each component which is selected according to the properties of the decomposed problems. The effectiveness and efficiency of all the hybrid approaches to the two application problems developed in this thesis are demonstrated. The idea of designing appropriate components in hybrid approach concerning properties of subproblems is a promising methodology with extensive potential applications in other real-world combinatorial optimisation problems.

Dans le domaine de l'Optimisation Combinatoire, la résolution de manière optimale de problèmes de grande taille par le biais d'algorithmes Branch-and-Bound requiert un nombre très élevé de ressources de calcul. De nos jours, de telles ressources sont accessibles grâce aux grilles de calcul, composées de grappes de clusters réparties sur différents sites géographiques. Ces environnements parallèles posent de nombreux défis scientifiques, notamment en termes de passage à l'échelle, de la prise en compte de l'hétérogénéité des ressources ainsi qu'en termes de tolérance aux pannes. La plupart des approaches existantes pour l'algorithme Branch-and-Bound parallèle sont basées sur une architecture de type Maître-Esclave, où un processus maître répartit les tâches à accomplir auprès de processus esclaves en charge de les traiter. L'utilisation d'une telle entité centrale constitue un obstacle majeur en ce qui concerne le passage à l'échelle. Dans cette thèse, nous proposons de relever ces défis ainsi que de surmonter cet obstacle grâce à une approche innovante et complètement distribuée, basée sur une architecture Pair-à-Pair (P2P). Celle-ci repose sur un seul type de processus (le pair), qui a pour mission d'explorer son propre ensemble de tâches, de le partager avec d'autres pairs et de diffuser l'information globale. Nous définissons des mécanismes adaptés en lien avec l'algorithme Branch-and-Bound, qui traitent de la répartition de la charge, de la diffusion de la meilleure solution trouvée et de la détection de la terminaison des calculs. En plus de multiples expérimentations sur le problème d'ordonnancement du Flow-Shop sur la grille de calcul Grid'5000, nous proposons une preuve formelle de la correction de notre approche. Par ailleurs, nous traitons une problématique souvent ignorés dans les travaux relatifs au calcul P2P, qui est l'importance de la topologie du réseau P2P. Généralement, une topologie très simple est utilisée. Les résultats obtenus montrent que notre approche permet le déploiement de réseaux de calculs à de très grandes échelles, constitués potentiellement de centaines de milliers de coeurs de calcul. Notre dernière contribution consiste en une approche Pair-à-Pair tolérante aux pannes afin de prendre en compte la nature généralement très volatile des ressources de calcul. Les résultats obtenus prouvent la robustesse de l'approche dans des environnements à la fois réalistes et sujets à de nombreux dysfonctionnements. / In the field of Combinatorial Optimization, the resolution to optimality of large instances of optimization problems through the use of Branch-and-Bound algorithms require a huge amount of computational resources. Nowadays, such resources are available from computing grids, which are sets of computing nodes geographically distributed over multiple sites. These parallel environments introduces multiples challenges related to the scalability, the heterogeneity of resources and the fault tolerance. Most of the existing approaches for the Branch-and-Bound algorithm are based on the Master-Slave paradigm where a central entity shares work units among slave entities in charge of processing them. Such an architecture represents an obstacle to scalability. In this thesis, we propose to face the challenges of grid environments and overcome this limitation by proposing an innovative and fully distributed approach based on the Peer-to-Peer paradigm. This architecture is based on a unique type of entity, a peer which is in charge of exploring its own local work pool and broadcasts global information to the network. We provide mechanisms to deal with the main tasks of the Branch-and-Bound algorithm : the load balancing, the diffusion of the best solution and the detection of the termination. Along with extensive experiments conducted on the Flow-Shop Scheduling Problem using the Grid'5000 Experimental Grid, we propose a formal proof of the correctness of our approach.In addition to this, we tackle a central issue when designing a Peer-to-Peer application : the impact of the P2P network topology on the performance of our approach. This aspect is often ignored in most of existing works, where only a predefined organization is chosen for the peers. The obtained results showed that the approach allows to deploy computing networks at extreme scales, involving hundreds of thousands of computing cores. Our final contribution consists in a Fault-Tolerant approach to deal with the dynamicity of the network (the volatility of computational resources). Results indicate that it faces efficiently various real-case and failure-intensive situations.

Constraint programming is a generalised framework designed to solve combinatorial problems. This framework is made up of a set of predefined independent components and generalised algorithms. This is a very versatile structure which allows for a variety of rich combinatorial problems to be represented and solved relatively easily. Stable matching problems consist of a set of participants wishing to be matched into pairs or groups in a stable manner. A matching is said to be stable if there is no pair or group of participants that would rather make a private arrangement to improve their situation and thus undermine the matching. There are many important "real life" applications of stable matching problems across the world. Some of which includes the Hospitals/Residents problem in which a set of graduating medical students, also known as residents, need to be assigned to hospital posts. Some authorities assign children to schools as a stable matching problem. Many other such problems are also tackled as stable matching problems. A number of classical stable matching problems have efficient specialised algorithmic solutions. Constraint programming solutions to stable matching problems have been investigated in the past. These solutions have been able to match the theoretically optimal time complexities of the algorithmic solutions. However, empirical evidence has shown that in reality these constraint solutions run significantly slower than the specialised algorithmic solutions. Furthermore, their memory requirements prohibit them from solving problems which the specialised algorithmic solutions can solve in a fraction of a second. My contribution investigates the possibility of modelling stable matching problems as specialised constraints. The motivation behind this approach was to find solutions to these problems which maintain the versatility of the constraint solutions, whilst significantly reducing the performance gap between constraint and specialised algorithmic solutions. To this end specialised constraint solutions have been developed for the stable marriage problem and the Hospitals/Residents problem. Empirical evidence has been presented which shows that these solutions can solve significantly larger problems than previously published constraint solutions. For these larger problem instances it was seen that the specialised constraint solutions came within a factor of four of the time required by algorithmic solutions. It has also been shown that, through further specialisation, these constraint solutions can be made to run significantly faster. However, these improvements came at the cost of versatility. As a demonstration of the versatility of these solutions it is shown that, by adding simple side constraints, richer problems can be easily modelled. These richer problems add additional criteria and/or an optimisation requirement to the original stable matching problems. Many of these problems have been proven to be NP-Hard and some have no known algorithmic solutions. Included with these models are results from empirical studies which show that these are indeed feasible solutions to the richer problems. Results from the studies also provide some insight into the structure of these problems, some of which have had little or no previous study.

Cette thèse s'intéresse à l'étude de deux problèmes d'optimisation pour la production d’énergie électrique. Le premier est un problème académique très étudié : le Unit Commitment Problem (UCP). Le second est un problème de planification des débits d'eau dans un réseau hydro-électrique issu d'une application industrielle. Ces deux problèmes sont des problèmes NP-complets très difficiles car ils sont non linéaires, fortement contraints et que la taille des données est importante. Dans la première partie de cette thèse, nous proposons DYNAMOP. Il s'agit d'un algorithme génétique qui guide la recherche effectuée par la programmation dynamique en manipulant des solutions représentées sous forme de chemins du graphe d’états. Cette représentation est avantageuse car, d'une part, elle facilite la mise en place d'hybridations avec la programmation dynamique et, d'autre part, elle permet de proposer des opérateurs évolutionnaires efficaces tenant compte les dépendances entre les variables. DYNAMOP est appliqué aux deux problèmes de production d'énergie. La qualité des résultats permet d'affirmer que cette méthode est bien adaptée à la résolution de ce type de problèmes. Dans la seconde partie, nous présentons MO-DYNAMOP une extension de DYNAMOP à l'optimisation multi-objectif. MO-DYNAMOP est évalué sur une version bi-objectif de l'UCP nécessitant l'utilisation d'une représentation indirecte. Une solution partielle sera ainsi décodée en un ensemble de solutions complètes Pareto équivalentes ce qui rend difficile l'évaluation sa qualité. Nous proposons donc plusieurs adaptations des stratégies usuelles d'assignation de fitness et comparons les méthodes obtenues à la littérature. / In this thesis, two energy production problems are studied. The first is a well known academic problem: the Unit Commitment Problem (UCP). The second one is a hydro scheduling problem with a real world application. These two problems are very hard NP-complete problems because they are non-linear, highly constrained, and the data size is large. In the first part of this thesis we propose DYNAMOP. It is a genetic algorithm that uses a representation based on a path in the graph of states of dynamic programming. The advantages of this representation are that it makes it easy to propose efficient evolutionary operators taking the dependencies into account, and that it facilitates the hybridization with dynamic programming. DYNAMOP is tested  on the two energy production problems. The results confirm the competitiveness of the proposed method to solve energy problems. In the second part, we present MO-DYNAMOP, which is an extension of DYNAMOP to multi-objective combinatorial optimization problems. MO-DYNAMOP is applied to a bi-objective version of the UCP, but this implies an indirect representation, which is problematic. Indeed, in this case, decoding a genotypic solution involves the resolution of a multi-objective problem. Then many Pareto equivalent phenotypic solutions can be produced from one genotypic solution. We propose and compare 3 decoding strategies to solve this difficulty. A comparison study beetween MO-DYNAMOP and methods previously proposed for the bi-objective UCP is performed. Experiments indicate that MO-DYNAMOP performs considerably better.

Les algorithmes Branch-and-Bound (B&B) font partie des méthodes exactes pour la résolution de problèmes d’optimisation combinatoire. Les calculs induits par un algorithme B&B sont extrêmement couteux surtout lorsque des instances de grande tailles sont considérées. Un algorithme B&B peut être vu comme une exploration implicite d’un espace représenté sous la forme d’un arbre qui a pour spécificité d’être hautement irrégulier. Pour accélérer l’exploration de cet espace, les calculs parallèles et distribués à très large échelle sont souvent utilisés. Cependant, atteindre des performances parallèles optimales est un objectif difficile et jalonné de plusieurs défis, qui découlent essentiellement de deux facteurs: (i) l’irrégularité des calculs inhérents à l’arbre B&B et (ii) l’hétérogénéité inhérente aux environnements de calcul large échelle. Dans cette thèse, nous nous intéressons spécifiquement à la résolution de ces deux défis. Nous nous concentrons sur la conception d’algorithmes distribués pour l’équilibrage de charge afin de garantir qu’aucune entité de calcul n’est surchargée ou sous-utilisée. Nous montrons comment résoudre l’irrégularité des calculs sur différents type d’environnements, et nous comparons les approches proposées par rapport aux approches de références existantes. En particulier, nous proposons un ensemble de protocoles spécifiques à des contextes homogènes, hétérogène en terme de puissance de calcul (muti-coeurs, CPU et GPU), et hétérogènes en terme de qualité des lien réseaux. Nous montrons à chaque fois la supériorité de nos protocoles à travers des études expérimentales extensives et rigoureuses. / Branch and Bound (B&B) algorithms are exact methods used to solve combinatorial optimization problems (COPs). The computation process of B&B is extremely time-intensive when solving large problem instances since the algorithm must explore a very large space which can be viewed as a highly irregular tree. Consequently, B&B algorithms are usually parallelized on large scale distributed computing environments in order to speedup their execution time. Large scale distributed computing environments, such as Grids and Clouds, can provide a huge amount of computing resources so that very large B&B instances can be tackled. However achieving high performance is very challenging mainly because of (i) the irregular characteristics of B&B workload and (ii) the heterogeneity exposed by large scale computing environments. This thesis addresses and deals with the above issues in order to design high performance parallel B&B on large scale heterogeneous computing environments. We focus on dynamic load balancing techniques which are to guarantee that no computing resources are underloaded or overloaded during execution time. We also show how to tackle the irregularity of B&B while running on different computing environments, and consider to compare our proposed solutions with the state-of-the-art algorithms. In particular, we propose several dynamic load balancing algorithms for homogeneous, node-heterogeneous and link-heterogeneous computing platforms. In each context, our approach is shown to perform much better than the state-of-the-art approaches.

This thesis develops efficient optimization methods for Model Predictive Control (MPC) to enable its application to constrained systems with fast and uncertain dynamics. The key contribution is an active set method which exploits the parametric nature of the sequential optimization problem and is obtained from a dynamic programming formulation of the MPC problem. This method is first applied to the nominal linear MPC problem and is successively extended to linear systems with additive uncertainty and input constraints or state/input constraints. The thesis discusses both offline (projection-based) and online (active set) methods for the solution of controllability problems for linear systems with additive uncertainty. The active set method uses first-order necessary conditions for optimality to construct parametric programming regions for a particular given active set locally along a line of search in the space of feasible initial conditions. Along this line of search the homotopy of optimal solutions is exploited: a known solution at some given plant state is continuously deformed into the solution at the actual measured current plant state by performing the required active set changes whenever a boundary of a parametric programming region is crossed during the line search operation. The sequence of solutions for the finite horizon optimal control problem is therefore obtained locally for the given plant state. This method overcomes the main limitation of parametric programming methods that have been applied in the MPC context which usually require the offline precomputation of all possible regions. In contrast to this the proposed approach is an online method with very low computational demands which efficiently exploits the parametric nature of the solution and returns exact local DP solutions. The final chapter of this thesis discusses an application of robust tube-based MPC to the nonlinear MPC problem based on successive linearization.