L’optimisation globale fiable est dédiée à la recherche d’un minimum global en présence d’erreurs d’arrondis. Les seules approches fournissant une preuve numérique d’optimalité sont des méthodes d’intervalles qui partitionnent l’espace de recherche et éliminent les sous-espaces qui ne peuvent contenir de solution optimale. Ces méthodes exhaustives, appelées branch and bound par intervalles, sont étudiées depuis les années 60 et ont récemment intégré des techniques de réfutation et de contraction, issues des communautés d’analyse par intervalles et de programmation par contraintes. Il est d’une importance cruciale de calculer i) un encadrement précis de la fonction objectif et des contraintes sur un sous-domaine ; ii) une bonne approximation (un majorant) du minimum global. Les solveurs de pointe sont généralement des méthodes intégratives : ils invoquent sur chaque sous-domaine des algorithmes d’optimisation locale afin d’obtenir une bonne approximation du minimum global. Dans ce document, nous nous intéressons à un cadre coopératif combinant des méthodes d’intervalles et des algorithmes évolutionnaires. Ces derniers sont des algorithmes stochastiques faisant évoluer une population de solutions candidates (individus) dans l’espace de recherche de manière itérative, dans l’espoir de converger vers des solutions satisfaisantes. Les algorithmes évolutionnaires, dotés de mécanismes permettant de s’échapper des minima locaux, sont particulièrement adaptés à la résolution de problèmes difficiles pour lesquels les méthodes traditionnelles peinent à converger. Au sein de notre solveur coopératif Charibde, l’algorithme évolutionnaire et l’algorithme sur intervalles exécutés en parallèle échangent bornes, solutions et espace de recherche par passage de messages. Une stratégie couplant une heuristique d’exploration géométrique et un opérateur de réduction de domaine empêche la convergence prématurée de la population vers des minima locaux et évite à l’algorithme évolutionnaire d’explorer des sous-espaces sous-optimaux ou non réalisables. Une comparaison de Charibde avec des solveurs de pointe (GlobSol, IBBA, Ibex) sur une base de problèmes difficiles montre un gain de temps d’un ordre de grandeur. De nouveaux résultats optimaux sont fournis pour cinq problèmes multimodaux pour lesquels peu de solutions, même approchées, sont connues dans la littérature. Nous proposons une application aéronautique dans laquelle la résolution de conflits est modélisée par un problème d’optimisation sous contraintes universellement quantifiées, et résolue par des techniques d’intervalles spécifiques. Enfin, nous certifions l’optimalité de la meilleure solution connue pour le cluster de Lennard-Jones à cinq atomes, un problème ouvert en dynamique moléculaire. / Reliable global optimization is dedicated to finding a global minimum in the presence of rounding errors. The only approaches for achieving a numerical proof of optimality in global optimization are interval-based methods that interleave branching of the search-space and pruning of the subdomains that cannot contain an optimal solution. The exhaustive interval branch and bound methods have been widely studied since the 1960s and have benefitted from the development of refutation methods and filtering algorithms, stemming from the interval analysis and interval constraint programming communities. It is of the utmost importance: i) to compute sharp enclosures of the objective function and the constraints on a given subdomain; ii) to find a good approximation (an upper bound) of the global minimum. State-of-the-art solvers are generally integrative methods, that is they embed local optimization algorithms to compute a good upper bound of the global minimum over each subspace. In this document, we propose a cooperative framework in which interval methods cooperate with evolutionary algorithms. The latter are stochastic algorithms in which a population of individuals (candidate solutions) iteratively evolves in the search-space to reach satisfactory solutions. Evolutionary algorithms, endowed with operators that help individuals escape from local minima, are particularly suited for difficult problems on which traditional methods struggle to converge. Within our cooperative solver Charibde, the evolutionary algorithm and the intervalbased algorithm run in parallel and exchange bounds, solutions and search-space via message passing. A strategy combining a geometric exploration heuristic and a domain reduction operator prevents premature convergence toward local minima and prevents the evolutionary algorithm from exploring suboptimal or unfeasible subspaces. A comparison of Charibde with state-of-the-art solvers based on interval analysis (GlobSol, IBBA, Ibex) on a benchmark of difficult problems shows that Charibde converges faster by an order of magnitude. New optimality results are provided for five multimodal problems, for which few solutions were available in the literature. We present an aeronautical application in which conflict solving between aircraft is modeled by an universally quantified constrained optimization problem, and solved by specific interval contractors. Finally, we certify the optimality of the putative solution to the Lennard-Jones cluster problem for five atoms, an open problem in molecular dynamics.

