文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 资格考试/认证 > 从业资格考试 > PBS A backtrack search pseudo Boolean solver
侵权投诉

PBS A backtrack search pseudo Boolean solver

in areas such as hardware and software verification, FPGA routing, planning in AI, etc. Further uses are complicated by the need to express “counting constraints ” in conjunctive normal form (CNF). Expressing such constraints by pure CNF leads to more co

Fifth International Symposium on Theory and Applications of Satisfiability Testing, May 6-9, 2000, Cincinnati, Ohio

PBS: A Backtrack-Search Pseudo-Boolean Solver and Optimizer

Fadi A. Aloul, Arathi Ramani, Igor L. Markov, Karem A. Sakallah

Department of Electrical Engineering and Computer Science

University of Michigan

{faloul, ramania, imarkov, karem}@eecs.umich.edu

Abstract

Optimized solvers for the Boolean Satisfiability (SAT)problem [5, 14, 15, 17, 19, 23, 24] found many applicationsin areas such as hardware and software verification, FPGArouting, planning in AI, etc. Further uses are complicated bythe need to express “counting constraints” in conjunctivenormal form (CNF). Expressing such constraints by pureCNF leads to more complex SAT instances. Alternatively,those constraints can be handled by Integer Linear Pro-gramming (ILP), but off-the-shelf ILP solvers tend to ignorethe Boolean nature of 0-1 variables.

This work attempts to generalize recent highly successfulSAT techniques to new applications. First, we extend thebasic Davis-Putnam framework to handle counting con-straints and apply it to solve routing problems. Our imple-mentation outperforms previously reported solvers for thesatisfiability with “pseudo-Boolean” constraints and showssignificant speed-up over best SAT solvers when such con-straints are translated into CNF,.

Additionally, we solve instances of the Max-ONEs opti-mization problem which seeks to maximize the number of“true” values over all satisfying assignments. This, and therelated Min-ONEs problem are important due to reductionsfrom Max-Clique and Min Vertex Cover. Our experimentalresults for various benchmarks are superior to allapproaches reported earlier.

which impose an upper or a lower bound on the number ofcertain objects. More generally, given a collection of predi-cates, one may want to limit the number of predicates whichevaluate to true. VLSI routing is a source of such examples -only a certain number of wires can be routed through a givenchannel (no more than the channel capacity), but the particu-lar choice of wires is often not important. Expressing such aconstraint in pure CNF may lead to a serious increase in thenumber of clauses and variables, or in the addition of a fairlycomplicated set of clauses derived from adder and compara-tor circuits. This problem was addressed in a recent work [23]by an algorithm that handles non-CNF constraints such ascube lists and pseudo-Boolean (PB) constraints [3] of theform:

∑cixi≤n ci,n∈Z,xi∈{0,1}

The term pseudo-Boolean constraints refers to arbitrary lin-ear inequalities 0-1 in terms of variables, however manyapplications require only integer coefficients. The SATIREsolver [23] was successfully applied to functional delay faulttesting. It showed that PB encodings can be solved muchmore efficiently (by both runtime and memory usage) thanpure CNF encodings. Note that decision problems withpseudo-Boolean constraints are a special case of Integer Lin-ear Programming (ILP). However, as has been pointed out in[3], common ILP algorithms fail to take 0-1 variables intoaccount and are outperformed by specialized algorithms.Our first contribution is a solver architecture that com-bines data structures used in SATIRE with those used in thecurrently best pure CNF solver Chaff [15]. Our new SATsolver, PBS, handles CNF constraints and PB inequalities.Unlike previously proposed stochastic local search solvers[22], this solver is complete and is based on a backtracksearch algorithm. We believe that our proposed algorithms tohandle PB constraints can be added to any backtrack SATsolver.

To demonstrate the effectiveness of PBS, we compare itto (i) the currently best CNF-SAT solver Chaff [15], (ii) theearlier PB-SAT solver SATIRE [23] based on GRASP [14],and (iii) one of the best linear programming solvers OPBDP[4] based on branch-and-bound. Our experimental resultsshow at least an order-of-magnitude speed-up on instanceswith more than 300 variables and also on many smaller in-stances.

From the application standpoint, the availability of PBconstraints helps to address a broader range of problems, es-pecially those which cannot be efficiently encoded with pure

346

1 Introduction

Boolean Satisfiability has been the topic of intensive re-search over the past few decades. It has become a promisingnew technology for a number of applications in the field ofelectronic design automation (EDA) and has been successful-ly applied to various problems arising in formal verification[6, 21], timing analysis [18], routing of field-programmablegate arrays [16], automatic test pattern generation (ATPG)[12, 20], etc. As a result, several powerful SAT solvers [5, 14,15, 19, 23, 24] have been proposed, many of which use oneor another variation of the Davis-Logemann-Loveland (DLL)[8] approach. A recently developed solver, Chaff [15], pro-posed significant enhancements in both algorithm and imple-mentation level to backtrack search algorithms, which haslead to dramatic performance gains on many SAT instances. SAT solvers typically input Boolean formulas in conjunc-tive normal form (CNF), and an arbitrary Boolean formulawithout quantifiers can be quickly converted into a CNF.However, some applications contain counting constraints

第1页

TOP相关主题

你可能喜欢

热门文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email