Algorithms for Weighted Boolean Optimization

Details Algorithms for Weighted Boolean Optimization Algorithms for Weighted Boolean Optimization

2009-03-04

arxiv.org/abs/0903.0843v2

Computer Science

Artificial Intelligence

14 pages, 2 algorithms, 3 tables, 1 figure

Scientific paper

The Pseudo-Boolean Optimization (PBO) and Maximum Satisfiability (MaxSAT) problems are natural optimization extensions of Boolean Satisfiability (SAT). In the recent past, different algorithms have been proposed for PBO and for MaxSAT, despite the existence of straightforward mappings from PBO to MaxSAT and vice-versa. This papers proposes Weighted Boolean Optimization (WBO), a new unified framework that aggregates and extends PBO and MaxSAT. In addition, the paper proposes a new unsatisfiability-based algorithm for WBO, based on recent unsatisfiability-based algorithms for MaxSAT. Besides standard MaxSAT, the new algorithm can also be used to solve weighted MaxSAT and PBO, handling pseudo-Boolean constraints either natively or by translation to clausal form. Experimental results illustrate that unsatisfiability-based algorithms for MaxSAT can be orders of magnitude more efficient than existing dedicated algorithms. Finally, the paper illustrates how other algorithms for either PBO or MaxSAT can be extended to WBO.

Affiliated with

Also associated with

No associations

Rating

Algorithms for Weighted Boolean Optimization 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 Algorithms for Weighted Boolean Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Weighted Boolean Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-114135