constraint programming allows difficult combinatorial problems to be modelled declaratively and solved automatically. Advances in solver technologies over recent years have allowed the successful use of constraint pro...
详细信息
constraint programming allows difficult combinatorial problems to be modelled declaratively and solved automatically. Advances in solver technologies over recent years have allowed the successful use of constraint programming in many application areas. However, when a particular solver's search for a solution takes too long, the complexity of the constraint program execution hinders the programmer's ability to profile that search and understand how it relates to their model. Therefore, effective tools to support such profiling and allow users of constraint programming technologies to refine their model or experiment with different search parameters are essential. This paper details the first user-centred design process for visual profiling tools in this domain. We report on: our insights and opportunities identified through an on-line questionnaire and a creativity workshop with domain experts carried out to elicit requirements for analytical and visual profiling techniques;our designs and functional prototypes realising such techniques;and case studies demonstrating how these techniques shed light on the behaviour of the solvers in practice.
We study a tournament format that extends a traditional double round-robin format with divisional single round-robin tournaments. Elitserien, the top Swedish handball league, uses such a format for its league schedule...
详细信息
We study a tournament format that extends a traditional double round-robin format with divisional single round-robin tournaments. Elitserien, the top Swedish handball league, uses such a format for its league schedule. We present a constraint programming model that characterizes the general double round-robin plus divisional single round-robin format. This integrated model allows scheduling to be performed in a single step, as opposed to common multistep approaches that decompose scheduling into smaller problems and possibly miss optimal solutions. In addition to general constraints, we introduce Elitserien-specific requirements for its tournament. These general and league-specific constraints allow us to identify implicit and symmetry-breaking properties that reduce the time to solution from hours to seconds. A scalability study of the number of teams shows that our approach is reasonably fast for even larger league sizes. The experimental evaluation of the integrated approach takes considerably less computational effort to schedule Elitserien than does the previous decomposed approach. (C) 2016 Elsevier B.V. All rights reserved.
Juxtapositioning manually created business process models with diagrams generated using process discovery algorithms exposes high complexity of the latter. As a consequence, their formal verification requires signific...
详细信息
ISBN:
(纸本)9781538623718
Juxtapositioning manually created business process models with diagrams generated using process discovery algorithms exposes high complexity of the latter. As a consequence, their formal verification requires significant computational resources due to a large state space. Nevertheless, an analysis of the generated model is needed to assure its correctness and the ability to represent source data. As a solution to this problem, we present an approach for constraint-based generation of a complete workflow log for a given BPMN model. In this paper, we propose a method to extract directed subgraphs representing token flows in the process together with a set of predefined constraints. Likewise, in the case of process simulation, these constraints ensure the correctness of the generated traces. Ultimately, the obtained results can be compared to the original workflow log used for process discovery in order to verify the obtained model.
This paper introduces a new method based on constraint programming (CP) and genetic algorithm (GA) for solving dynamic scheduling problems. The proposed approach allows us to handle scheduling problems with large size...
详细信息
ISBN:
(纸本)9781538608753
This paper introduces a new method based on constraint programming (CP) and genetic algorithm (GA) for solving dynamic scheduling problems. The proposed approach allows us to handle scheduling problems with large sizes (i.e. search spaces are too large). Our idea is to break up the search space into disjoined sub-spaces by the genetic algorithm. To each individual of the population is associated a sub-space. Each sub-space is represented by a sub-CSP which is easier to solve than the original scheduling problem. Our first experimentations are addressed to the Endoscopy Unit scheduling in dynamic way.
In our paper, we analyze new exact approaches for the multi-mode resource-constrained project scheduling (MRCPSP) problem with the aim of makespan minimization. For the single-mode RCPSP (SRCPSP) recent exact algorith...
详细信息
In our paper, we analyze new exact approaches for the multi-mode resource-constrained project scheduling (MRCPSP) problem with the aim of makespan minimization. For the single-mode RCPSP (SRCPSP) recent exact algorithms combine a Branch and Bound algorithm with principles from constraint programming (CP) and Boolean Satisfiability Solving (SAT). We extend the above principles for the solution of MRCPSP instances. This generalization is on the one hand achieved on the modeling level. We propose three CP-based formulations of the MRCPSP for the G12 CP platform and the optimization framework SCIP which both provide solution techniques combining CP and SAT principles. For one of the latter we implemented a new global constraint for SCIP, which generalizes the domain propagation and explanation generation principles for renewable resources in the context of multi-mode jobs. Our constraint applies the above principles in a more general way than the existing global constraint in SCIP. We compare our approaches with the state-of-the-art exact algorithm from the literature on MRCPSP instances with 20 and 30 jobs. Our computational experiments show that we can outperform the latter approach on these instances. Furthermore, we are the first to close (find the optimal solution and prove its optimality for) 628 open instances with 50 and 100 jobs from the literature. In addition, we improve the best known lower bound of 2815 instances and the best known upper bound of 151 instances. (C) 2017 The Authors. Published by Elsevier Ltd.
Cloud computing is the widely spread paradigm of utility-computing that offers an "on-demand" internet-based access to configurable resources available within data centers. On one hand, public Cloud provider...
详细信息
ISBN:
(纸本)9781538621295
Cloud computing is the widely spread paradigm of utility-computing that offers an "on-demand" internet-based access to configurable resources available within data centers. On one hand, public Cloud providers are well suited for highly available access to IT resources (infrastructure, platform and software), for sporadic use, or for elastic demands. On the other hand, private clouds could sometimes be preferred for security or privacy reasons, or for cost reasons due to a high frequency usage of services. However, in many cases a choice between public or private clouds does not fulfill all requirements of companies, and hybrid cloud infrastructures should be preferred. A hybrid cloud solution could, for example, answer sudden workload increase in private clouds, security or fault tolerance requirements, or even latency issues thanks to data-locality. Solutions have already been proposed to address hybrid cloud infrastructures, however most of the time the placement of a distributed software on such infrastructure has to be indicated manually. For this reason, the automation of software deployment on hybrid clouds is still under research. In this paper we propose new specific placement constraints and objectives adapted to hybrid clouds infrastructures within our placement solution, namely OptiPlace, and we address this problem through constraint programming. Furthermore, we evaluate the expressivity and performance of the proposed solution on a real case study.
The CP conference is the annual international conference on constraint programming. It is concerned with all aspects of computing with constraints, including theory, algorithms, environments, languages, models, system...
详细信息
The CP conference is the annual international conference on constraint programming. It is concerned with all aspects of computing with constraints, including theory, algorithms, environments, languages, models, systems, and applications such as decision-making, resource allocation, scheduling, configuration, and planning. The CP community is very keen to ensure it remains open to interdisciplinary research at the intersection between constraint programming and related fields. Hence, in addition to the usual technical and application tracks, the CP 2016 conference featured thematic tracks: "Computational Sustainability", "CP and Biology", "Preferences, Social Choice and Optimization", and "Testing and Verification". In this overview, we highlight several remarkable papers that have been selected by the senior program committee and papers with the most innovative methods and techniques, and a very high potential for applications (in our opinion).
We describe constraint programming (CP) models to solve a cryptanalytic problem: the chosen key differential attack against the standard block cipher AES. We show that CP solvers are able to solve these problems quick...
详细信息
ISBN:
(纸本)9780999241103
We describe constraint programming (CP) models to solve a cryptanalytic problem: the chosen key differential attack against the standard block cipher AES. We show that CP solvers are able to solve these problems quicker than dedicated cryptanalysis tools, and we prove that a solution claimed to be optimal in two recent cryptanalysis papers is not optimal by providing a better solution.
The problem of Causal Structure Discovery is defined by given inputs, outputs, auxiliary knowledge of components and possible internal connections. constraints programming is employed to discover admissible system mod...
详细信息
ISBN:
(数字)9783319604381
ISBN:
(纸本)9783319604381;9783319604374
The problem of Causal Structure Discovery is defined by given inputs, outputs, auxiliary knowledge of components and possible internal connections. constraints programming is employed to discover admissible system models. Existence of internal connections and predefined functionality of components is handled through reification.
Effective general-purpose search strategies are an important component in constraint programming. We introduce a new idea, namely, using correlations between variables to guide search. Variable correlations are measur...
详细信息
ISBN:
(纸本)9781538638767
Effective general-purpose search strategies are an important component in constraint programming. We introduce a new idea, namely, using correlations between variables to guide search. Variable correlations are measured and maintained by using domain changes during constraint propagation. We propose two variable heuristics based on the correlation matrix, crbs-sum and crbs-max. We evaluate our correlation heuristics with well known heuristics, namely, domiwdeg, impact-based search and activity-based search. Experiments on a large set of benchmarks show that our correlation heuristics are competitive with the other heuristics, and can be the fastest on many series.
暂无评论