Suchergebnisse

At the moment, constraint programming technology is a powerful tool for solving combinatorial search and combinatorial optimization problems. To use this technology, any task must be formulated as a task of satisfying constraints. The role of the concept of global constraints in modeling and solving applied problems within the framework of the constraint programming paradigm can hardly be overestimated. The procedures that implement the algorithms of filtering global constraints are the elementary "building blocks" from which the model of a specific applied problem is built. Algorithms for filtering global constraints, as a rule, are supported by the corresponding developed theories that allow organizing high-performance computing. The choice of a particular software library is primarily determined by the extent to which the set and method of implementing global constraints corresponds tothe level of modern research in this area. The main focus of this article is focused on an overview of global constraints that are implemented within the most popular constraint programming libraries: Choco, GeCode, JaCoP, MiniZinc.

The work is aimed at solving the three-dimensional problem of finding the open-pit working edge positions by the periods of mining, taking into account the a priori specified productivity for the mineral and overburden. The proposed method uses a block model of a pit, where for each block its coordinates, the content of minerals in it, and the conditional initial value of the block are known. Also, a discounting function is set - a change in the total value of a block, depending on the period of its mining. The task is to find the distribution of blocks over mining periods that maximizes the total value of the blocks. Combinatorial search acceleration is achieved by representing a number of technological constraints in the form of global constraints.

Vehicle routing problems are very hard combinatorial optimization problems with significant economic and environmental challenges. The fundamental problem is to visit a set of customers with a given fleet of vehicles in order to minimize the total distance travelled. Moreover, these problems arise with a wide variety of objectives and additional constraints, related to the legislation and the diversity of industrial sectors. They are very common for many industries and the design of generic solvers has become an important research issue.This thesis focuses on the design and implementation of a new solver for the vehicle routing services offered by the company GEOCONCEPT. The proposed solver is based on constraint programming (CP) to improve flexibility (ability to take additional constraints into account), declarative modelling and maintenance, which are the limits of current GEOCONCEPT solvers based on local search.Firstly, a graph model is established to provide a common representation of the input-data and the numerous business constraints. The resolution is performed using large neighbourhood search methods available in modern CP solvers. It is thus possible to deal with large instances efficiently with a declarative approach where a broad class of vehicle routing problems can be modelled. Secondly, several CP models based on redundant views of the problem are proposed to strengthen the filtering. We focus on the filtering mechanisms for removing infeasible or suboptimal values in the domains of the variables. These algorithms can quickly simplify the problem and derive lower bounds to assert the quality of the solutions found. The lower bounds are obtained by solving relaxations of the most famous problem in Operations Research: the Traveling Salesman Problem (TSP). This problem is the core of the global constraint WEIGTEHDCIRCUIT for modelling routing problems in CP. We propose new filtering algorithms for this constraint based on three relaxations of the TSP. These relaxations are compared theoretically ...

Vehicle routing problems are very hard combinatorial optimization problems with significant economic and environmental challenges. The fundamental problem is to visit a set of customers with a given fleet of vehicles in order to minimize the total distance travelled. Moreover, these problems arise with a wide variety of objectives and additional constraints, related to the legislation and the diversity of industrial sectors. They are very common for many industries and the design of generic solvers has become an important research issue.This thesis focuses on the design and implementation of a new solver for the vehicle routing services offered by the company GEOCONCEPT. The proposed solver is based on constraint programming (CP) to improve flexibility (ability to take additional constraints into account), declarative modelling and maintenance, which are the limits of current GEOCONCEPT solvers based on local search.Firstly, a graph model is established to provide a common representation of the input-data and the numerous business constraints. The resolution is performed using large neighbourhood search methods available in modern CP solvers. It is thus possible to deal with large instances efficiently with a declarative approach where a broad class of vehicle routing problems can be modelled. Secondly, several CP models based on redundant views of the problem are proposed to strengthen the filtering. We focus on the filtering mechanisms for removing infeasible or suboptimal values in the domains of the variables. These algorithms can quickly simplify the problem and derive lower bounds to assert the quality of the solutions found. The lower bounds are obtained by solving relaxations of the most famous problem in Operations Research: the Traveling Salesman Problem (TSP). This problem is the core of the global constraint WEIGTEHDCIRCUIT for modelling routing problems in CP. We propose new filtering algorithms for this constraint based on three relaxations of the TSP. These relaxations are compared theoretically and experimentally. The originality of this work is to propose a new filtering algorithm for reasoning on the direct successors of a customer as well as his position in the tour. It is particularly useful in the presence of time window constraints, which are very common in industrial problems.The new solver shows excellent performance on academic and industrial problems and can compute informative lower bounds for real-life problems. ; Les problèmes de tournées de véhicules sont des problèmes d'optimisation combinatoire épineux avec des enjeux économiques et environnementaux importants au sein de la chaîne logistique. Le problème fondamental est de desservir des clients avec un ensemble de véhicules de façon à minimiser la distance totale parcourue. En pratique, il y a une grande variété d'objectifs et de contraintes additionnelles, liées à la législation et à la diversité des domaines d'applications. Ces problèmes de tournées sont très fréquents pour de nombreuses industries et la conception d'approches de résolution génériques est devenue une question de recherche importante.Cette thèse porte sur la conception et le développement d'un nouveau moteur de résolution pour les logiciels de tournées de véhicules proposés par l'entreprise GEOCONCEPT. Le solveur mis au point s'appuie sur la programmation par contraintes (PPC) pour améliorer la flexibilité (prise en compte de contraintes additionnelles), la déclarativité et la maintenance qui sont les limites des solveurs actuels de GEOCONCEPT fondés sur la recherche locale.Dans un premier temps, un modèle de graphe est établi pour la représentation unifiée des données et de nombreuses contraintes métiers. La résolution s'effectue par des approches à base de voisinage large disponibles dans les solveurs de PPC modernes. On peut ainsi traiter des instances de très grandes tailles efficacement tout en conservant une approche déclarative pour exprimer une classe très large de problèmes de tournées de véhicules. Dans un second temps, des modèles PPC s'appuyant sur des représentations redondantes du problème sont proposés afin de renforcer le filtrage. Nous nous intéressons en détails aux mécanismes de filtrage c'est-à-dire aux processus d'élimination des valeurs infaisables ou sous-optimales dans les domaines des variables. Ces algorithmes permettent de simplifier rapidement le problème et de fournir des bornes inférieures afin d'évaluer la qualité des solutions obtenues. Les bornes inférieures sont obtenues en résolvant des relaxations du plus célèbre des problèmes de la Recherche Opérationnelle : le problème du voyageur de commerce (TSP). Ce problème est le cœur de la contrainte globale weightedcircuit permettant de modéliser les problèmes de tournées en PPC. Nous proposons de nouveaux mécanismes de filtrage pour cette contrainte s'appuyant sur trois relaxations du TSP. Ces relaxations sont comparées sur les plans théorique et expérimental. L'originalité de ce travail est de proposer un nouvel algorithme de filtrage permettant de raisonner à la fois sur les successeurs directs d'un client et sur sa position dans la tournée. Ces raisonnements sont particulièrement utiles en présence de contraintes de fenêtres de temps, très communes dans les problèmes industriels.Le nouveau moteur de résolution offre d'excellentes performances sur des problèmes académiques et industriels tout en proposant des bornes inférieures informatives à des problèmes industriels réels.

