NDLI: Dynamic symmetry-breaking for improved Boolean optimization

Content Provider	IEEE Xplore Digital Library
Author	Aloul, F.A. Ramani, A. Markov, I.L. Sakallah, K.A.
Copyright Year	2005
Description	Author affiliation: Dept. of Comput. Eng., American Univ. of Sharjah, United Arab Emirates (Aloul, F.A.)
Abstract	With impressive progress in Boolean satisfiability (SAT) solving and several extensions to pseudo-Boolean (PB) constraints, many applications that use SAT, such as high-performance formal verification techniques are still restricted to checking satisfiability of certain conditions. However, there is also frequently a need to express a preference for certain solutions. Extending SAT-solving to Boolean optimization allows the use of objective functions to describe a desirable solution. Although recent work in 0-1 integer linear programming (ILP) offers extensions that can optimize a linear objective function, this is often achieved by solving a series of SAT or ILP decision problems. Our work articulates some pitfalls of this approach. An objective function may complicate the use of any symmetry that might be present in the given constraints, even when the constraints are unsatisfiable and the objective function is irrelevant. We propose several new techniques that treat objective functions differently from CNF/PB constraints and accelerate Boolean optimization in many practical cases. We also develop an adaptive flow that analyzes a given Boolean optimization problem and picks the symmetry-breaking technique that is best suited to the problem characteristics. Empirically, we show that for non-trivial objective functions that destroy constraint symmetries, the benefit of static symmetry-breaking is lost but dynamic symmetry-breaking accelerates problem-solving in many cases. We also introduce a new objective function, localized bit selection (LBS), that can be used to specify a preference for bit values in formal verification applications.
Sponsorship	Chinese Inst. of Electron
Starting Page	445
Ending Page	450
File Size	1285897
Page Count	6
File Format	PDF
ISBN	0780387368
DOI	10.1109/ASPDAC.2005.1466204
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-01-21
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Constraint optimization Acceleration Problem-solving Encoding Formal verification Automatic test pattern generation Field programmable gate arrays Routing Microprocessors Lead
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Dynamic symmetry-breaking for improved boolean optimization (2005)

Dynamic symmetry-breaking for improved boolean optimization (2005)

Dynamic Symmetry-Breaking for Boolean Satisfiability

Fast Boolean optimization by rewiring

Effective use of Boolean satisfiability procedures in the formal verification of superscalar and VLIW microprocessors

Integration of supercubing and learning in a SAT solver

A verification methodology for reconfigurable systems

Using problem symmetry in search based satisfiability algorithms

B-cubing theory: new possibilities for efficient SAT-solving

Dynamic symmetry-breaking for improved Boolean optimization

Similar Documents

Dynamic symmetry-breaking for improved boolean optimization (2005)

Dynamic symmetry-breaking for improved boolean optimization (2005)

Dynamic Symmetry-Breaking for Boolean Satisfiability

Fast Boolean optimization by rewiring

Effective use of Boolean satisfiability procedures in the formal verification of superscalar and VLIW microprocessors

Integration of supercubing and learning in a SAT solver

A verification methodology for reconfigurable systems

Using problem symmetry in search based satisfiability algorithms

B-cubing theory: new possibilities for efficient SAT-solving

Dynamic symmetry-breaking for improved Boolean optimization