Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/ integer programming methods. We ...
详细信息
Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/ integer programming methods. We consider three Life pattern- creation problems: finding maximum density still- Lifes, finding smallest immediate predecessor patterns, and finding period- 2 oscillators. For the first two problems, integrating integer programming and constraint programming approaches provides a much better solution procedure than either individually. For the final problem, the constraint programming formulation provides the better approach.
Diagnostic reasoning is often based on abduction. Abductive inference consists in generation of hypotheses which explain the current behavior of the system under investigation. Such a reasoning is based on accessible ...
详细信息
ISBN:
(纸本)9783319644745;9783319644738
Diagnostic reasoning is often based on abduction. Abductive inference consists in generation of hypotheses which explain the current behavior of the system under investigation. Such a reasoning is based on accessible background knowledge and the results must be consistent with all auxiliary observations. Efficient abductive diagnosis is carried out as Model-Based Reasoning. The knowledge about the model defines the search-space for diagnostic hypotheses. Unfortunately, use of classical consistency-based reasoning leads to rough, qualitative results only, even if good knowledge of the correct model is available. In this paper and attempt to use constraint programming as a tool for diagnostic reasoning is presented. The ultimate goal is to provide more precise diagnoses. Two case studies, one concerning fault parameter evaluation, and the second concerning structural fault localization are presented.
Genome Rearrangements addresses the problem of finding the minimum number of global operations, such as transpositions, reversals, fusions and fissions that transform a given genome into another. In this paper we deal...
详细信息
ISBN:
(纸本)9783642032226
Genome Rearrangements addresses the problem of finding the minimum number of global operations, such as transpositions, reversals, fusions and fissions that transform a given genome into another. In this paper we deal with transposition events, which are events that change the position of two contiguous block of genes in the same chromosome. The transposition event generates the transposition distance problem, that is to find the minimum number of transposition that transform one genome (or chromosome) into another. Although some tractables instances were found [20, 14], it is not known if an exact polynomial time algorithm exists. Recently, Dias and Souza [9] proposed polynomial-sized Integer Linear programming (ILP) models for rearrangement distance problems where events are restricted to reversals, transpositions or a combination of both. In this work we devise a slight different approach. We present some constraint Logic programming (CLP) models for transposition distance based on known bounds to the problem.
In this thesis we investigate the potential use of constraint programming to develop a production planning solver. We focus on lot-sizing problems that are crucial and challenging problems of the tactical level of pro...
详细信息
In this thesis we investigate the potential use of constraint programming to develop a production planning solver. We focus on lot-sizing problems that are crucial and challenging problems of the tactical level of production planning and use one of the main strengths of constraint programming, namely global constraints. The goal of this work is to set the grounds of a constraint programming framework for solving complex lot-sizing problems. We define a LotSizing global constraint based on a generic single-item, single-level lot-sizing problem that considers production and inventory capacities, unitary production and inventory costs and setup costs. This global constraint is an intuitive modeling tool for complex lot-sizing problems as it can model the nodes of lot-sizing networks. We use classical dynamic programming techniques of the lot-sizing field to develop powerful filtering algorithms for the global constraint. Furthermore we model multi-item problems that are natural extensions of the core *** we introduce a new generic filtering algorithm based on linear programming. We show that arc consistency can be achieved with only one call to a linear programming solver when the global constraint has an ideal formulation and adapt the result to provide partial filtering when no restriction is made on the constraints. This technique can be useful to tackle polynomial lot-sizing underlying flow and sequence sub-problems.
The Spatial Packaging Problem (SPP) aims to solve a mixture of the 3D Packing Problem (3DPP) and the 3D Pipe-Routing Problem. The main feature that distinguishes the SPP from the traditional 3DPP is the interconnectio...
详细信息
ISBN:
(纸本)9783319339542;9783319339535
The Spatial Packaging Problem (SPP) aims to solve a mixture of the 3D Packing Problem (3DPP) and the 3D Pipe-Routing Problem. The main feature that distinguishes the SPP from the traditional 3DPP is the interconnections that exist between its components. The SPP is more challenging because the shape and dimensions of the interconnections are unknown, and must be determined as part of the solution. In this paper, we propose a relaxation, a constraint programming model and a search heuristic to solve the SPP. We relax the SPP by using taxicab geometry and model it as a constraint satisfaction problem, then solve it by using a search heuristic based on interconnection volumes. The proposed approach has been evaluated on a challenging benchmark that reflects a range of aerospace and commercial applications varying in number of components and interconnections. The preliminary results show the effectiveness and efficiency of the proposed approach.
This paper addresses the robust two-machine permutation flow-shop scheduling problem considering non-deterministic operation processing times associated with an uncertainty budget. The objective is to minimize the mak...
详细信息
ISBN:
(纸本)9783031332708;9783031332715
This paper addresses the robust two-machine permutation flow-shop scheduling problem considering non-deterministic operation processing times associated with an uncertainty budget. The objective is to minimize the makespan of the schedule. Exact solution methods incorporated within the framework of a two-stage robust optimization are proposed to solve the problem. We first prove that under particular conditions the robust two-machine permutation flow-shop scheduling problem can be solved in polynomial time by the well-known Johnson's algorithm usually dedicated to the deterministic version. Then we tackle the general problem, for which we propose a column and constraint generation algorithm. We compare two versions of the algorithm. In the first version, a mixed-integer linear programming formulation is used for the master problem. In the second version, we use a constraint programming model for the master problem. To the best of our knowledge, the use of constraint programming for a master problem in a two-stage robust optimization problem is innovative. The experimental results show the very good performance of the method based on the constraint programming formulation. We also notice that Johnson's algorithm is surprisingly efficient for the robust version of the general problem.
High School Timetabling (HSTT) is a well-known and widespread problem. It consists of coordinating resources (e.g. teachers, rooms), times, and events (e.g. classes) with respect to a variety of constraints. In this p...
详细信息
ISBN:
(数字)9783319930312
ISBN:
(纸本)9783319930312;9783319930305
High School Timetabling (HSTT) is a well-known and widespread problem. It consists of coordinating resources (e.g. teachers, rooms), times, and events (e.g. classes) with respect to a variety of constraints. In this paper, we study the applicability of constraint programming (CP) for high school timetabling. We formulate a novel CP model for HSTT using a scheduling-based point of view. We show that a drastic improvement in performance over the baseline CP model can be achieved by including solution-based phase saving, which directs the CP solver to first search in close proximity to the best solution found, and our hot start approach, where we use existing heuristic methods to produce a starting point for the CP solver. The experiments demonstrate that our approach outperforms the IP and maxSAT complete methods and provides competitive results when compared to dedicated heuristic solvers.
In the standard constraint programming (CP) framework, an integer variable represents a signed integer and its domain is bounded by some minimal and maximal integer type values. In existing CP tools, the integer type ...
详细信息
ISBN:
(纸本)9783642135194
In the standard constraint programming (CP) framework, an integer variable represents a signed integer and its domain is bounded by some minimal and maximal integer type values. In existing CP tools, the integer type is used to represent domain values, and hence domain bounds are inherently limited by the minimal and maximal signed integer values representable on a given platform. However, this implementation of integer variable fails to satisfy use cases where modeled integers can be arbitrarily large. An example of such CP application is the functional test generation where integer variables are used to model large architectural fields like memory addresses or operand data. In addition, in such applications, the set of standard arithmetic operations on an integer variable provided by the traditional CP framework does not represent the whole range of operations required for modeling. In this paper, we define a new type of integer variables with arbitrarily large domain size and a modified operation set. We show how this variable type can be realized on top of a traditional CP framework by means of global constraints over standard integer variables. The ideas presented in this paper can also be used to implement a native variable of the introduced type in a CP tool. The paper provides experimental results to demonstrate the effectiveness of the proposed approach.
The paper proposes an original approach to solving the problem of ineffective processing of qualitative constraints of a subject domain using the constraint programming technique. The approach is based on the use of s...
详细信息
ISBN:
(纸本)9781614999331;9781614999324
The paper proposes an original approach to solving the problem of ineffective processing of qualitative constraints of a subject domain using the constraint programming technique. The approach is based on the use of specialized matrix-like structures providing a "compressed" representation of constraints over finite domains, as well as on the use of the authors' inference techniques on these structures. In comparison with the prototypes using the typical representation of multi-place relations in the form of a table, the techniques make it possible to more efficiently reduce the search space. The paper presents practical aspects of implementation of user-developed types of constraints and corresponding algorithmspropagators, with the help of constraint programming libraries. The algorithms performance has been assessed by means of the above matrix structures to clearly demonstrate the advantages of representation and processing of qualitative constraints of a subject domain.
Problems affecting the transport of people or goods are plentiful in industry and commerce and they also appear to be at the origin of much more complex problems. In recent years, the logistics and transport sector ke...
详细信息
Problems affecting the transport of people or goods are plentiful in industry and commerce and they also appear to be at the origin of much more complex problems. In recent years, the logistics and transport sector keeps growing supported by technological progress, i.e. companies to be competitive are resorting to innovative technologies aimed at efficiency and effectiveness. This is why companies are increasingly using technologies such as Artificial Intelligence (AI), Blockchain and Internet of Things (IoT). Artificial intelligence, in particular, is often used to solve optimization problems in order to provide users with the most efficient ways to exploit available resources. In this work we present an overview of our current research activities concerning the development of new algorithms, based on constraint Logic programming (CLP) techniques, for route planning problems exploiting the geometric information intrinsically present in many of them or in some of their variants. The research so far has focused in particular on the Euclidean Traveling Salesperson Problem (Euclidean TSP) with the aim to exploit the results obtained also to other problems of the same category, such as the Euclidean Vehicle Routing Problem (Euclidean VRP), in the future.
暂无评论