No description available.

Dans le cadre de cette thèse, nous nous sommes intéressés à la mise en œuvre d'algorithmes auto-adaptatifs d'Intelligence Collective pour la résolution de problèmes d'optimisation modélisés dans un langage de Programmation par contraintes (PPC). Nous avons porté une attention particulière à la famille d'algorithmes de type « Ant Colony Optimization » (ACO). Nous avons développé trois contributions, à savoir : (1) Intégration des algorithmes de type ACO dans un langage de programmation par contraintes pour la résolution de problèmes de satisfaction de contraintes; (2) Proposition d'un algorithme hybride et générique où ACO est couplé à une approche complète pour résoudre des problèmes d'optimisation combinatoires (3) Proposition d'une stratégie capable d'adapter dynamiquement les paramètres de ACO. / In this thesis, we focused on the implementation of self-adaptive algorithms for solving optimization problems modeled in a Constraint Programming (CP) language. We focus on to the Ant Colony Optimization (ACO) algorithms. We have developed three contributions, namely: (1) Integration of ACO algorithms in a constraint programming language for solving constraint satisfaction problems, (2) Proposal of a generic hybrid algorithm which combines ACO and CP approach to solving combinatorial optimization problems (3) Proposal of a strategy to dynamically adjust the parameters of ACO.

Un vérificateur de modèle peut produire une trace de contreexemple, pour un programme erroné, qui est souvent difficile à exploiter pour localiser les erreurs dans le code source. Dans ma thèse, nous avons proposé un algorithme de localisation d'erreurs à partir de contreexemples, nommé LocFaults, combinant les approches de Bounded Model Checking (BMC) avec un problème de satisfaction de contraintes (CSP). Cet algorithme analyse les chemins du CFG (Control Flow Graph) du programme erroné pour calculer les sous-ensembles d'instructions suspectes permettant de corriger le programme. En effet, nous générons un système de contraintes pour les chemins du graphe de flot de contrôle pour lesquels au plus k instructions conditionnelles peuvent être erronées. Ensuite, nous calculons les MCSs (Minimal Correction Sets) de taille limitée sur chacun de ces chemins. La suppression de l'un de ces ensembles de contraintes donne un sous-ensemble satisfiable maximal, en d'autres termes, un sous-ensemble maximal de contraintes satisfaisant la postcondition. Pour calculer les MCSs, nous étendons l'algorithme générique proposé par Liffiton et Sakallah dans le but de traiter des programmes avec des instructions numériques plus efficacement. Cette approche a été évaluée expérimentalement sur des programmes académiques et réalistes. / A model checker can produce a trace of counter-example for erroneous program, which is often difficult to exploit to locate errors in source code. In my thesis, we proposed an error localization algorithm from counter-examples, named LocFaults, combining approaches of Bounded Model-Checking (BMC) with constraint satisfaction problem (CSP). This algorithm analyzes the paths of CFG (Control Flow Graph) of the erroneous program to calculate the subsets of suspicious instructions to correct the program. Indeed, we generate a system of constraints for paths of control flow graph for which at most k conditional statements can be wrong. Then we calculate the MCSs (Minimal Correction Sets) of limited size on each of these paths. Removal of one of these sets of constraints gives a maximal satisfiable subset, in other words, a maximal subset of constraints satisfying the postcondition. To calculate the MCSs, we extend the generic algorithm proposed by Liffiton and Sakallah in order to deal with programs with numerical instructions more efficiently. This approach has been experimentally evaluated on a set of academic and realistic programs.

