Finding the largest clique in a given graph is one of the fundamental NP-hard problems. We take a widely used branch and bound algorithm for the maximum clique problem, and discuss an alternative way of understanding ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Finding the largest clique in a given graph is one of the fundamental NP-hard problems. We take a widely used branch and bound algorithm for the maximum clique problem, and discuss an alternative way of understanding the algorithm which closely resembles a constraint model. By using this view, and by taking measurements inside search, we provide a new explanation for the success of the algorithm: one of the intermediate steps, by coincidence, often approximates a "smallest domain first" heuristic. We show that replacing this step with a genuine "smallest domain first" heuristic leads to a reduced branching factor and a smaller search space, but longer runtimes. We then introduce a "domains of size two first" heuristic, which integrates cleanly into the algorithm, and which both reduces the size of the search space and gives a reduction in runtimes.
In order to improve the deductive power of ffinite domain constraint solvers usually redundant and global constraints are added to the constraint system. the objective of this work [2] is to develop a new constraint s...
详细信息
ISBN:
(纸本)3540652248
In order to improve the deductive power of ffinite domain constraint solvers usually redundant and global constraints are added to the constraint system. the objective of this work [2] is to develop a new constraint solving scheme designed as an extension of a classical arc-consistency algorithm. Associated to a declarative language, it allows the user to implement his own global relations without the need of manipulating internal structures of the solver or modifying in depththe original model of the studied problem. this system relies on two new structures: index-sets and constraint templates. the former consist in sets of integers used as indices over tables. they collect variables sharing some properties (for instance tasks in a scheduling problem assigned to the same machine). the latter are descriptions of constraints that must be applied (possibly) over selected sets of variables (for instance the fact that a set of tasks must be scheduled before another set). Both, set-index and constraint template deffnitions are evaluated dynamically and depend on the variables’ domains. Indeed, the new constraints are automatically generated by the constraint solver based on the set contents and variable domain values. the index-set and constraint deffinition language uses a mathematic style notation. the deffnitions are compiled to the solver representation which can be directly handled by the propagation mechanism. this organisation guarantees a high level of efficiency.
A broken triangle is a pattern of (in) compatibilities between assignments in a binary CSP (constraint satisfaction problem). In the absence of certain broken triangles, satisfiability-preserving domain reductions are...
详细信息
ISBN:
(纸本)9783319232195;9783319232188
A broken triangle is a pattern of (in) compatibilities between assignments in a binary CSP (constraint satisfaction problem). In the absence of certain broken triangles, satisfiability-preserving domain reductions are possible via merging of domain values. We investigate the possibility of maximising the number of domain reduction operations by the choice of the order in which they are applied, as well as their interaction with arc consistency operations. It turns out that it is NP-hard to choose the best order.
Tolerant Algebraic Side-Channel Attack (TASCA) is a combination of algebraic and side-channel analysis with error tolerance. Oren et al., used mathematical programming to implement TASCA over a round-limited version o...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Tolerant Algebraic Side-Channel Attack (TASCA) is a combination of algebraic and side-channel analysis with error tolerance. Oren et al., used mathematical programming to implement TASCA over a round-limited version of AES. In [7], Liu et al. revisited their results and introduced a TASCA-CP model that delivers solutions to this 1-round relaxation with orders of magnitude improvement in both solving time and memory consumption. this paper extends the result and considers TASCA for the full 10-rounds AES algorithm. Two approaches are introduced: staged and integrated. the staged approach uses TASCA-CP as a spring board to enumerate and check its candidate solutions against the requirements of subsequent rounds. the integrated model formulates all the rounds of AES together with side-channel constraints on all rounds within a single unified optimization model. Empirical results shows both approaches are suitable to find the correct key of AES while the integrated model dominates the staged both in simplicity and solving time.
Inspired by AND/OR search spaces for graphical models recently introduced, we propose to augment Ordered Decision Diagrams with AND nodes, in order to capture function decomposition structure. this yields AND/OR multi...
详细信息
ISBN:
(纸本)3540462678
Inspired by AND/OR search spaces for graphical models recently introduced, we propose to augment Ordered Decision Diagrams with AND nodes, in order to capture function decomposition structure. this yields AND/OR multivalued decision diagram (AOMDD) which compiles a constraint network into a canonical form that supports polynomial time queries such as solution counting, solution enumeration or equivalence of constraint networks. We provide a compilation algorithm based on Variable Elimination for assembling an AOMDD for a constraint network starting from the AOMDDs for its constraints. the algorithm uses the APPLY operator which combines two AOMDDs by a given operation. this guarantees the complexity upper bound for the compilation time and the size of the AOMDD to be exponential in the treewidth of the constraint graph, rather than pathwidth as is known for ordered binary decision diagrams (OBDDs).
In a constraint optimization problem (COP), many feasible assignment's have the same objective value. this usually means huge search space and poor propagation among the objective variables (which appear in the ob...
详细信息
ISBN:
(纸本)9783540859574
In a constraint optimization problem (COP), many feasible assignment's have the same objective value. this usually means huge search space and poor propagation among the objective variables (which appear in the objective function) and the problem variables (which do not). In this paper, we investigate a. search strategy that focuses oil the objective function, namely, the objective variables are assigned before the problem variables Despite the larger search space;we may indeed solve a COP faster, provided that the constraint propagation is strong - the search can reach the optimal objective value faster in the objective space, and by strong propagation it knows if the constraints are unsatisfiable with little search ill tile problem space. To obtain strong propagation we study the use of dual encoding [1] for COP's. Our COP formulation and search strategy are general and can handle any dual COPS.
Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. this paper considers invariants ...
详细信息
Modeling and programming tools for neighborhood search often support invariants, i.e., data structures specified declaratively and automatically maintained incrementally under changes. this paper considers invariants for longest paths in directed acyclic graphs, a fundamental abstraction for many applications. It presents bounded incremental algorithms for arc insertion and deletion which run in O ( ||delta|| + |delta| log |delta|) time and O ( ||delta||) time respectively, where |delta| and ||delta|| are measures of the change in the input and output. the paper also shows how to generalize the algorithm to various classes of multiple insertions/ deletions encountered in scheduling applications. Preliminary experimental results show that the algorithms behave well in practice.
the multi-way dataflow constraint model allows a user to describe interactive applications whose consistency is maintained by a local propagation algorithm. Local propagation applies a sequence of methods that solve t...
详细信息
ISBN:
(纸本)3540652248
the multi-way dataflow constraint model allows a user to describe interactive applications whose consistency is maintained by a local propagation algorithm. Local propagation applies a sequence of methods that solve the constraints individually. the local aspect of this solving process makes this model sensitive to cycles in the constraint graph. We use a formalism which overcomes this major limitation by allowing the definition of general methods that can solve several constraints simultaneously. this paper presents an algorithm called General-PDOF to deal withthese methods which has a polynomial worst case time complexity. this algorithm therefore has the potential to tackle numerous real-life applications where cycles make local propagation unfeasible. Especially: general methods can implement "ruler and compass " rules to solve geometric constraints.
In this paper we describe the design and implementation of CP-VIZ, a generic visualization platform for constraintprogramming. It provides multiple views to show the search tree, and the state of constraints and vari...
详细信息
ISBN:
(纸本)9783642153952
In this paper we describe the design and implementation of CP-VIZ, a generic visualization platform for constraintprogramming. It provides multiple views to show the search tree, and the state of constraints and variables for a postmortem analysis of a constraint program. Different to most previous visualization tools, it is system independent, using a light-weight, intermediate XML format to exchange information between solvers and the visualization tools. CP-VIZ is available under an open-source licence, and has already been interfaced to four different constraint systems.
constraintprogramming has become an important technology for solving hard combinatorial problems in a diverse range of application domains. It has its roots in artificial intelligence, mathematical programming, opera...
详细信息
暂无评论