Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Constraint Programming (2020)

mareknarozniak.com

Post reply on HN
Print view View original

11–20 of 29 posts

Re: Constraint Programming (2020)

#11

Post by ben-schaaf »

default-kramer wrote: post #8

I'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)

Re: Constraint Programming (2020)

#12

Post by bendbro »

brutusborn wrote: post #3
binkHN wrote: post #2

I took a similar approach with a somewhat complicated scheduling requirement across dates and times. I originally brute forced the problem, but the solution was a bit inelegant and not ideal. When I used constraint programming to solve the same problem, it took me a little longer to devise the solution, but the result was superior. Also, the constraint programming solution is a little more memory intensive, but a nec…

What libraries / solvers did you find useful for scheduling?

I've used Google's ORTools and Microsoft Z3. If you need to input a lot of variables, I found Z3 to be better since it took SMTLIB formatted text as one big chunk- rather than numerous API calls which each suffer native binding overhead. Z3 can also iteratively solve, where you can append additional constraints and rerun the solver from its current position- I don't think ORTools had this feature.

Re: Constraint Programming (2020)

#13

Post by Guthur »

sriku wrote: post #4
brutusborn wrote: post #3

Earlier quoted context omitted.

What libraries / solvers did you find useful for scheduling?

Many constraint toolkits in other languages wrap around https://www.gecode.org/ . A rathe well established and performant library. I think the same folks behind Mozart/Oz are key behind this if I'm not mistaken. For a free one, SWIProlog has a very usable and fairly performant constraint library too (CLPFD and CLPQ). It also has the more general "constraint handling rules" (CHR) as an embedded language. If you need t…

I've used the CLPFD library, really quite cool. It fits very naturally into a prolog program.

Re: Constraint Programming (2020)

#14

Post by canadianfella »

binkHN wrote: post #2

I took a similar approach with a somewhat complicated scheduling requirement across dates and times. I originally brute forced the problem, but the solution was a bit inelegant and not ideal. When I used constraint programming to solve the same problem, it took me a little longer to devise the solution, but the result was superior. Also, the constraint programming solution is a little more memory intensive, but a nec…

[dead]

Re: Constraint Programming (2020)

#15

Post by pjot »

brutusborn wrote: post #3
binkHN wrote: post #2

I took a similar approach with a somewhat complicated scheduling requirement across dates and times. I originally brute forced the problem, but the solution was a bit inelegant and not ideal. When I used constraint programming to solve the same problem, it took me a little longer to devise the solution, but the result was superior. Also, the constraint programming solution is a little more memory intensive, but a nec…

What libraries / solvers did you find useful for scheduling?

In grad school we used a language called GAMS to model and solve linear, MIP, and other types of constraint type problems. It was really powerful, but equally a pain to write.

Like others have already suggested, look into google’s ORtools library

Re: Constraint Programming (2020)

#16

Post by habitue »

Recently 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?

Re: Constraint Programming (2020)

#17

Post by gcanyon »

bobby__joe wrote: post #5
brutusborn wrote: post #3

Earlier quoted context omitted.

What libraries / solvers did you find useful for scheduling?

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-solution-to-einav...

Re: Constraint Programming (2020)

#18

Post by niemandhier »

habitue wrote: post #16

Recently 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?

CP is different in that it is less a sigle method than a framework for individual CS insights into enforcing constraints. This is usually down by a global constraint store and a watchlist of variable for the problem under consideration.

A good example is the famous “ All different” constraint. In MIP you would implement that as a fancy summ, in CP one can use a corollary from Berge’s lemma to get a specialised constraint to just enforce that.

Rule of Thump is that CP excels when the problem is thigh lay constraint and one has many global constraints ( those that apply to all variables).

Another point is that contrary to MIP programs that often are modelled directly using sums and inequalities, CP Programms usually are written in a declarative language such as ZINC, which in my opinion makes it easier to get into the subject.

If you are interested: This series of blog posts builds a CP solver in Julia

https://opensourc.es/blog/constraint-solver-1/

ortoools by Google also contains a CP solver and the doc is quite interesting

https://developers.google.com/optimization/cp

Finally there is the dissertation of Guido Tack, who developed a oss Cp solver as his PhD project ( I think that is the internal solver used by SAP software now)

https://www.gecode.org/papers/Tack_PhD_2009.pdf

Re: Constraint Programming (2020)

#19

Post by niemandhier »

niemandhier wrote: post #18
habitue wrote: post #16

Recently 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?

CP is different in that it is less a sigle method than a framework for individual CS insights into enforcing constraints. This is usually down by a global constraint store and a watchlist of variable for the problem under consideration. A good example is the famous “ All different” constraint. In MIP you would implement that as a fancy summ, in CP one can use a corollary from Berge’s lemma to get a specialised constr…

I think the wonderful people of the association for constraint programming deserv a mention here, for those interested check out the cap summer schools 2023

https://school.a4cp.org/summer2023/

Re: Constraint Programming (2020)

#20

Post by tannhaeuser »

sriku wrote: post #4
brutusborn wrote: post #3

Earlier quoted context omitted.

What libraries / solvers did you find useful for scheduling?

Many constraint toolkits in other languages wrap around https://www.gecode.org/ . A rathe well established and performant library. I think the same folks behind Mozart/Oz are key behind this if I'm not mistaken. For a free one, SWIProlog has a very usable and fairly performant constraint library too (CLPFD and CLPQ). It also has the more general "constraint handling rules" (CHR) as an embedded language. If you need t…

Yes, Constraint Logic Programming evolved from Prolog, as the name implies, and because Prolog's indeterminism and backtracking is as natural as it gets for this kind of problems. While the article mentions the foundational Jaffar et al paper, there have been numerous constraint solvers embedded into Prolog ever since, known by names such as CLP(x) where x is a parameter for the domain (reals or finite domains, or Booleans as in SAT solvers), though this nomenclature suggests portability and a common approach that isn't there. An introductory article for robotic planning and scheduling based purely on Prolog and hence not requiring a magic CLP solver library and at the same time beyond constraint solvers in its ability to generate load plans in container ship logistics with an unbounded number of steps is described on the Quantum Prolog site [1]. The demo works in the browser even.

[1]: https://quantumprolog.sgml.io/

Post reply on HN