Indeed anything with constraints is usually a great use case for Prolog. I particularly like this version in ECLiPSe which is specialized on constraint programming with Prolog:
https://gist.github.com/JuanitoFatas/2227711
I haven't benchmarked it but it is pretty intuitive to read which is very important for these types of problems.
The article mentions the problem of "local minimums". The author suggests occasionally accepting worse solutions, in order to escape from such. "The hope here is that by following this worse solution, we can eventually get to the global minimum." This is good but one may wish to take it further.
I once messed with something called "metropolis coupling", where you run multiple threads in parallel, with different thresholds for how often they accept worse solutions, i.e. one thread is "cold", one is slightly "hotter", and so on. If a hot thread's current solution is better than the solution of the neighbouring colder thread, the solutions are swapped. In this way the coldest thread (which is the one we're paying attention to) gets pulled out of the local minimum.
As I say, I messed with this once and it did seem to help. It seems to have been developed for inference in evolutionary phylogenetics, and is perhaps a bit obscure?
This has the advantage of working as a sampling strategy, not just an optimization strategy. It is useful when the mass of your distribution is concentrated in a region that may be hard to find with a random walk.
That's actually pretty brilliant. I haven't ever heard of metropolis coupling before, but I can see how it would break the algo out of a local minimum.
Also, klaatu barada nikto.
Nice. I've used Simulated Annealing to achieve good results in problems were the solution space was too large for constraint programming, but for this specific sort of problems I've had good experience using constraint programming frameworks like GECODE or choco
A lot of people here mention Prolog as another tool to solve this problem. I wonder if there's a natural way to combine constraint solving with simulated annealing.
If you like this sort of thing, I wrote some code a couple of years ago to generate and solve logical deduction problems, such as the "Cheryl's Birthday" brainteaser:
The code isn't very clean (it was written hastily as part of a hack days project at work) but the notebook walks you through it, so even if you're not familiar with Python, you'll get a sense of the technique.
I've used simulated annealing to make constraint solvers more efficient. The nice thing about constraint solvers and simulated annealing as demonstrated is that it's fairly straight forward to adapt the algorithm to your specific problem and data in order to get the best performance.
Simulated annealing and similar techniques such as Tabu Search are good for problems that have large search spaces due to combinatorial explosion (https://en.wikipedia.org/wiki/Combinatorial_explosion) and can be expressed as a state and an associated cost/fitness function.
Constraint Satisfaction Problems can be modeled as Hopfield-type neural networks, such as Boltzmann machines (RBMs of deep learning are a variant) which can be tuned using simulated annealing.
There was plenty of research on this around 1985-1995 (the "second coming" of neural networks), but it died out with the hype because it was never an actually practical way to solve CSPs. Given the recent innovations in deep learning, it should eventually pick up again, to enable deep learners to solve constraint satisfaction subproblems within the same integrated architecture.
Really interesting, I wrote a logic puzzle solver in Prolog a long time ago while I was in uni, I just created a repo for anyone who wants to check it out. Unfortunately the documentation and comments are all in Spanish...
Tweaking 't' here seems to be similar to tweaking the learning rate in gradient descent. But in gradient descent you assume the problem is convex.
Is there any way to tell whether this logic problem (or any other) is convex? Is it possible that the correct solution's 5-away neighbours all have very high costs (like 9+)? What prevents you from doing worse that brute force?
What if we change the cost function to something that returns a number which has a direct correlation with the maximum number of attributes that matched? Would solving the problem be any easier or we would still leave the possibility of getting stuck in local optimums just like the one described in the post?
I think in theory it is possible by unary encoding attributes of the five houses then defining the appropriate weights according to the constraints.
In practice it might not be possible to map the resulting graph on the D-Wave's architecture, I can't find any good documentation on the D-Wave though.
[+] [-] osense|9 years ago|reply
[+] [-] kriro|9 years ago|reply
I haven't benchmarked it but it is pretty intuitive to read which is very important for these types of problems.
[+] [-] gort|9 years ago|reply
I once messed with something called "metropolis coupling", where you run multiple threads in parallel, with different thresholds for how often they accept worse solutions, i.e. one thread is "cold", one is slightly "hotter", and so on. If a hot thread's current solution is better than the solution of the neighbouring colder thread, the solutions are swapped. In this way the coldest thread (which is the one we're paying attention to) gets pulled out of the local minimum.
As I say, I messed with this once and it did seem to help. It seems to have been developed for inference in evolutionary phylogenetics, and is perhaps a bit obscure?
[+] [-] ChronosKey|9 years ago|reply
Yep, this is the sort of thing we study in our cooperative and adaptive algorithms class. Similar techniques to what you suggest are shown here https://books.google.ca/books?id=G5ML5EYch94C&pg=PA88&lpg=PA...
[+] [-] murbard2|9 years ago|reply
https://en.wikipedia.org/wiki/Parallel_tempering
Markov-chain Monte-Carlo sampling gives a theoretical underpinning which explains why simulated annealing works in optimization.
[+] [-] tekromancr|9 years ago|reply
[+] [-] placebo|9 years ago|reply
[+] [-] doomrobo|9 years ago|reply
[+] [-] rsingla|9 years ago|reply
[+] [-] jawns|9 years ago|reply
https://github.com/shaungallagher/cheryls-murder/blob/master...
The code isn't very clean (it was written hastily as part of a hack days project at work) but the notebook walks you through it, so even if you're not familiar with Python, you'll get a sense of the technique.
[+] [-] baldeagle|9 years ago|reply
[+] [-] agentultra|9 years ago|reply
[+] [-] tunesmith|9 years ago|reply
[+] [-] ChronosKey|9 years ago|reply
[+] [-] waynecochran|9 years ago|reply
https://ezekiel.encs.vancouver.wsu.edu/~cs330/archive/archiv...
[+] [-] machinelearning|9 years ago|reply
[+] [-] kej|9 years ago|reply
[+] [-] makeset|9 years ago|reply
There was plenty of research on this around 1985-1995 (the "second coming" of neural networks), but it died out with the hype because it was never an actually practical way to solve CSPs. Given the recent innovations in deep learning, it should eventually pick up again, to enable deep learners to solve constraint satisfaction subproblems within the same integrated architecture.
[+] [-] cordite|9 years ago|reply
There's relational properties, combinations, and maybes all over
[+] [-] Anilm3|9 years ago|reply
https://github.com/Anilm3/Logic-Puzzle-Solver
[+] [-] anthk|9 years ago|reply
Gracias de todo modos ;)
[+] [-] rahimnathwani|9 years ago|reply
Is there any way to tell whether this logic problem (or any other) is convex? Is it possible that the correct solution's 5-away neighbours all have very high costs (like 9+)? What prevents you from doing worse that brute force?
[+] [-] jasdeepsingh|9 years ago|reply
[+] [-] rahimnathwani|9 years ago|reply
[+] [-] unknown|9 years ago|reply
[deleted]
[+] [-] jnwrd|9 years ago|reply
[+] [-] leni536|9 years ago|reply
In practice it might not be possible to map the resulting graph on the D-Wave's architecture, I can't find any good documentation on the D-Wave though.