Raftul cu initiativa Book Archive

Machine Theory

Bridging Constraint Satisfaction and Boolean Satisfiability by Justyna Petke

By Justyna Petke

This publication offers an important step in the direction of bridging the components of Boolean satisfiability and constraint delight via answering the query why SAT-solvers are effective on definite periods of CSP circumstances that are tough to resolve for normal constraint solvers. the writer additionally offers theoretical purposes for selecting a selected SAT encoding for a number of very important periods of CSP instances.

Boolean satisfiability and constraint pride emerged independently as new fields of computing device technological know-how, and various fixing options became average for challenge fixing within the components. although any propositional formulation (SAT) may be seen to illustrate of the overall constraint pride challenge (CSP), the results of this connection have purely been studied within the previous couple of years.

The booklet may be important for researchers and graduate scholars in man made intelligence and theoretical laptop technology.

Show description

Read Online or Download Bridging Constraint Satisfaction and Boolean Satisfiability PDF

Best machine theory books

Digital and Discrete Geometry: Theory and Algorithms

This booklet offers finished insurance of the fashionable tools for geometric difficulties within the computing sciences. It additionally covers concurrent issues in info sciences together with geometric processing, manifold studying, Google seek, cloud information, and R-tree for instant networks and BigData. the writer investigates electronic geometry and its similar optimistic equipment in discrete geometry, delivering specific tools and algorithms.

Artificial Intelligence and Symbolic Computation: 12th International Conference, AISC 2014, Seville, Spain, December 11-13, 2014. Proceedings

This e-book constitutes the refereed lawsuits of the twelfth foreign convention on synthetic Intelligence and Symbolic Computation, AISC 2014, held in Seville, Spain, in December 2014. The 15 complete papers offered including 2 invited papers have been rigorously reviewed and chosen from 22 submissions.

Statistical Language and Speech Processing: Third International Conference, SLSP 2015, Budapest, Hungary, November 24-26, 2015, Proceedings

This ebook constitutes the refereed court cases of the 3rd foreign convention on Statistical Language and Speech Processing, SLSP 2015, held in Budapest, Hungary, in November 2015. The 26 complete papers provided including invited talks have been conscientiously reviewed and chosen from seventy one submissions.

Extra info for Bridging Constraint Satisfaction and Boolean Satisfiability

Example text

This ensured that the system of inequalities had at least one solution. 5. On this simple set of instances all solvers performed very well, although Minion was noticeably slightly slower. It is worth mentioning that most of these instances were essentially solved at the translation stage. 9), or some trivially unsatisfiable constraints in the unsatisfiable cases. Again pure solving time of FznTini was sightly better than the runtimes shown, since these include the translation time from FlatZinc to SAT.

6). 1 because they can be solved by the trivial algorithm that assigns the value d to every variable in the instance. Such classes were included (for completeness) in several early lists of tractable classes, including Schaefer’s Dichotomy Theorem for the Boolean satisfiability problem [Sch78] and the first survey of tractable cases identified by the algebraic approach to constraint complexity [JCG97]. Surprisingly, instances with this property do occur in practice: the majority of the satisfiable binary decision diagram instances used in the third CSP-solver competition [vDLR08] have constant solutions2 .

This approach can also help to drive improvements in the robustness and flexibility of constraint-solving software. 7, and these have been used to compare the performance of various solvers, and to develop and test an alternative solver, FznTini [Hua08], based on translation to Boolean satisfiability. How can suitable benchmark instances be obtained? One obvious source of benchmark instances is from practical applications such as scheduling and manufacturing process organisation; the G12 MiniZinc suite includes several examples of this kind, such as “nurse scheduling” problems and “car sequencing” problems.

Download PDF sample

Rated 4.05 of 5 – based on 27 votes