Models and Algorithms for Computing Minimum-Size Prime Implicants
See where this sits in the topic map →Summary AI-generated
- TL;DR
- This paper explores models and algorithms for computing minimum-size prime implicants of Boolean functions, which are useful in fields like Electronic Design Automation and Artificial Intelligence.
- Problem
- Computing minimum-size prime implicants is challenging, and standard Integer Linear Programming (ILP) algorithms are generally impractical for this task.
- Method
- The paper presents and evaluates two fundamentally different algorithmic approaches: an explicit search method using dedicated Integer Linear Programming models and algorithms, and an implicit technique based on Binary Decision Diagrams.
- Results
- Experiments demonstrate that standard well-known ILP algorithms are generally impractical for these problems, while the newly proposed dedicated ILP algorithms provide a viable alternative for the explicit approach.
- Contributions
- The paper introduces new dedicated ILP algorithms specifically targeted at solving minimum-size prime implicant problems and provides an experimental evaluation of both the explicit and implicit strategies.
- Limitations
- Not specified in the abstract.
- Takeaways
- The study successfully describes, implements, and experimentally compares two contrasting algorithmic strategies for computing minimum-size prime implicants.
- Applications
- Electronic Design Automation and Artificial Intelligence.
- Topics
- Boolean functions, prime implicants, Integer Linear Programming, Binary Decision Diagrams, algorithms
- For industry
- Electronic Design Automation, Artificial Intelligence
- Why it matters
- Not specified in the abstract.
Abstract
Minimum-size prime implicants of Boolean functions find application in many areas of Computer Science including, among others, Electronic Design Automation and Artificial Intelligence. The main purpose of this paper is to describe and evaluate two fundamentally different modeling and algorithmic solutions for the computation of minimum-size prime implicants. One is based on explicit search methods, and uses Integer Linear Programming models and algorithms, whereas the other is based on implicit techniques, and so it uses Binary Decision Diagrams. For the explicit approach we propose new dedicated ILP algorithms, specifically target at solving these types of problems. As shown by the experimental results, other well-known ILP algorithms are in general impractical for computing minimumsize prime implicants. Moreover, we experimentally evaluate the two proposed algorithmic strategies. 1