The use of restart techniques in complete Satisfiability (SAT) algorithms has made solving hard real world instances possible. Without restarts such algorithms could not solve those instances, in practice. State of th...
详细信息
The use of restart techniques in complete Satisfiability (SAT) algorithms has made solving hard real world instances possible. Without restarts such algorithms could not solve those instances, in practice. State of the art algorithms for SAT use restart techniques, conflict clause recording (nogoods), heuristics based on activity variable in conflict clauses, among others. Algorithms for SAT and constraint problems share many techniques; however, the use of restart techniques in constraint programming with finite domains (CP(FD)) is not widely used as it is in SAT. We believe that the use of restarts in CP(FD) algorithms could also be the key to efficiently solve hard combinatorial problems. In this PhD thesis we study restarts and associated techniques in CP(FD) solvers. In particular, we propose to including in a CP(FD) solver restarts, nogoods and heuristics based in nogoods as this should improve search algorithms, and, consequently, efficiently solve hard combinatorial problems. We thus intend to: a) implement restart techniques (successfully used in SAT) to solve constraint problems with finite domains; b) implement nogoods (learning) and heuristics based on nogoods, already in use in SAT and associated with restarts; and c) evaluate the use of restarts and the interplay with the other implemented techniques. We have conducted the study in the context of domain splitting backtrack search algorithms with restarts. We have defined domain splitting nogoods that are extracted from the last branch of the search algorithm before the restart. And, inspired by SAT solvers, we were able to use information within those nogoods to successfully help the variable selection heuristics. A frequent restart strategy is also necessary, since our approach learns from restarts.
Anti-unification refers to the process of generalizing two (or more) goals into a single, more general, goal that captures some of the structure that is common to all initial goals. In general one is typically interes...
详细信息
This study presents a constraint programming (CP) approach for modeling batch operations both in fab (incompatible job families) and backend (compatible job families) which involves the constraints of different job re...
详细信息
ISBN:
(纸本)9781509054497
This study presents a constraint programming (CP) approach for modeling batch operations both in fab (incompatible job families) and backend (compatible job families) which involves the constraints of different job release times, non-identical job sizes, and different batch size. We formulate this scheduling problem as CP and compare with a mixed integer programming (MIP) approach. The models are tested on a set of common problem instances from a paper in the literature. Computational results show that CP outperforms the MIP approach with respect to solution quality and run time.
This paper considers the integrated problem of quay crane assignment, quay crane scheduling, yard location assignment, and vehicle dispatching operations at a container terminal. The main objective is to minimize vess...
详细信息
ISBN:
(纸本)9783319930312;9783319930305
This paper considers the integrated problem of quay crane assignment, quay crane scheduling, yard location assignment, and vehicle dispatching operations at a container terminal. The main objective is to minimize vessel turnover times and maximize the terminal throughput, which are key economic drivers in terminal operations. Due to their computational complexities, these problems are not optimized jointly in existing work. This paper revisits this limitation and proposes Mixed Integer programming (MIP) and constraint programming (CP) models for the integrated problem, under some realistic assumptions. Experimental results show that the MIP formulation can only solve small instances, while the CP model finds optimal solutions in reasonable times for realistic instances derived from actual container terminal operations.
The objective of airline manpower planning is to have the right number of pilots with the right qualifications at the right time. To accomplish this, one has to solve the subproblem of assigning pilots to promotion co...
详细信息
The objective of airline manpower planning is to have the right number of pilots with the right qualifications at the right time. To accomplish this, one has to solve the subproblem of assigning pilots to promotion courses such that pilots' seniority ranks and preferences are taken into account: no senior pilot should be able to find a junior pilot with a promotion that the senior pilot would have preferred. We call this subproblem the airline promotion assignment problem (APA). The objective of this thesis is to develop an efficient model for APA. We show how APA can be modelled as a stable matching problem, and more specifically how it can be formulated as an instance of the hospitals/residents prob- lem with ties and forbidden pairs. A constraint satisfaction problem model for APA is presented, which we have implemented in a constraint programming system. We also present a model for an extension to APA, which we call the airline promo- tion assignment problem with detailed preferences (APA-D), and which involves additional rules used within a specific airline. We show results from running our constraint programming implementation on different types of test data derived from real airline data. The thesis is concluded with a discussion of our work and some remarks on how the problem could be modelled and solved differently.
We present a method for solving programming by Example (PBE) problems that tightly integrates a neural network with a constraint logic programming system called miniKanren. Internally, miniKanren searches for a progra...
详细信息
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.
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.
Inspired by the geometric reasoning exploited in discrete ellipsoid-based search (DEBS) from the communications literature, we develop a constraint programming (CP) approach to solve problems with strictly convex quad...
详细信息
ISBN:
(纸本)9783319449531;9783319449524
Inspired by the geometric reasoning exploited in discrete ellipsoid-based search (DEBS) from the communications literature, we develop a constraint programming (CP) approach to solve problems with strictly convex quadratic constraints. Such constraints appear in numerous applications such as modelling the ground-to-satellite distance in global positioning systems and evaluating the efficiency of a schedule with respect to quadratic objective functions. We strengthen the key aspects of the DEBS approach and implement them as combination of a global constraint and variable/value ordering heuristics in IBM ILOG CP Optimizer. Experiments on a variety of benchmark instances show significant improvement compared to the default settings and state-of-the-art performance compared to competing technologies of mixed integer programming, semi-definite programming, and mixed integer nonlinear programming.
This paper describes a learning parallel constraint programming (CP) solver designed for solving CP problems with several instances on massively parallel computing platforms comprising multi-core parallel machines or ...
详细信息
This paper describes a learning parallel constraint programming (CP) solver designed for solving CP problems with several instances on massively parallel computing platforms comprising multi-core parallel machines or Many Integrated Cores. The CP solver proposed in this work is based on a Portfolio parallelization that employs a linear reward inaction learning algorithm in order to obtain the best possible performance for a large set of instances of the same problem. The linear reward inaction algorithm enables the prediction of the number of cores to be assigned to each search strategy based on previous experiments, reducing the computing time required to solve constraint satisfaction and optimization problems. The underlying principle of the Portfolio approach is to run N sequential search strategies using N computing cores (N To N Portfolio) where each core uses its own strategy in order to perform a search that is different from strategies used by the other cores. The first strategy that finds a solution stops all other strategies. The problem with the N To N Portfolio approach is that the number of search strategies is very small compared with the current number of computing cores used by the parallel machines. However, using an internal parallelization for each search strategy, it is possible to run N parallel search using P computing cores with P >> N (N To P Portfolio). This N To P Portfolio performs suboptimally for solving different CP problems because many computing resources are wasted. To improve this Portfolio model, an adaptive N To P Portfolio was proposed, which tries to privilege the strategy that is most likely to find a solution first in order to give it more computing cores than the other strategies. However, the main problem with the adaptive Portfolio is that it loses all the learned information at the end of each search;it is designed to solve just one CP problem. Furthermore, many computational resources are wasted by both Portfolio solvers,
暂无评论