EVBDD-based algorithms for integer linear programming, spectral transformation, and function decomposition
- 1 January 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 13 (8) , 959-975
- https://doi.org/10.1109/43.298033
Abstract
Edge-Valued Binary-Decision Diagrams (EVBDD's) are directed acyclic graphs that can represent and manipulate integer functions as effectively as Ordered Binary-Decision Diagrams OBDD's) do for Boolean functions. They have been used in logic verification for showing the equivalence between Boolean functions and arithmetic functions. In this paper, we present EVBDD-based algorithms for solving integer linear programs, computing spectral coefficients of Boolean functions, and performing function decomposition. These algorithms have been implemented in C under the SIS environment and experimental results are providedKeywords
This publication has 32 references indexed in Scilit:
- Spectral transforms for large boolean functions with applications to technology mappingPublished by Association for Computing Machinery (ACM) ,1993
- On the OBDD-representation of general Boolean functionsIEEE Transactions on Computers, 1992
- Integer and Combinatorial OptimizationPublished by Wiley ,1988
- Computer Codes for Problems of Integer ProgrammingAnnals of Discrete Mathematics, 1979
- Investigation of some branch and bound strategies for the solution of mixed integer linear programsMathematical Programming, 1973
- Branch-and-Bound Methods: General Formulation and PropertiesOperations Research, 1970
- An Algorithm for the Solution of Mixed Integer Programming ProblemsManagement Science, 1966
- A tree-search algorithm for mixed integer programming problemsThe Computer Journal, 1965
- Minimization Over Boolean GraphsIBM Journal of Research and Development, 1962
- An Automatic Method of Solving Discrete Programming ProblemsEconometrica, 1960