Trap Escaping Strategies in Discrete Lagrangian Methods for Solving Hard Satisfiability and Maximum Satisfiability Problems

Abstract

In this paper, we present efficient trap-escaping strategies in a search based on discrete Lagrange multipliers to solve difficult SAT problems. Although a basic discrete Lagrangian method (DLM) can solve most of the satisfiable DIMACS SAT benchmarks efficiently, a few of the large benchmarks have eluded solutions by any local-search methods today. These difficult benchmarks generally have many traps that attract localsearch trajectories. To this end, we identify the existence of traps when any change to a variable will cause the resulting Lagrangian value to increase. Using the hanoi4 and par16-1 benchmarks, we illustrate that some unsatisfied clauses are trapped more often than others. Since it is too difficult to remember explicitly all the traps encountered, we propose to remember these traps implicitly by giving larger increases to Lagrange multipliers of unsatisfied clauses that are trapped more often. We illustrate the merit of this new update strategy by solving some of most di...