CODEWITHSUNDEEP
algorithmsearchcomplexity-theoryconstraint-programming
Nyamiou The Galeanthrope
Nyamiou The Galeanthrope

Reputation: 1224

Constraint Satisfaction Problems with solvers VS Systematic Search

We have to solve a difficult problem where we need to check a lot of complex rules from multiple sources against a system in order to decide if the system satisfy those rules or how it should be changed to satisfy them.

We initially started using Constraint Satisfaction Problems algorithms (using Choco) to try to solve it but since the number of rules and variables would be smaller than anticipated, we are looking to build a list of all possibles configurations on a database and using multiple requests based on the rules to filter this list and find the solutions this way.

Is there limitations or disadvantages of doing a systematic search compared to using a CSP solver algorithms for a reasonable number of rules and variables? Will it impact performances significantly? Will it reduce the kind of constraints we can implement?

As examples :

You have to imagine it with a much bigger number of variables, much bigger domains of definition (but always discrete) and bigger number of rules (and some much more complex) but instead of describing the problem as :

x in (1,6,9)
y in (2,7)
z in (1,6)
y = x + 1
z = x if x < 5 OR z = y if x > 5

And giving it to a solver we would build a table :

X | Y | Z
1   2   1
6   2   1
9   2   1
1   7   1
6   7   1
9   7   1
1   2   6
6   2   6
9   2   6
1   7   6
6   7   6
9   7   6

And use queries like (this is just an example to help understand, actually we would use SPARQL against a semantic database) :

SELECT X, Y, Z WHERE Y = X + 1 
INTERSECT 
SELECT X, Y, Z WHERE (Z = X AND X < 5) OR (Z = Y AND X > 5)

Upvotes: 8

Views: 495

Answers (1)

AnoE
AnoE

Reputation: 8355

CSP allows you to combine deterministic generation of values (through the rules) with heuristic search. The beauty happens when you customize both of those for your problem. The rules are just one part. Equally important is the choice of the search algorithm/generator. You can cull a lot of the search space.

While I cannot make predictions about the performance of your SQL solution, I must say that it strikes me as somewhat roundabout. One specific problem will happen if your rules change - you may find that you have to start over from scratch. Also, the RDBMS will fully generate all of the subqueries, which may explode.

I'd suggest to implement a working prototype with CSP, and one with SQL, for a simple subset of your requirements. You then will get a good feeling what works and what does not. Be sure to think about long term maintenance as well.

Full disclaimer: my last contact with CSP was decades ago in university as part of my master's (I implemented a CSP search engine not unlike choco, of course a bit more rudimentary, and researched a bit on that topic). But the field will certainly have evolved since then.

Upvotes: 5

Related Questions