21–30 of 63 posts
Picat Language which is designed to be more main stream than Prolog supports CP out of the box , also has a planning module
MiniZinc is a fairly simple-to-understand and open source constraint language: https://www.minizinc.org I learned about it when a friend gave me a programming challenge: https://gcanyon.wordpress.com/2009/10/28/a-programming-puzzl... She was going to work in PHP, I wrote a solution in J, and a commenter solved it in MiniZinc. Here is their solution in MiniZinc: http://www.hakank.org/minizinc/einav_puzzle.mzn
MiniZinc is a fairly simple-to-understand and open source constraint language: https://www.minizinc.org I learned about it when a friend gave me a programming challenge: https://gcanyon.wordpress.com/2009/10/28/a-programming-puzzl... She was going to work in PHP, I wrote a solution in J, and a commenter solved it in MiniZinc. Here is their solution in MiniZinc: http://www.hakank.org/minizinc/einav_puzzle.mzn
as a note, I've tried MiniZinc for modeling a problem in the past, and the language/ecosystem simply wasn't up to my task. iirc, function calls in MiniZinc are expanded/unrolled when the model is generated, rather than the function definition and its callers being symbolically translated into the model. this is no fault of MiniZinc, I simply thought that an SMT solver would be sufficient and it wasn't. I need a mixed…
These techniques are usable in every language, and not just in special ones like Prolog. For example https://norvig.com/sudoku.html uses constraint propagation to solve sudoku puzzles in Python.
In the sense that Turing-complete languages are all equivalent, yes. But in most imperative and functional languages, you'll end up implementing your own solver (as Norvig did), and a DSL to model your problem. Why reinvent the wheel?
For example, to optimize the grid, you might have a Python app that imports the GUROBI solver module and tells GUROBI to optimize. The advantage is all the file IO, directory, and database stuff gets to be handled with Python (easy easy).
Earlier quoted context omitted.
In Prolog, the predicate order matters. So, if I understand your question correctly, no. It's up to the dev to order predicates in such a way that the amount of backtracking is kept to minimal.
Well, most Prolog support clp(fd) (Constraint Logic Programming, Finite Domain) which mostly include support for minimizing/maximizing objectives.
Any recommendations on a "this but for dribbling primates" introduction?
I feel like this is something I may understand the solution to but the problem it solves leaves me dumbfounded. Any recommendations on a "this but for dribbling primates" introduction?
These techniques are usable in every language, and not just in special ones like Prolog. For example https://norvig.com/sudoku.html uses constraint propagation to solve sudoku puzzles in Python.
In the sense that Turing-complete languages are all equivalent, yes. But in most imperative and functional languages, you'll end up implementing your own solver (as Norvig did), and a DSL to model your problem. Why reinvent the wheel?
I feel like this is something I may understand the solution to but the problem it solves leaves me dumbfounded. Any recommendations on a "this but for dribbling primates" introduction?
IE: Knapsack problem, Traveling Salesman, etc. etc.
Today, it seems more popular to use "3-SAT Solvers". But constraint programming is "more logical" for some problems to get converted into rather than 3-SAT. Consider 3-SAT and Constraint Programming to be two different "assembly languages" that you can compile your problem into, and then have a generic solver into.
-----------
For example: Sudoku can be "compiled" into the 3SAT problem: https://www.mit.edu/~6.005/sp12/psets/ps2/ps2.html
But it also can be "compiled" into the Constraint-problem, which then gets solved by a constraint solver. https://sonalake.com/latest/constraint-programming-solving-s...
------------
Personally speaking, I think that the constraint solver problem is "easier to compile into" rather than the 3SAT problem, especially when you consider generic constraints that have very efficient solutions.
For example, it is difficult to think of the optimal alldifferent constraint within 3SAT, but in a constraint-solver framework, its just... well... alldifferent. So you can describe Sudoku as the following:
Domain = {1 2 3 4 5 6 7 8 9}
Alldifferent(X11, X12, X13, X14, X15, X16, X17, X18, X19)
Alldifferent(X21, X22, X23, X24, X25, X26, X27, X28, X29)
Alldifferent(X31, X32, X33, X34, X35, X36, X37, X38, X39)
...
Alldifferent(X91, X92, X93, X94, X95, X96, X97, X98, X99)
------------------------------------------------------------------------
Alldifferent(X11, X21, X31, X41, X51, X61, X71, X81, X91)
Alldifferent(X12, X22, X32, X42, X52, X62, X72, X82, X92)
Alldifferent(X13, X23, X33, X43, X53, X63, X73, X83, X93)
...
Alldifferent(X19, X29, X39, X49, X59, X69, X79, X89, X99)
------------------------------------------------------------------------
Alldifferent(X11, X12, X13, X21, X22, X23, X31, X32, X33)
...
Alldifferent(X77, X78, X79, X87, X88, X89, X97, X98, X99)
----------
IIRC, the Alldifferent constraint can be efficiently solved using maximum flow. So you write a specialized solver for alldifferent using maximum flow (faster than 3SAT / NP Completeness), and this maximum-flow local solution can be "plugged into" the rest of the constraint solver problem, and integrates cleanly with the rest of the solver's NP-completeness search.
I feel like this is something I may understand the solution to but the problem it solves leaves me dumbfounded. Any recommendations on a "this but for dribbling primates" introduction?
I think this can be applied to much the same domains as simplex or similar algorithms. So optimization problems/OR. See https://en.wikipedia.org/wiki/Operations_research
Simplex is provably within the polynomial bounds of complexity, ie: simplex is a so called "easy" problem in complexity theory.
--------
You're right that simplex is applied to optimization problems. Constraint programming could be seen as a "more generic" optimizer, in that it can handle integer-optimization (simplex cannot handle integer optimization at all).
Of course, integer-optimization is NP complete, which means that constraint programming is innately "inefficient" or "hard" in terms of complexity.