NP-complete problems and the FET algorithm

[Liviu Lalescu]

Since FET is a fast heuristic method for solving the timetabling problem, which is an NP-complete problem, the method might be applied to other NP-complete problems.

I just thought of a method to apply the FET algorithm to traveling salesman and it seems possible. Also, to graph coloring it applies directly (as a timetable is a graph coloring in n_hours_per_week colors if each activity has duration 1). I didn't think too much, but it seems that 3-SAT and clique problem can also be solved.

Note: by solving, I mean heuristically solving practical cases, like FET does. I do not claim to solve NP-complete problems polynomially.

The algorithm is simple: there are given n inputs: a1, a2, ..., an, and we try to put them into n slots. There are constraints, so that if the algorithm places ai into a slot, then a set of inputs aj, ak, ... will need to be displaced and placed into other slots. So, place ai into a slot and displace aj, ak, ... and place them recursively, like ai. We might need to impose a limit on the recursion level. Also, if recursion seems to work in vain for a time limit, place ai into a slot, displace aj, ak, ..., and start a new iteration with this state.

Also, a good initial sorting might be important.

I recommend you reading the Documentation section on FET homepage, then the doc/ directory of the FET package and then the src/engine/generate.cpp file of the FET package.

Maybe you are interested into spreading the word about this method.

[Liviu Lalescu]

I adapted the algorithm from FET and solved an instance of SAT which is categorized as UNKNOWN-SAT :-)

Attached the files with the solution.

I took the instance from http://www.satcompetition.org/ (SAT 2009 competition).

I'll think about sending a solver for this year's contest.

[Liviu Lalescu]

Sorry, it seems that UNKNOWN-SAT means something different - the problem was also solved by other solvers in the past, easily.

[mbarsan]

Hi Liviu, I find it's a good idea to partecipate in the contest!  8-)