Constraint Programming
en.wikipedia.org
Constraint Programming
1–10 of 63 posts
Re: Constraint Programming
#2These 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.
Re: Constraint Programming
#3MiniZinc 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
Re: Constraint Programming
#4There's a good course on Coursera on using MiniZinc to express constraints for solvers: https://www.coursera.org/learn/basic-modeling
Re: Constraint Programming
#5MiniZinc 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
Hi again Geoff.
Here are some other constraint modelling implementations of this problem: http://hakank.org/common_cp_models/#einavpuzzle .
Re: Constraint Programming
#6These 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?
Re: Constraint Programming
#7MiniZinc 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-integer or non-linear program solver, and ended up approaching it with a computer algebra system to generate my models and passing it to Gurobi or HiGHS.
tl;dr there's different types of hard, and SMT solvers are only good at some types of hard.
Re: Constraint Programming
#8MiniZinc 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…
One interesting development in the latter years is the mix of Constraint programming and SAT solvers. For example Google OR-tools (https://developers.google.com/optimization/ ) which mixes CP, SAT and MIP. It has won most of the MiniZinc Challenge categories (https://www.minizinc.org/challenge.html ) several years now. The Chuffed solver is another solver mixing CP and SAT.
Re: Constraint Programming
#9Does Prolog naturally support optimizing for an objective function?
Re: Constraint Programming
#10Earlier quoted context omitted.
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…
One interesting development in the latter years is the mix of Constraint programming and SAT solvers. For example Google OR-tools ( https://developers.google.com/optimization/ ) which mixes CP, SAT and MIP. It has won most of the MiniZinc Challenge categories ( https://www.minizinc.org/challenge.html ) several years now. The Chuffed solver is another solver mixing CP and SAT.
isn't or-tools just a wrapper library for a bunch of solvers? I must be missing something.