We study the automatic generation of primal and dual bounds from decision diagrams in constraintprogramming. In particular, we expand the functionality of the Haddock system to optimization problems by extending its ...
详细信息
ISBN:
(数字)9783031332715
ISBN:
(纸本)9783031332708;9783031332715
We study the automatic generation of primal and dual bounds from decision diagrams in constraintprogramming. In particular, we expand the functionality of the Haddock system to optimization problems by extending its specification language to include an objective function. We describe how restricted decision diagrams can be compiled in Haddock similar to the existing relaxed decision diagrams. Together, they provide primal and dual bounds on the objective function, which can be seamlessly integrated into the constraintprogramming search. The entire process is automatic and only requires a high-level user model specification. We evaluate our method on the sequential ordering problem and compare the performance of Haddock to a dedicated decision diagram approach. The results show that Haddock achieves comparable results in similar time, demonstrating the viability of our automated decision diagram procedures for constraint optimization problems.
One of the current challenges in the context of Metamorphic Testing (MT) is the formalization and validation of metamorphic relations (MRs), as there is no single method or homogeneous way of doing it. It is a part of...
详细信息
ISBN:
(纸本)9781728122359
One of the current challenges in the context of Metamorphic Testing (MT) is the formalization and validation of metamorphic relations (MRs), as there is no single method or homogeneous way of doing it. It is a part of this software testing technique that, unlike others, is not yet developed. On one hand, the fact of having an artifact that formally validates these main elements in MT, facilitates the task for developers and testers and ensures that the technique applied fulfills its function with guarantees. On the other hand, nowadays, there are numerous accessible tools based on highly consolidated and mature constraint solvers that can help in this process of validation. Interpreting MRs as a set of constraints, their validation with these tools is directly applicable. This paper presents a proposal based on a use case, in which MRs are implemented as a set of restrictions. The experiments and the results are described and future lines of research are outlined.
The use of constraint propagation is the main feature of any constraint solver. It is thus of prime importance to manage the propagation in an efficient and effective fashion. There are two classes of propagation algo...
详细信息
The use of constraint propagation is the main feature of any constraint solver. It is thus of prime importance to manage the propagation in an efficient and effective fashion. There are two classes of propagation algorithms for general constraints: fine-grained algorithms where the removal of a value for a variable will be propagated to the corresponding values for other variables, and coarse-grained algorithms where the removal of a value will be propagated to the related variables. One big advantage of coarse-grained algorithms, like AC-3, over fine-grained algorithms, like AC-4, is the ease of integration when implementing an algorithm in a constraint solver. However, fine-grained algorithms usually have optimal worst case time complexity while coarse-grained algorithms do not. For example, AC-3 is an algorithm with non-optimal worst case complexity although it is simple, efficient in practice, and widely used. In this paper we propose a coarse-grained algorithm, AC2001/3.1, that is worst case optimal and preserves as much as possible the ease of its integration into a solver (no heavy data structure to be maintained during search). Experimental results show that AC2001/3.1 is competitive with the best fine-grained algorithms such as AC-6. The idea behind the new algorithm can immediately be applied to obtain a path consistency algorithm that has the best-known time and space complexity. The same idea is then extended to non-binary constraints. (c) 2005 Elsevier B.V. All rights reserved.
暂无评论