Solving Combinatorial Problems with Regular Local Search Algorithms

Abstract In this paper we describe new local search algorithms for regular CNF formulas and investigate their suitability for solving problems from the domains of graph coloring and sports scheduling. First, we define suitable encodings for such problems in the logic of regular CNF formulas. Second, we describe Regular-GSAT and Regular-WSAT, as well as some variants, which are a natural generalization of two prominent local search algorithms -GSAT and WSAT- used to solve the prepositional satisfiability (SAT) problem in classical logic. Third, we report on experimental results that demonstrate that encoding graph coloring and sports scheduling problems as instances of the SAT problem in regular CNF formulas and then solving these instances with local search algorithms can outperform or compete with state-of-the-art approaches to solving hard combinatorial problems.

Authors

• Ramón Béjar
• Felip Manyà

Keywords

No keywords are indexed for this paper.