Algorithms

[Liviu Lalescu]

Hello,

Since FET is quite in a stable state, I would like to think of other algorithms. Maybe you have some suggestions.

I tried applying the FET recursive swapping algorithm to the 3-satisfiability problem, but it fails miserably compared to other very fast methods, like gnovelty+, which is based on a simple algorithm. I am sure, looking at many FET users, that FET algorithm is very efficient. I also tried simple methods before in FET, but they failed by far.

I would like to have a longer discussion here, on useful things for me to do, as I am stalling.

[Benahmed Abdelkrim]

general : every problem requires a specific algorithm .

if an algorithm successful to solve a problem , it is not necessary that he managed to solve else!

[Volker Dirr]

that is wrong. every mathematic do that.
mainly because of 2 reasons:
a) proof that the old algorithm and/or solution is correct
b) check if the other algorithm is faster.

[Benahmed Abdelkrim]

 thank you Mr. volker for your quick reply.  there is a malentedu, I have not talked about the accuracy of the algorithm, but its convenience in relation to the problem.
example: the genetic algorithm is corect, but has proven its limits for the problem of the time table; it is slow, it is the main reason it is replaced by the heuristic algorithm.

[Volker Dirr]

yes, but there are many other possible algorithms we didn't checked yet.

also we didn't proof that the current one is correct. maybe there is still a bug and it can find only 99.9999% of all possible solutions.
in normal case not critical, but in wost case we might skip possible solution and we will never find a solution with this algorithm even there is one.

i think Liviu also talked a bit more general. so not only timetabling algorithms.

[Bob Hairgrove]

yes, but there are many other possible algorithms we didn't checked yet.

also we didn't proof that the current one is correct. maybe there is still a bug and it can find only 99.9999% of all possible solutions.
in normal case not critical, but in wost case we might skip possible solution and we will never find a solution with this algorithm even there is one.

i think Liviu also talked a bit more general. so not only timetabling algorithms.

I have read somewhere that timetabling belongs to the class of problems which are "NP complete" (or "NP hard"?) In other words, there is no algorithm which is guaranteed to find a solution, or which can guarantee that there is no solution with the given data, except for brute force. There are only heuristic algorithms, some of which work better than others.

However, I am not a computer scientist or engineer, so I think that the present algorithm which introduces an element of randomness to the search path works quite well. If one generation takes too long, you can cancel it and try again. The random ordering should make it possible to find a solution quickly (if there is one).

[Liviu Lalescu]

Yes, indeed, Bob

[canhathuongnhau]

Dear Mr Liviu,
I'm research about FET. So can you tell me what is  exactly algorithms that you use in FET?
Hopefully, I can get your information as soon as possible.
Thanks so much!

[Liviu Lalescu]

Please see http://lalescu.ro/liviu/fet/doc/ , "Timetable generation algorithm".

There are also some other topics here on the forum about the algorithm, you may search the forum.

[canhathuongnhau]

Mr Liviu Thanks for your quickly reply. Next time I will read document first before ask you

[Liviu Lalescu]

No problem