The classical solving approach for two-level logic minimisation reduces the problem to a special case of unate covering and attacks the latter with a (possibly limited) branch-and-bound algorithm. We adopt this approach, but we propose a constructive heuristic algorithm that combines the use of Binary Decision Diagrams (BDDs) with the Lagrangian relaxation. This technique permits us to achieve an effective choice of the elements to include in the solution, as well as cost-related reductions of the problem and a good lower bound on the optimum. The results support the effectiveness of this approach: on a wide set of benchmark problems, the algorithm nearly always hits the optimum, and in most cases proves it to be so. On the problems whose optimum is actually unknown, the best known result is strongly improved.
An efficient heuristic approach to solve the unate covering problem [logic minimisation] / R. Cordone, F. Ferrandi, D. Sciuto, R.W. Calvo (PROCEEDINGS - DESIGN, AUTOMATION, AND TEST IN EUROPE CONFERENCE AND EXHIBITION). - In: Proceedings Design, Automation and Test in Europe Conference and Exhibition 2000 (Cat. No. PR00537)[s.l] : IEEE, 2000. - ISBN 0769505376. - pp. 364-371 (( convegno Design, Automation and Test in Europe Conference and Exhibition tenutosi a Paris nel 2000 [10.1109/DATE.2000.840297].
An efficient heuristic approach to solve the unate covering problem [logic minimisation]
R. Cordone;
2000
Abstract
The classical solving approach for two-level logic minimisation reduces the problem to a special case of unate covering and attacks the latter with a (possibly limited) branch-and-bound algorithm. We adopt this approach, but we propose a constructive heuristic algorithm that combines the use of Binary Decision Diagrams (BDDs) with the Lagrangian relaxation. This technique permits us to achieve an effective choice of the elements to include in the solution, as well as cost-related reductions of the problem and a good lower bound on the optimum. The results support the effectiveness of this approach: on a wide set of benchmark problems, the algorithm nearly always hits the optimum, and in most cases proves it to be so. On the problems whose optimum is actually unknown, the best known result is strongly improved.File | Dimensione | Formato | |
---|---|---|---|
05C_2.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
115.38 kB
Formato
Adobe PDF
|
115.38 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.