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.
Contemporary motor vehicles have increasing numbers of automated functions to augment the safety and comfort of a car. The automotive industry has to incorporate increasing numbers of processing units in the structure...
详细信息
Contemporary motor vehicles have increasing numbers of automated functions to augment the safety and comfort of a car. The automotive industry has to incorporate increasing numbers of processing units in the structure of cars to run the software that provides these functionalities. The software components often need access to sensors or mechanical devices which they are designed to operate. The result is a network of hardware units which can accommodate a limited number of software programs, each of which has to be assigned to a hardware unit. A prime goal of this deployment problem is to find software-to-hardware assignments that maximise the reliability of the system. In doing so, the assignments have to observe a number of constraints to be viable. This includes limited memory of a hardware unit, collocation of software components on the same hardware units, and communication between software components. Since the problem consists of many constraints with a significantly large search space, we investigate an ACO and constraint programming (CP) hybrid for this problem. We find that despite the large number of constraints, ACO on its own is the most effective method providing good solutions by also exploring infeasible regions.
Milton Babbitt (1916-2011) was a composer of twelve-tone serial music noted for creating the all-partition array. One part of the problem in generating an all-partition array requires finding a covering of a pitch-cla...
详细信息
ISBN:
(纸本)9783319449531;9783319449524
Milton Babbitt (1916-2011) was a composer of twelve-tone serial music noted for creating the all-partition array. One part of the problem in generating an all-partition array requires finding a covering of a pitch-class matrix by a collection of sets, each forming a region containing 12 distinct elements and corresponding to a distinct integer partition of 12. constraint programming (CP) is a tool for solving such combinatorial and constraint satisfaction problems. In this paper, we use CP for the first time to formalize this problem in generating an all-partition array. Solving the whole of this problem is difficult and few known solutions exist. Therefore, we propose solving two sub-problems and joining these to form a complete solution. We conclude by presenting a solution found using this method. Our solution is the first we are aware of to be discovered automatically using a computer and differs from those found by composers.
暂无评论