Discrete Lagrangian-Based Search for Solving MAX-SAT Problems

1 Introduction

The satisfiability (SAT) problem is defined as follows. Given a set of n clauses { C1. C2 , · · ·, Cn} on m variables x = (x1. xz, · · ·, Xm), x; E {0, 1}, and a Boolean formula in conjunctive normal form (CNF),

find an assignment to the variables so that ( 1) evaluates to be true, or derive its infeasibility if (1) is infeasible.

The weighted maximum satisfiability problem (MAX­ SAT) is a general case of SAT. In MAX-SAT, each clause C; is associated with weight w;. The objective is to find an assignment to the variables that maximizes the sum of the weights of satisfied clauses,

*Research supported by National Science Foundation Grant MIP 96-32316 and National Aeronautics and Space Administration Grant NAG 1-613.

Source code of DLM is at http:/ /manip.crhc.uiuc.edu.

where S; equals 1 iflogical assignment x satisfies C;, and 0 otherwise. This objective is equivalent to minimizing the sum of the weights of unsatisfied clauses.

MAX-SAT problems are difficult to solve for the following reasons. First, they have a large number of local minima in their search space, where a local minimum is a state whose local neighborhood does not include any state that is strictly better. Second, the weights in the objective function of a MAX-SAT problem can lead to a much more rugged search space than the cor­ responding SAT problem. When a MAX-SAT prob­ lem is satisfiable, existing SAT algorithms [Gu, 1989; Selman and Kautz, 1993] developed to find a satisfiable assignment to the corresponding SAT problem can be applied, and the resulting assignment is also optimal for (2). However, this approach does not work when the MAX-SAT problem is not satisfiable. In this case, exist­ ing local search SAT methods have difficulties in over­ coming the rugged search space.

Methods for solving MAX-SAT can be classified as in­ complete and complete, depending on whether they can find the optimal assignment . Complete algorithms can determine optimal assignments. They include mixed in­ teger linear programming methods [Resende et al., 1997] and various heuristics [Hansen and Jaumard, 1990; Goe­ mans and Williamson, 1995; Joy et al., 1997]. They are generally computationally expensive and have difficulties in solving large problems. On the other hand, incom­ plete methods are usually faster and can solve some large problems that complete methods cannot handle. Many incomplete local search methods have been designed to solve large SAT problems of thousands of variables [Gu, 1989; Selman and Kautz, 1993; Wah and Shang, 1996; Shang and Wah, 1997] and have obtained promising re­ sults in solving MAX-SAT problems [Jiang et al., 1995; Resende et al., 1997].

Another approach to solve MAX-SAT is to transform it into continuous formulations. Discrete variables in the original problem are relaxed into continuous variables in such a way that solutions to the continuous problem are binary solutions to the original problem. This transfor­ mation is potentially beneficial because an objective in continuous space may smooth out some local minima. Unfortunately, continuous formulations require compu­ tationally expensive algorithms, rendering them applica­ ble only to small problems.

A discrete Lagrangian-based search method was de­ veloped previously for solving SAT problems [Wah and Shang, 1996; Shang and Wah, 1997]. Traditional La­ grangian theory for solving continuous problems was extended to discrete constrained optimization problems and incorporated in DLM (Discrete Lagrangian method) that works on discrete variables. Instead of restarting from a new starting point when a search reaches a local trap, the Lagrange multipliers in DLM provide a force to lead the search out of the local minimum and move it in the direction provided by the Lagrange multipliers. Hence, DLM can escape from local minima in a continu­ ous trajectory without restarts, avoiding a break in the trajectory as in methods based on restarts. This is ad­ vantageous when the trajectory is already in the vicinity of a local minimum, and a random restart may bring the search to a completely different search space. Moreover, DLM has very few algorithmic parameters to be tuned by users, and the search procedure can be made deter­ ministic and the results, reproducible. When applied to the DIMACS SAT benchmarks, DLM generally performs better than the best competing methods and can achieve an order-of-magnitude speedup for many problems.

In this paper we extend the discrete Lagrange­ multiplier-based search method to solve MAX-SAT problems. We formulate a MAX-SAT problem in (2) as a discrete constrained optimization problem.

where w; > 0, and U; (x) equals 0 if the logical assign­ ment x satisfies C;, and 1 otherwise. We propose a mech­ anism to control the growth rate and magnitude of La­ grange multipliers, which is essential in solving difficult MAX-SAT problems. Our method belongs to the class of incomplete methods that attempt to find approximate solutions in a fixed amount of time.

This paper is organized as follows. Section 2 presents our discrete Lagrangian algorithm. Section 3 discusses issues and alternatives in implementing DLM. Finally, Section 4 presents experimental results in applying DLM to solve a large set of test problems.

