NDLI: Tutorial proposal efficient solving of optimization problems using advanced boolean satisfiability and Integer Linear Programming techniques

Content Provider	IEEE Xplore Digital Library
Author	Aloul, Fadi A.
Copyright Year	2009
Description	Author affiliation: Department of Computer Engineering American University in Sharjah, U.A.E. (Aloul, Fadi A.)
Abstract	Recent years have seen a tremendous growth in the number of research and development groups at universities, research labs, and companies that have started using Boolean Satisfiability (SAT) algorithms for solving different decision and optimization problems in Computer Science and Engineering. This has lead to the development of highly-efficient SAT solvers that have been successfully applied to solve a wide-range of problems in Electronic Design Automation (EDA), Artificial Intelligence (AI), Networking, Fault Tolerance, Security, and Scheduling. Examples of such problems include automatic test pattern generation for stuck-at faults (ATPG), formal verification of hardware and software, circuit delay computation, FPGA routing, power leakage minimization, power estimation, circuit placement, graph coloring, wireless communications, wavelength assignment, university classroom scheduling, and failure diagnosis in wireless sensor networks. SAT solvers have recently been extended to handle Pseudo-Boolean (PB) constraints which are linear inequalities with integer coefficients. This feature allowed SAT solvers to handle optimization problems, as opposed to only decision problems, and to be applied to a variety of new applications. Recent work has also showed that free open source SAT-based PB solvers can compete with the best generic Integer Linear Programming (ILP) commercial solvers such as CPLEX. This tutorial is aimed at introducing the latest advances in S AT technology. Specifically, we describe the simple new input format of SAT solvers and the common SAT algorithms used to solve decision/optimization problems. In addition, we highlight the use of SAT algorithms in solving a variety of EDA decision and optimization problems and compare its performance to generic ILP solvers. This should guide researchers in solving their existing optimization problems using the new SAT technology. Finally, we provide a prospective on future work on SAT.
Starting Page	6
Ending Page	11
File Size	507588
Page Count	6
File Format	PDF
ISBN	9781424458141
e-ISBN	9781424458165
DOI	10.1109/ICM.2009.5418586
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-12-19
Publisher Place	Morocco
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Tutorial Proposals Integer linear programming Electronic design automation and methodology Educational institutions Artificial intelligence Processor scheduling Automatic test pattern generation Circuits Delay estimation
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