Cette thèse, réalisée en collaboration avec Sagem Défense Sécurité, porte sur l'élaboration d'une stratégie de recherche efficace pour la résolution de problèmes de planification d'itinéraires de véhicules. Nous considérons ici en particulier les problèmes de planification avec contraintes de points de passage et de "capacité" (énergie, bande passante radio) appliquées au véhicule. Ce document propose une approche originale, hybridant un algorithme de colonies de fourmis avec un solveur de Programmation par Contraintes existant. Le premier est utilisé pour résoudre rapidement une version relaxée du problème. La solution partielle obtenue est alors employée pour guider la recherche du second, par le biais d'une méthode de sonde, vers les zones les plus prometteuses de l'espace d'état. Cette approche permet ainsi de combiner la rapidité des métaheuristiques et la complétude de la programmation par contraintes. Nous montrons expérimentalement que cette approche satisfait les exigences pour une utilisation du planificateur dans un cadre embarqué. / This thesis, led in collaboration with Sagem Defence & Security, focuses on defining an efficient search strategy to solve vehicle path planning problems. This work addresses more precisely planning problems in which waypoints and "capacity" constraints (energy, radio bandwidth) are applied to vehicles.This document proposes an original approach, mixing an Ant Colony algorithm with an existing Constraint Programming solver. The former is used to fastly solve a relaxed version of the problem. The partial solution returned is then employed to guide the search of the latter, through a Probe Backtrack mechanism, towards the most promising areas of the state space. This approach allows to combine the metaheuristics solving fastness and the Constraint Programming completeness. We experimentally show that this approach meets the requirements for an on-line use of the planner.

Développer un programme capable de jouer à n’importe quel jeu de stratégie, souvent désigné par le General Game Playing (GGP) constitue un des Graal de l’intelligence artificielle. Les compétitions GGP, où chaque jeu est représenté par un ensemble de règles logiques au travers du Game Description Language (GDL), ont conduit la recherche à confronter de nombreuses approches incluant les méthodes de type Monte Carlo, la construction automatique de fonctions d’évaluation, ou la programmation logique et ASP. De par cette thèse, nous proposons une nouvelle approche dirigée par les contraintes stochastiques.Dans un premier temps, nous nous concentrons sur l’élaboration d’une traduction de GDL en réseauxde contraintes stochastiques (SCSP) dans le but de fournir une représentation dense des jeux de stratégies et permettre la modélisation de stratégies.Par la suite, nous exploitons un fragment de SCSP au travers d’un algorithme dénommé MAC-UCBcombinant l’algorithme MAC (Maintaining Arc Consistency) utilisé pour résoudre chaque niveau duSCSP tour après tour, et à l’aide de UCB (Upper Confidence Bound) afin d’estimer l’utilité de chaquestratégie obtenue par le dernier niveau de chaque séquence. L’efficacité de cette nouvelle technique sur les autres approches GGP est confirmée par WoodStock, implémentant MAC-UCB, le leader actuel du tournoi continu de GGP.Finalement, dans une dernière partie, nous proposons une approche alternative à la détection de symétries dans les jeux stochastiques, inspirée de la programmation par contraintes. Nous montrons expérimentalement que cette approche couplée à MAC-UCB, surpasse les meilleures approches du domaine et a permis à WoodStock de devenir champion GGP 2016. / The ability for a computer program to effectively play any strategic game, often referred to General Game Playing (GGP), is a key challenge in AI. The GGP competitions, where any game is represented according to a set of logical rules in the Game Description Language (GDL), have led researches to compare various approaches, including Monte Carlo methods, automatic constructions of evaluation functions, logic programming, and answer set programming through some general game players. In this thesis, we offer a new approach driven by stochastic constraints. We first focus on a translation process from GDL to stochastic constraint networks (SCSP) in order to provide compact representations of strategic games and to model strategies. In a second part, we exploit a fragment of SCSP through an algorithm called MAC-UCB by coupling the MAC (Maintaining Arc Consistency) algorithm, used to solve each stage of the SCSP in turn, together with the UCB (Upper Confidence Bound) policy for approximating the values of those strategies obtained by the last stage in the sequence. The efficiency of this technical on the others GGP approaches is confirmed by WoodStock, implementing MAC-UCB, the actual leader on the GGP Continuous Tournament. Finally, in the last part, we propose an alternative approach to symmetry detection in stochastic games, inspired from constraint programming techniques. We demonstrate experimentally that MAC-UCB, coupled with our constranit-based symmetry detection approach, significantly outperforms the best approaches and made WoodStock the GGP champion 2016.

