5 ms·

What libraries / solvers did you find useful for scheduling?

sriku 4y ago
Many constraint toolkits in other languages wrap around https://www.gecode.org/ 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 to develop your own constraint search strategies, Mozart/Oz 's "space" concept is elegant.
- Guthur 4y ago
  I've used the CLPFD library, really quite cool. It fits very naturally into a prolog program.
- tannhaeuser 4y ago
  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/ https://quantumprolog.sgml.io/
bobby__joe 4y ago
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 https://www.coursera.org/learn/basic-modeling
- gcanyon 4y ago
  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-puzzle-from-einav/ https://gcanyon.wordpress.com/2009/10/28/a-programming-puzzl... And the solution in Minizinc: http://www.hakank.org/minizinc/einav_puzzle.mzn http://www.hakank.org/minizinc/einav_puzzle.mzn And my solution in J: https://gcanyon.wordpress.com/2009/10/30/a-solution-to-einavs-programming-puzzle/ https://gcanyon.wordpress.com/2009/10/30/a-solution-to-einav...
  - hakank 4y ago
    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 http://www.hakank.org/common_cp_models/#einavpuzzle
    - gcanyon 4y ago
      Hakan, good to see you! I love how we run into each other whenever constraint programming comes up on HN :-)
nickpeterson 4y ago
You could also try Google OR tools, ‘OR’ means operations research.
placebo 4y ago
There are quite a few out there. I played with gecode as well as https://choco-solver.org/ https://choco-solver.org/ which I found intuitive and fun to use.
bendbro 4y ago
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.
pjot 4y ago
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

Many constraint toolkits in other languages wrap around https://www.gecode.org/ 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 to develop your own constraint search strategies, Mozart/Oz 's "space" concept is elegant.

Guthur 4y ago
I've used the CLPFD library, really quite cool. It fits very naturally into a prolog program.
tannhaeuser 4y ago
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/ https://quantumprolog.sgml.io/

bobby__joe 4y ago

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 https://www.coursera.org/learn/basic-modeling

gcanyon 4y ago
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-puzzle-from-einav/ https://gcanyon.wordpress.com/2009/10/28/a-programming-puzzl... And the solution in Minizinc: http://www.hakank.org/minizinc/einav_puzzle.mzn http://www.hakank.org/minizinc/einav_puzzle.mzn And my solution in J: https://gcanyon.wordpress.com/2009/10/30/a-solution-to-einavs-programming-puzzle/ https://gcanyon.wordpress.com/2009/10/30/a-solution-to-einav...
- hakank 4y ago
  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 http://www.hakank.org/common_cp_models/#einavpuzzle
  - gcanyon 4y ago
    Hakan, good to see you! I love how we run into each other whenever constraint programming comes up on HN :-)

nickpeterson 4y ago

You could also try Google OR tools, ‘OR’ means operations research.

placebo 4y ago

There are quite a few out there. I played with gecode as well as https://choco-solver.org/ https://choco-solver.org/ which I found intuitive and fun to use.

bendbro 4y ago

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.

pjot 4y ago

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