Logic programming online resources

Question

I might look like a n00b, but I would like to know whether anyone here in SO knows any good online resources on logic programming. I'm working on a huge scheduling application and I have "reduced" the algorithmic problem to another huge constraint satisfaction problem. Now I want to know how to use these constraints to derive logically equivalent constraints that either

1. are more easily evaluated than the original constraints
2. reduce the set of possibilities that must be evaluated

Thank you in advance for your help.

Answer 1

I don't think you want logic programming, but rather constraint satisfaction.

The obvious place to look is Wikipedia: Constraint Satisfaction Problem (CSP).

There are a number of constraint solvers out there already. I'd suggest you simply find one and try to use it.

Answer 2

For applications with large amount of constraints with moderate amount of facts you can choose Rule Engines. For example in Java it is Drools. http://www.jboss.org/drools/drools-solver.html

Answer 3

This is a pretty huge area, and so it really depends what you're asking for.

An excellent paper describing applying a constraint-solving language to a university timetabling problem is Abdennadher and Marte, 2000. If you're really wanting to implement a constraint language, then I strongly recommend the book Essentials of Constraint Programming, by one of the authors, which is excellent, but quite theoretical. That paper is just the first in a vast field - if you're serious about this, then you can follow the citations and check out other research by the authors (linked from the book page I mentioned earlier).

If you can afford a commercial implementation, then ILOG from IBM is supposed to be the state-of-the-art, and is used for logistics management by huge commerical companies. I have no personal experience with it.

Alternatively, you can look at the wide variety of algorithms that may be applicable to your problem, and see if you can cast your problem in terms that allow you to leverage them. Without more information on your problem, I can't make specific recommendations, but depending on your choice, there may be libraries and implementations available. See for example this question and answers. There are several more like this on SO with useful links - follow the tags.

Answer 4

Most automated scheduling problems I 've seen have an un-understandable large amount of possible solutions. For example, scheduling a 800 exams into 50 periods and 20 rooms, has 1000^800 or 10^2400 possible solutions. By comparison, there are only 10^80 atoms in the known universe! So you wont find the optimal solution in a billion years, but that's ok, as long as you find a good-as-it-gets feasible solution within 5 minutes or an hour.

Many people think that if they have a branch&bround algorithm that works on 10 exams in a second, that they can optimize it to work on 800 exams. Yet, for 12 exams it takes days. In practice, it's useless...

Drools Solver (now called Drools Planner) uses tabu search and can find optimal solutions. It's free and open source (ASL). Just copy-paste the curriculum course example and you should be able to prototype this in a few days.