Cette thèse a pour objectif la génération de séquences de franchissement dans les Réseaux de Petri Temporisés (RdPT) en utilisant une approche incrémentale. Le verrou principal auquel est confronté ce travail est l’explosion combinatoire qui résulte de la construction classique du graphe d’accessibilité du RdPT. Nous proposons d’utiliser la notion de séquence de steps temporisés, afin d’exprimer progressivement l’ensemble des séquences de franchissements permettant de passer d’un état courant à un état cible. La notion de step temporisé correspond à une abstraction logique du comportement du système considéré. Le caractère incrémental de l’approche a pour objectif de gagner en efficacité. En effet, il consiste à exprimer tout nouvel état de la résolution par rapport à une profondeur K+1, en fonction d’un état atteint à la profondeur K. Ainsi, nous proposons plusieurs algorithmes de recherche incrémentale permettant d'améliorer l'efficacité de la résolution des problèmes d'accessibilité. Nous utilisons ensuite la programmation par contraintes pour modéliser le problème de recherche d’accessibilité dans un RdPT et mettre en œuvre notre approche incrémentale. Notre approche permet également d’ajouter des contraintes spécifiques à un contexte de résolution. Nous avons notamment utilisé cette possibilité pour proposer des techniques d'identification des jetons dans un RdPT borné, dans le cadre de la reconfiguration des systèmes manufacturiers. Nous concluons par l’évaluation de différentes applications constituant des « benchmarks » permettant d’illustrer l'efficacité des approches proposées / This PhD thesis is dedicated to the generation of firing sequences in Timed Petri Net (TPN) using an incremental approach. To reduce the influence of the well-known combinatorial explosion issue, a unique sequence of timed steps is introduced to represent implicitly the underlying reachability graph of the TPN, without needing its whole construction. This sequence of timed steps is developed based on the logical abstraction technique. The advantage of the incremental approach is that it can express any state just from the last step information, instead of representing all states before.Several incremental search algorithms are introduced to improve the efficiency of our methodology. Constraint programming techniques are used to model and solve our incremental model, in which search strategies are developed that can search for solutions more efficiently. Our methodology can be used to add specific constraints to model realistic systems. Token identification techniques are developed to handle token confusion issues that appear when addressing the reconfiguration of manufacturing systems. Experimental benchmarks illustrate the effectiveness of approaches proposed in this thesis

La gestion de l’énergie est une préoccupation majeure dans les réseaux de capteurs sans fil. Ces capteurs sont généralement alimentés par une batterie embarquant une quantité d’énergie finie. Par conséquent, le temps pendant lequel les capteurs peuvent surveiller une zone et communiquer par signaux radio peut être limitée lorsqu’il n’est pas possible de remplacer leur batterie. En outre, les réseaux de capteurs sont parfois déployés dans les zones difficiles d’accès ou dans des environnements hostiles dans lesquels le placement des capteurs peut être considéré comme aléatoire (c’est le cas par exemple lorsque les capteurs sont largués d’un avion ou d’un hélicoptère). Ainsi, l’emplacement des capteurs n’est pas connu a priori et les approches pour utiliser efficacement l’énergie sont nécessaires. Cette thèse explore l’utilisation de la génération colonnes pour optimiser l’utilisation de l’énergie dans les réseaux de capteurs sans fil. La génération de colonnes peut être vue comme un cadre général pour résoudre différents problèmes dans la conception et l’exploitation de ces réseaux. Plusieurs versions du problème et divers modèles sont proposés pour représenter leur fonctionnement,en utilisant notamment la génération de colonnes. Ces approches exploitent le caractère naturel de la génération de colonnes pour modéliser les différents aspects des réseaux de capteurs sans fil.Dans cette thèse, des contributions algorithmiques sont apportées afin de tirer le meilleur parti de la génération de colonnes au plan de l’efficacité computationnelle. Des stratégies hybrides combinant génération de colonnes et (méta)-heuristiques et donnant lieu à des méthodes exactes et approchées sont proposées et évaluées. Des tests numériques montrent l’efficacité des approches proposées et des bornes supérieures qui peuvent être employées pour évaluer l’efficacité des méthodes centralisées et distribuées. Enfin, des perspectives sont dégagées concernant les performances et la portabilité de la génération de colonnes pour aborder des problèmes plus réalistes et tenir compte des caractéristiques des réseaux de capteurs sans fil du futur. / Energy is a major concern in wireless sensor networks (WSN). These devices are typically battery operated and provided with a limited amount of energy. As a consequence, the time during which sensors can monitor the interesting phenomena and communicate through wireless signals might be limited because of (sometimes) irreplaceable batteries. Additionally, it is very common for WSN to be usedin remote or hostile environments which possibly makes necessary a random placement strategy (by using an airplane, a drone or a helicopter). Hence, the sensors location is not known a priori and approaches to efficiently use the energy are needed to answer to network topologies only known after sensors deployment. This thesis explores the use of column generation to efficiently use the energy in WSN. It is shown that column generation can be used as a general framework to tackle different problems in WSN design. Several versions of the problem and models for the operation of the WNS are adapted to be solved through column generation. These approaches take advantage of the natural way that column generation offers to consider different features of the WSN operation. Additionally, some computational improvements are proposed to keep the column generation method operating as an efficient exact approach. Hybrid strategies combining column generation with (meta)heuristic and exact approaches are considered and evaluated. The computational experiments demonstrate the efficiency of the proposed approaches and provide practitioners on WSN research with strategies to compute upper bounds to evaluate heuristic centralized and decentralized approaches. Finally, some future directions of research are provided based on the performance and adaptability of column generation to consider more sophisticated models and characteristics newly introduced in sensor devices.

