in reply to Looking for help with AI::Genetic and classroom scheduling

After reading through the thread, I think its timely to call your attention that Genetic Algorithm (GA) is not the one and only choice when solving the classroom scheduling problem. While I am not proficient in the field, in my understanding of combinatorial optimization, your problem is a special form of the broader range of assignment problems, and as such, it quite naturally lends itself to be formulated as an integer linear program (ILP). Here you can read a pretty good introduction to the topic with the most important backgrounds.

Now, the only thing that remained to be done is to actually solve the resultant ILP. For this I coded and maintain (unfortunately, out of CPAN) a nice Perl module, Math::GLPK, which wraps the GNU Linear Programming Toolkit (GLPK). Based on my thorough experience with GLPK and ILPs, you have pretty good chance to obtain 100 percent optimal solution in all cases as long as the size of the problem remains of similar range as yours.

It is clear that both approaches have its pros and cons. However, for me at least, the ILP approach proved itself much more natural and concise than any other formulations of hard combinatorial optimization problems...

rg0now

  • Comment on Re: Looking for help with AI::Genetic and classroom scheduling

Replies are listed 'Best First'.
Re^2: Looking for help with AI::Genetic and classroom scheduling
by merlyn (Sage) on Feb 20, 2005 at 14:09 UTC
    One thing that may surprise most people is that my programming skills are self-taught. I know only enough programming and enough writing and enough math to have solved whatever problem was facing me in the trench that day. Luckily, I learn really fast, but I just have to have the right problem to chew on, and see the proper "next steps" so I don't get completely swirled.

    So, those of you with letters after your names have an advantage, because you got some book learnin' that I haven't gotten around to doing yet. That's what I was hoping to leverage from here.

    It occurred to me that the problem might be small enough that some sort of more direct (non-genetic) algorithm might do the job, but I knew that this "bear of very little brane" would get a faster result by applying things that I could learn in an afternoon, not a week. {grin}

    -- Randal L. Schwartz, Perl hacker
    Be sure to read my standard disclaimer if this is a reply.

[reply]
      I admit I was not specific enough. To serve as a real help, I would have come up with a concrete methodology to formulate your problem as an ILP, which I missed to do. The problem is that I am not familiar enough with timetabling and currently, I do not have time to do the essential research. Hopefully, some other monks will do it...:-) By all means, I pretty much recommend you to take the time and look into linear programming. You will be surprized, how generic problem solving technique it gives to your disposal and might very well open up a completely new way of thinking about optimization.

      The only thing that I could find, which could get you started is this paper, or better to say, Section 2 of the paper... It gives the basic notation (which might look like a bit bloated for the first sight, and yes, for the second too), but once you get the point, it is much simpler than you might have expected.

      rg0now

[reply]

In Section Seekers of Perl Wisdom