2 Discrete Lagrangian Methods (DLM)

In this section we first summarize previous work on La­ grangian methods for solving continuous constrained op­ timization problems. We then extend continuous La­ grangian methods to discrete constrained optimization problems, and apply it to solve MAX~SAT problems.

2.1 Continuous Lagrangian Methods

Lagrangian methods are classical methods for solving continuous constrained optimization problems [Luen­ berger, 1984]. Define an equality constrained optimiza­ tion problem as follows:

where g(x) = (g1(x),g2(x), · · ·,gn(x)) are n constraints. Lagrangian function F is defined by

where A= (AI,···, An) E En are Lagrange multipliers. A saddle-point (x·, A*) of Lagrangian function F(x, A) is defined as one that satisfies the following condition.

for all (x*, ,\)and all (x, ,\*)sufficiently close to (x*, ,\*).

(Continuous) Saddle-Point Theorem [Luenberger, 1984]. x* is a local minimum to the original problem de­ fined in ( 4) if and only if there exists ,\ * such that ( x*, ,\ *) constitutes a saddle point of the associated Lagrangian function F(x, ,\).

Based on the Saddle Point Theorem, numerical algo­ rithms have been developed to look for saddle points corresponding to local minima in a search space. One typical method is to do descents in the original variable space of x and ascents in the Lagrange-multiplier space of ,\, The method can be written as a set of ordinary differential equations as follows:

where t is an autonomous variable and V is a gradient.

2.2 General DLM

Little work has been done in applying Lagrangian meth­ ods to solve discrete constrained combinatorial search problems. The difficulty lies in the requirement of a differentiable continuous space. To apply Lagrangian methods to discrete optimization problems, we need to develop the counterpart of gradient in discrete space.

Similar to ( 4), a discrete optimization problem is de­ fined as follows.

where D is the set of integers. We can also define a discrete Lagrangian function similar to ( 5).

A saddle point ( x*, A*) of F ( x, A) is defined as one that satisfies the following condition:

for all A sufficiently close to A* and for all x whose Ham­ ming distance between x* and x is 1.

Discrete Saddle-Point Theorem. x* is a local mini­ mum of (8) if and only if there exists some A* such that (x*, A*) constitutes a saddle point of the associated dis­ crete Lagrangian function F(x, A).

The proof is quite straightforward and is based on showing that U(x*) = 0 in both directions. Based on the Discrete Saddle-Point Theorem, we have developed the following DLM to find discrete saddle points.

Discrete Lagrangian Method (DLM) A.

where 8 represents exclusive OR (XOR). We define the discrete gradient ~xF(x, A) with respect to x such that ~xF(x,A) = (Jl,···,Om) E {0,1}m with at most one non-zero J;, and it gives F(x, A) the greatest reduction i~ the neighborhood of x with Hamming distance 1.

DLM provides a theoretical foundation and generaliza­ tion of local search schemes that optimize the objective alone and clause-weight schemes that optimize the con­ straints alone. In contrast to local search methods that restart from a new starting point when a search reaches a local trap, the Lagrange multipliers in DLM provide a force to lead the search out of a local minimum and move it in the direction provided by the Lagrange multipliers. In contrast to constraint-weight schemes that rely only on the weights of violated constraints to escape from lo­ cal minima, DLM also uses the value of the objective function to provide further guidance.

In most existing clause-weight schemes, weights are updated dynamically based on which constraints are vi­ olated after each flip or after a series of flips. However, they do not use any objective function that may be im­ portant in some stages of the search. For instance, when the number of violated constraints is large, then it is important to reduce the number of violated constraints by choosing proper variables to flip. In this case, the weights on the violated constraints may be relatively small as compared to the number of violated constraints and, hence, play a minor role in determining the vari­ ables to flip. The advantage of the objective is more apparent in applications in which its value may be large, such as the MAX-SAT problems studied in this paper. The dynamic shift in emphasis between the objective and the constraints, depending on their relative values, is the key of DLM.

2.3 DLM Formulation of MAX-SAT

Using the MAX-SAT problem in (3), the Lagrangian function has the same form as in (5):

where x E {0, 1}m, U(x) E {0, 1}n, and AT (the trans­ pose of A = (At, A2 , ··· , An)) denotes the Lagrange mul­ tipliers.

There are three important properties about DLM.

