I love constraint programming. It allows you to code very close to the original spec. There are differences between systems though. Z3 might have a good raw performance, but using it feels like programming in "two worlds". In contrast, Picat or Prolog integrate seamlessly with constraints. I did a talk about constraint programming with Scryer Prolog here (Spanish audio): https://www.youtube.com/watch?v=c_yP_kr7DxI
Constraint Programming (2020)
21–29 of 29 posts
Re: Constraint Programming (2020)
#22Recently I've been playing around with MILP solvers and this sounds similar. Can anyone with some experience in these kinds of optimization problems give a summary of the similarities and differences between CP and MILP?
In milps you can have an objective function to minimize/maximize and continuous variables. The techniques used are based on the characteristics of the mathematical space of the possible solution and methods to reduce the size of space that you have to look into.
The solution of milp solver are provably optimal.
CP allows for constrains that are difficult to model and/or solve in milps (or even mip).
There is some overlap between the two. For example, presolving in milp is basically a generalization of constraint programming.
Re: Constraint Programming (2020)
#23Obvious in hindsight but I hadn’t thought of using a non-optimizing solver for an optimization problem.
-
I think constraint programming may get more popular because of LLMs. One of the big issues with them is translating your problem into constraints. It’s tough for people to do that. But an LLM can do that well, even just to make sure its own solution is logical.
Re: Constraint Programming (2020)
#24I'm guessing the library python-constraint is basically just brute-forcing all possible combinations, at least when a regular python function is used as a constraint? Barring some crazy introspection, it would have to, right? And if I'm right, I don't understand why you would use a library rather than just loop over x, y, and z the old-fashioned way.
Aside from the solver being a little smarter. Just syntactically, it might be fine with x,y,z but brute force looping over a,b,c,d...w,x,y,z is gonna take a really really wide monitor.
Re: Constraint Programming (2020)
#25I recall learning Prolog for a CS class back in the late 80s to model problems using its backtracking (chaining) algorithm with facts. Sometime later Rete-based rules languages became popular, but I always thought Prolog’s language approach was more suitable.
Re: Constraint Programming (2020)
#26Earlier quoted context omitted.
I strongly recommend Minizinc. The coursera course related to it is also an excellent introduction to constraint programming: https://www.coursera.org/learn/basic-modeling
I posted a programming puzzle years back, and someone named Hakan Kjellerstrand pointed out that the problem leant itself to constraint programming and posted a solution in Minizinc. Here's the puzzle page: https://gcanyon.wordpress.com/2009/10/28/a-programming-puzzl... And the solution in Minizinc: http://www.hakank.org/minizinc/einav_puzzle.mzn And my solution in J: https://gcanyon.wordpress.com/2009/10/30/a-soluti…
Here are some implementations in different constraint languages on this puzzle (which I call the "Einav puzzle"): http://www.hakank.org/common_cp_models/#einavpuzzle
Re: Constraint Programming (2020)
#27Earlier quoted context omitted.
I posted a programming puzzle years back, and someone named Hakan Kjellerstrand pointed out that the problem leant itself to constraint programming and posted a solution in Minizinc. Here's the puzzle page: https://gcanyon.wordpress.com/2009/10/28/a-programming-puzzl... And the solution in Minizinc: http://www.hakank.org/minizinc/einav_puzzle.mzn And my solution in J: https://gcanyon.wordpress.com/2009/10/30/a-soluti…
Here are some implementations in different constraint languages on this puzzle (which I call the "Einav puzzle"): http://www.hakank.org/common_cp_models/#einavpuzzle
Hakan, good to see you! I love how we run into each other whenever constraint programming comes up on HN :-)
Re: Constraint Programming (2020)
#28Recently I've been playing around with MILP solvers and this sounds similar. Can anyone with some experience in these kinds of optimization problems give a summary of the similarities and differences between CP and MILP?
In milps you can have an objective function to minimize/maximize and continuous variables. The techniques used are based on the characteristics of the mathematical space of the possible solution and methods to reduce the size of space that you have to look into. The solution of milp solver are provably optimal. CP allows for constrains that are difficult to model and/or solve in milps (or even mip). There is some ove…
Thanks, that's helpful
Re: Constraint Programming (2020)
#29I'm guessing the library python-constraint is basically just brute-forcing all possible combinations, at least when a regular python function is used as a constraint? Barring some crazy introspection, it would have to, right? And if I'm right, I don't understand why you would use a library rather than just loop over x, y, and z the old-fashioned way.
From the docs it's using proper backtracking solvers. It doesn't need introspection to do this, just a python object that "records" its operations, eg: def __mul__(self, other): return Multiplication(self, other)
Cool trick! I don't know enough Python to have thought of this myself.