Computer Science – Data Structures and Algorithms
Scientific paper
2010-11-24
Computer Science
Data Structures and Algorithms
10 pages
Scientific paper
In the last decade, the power of the state-of-the-art SAT and Integer Programming solvers has dramatically increased. They implement many new techniques and heuristics and since any NP problem can be converted to SAT or ILP instance, we could take advantage of these techniques in general by converting the instance of NP problem to SAT formula or Integer program. A problem we consider, in this proof of concept, is finding a largest clique in a graph. We ran several experiments on large random graphs and compared 3 approaches: Optimised backtrack solution, Translation to SAT and Translation to Integer program. The last one was the fastest one.
No associations
LandOfFree
Proof of Concept: Fast Solutions to NP-problems by Using SAT and Integer Programming Solvers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Proof of Concept: Fast Solutions to NP-problems by Using SAT and Integer Programming Solvers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Proof of Concept: Fast Solutions to NP-problems by Using SAT and Integer Programming Solvers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-241561