• Since U ( x) = 0 when A converges to a discrete sad­ dle point, x is globally (not just lO<;ally) optimal when A converges. If any ofthe constraints in U(x) is not satisfied, then A will continue to evolve to handle the unsatisfied constraints, and the search continues.
• Since U;(x) is weighted by w; +A; in (12), the min­ imization of L(x, A) by DLM while A is changing is equivalent to perturbing the weights in the original objective function defined in (3). In contrast, ex­ isting MAX-SAT methods explore the search space without modifying the weights. This is the major difference between existing methods and DLM.
• The minimization of (12) is equivalent to a clause­ weight scheme. This happens because the objective and the constraints in (3) are dependent. In general, when the objective and the constraints are inde­ pendent, descents in the original-variable space and ascents in the Lagrange-multiplier space form two counteracting forces to converge to saddle points.

3 Implementation Issues of DLM

In this section, we discuss various considerations in im­ plementing DLM. Figure 1 shows the pseudo code of At, a generic DLM implementing (10) and (11). Define one iteration as one pass through the while loop. In the fol­ lowing, we describe some of our design considerations.

• (a) Initial Points (Lines 1-2). DLM is started from either the origin or from a random initial point generated using a fixed random seed. Further, A is always set to zero. The fixed initial points allow the results to be reproducible easily.

1. Set initial x randomly by a fixed random seed
2. Set initial ,\ to be zero
3. while xis not a feasible solution, i.e., N(x) > 0
4. update x: X~ X 8 tJ...,L(x, ..\)
5. update incumbent if N(x) is better than the current incumbent
6. if condition for updating ,\ is satisfied then
7. update..\: ,\ ~ ,\ +c x U(x)
8. end if
9. end while

Figure 1: Generic DLM A1 for solving SAT problems.

(b) Descent and Ascent Strategies (Line 4). There are two ways to calculate LlxL(x, >.): greedy and hill­ climbing, each involving a search in the range of Ham­ ming distance one from the current x. In a greedy strat­ egy, the assignment leading to the maximum decrease in L(x, >.) is selected to update the current assignment. In hill-climbing, the first assignment leading to a decrease in L(x, >.) is selected to update the current assignment. Depending on the order of search and the number of as­ signments that can be improved, hill-climbing strategies are generally much faster than greedy strategies.

Among various ways of hill-climbing, we used two al­ ternatives in our implementation: flip the variables one by one in a predefined order, or maintain a list of vari­ ables that can improve the current L(x, >.) and just flip the first variable in the list. The first alternative is fast when the search starts. By starting from a randomly generated initial assignment, it usually takes very few flips to find a variable that improves the current L(x, >.). As the search progresses, there are fewer variables that can improve L(x, >.). At this point, the second alterna­ tive becomes more efficient and should be applied.

• (c) Conditions for updating >. (Line 6). The fre­ quency in which >. is updated affects the performance of a search. The considerations. here are different from those of continuous problems. In a discrete problem, descents based on discrete gradients usually make small changes in L(x, >.) in each update of x because only one variable changes. Hence, >. should not be updated in each iteration of the search to avoid biasing the search in the Lagrange-multiplier space of >. over the original variable space of x.

Experimental results show that a good strategy is to update >. only when LlxL(x, >.) = 0. At this point, a local minimum in the original variable space is reached, and the search can only escape from it by updating >..

• (d) Amount of update of>. (Line 7). A parameter c controls the magnitude of changes in >.. In general, c can be a vector of real numbers, allowing non-uniform updates of >. across different dimensions and possibly across time. In our experiments, c = 1 has been found to work well for most of the benchmarks tested. How-

Figure 2: Execution profiles of jnhl (left) and jnhlO (right). jnhl is satisfiable and jnhlO is not.

ever, for some larger problems, a larger c could result in shorter search time and better solutions.

The update rule in Line 7 results in nondecreasing >. because U ( x) is either 0 or 1. In contrast, in continu­ ous problems>.; of constraint g;(x) = 0 increases when g;(x) > 0 and decreases when g;(x) < 0.

From previous experience in solving SAT problems us­ ing DLM, some >. values for some difficult problems can become very large after tens of thousands of iterations. At this point, the Lagrangian search space (12) becomes very rugged, and the search has difficulty in identify­ ing an appropriate direction to move. To cope with this problem, >. should be reduced periodically to keep them small and to allow DLM to better identify good solu­ tions.

The situation is worse in MAX-SAT because the weights of clauses, w, can be in a large range, making L(x, >.) in (12) even more rugged and difficult to search. Here, >. + w in MAX-SAT has a similar role as>. in SAT. Without any mechanism to reduce >. + w, L(x, >.) can become very large and rugged as the search progresses.

This situation is illustrated in the first two graphs of Figure 2 that show the behavior of DLM when it was applied to solve two MAX-SAT problems. The graphs show that the Lagrangian values vary in a very large range, and the Lagrangian space is difficult to search.

One way to overcome this problem is to reduce >. and w periodically. For instance, in the last two graphs of Figure 2, >.+w was scaled down by a factor of2 every 500 iterations. This strategy reduces L(x, >.) and restricts the growth of the Lagrange multipliers, leading to faster solutions for many test problems.