De nombreuses applications informatiques nécessitent de résoudre des problèmes de décision qui sont difficiles d’un point de vue mathématique. La programmation par contraintes permet de modéliser et résoudre certains de ces problèmes, parfois définis sur des graphes. Au delà des difficultés intrinsèques aux problèmes étudiés, la taille des instances à traiter contribue à la difficulté de la résolution. Cette thèse traite de l’utilisation des graphes en programmation par contraintes, dans le but d’en améliorer la capacité de passage à l’échelle. Une première partie porte sur l’utilisation de contraintes pour résoudre des problèmes de graphes impliquant la recherche d’arbres, de chemins et de cycles Hamiltoniens. Ce sont des problèmes importants que l’on retrouve dans de nombreuses applications industrielles. Nous étudions à la fois le filtrage et les stratégies d’exploration de l’espace de recherche. Nous chercherons ensuite à nous extraire progressivement des problèmes classiquement définis sur les graphes pour exploiter ce concept sur des problèmes définis sur les entiers, voire les réels. Une seconde partie porte ainsi sur l’utilisation des graphes pour le filtrage de contraintes globales très répandues. Nous proposerons entre autres d’utiliser des graphes comme support pour décomposer dynamiquement des algorithmes de filtrage, de manière générique. Le fil conducteur de ces travaux sera d’une part l’utilisation du concept de graphe à la base de chaque raisonnement et d’autre part, la volonté pratique d’augmenter la taille des problèmes pouvant être traités en programmation par contraintes. / Many IT applications require to solve decision problems which are hard from a mathematical point of view. Constraint-programming enables to model and solve some of these problems. Among them, some are defined over graphs. Beyond the difficulty stemming from each of these problems, the size of the instance to solve increases the difficulty of the task. This PhD thesis is about the use of graphs within constraint programming, in order to improve its scalability. First, we study the use of constraint-programming to solve some graph problems involving the computation of trees and Hamiltonian paths and cycles. These problems are important and can be found in many industrial applications. Both filtering and search are investigated. Next, we move on problems which are no longer defined in terms of graph properties. We then study the use of graphs to propagate global constraints. In particular, we suggest a generic schema, relying ona graph structure, to dynamically decompose filtering algorithms. The central theme in this work is the use of graph concepts at the origin of every reasoning and the practical will to increase the size of problems that can be addressed in constraint-programming.

