4 ms·

Sounds like a job for Prolog. Maybe Prolog to make a list of schedules, and something else to sort that list?

by idoh 10y ago

ufo 10y ago
I think SAT-solvers and other constraint solvers might be a better fit. They can use clever algorithmic search technique like clause learning, non-chronological backtracking and so on to achieve big speedups compared to naive backtracking, which is what Prolog would do in this case. And we also don't need the full turing-completeness that Prolog provides.
- zmonx 10y ago
  I agree completely that SAT solvers and constraint solvers are a great choice for this. However, SAT solvers and constraint solvers blend in naturally and in fact even ship with many Prolog implementations! Thus, you can have the best of both worlds by simply using Prolog together with such solvers. Thus, using Prolog gives you both a Turing-complete programming language and a highly optimized constraint solver for combinatorial tasks, assuming you choose an implementation that is sophisticated enough. For example, in SICStus Prolog, check out CLP(B) and CLP(FD) for combinatorial tasks involving Boolean and integral variables.
  - idoh 10y ago
    You seem to know a lot about this space - how would you rank Racket's offerings, like miniKanren and Rackalog?
    - zmonx 10y ago
      I regard miniKanren, Racklog, core.logic, and many other Prolog-style implementations and embeddings of logic programming as extremely valuable and useful contributions that are both of academic and practical importance. They also serve the important strategic purpose of drawing more attention to logic programming languages in general. However, these implementations, although elegant and admirable in their own right also due to their innovative approaches, cannot yet compare in terms of features or performance with what a full-fledged modern Prolog system offers. In my experience, the main attraction of a professional Prolog system is often found precisely in its _constraint solvers_, and it is in these areas where professional Prolog implementors compete extremely vigorously, and more simplistic implementations currently fall short either in terms of features or performance. Still, even a very simplistic Prolog implementation can definitely be very useful, and if you do not need sophisticated constraints, then you may not need a commercial Prolog system. This situation arises for example in parsing, web applications, rule-based systems and other tasks where Prolog can help a lot, and constraints are not primarily needed. For a use case like sports scheduling and combinatorial tasks in general, I definitely recommend a Prolog system with very strong support of constraints, since what you can do with constraints in this application area by far exceeds the possibilities of "plain" Prolog, both in terms of performance and convenience.
zmonx 10y ago
Definitely! Prolog is extremely well suited for solving such tasks. For example, one of the most highly rated Prolog question on Stackoverflow is about a related task involving Tennis match scheduling: http://stackoverflow.com/questions/4747498/tennis-match-scheduling http://stackoverflow.com/questions/4747498/tennis-match-sche... The posted Prolog solution is quite concise and very efficient, thanks to the built-in constraint solvers that most Prolog systems provide nowadays.

Sounds like a job for Prolog. Maybe Prolog to make a list of schedules, and something else to sort that list?

by idoh 10y ago

Sounds like a job for Prolog. Maybe Prolog to make a list of schedules, and something else to sort that list?

ufo 10y ago

I think SAT-solvers and other constraint solvers might be a better fit. They can use clever algorithmic search technique like clause learning, non-chronological backtracking and so on to achieve big speedups compared to naive backtracking, which is what Prolog would do in this case. And we also don't need the full turing-completeness that Prolog provides.

zmonx 10y ago
I agree completely that SAT solvers and constraint solvers are a great choice for this. However, SAT solvers and constraint solvers blend in naturally and in fact even ship with many Prolog implementations! Thus, you can have the best of both worlds by simply using Prolog together with such solvers. Thus, using Prolog gives you both a Turing-complete programming language and a highly optimized constraint solver for combinatorial tasks, assuming you choose an implementation that is sophisticated enough. For example, in SICStus Prolog, check out CLP(B) and CLP(FD) for combinatorial tasks involving Boolean and integral variables.
- idoh 10y ago
  You seem to know a lot about this space - how would you rank Racket's offerings, like miniKanren and Rackalog?
  - zmonx 10y ago
    I regard miniKanren, Racklog, core.logic, and many other Prolog-style implementations and embeddings of logic programming as extremely valuable and useful contributions that are both of academic and practical importance. They also serve the important strategic purpose of drawing more attention to logic programming languages in general. However, these implementations, although elegant and admirable in their own right also due to their innovative approaches, cannot yet compare in terms of features or performance with what a full-fledged modern Prolog system offers. In my experience, the main attraction of a professional Prolog system is often found precisely in its _constraint solvers_, and it is in these areas where professional Prolog implementors compete extremely vigorously, and more simplistic implementations currently fall short either in terms of features or performance. Still, even a very simplistic Prolog implementation can definitely be very useful, and if you do not need sophisticated constraints, then you may not need a commercial Prolog system. This situation arises for example in parsing, web applications, rule-based systems and other tasks where Prolog can help a lot, and constraints are not primarily needed. For a use case like sports scheduling and combinatorial tasks in general, I definitely recommend a Prolog system with very strong support of constraints, since what you can do with constraints in this application area by far exceeds the possibilities of "plain" Prolog, both in terms of performance and convenience.

zmonx 10y ago

Definitely! Prolog is extremely well suited for solving such tasks. For example, one of the most highly rated Prolog question on Stackoverflow is about a related task involving Tennis match scheduling: http://stackoverflow.com/questions/4747498/tennis-match-scheduling http://stackoverflow.com/questions/4747498/tennis-match-sche... The posted Prolog solution is quite concise and very efficient, thanks to the built-in constraint solvers that most Prolog systems provide nowadays.