Figure 3 shows A2, our implementation of DLM to

Set initial x Set A= 0 Set c = 1 Set " = n/3, where n is the number of variables Set A reduction interval h. (e.g. 500) Set reduction ratio r (e.g. 2.0) Set base A value Ab (e.g. 1) Set base weight value Wb (e.g. 1) while xis not a feasible solution, i.e., N(x) > 0 if number of iterations ~ " then Maintain a list, l, of variables such that if one of them is flipped, L( x , A) will improve. if l is not empty then Update x by flipping the first element of l else Update A: A+--- A+ c · U(x) endJf else if 3 variable v s.t . L(x', A) < L(x, A) when flipping v in a predefined order in x to get x' then x +--- x' else Update A: A+--- A+ c · U(x) endJf endJf if iteration index mod I>. = 0 then Reduce A and weights for all clauses if possible, e.g. A+--- max(Ab,A/r),wi +--- max(wb,Wi/r) endJf if xis better than incumbent , keep x as incumbent . end_while

solve MAX-SAT. A2 uses the first strategy of hill­ climbing in descents in the beginning and switches to the second strategy later. We use "' to control the switch from the first strategy to the second. We found that "' = n/3 works well and used it in our experiments.

A2 updates .X only when a local minimum is reached. In our experiments, we have used a simple scheme that increases .X by a constant across all clauses.

A2 controls the magnitude of L(x, .X) by periodically reducing .X and w. More sophisticated adaptive mecha­ nisms can be developed to lead to better performance.

4 Experimental Results

In this section we evaluate DLM using some bench­ marks and compare it with previous results obtained by GRASP [Resende and Feo, 1996; Resende et al., 1997]. GRASP is a greedy randomized adaptive search pro­ cedure that has been shown to quickly produce good­ quality solutions for a wide variety of combinatorial op­ timization problems, including SAT and MAX-SAT.

The 44 MAX-SAT problems tested by GRASP were derived from DIMACS SAT benchmark jnh that have 100 variables and between 800 and 900 clauses. Some of them are satisfiable, while others are not. Their weights are integers generated randomly between 1 and 1000. 1

Our DLM code was written in C. The experiments were run on a 50-MHz Sun SparcStation 10/51. The code was compiled using gee with the "-0" option.

In our experiments, we first studied the effect of re­ ducing .X and L(x, .X). We compared the results with and without periodic reduction of .X. We ran DLM between 5 to 20 times from random initial points, each for 10,000 iterations, for each test problem. We then took the best solution of the multiple runs as our final solution.

When .X was not reduced periodically, DLM found 25 optimal solutions out of the 44 problems (based on the best results of 10 runs). When .X was reduced periodi­ cally, we tried several values of/;,, the reduction interval , and r, the reduction ratio. Using h of 100, 1000, 2000 and 5000 and r of 1.5, 2 and 4, we found significant im­ provement in solution quality when .X was reduced pe­ riodically (except for the case when h = 5000). The best combination is when h = 500 and r = 2, in which 12 more optimal solutions were found than without .X reduction, 18 test problems were improved, and no solu­ tion is worse. Overall, we found optimal solutions in 39 out of the 44 test problems (based on best of 20 runs).

Table 1 compares the solutions obtained by DLM and by GRASP. The results of GRASP are from [Resende et al., 1997] that were run for 10,000 iterations on a 250-MHz SGI Challenge with MIPS R4400. In contrast , DLM was run between 5 and 20 times from random ini­ tial points using 10,000 iterations each. Our results show significant improvement over GRASP in 43 of the 44 test problems. It is important to note that, although the dif­ ferences between GRASP's results and the optimal so­ lutions are relatively small, improvements in this range are the most difficult for any search algorithm.

Table 2 shows the average time in seconds for 10,000 iterations of GRASP and DLM. Since GRASP was run on a faster machine, we estimate that one iteration of DLM takes around three orders of magnitude less time than that of GRASP on the same machine.

GRASP found better results when the number of iter­ ations is increased. Using the ten test problems reported in [Resende et al., 1997] that were run for 100,000 iter­ ations of GRASP, Table 3 compares the results of DLM and GRASP with longer runs. It shows that DLM still found better solutions in all the problems.

Increasing the number of iterations of DLM could im­ prove the best solutions found. DLM was able to find 40 out of 44 optimal solutions when the number of iter­ ations is increased to 100,000 (best of 10 runs).

Our experimental results show that DLM solved these benchmark problems much faster and found better solu­ tions for a majority of the test problems.

1 The 44 benchmark problems can be obtained from ftp:/ /netlib.att.com/math/people/mgcr/data/maxsat.tar.gz.