3

Yes, there are many such questions like this on SO. I saw genetic algorithms were the most common answers.

Making a timetable schedule and

Algorithm for creating a school timetable

However, I am worried about these characteristics of a GA

  • termination condition of the program are hard to define
  • cant escape local maxima easily

I expect the program to be pushed to conflicting criteria and impossible solutions too readily by it's users.

Hence I want a method that

  • is decisive- guaranteed to reach a near-optimal situation or report that the algorithm won't reach a solution
  • can take both hard (inviolable) limits and soft limits
  • elegantly takes in user-input constraints; if user-input doesnt work, it can be added to the code without breaking it

There are 100000 exhaustively possible timetables.

I searched around and saw that metaheuristic algorithms like simulated annealing are a good candidate. What about dynamic programming algorithms?

Is a brute-force approach okay for such a data set?

What is a good algorithm that can fit the criteria?

Community
  • 1
  • 1
Jesvin Jose
  • 22,498
  • 32
  • 109
  • 202
  • If there are only 100,000 possible timetables, it is not too computationally hard to just brute-force and check all of them.. The use of GA or other AI tools is usually used when there are MUCH more [sometimes billions and more] possible timetables. The brute force solution will not take too long for input of 100,000 possible time tables, and will obviously get you the optimal result. – amit Dec 20 '11 at 09:24

1 Answers1

5

For small input, with only 100,000 possibilities - I'd go with a plain brute force solution: Just check all possibilities, and chose the best out of them. For modern machines, running your scoring function on an input of size 100,000 is not computationally hard, and will most likely take just a few seconds.

GA and other AI algorithms, are usually used for much larger input [billions and more possibilities], so they might not be the best solution in your case.

Unlike any other solution, the brute force solution will ensure you the optimal solution, and will be terminated when it exhausts all possible solutions.

(*)Note: you can modify GA and steepest ascent hill climbing to overcome the 2nd problem you mention [escaping local maxima] by enforcing random restarts when the solution is not improving for k steps, but again - you will have no idea how close you are to the optimal solution at each point.

amit
  • 175,853
  • 27
  • 231
  • 333
  • 3
    You can improve upon the brute force search via [Branch and Bound](https://secure.wikimedia.org/wikipedia/en/wiki/Branch_and_bound) by discarding solutions that can't possibly become better than the best solution you already have. – DataWraith Dec 20 '11 at 11:21
  • 1
    100 000 possibilities is actually very small. If you have 10 lessons in 5 timeslots in 2 rooms you have 10 000 000 000 possibilities. See how [useless Brute force is](http://blog.athico.com/2011/09/brute-forcing-bin-packing-problem.html) (and Brand and Bound too probably). – Geoffrey De Smet Dec 21 '11 at 13:14
  • @GeoffreyDeSmet: The OP is specifically asking for the small number of possibilities. Though not useful in the general case, in **this specific question**, the brute force solution fit perfectly. Any usage of GA or other AI algorithm [such as hill climbing] on such a small data set as indicated by the OP, will be an overkill in my opinion. – amit Dec 21 '11 at 14:16