AbstractA program with a quadratic objective function and quadratic constraints is considered. Two duals to such programs are provided, and an algorithm is presented based upon approximations to the duals. The algorithm consists of a sequence of linear programs and programs involving the optimization of a quadratic function either unconstrained or constrained to the nonnegative orthant. An example involving production planning is presented.

A very large number of combinatorial problems belong to the family of Constraint Satisfaction Problems (CSP): configuration, planning, scheduling, resource allocation. These problems share a common description that generally allows a clear and intuitive modeling. In this thesis, we proposed and studied a new hybrid method for solving CSPs. We named this method Tabu-NG for Tabu Search based on NoGood. The name is a bit simplistic because it is a hybrid of filtering algorithm, constraint propagation, Tabu Search and nogood management. The method was applied to two types of problems. The first is the Frequency Assignment Problem (FAP) in military radio networks, particularly the problems proposed from 1993 (benchmarks of the European project CALMA) until 2010 (benchmarks of a DGA project). The second is the academic problem of k-coloring of graphs on the DIMACS instances. The method has improved some high scores currently known. In both problems we dealt with unary and binary constraints, and also with n-ary constraints and function optimization under constraints for FAP. The principles of Tabu-NG are general and can be applied to other CSPs. It can also accommodate specific heuristics to problems, we practiced it on the problems cited, and in this sense we believe we can qualify the method as metaheuristic without abusing this definition. ; Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP) : configuration, ordonnancement, affectation de ressources. Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s'agit d'une hybridation d'algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été ...

A very large number of combinatorial problems belong to the family of Constraint Satisfaction Problems (CSP): configuration, planning, scheduling, resource allocation. These problems share a common description that generally allows a clear and intuitive modeling. In this thesis, we proposed and studied a new hybrid method for solving CSPs. We named this method Tabu-NG for Tabu Search based on NoGood. The name is a bit simplistic because it is a hybrid of filtering algorithm, constraint propagation, Tabu Search and nogood management. The method was applied to two types of problems. The first is the Frequency Assignment Problem (FAP) in military radio networks, particularly the problems proposed from 1993 (benchmarks of the European project CALMA) until 2010 (benchmarks of a DGA project). The second is the academic problem of k-coloring of graphs on the DIMACS instances. The method has improved some high scores currently known. In both problems we dealt with unary and binary constraints, and also with n-ary constraints and function optimization under constraints for FAP. The principles of Tabu-NG are general and can be applied to other CSPs. It can also accommodate specific heuristics to problems, we practiced it on the problems cited, and in this sense we believe we can qualify the method as metaheuristic without abusing this definition. ; Un très grand nombre de problèmes combinatoires appartient à la famille des problèmes de satisfaction de contraintes (Constraint Satisfaction Problem ou CSP) : configuration, ordonnancement, affectation de ressources. Ces problèmes partagent une description commune qui autorise en général une modélisation claire et intuitive. Dans cette thèse, nous avons proposé et étudié une nouvelle méthode de résolution hybride pour les CSPs. Nous avons nommé cette méthode Tabu-NG pour Tabu Search based on NoGood. Le nom est un peu réducteur car il s'agit d'une hybridation d'algorithme de filtrage, de propagation de contraintes, de Recherche Tabou et de gestion de nogoods. La méthode a été ...

AbstractThis note describes some constraints that may be applied to shipping models structured as linear programming problems. These constraints defining port‐throughput capability have proven useful in applications of linear programming by the author and provide additional realism in problems of vessel allocation and ship design selection. Increase in model size through the use of the constraints is in general mode rate.