Ce manuscrit aborde des problèmes d’ordonnancement et de transport avec une modélisation explicite du transport. De tels problèmes se modélisent communément sous forme de graphes qui sont évalués afin d’obtenir les dates de début des opérations.Les évaluations classiques des graphes sont effectuées au moyen d’algorithmes de plus long chemin permettant d’obtenir une solution semi-active, où toutes les dates des opérations sont au plus tôt. Néanmoins, ces évaluations permettent généralement de ne prendre en compte que des critères de temps ou de distance à minimiser. Les travaux présentés dans ce manuscrit proposent de tenir compte de critères de qualité de service dans la fonction objectif. Cette prise en considération nécessite de nouvelles fonctions d’évaluation du graphe afin d’obtenir des solutions non nécessairement semi-actives permettant de maximiser la qualité de service. En effet, une solution semi-active propose rarement une qualité de service optimale. Les critères de qualité de service adoptés portent sur les ordonnancements et sur le transport.Trois problèmes intégrés sont successivement traités. Le premier problème est un problème de Job-shop avec transport et qualité de service, appelé Job-shop Scheduling Problem with Routing (JSPR). Des pièces, définies par une succession d’opérations, sont à fabriquer sur différentes machines, et entre deux opérations, la pièce doit être transportée de machine en machine. Le critère de qualité de service dans ce problème est dépendant des délais entre, d’une part les différentes opérations sur les machines, et d’autre part entre les différentes opérations de transport. Les gammes opératoires et les opérations de transport sont dépendantes les unes des autres.Le second problème est un problème de Workforce Scheduling and Routing Problem (WSRP), assimilable à un problème de planification de visites à domicile par un ensemble d’employés, et où le transport est pris en compte. Pour ce problème, le critère de qualité de service dépend des dates de début des visites. Les tournées sont indépendantes les unes des autres.Le troisième problème est le Generalised Workforce Scheduling and Routing Problem (GWSRP), qui prend en compte des contraintes de coordination entre les employés. Les tournées de ces derniers sont dépendantes les unes des autres. Elles nécessitent d’être toutes considérées simultanément pour évaluer les dates des visites respectant les contraintes de coordination et maximisant la qualité de service.Pour chaque problème, une nouvelle fonction d’évaluation est proposée. Pour le JSPR, cette fonction est basée sur l’algorithme de (Cordeau and Laporte, 2003) qui est initialement prévu pour le Dial-A-Ride Problem, ainsi que sur l’insertion de time-lags dans le graphe disjonctif du JSPR. Cette évaluation est incluse dans une métaheuristique. Pour le WSRP, la fonction d’évaluation est basée sur un algorithme de calcul du plus court chemin avec un algorithme de type programmation dynamique à labels. Elle est généralisée pour être utilisée dans une génération de colonnes. Et enfin, pour le GWSRP, l’évaluation est effectuée par un modèle PPC qui combiné à une génération de colonnes définissent tous deux un schéma d’optimisation global. / This manuscript addresses scheduling and transport problems where the transport is explicitly taken into account. Such problems are commonly modelled by graphs that are evaluated to obtain the starting times of operations.Classic graph evaluations are performed using longer path algorithms to obtain a semi-active solution, where all operations are left shifted. Nevertheless, these evaluations generally allow only time or distance criteria to be taken into account. The work presented in this thesis propose to take the quality of service criteria into account in the objective function. These considerations require new graph evaluation functions in order to obtain non-semi-active solutions that maximise the quality of service. Indeed, a semi-active solution rarely offers maximum quality of service. Three integrated problems are successively addressed. The first problem is a Job-shop Scheduling Problem with transport and quality of service, referred to as Job-shop Scheduling Problem with Routing (JSPR). Jobs, defined by a succession of operations, are to be performed on different machines, and between two operations, the job must be transported from a machine to another machine. The quality of service criterion in this problem depends on the delay between, on the one hand, the different operations belonging to the same job, and on the other hand, between the different transport operations. Machine-operations and transport-operations are dependent.The second problem is a Workforce Scheduling and Routing Problem (WSRP), which is similar to a problem of planning home services by a set of employees, and where transport is taken into account. For this problem, the quality of service criterion depends on the starting times of the visits. The trips of employees are independent.The third problem is the Generalised Workforce Scheduling and Routing Problem (GWSRP), which takes coordination constraints between employees into account. The trips are dependent on each other. The evaluation function of the starting times must consider simultaneously all trips in order to respect all coordination constraints and to maximise the service quality.For each problem, a new evaluation function is proposed. For the JSPR, this function is based on the algorithm of (Cordeau and Laporte, 2003) which is introduced first for the Dial-A-Ride Problem. The evaluation function, for the JSPR, is based on the insertion of time-lags in the disjunctive graph. This evaluation is included in a metaheuristic. For the WSRP, the evaluation function is based on the dynamic labelling algorithm used for an Elementary Shortest Path Problem With Resource Constraints. This function is generalised in order to be included in a column generation scheme. Finally, for the GWSRP, the evaluation is performed by a PPC model combined with a generation of columns and both define an overall optimisation scheme.