2006 · 54 citations · 8 references
ComputingComputer ScienceAlgorithmsMachine LearningTheory Of ComputationAutomated ReasoningConstraint SatisfactionConstraint SolvingAutomated Theorem ProvingAutomated Theorem Proving In AlgebraConstraint GenerationConstraint Satisfaction ModelingCsp ModellingCsp SolvingFinite Boolean Algebras
A well-known difficulty with solving Constraint Satisfaction Problems (CSPs) is that, while one formulation of a CSP may enable a solver to solve it quickly, a different formulation may take prohibitively long to solve. We demonstrate a system for automatically reformulating CSP solver models by combining the capabilities of machine learning and automated theorem proving with CSP systems. Our system is given a basic CSP formulation and outputs a set of reformulations, each of which includes additional constraints. The additional constraints are generated through a machine learning process and are proven to follow from the basic formulation by a theorem prover. Experimenting with benchmark problem classes from finite algebras, we show how the time invested in reformulation is often recovered many times over when searching for solutions to more difficult problems from the problem class.
8
Rippling: A heuristic for guiding inductive proofs
Alan Bundy, Andrew Stevens, Frank van Harmelen et al. · Artificial Intelligence · 1993 · 226 citations · Full text
Practical applications of constraint programming
Mark Wallace · Constraints · 1996 · 215 citations
Resolution versus Search: Two Strategies for SAT
Irina Rish, Rina Dechter · Journal of Automated Reasoning · 2000 · 110 citations
Adding new clauses for faster local search
Byungki Cha, Kazuo Iwama · 1996 · 54 citations