The paper presents a new approach to solve the unate covering problem based on exploitation of information provided by Lagrangean relaxation. In particular, main advantages of the proposed heuristic algorithm are the effective choice of elements to be included in the solution, 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 such. 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 / R. Cordone, F. Ferrandi, D. Sciuto, R. W. Calvo. - In: IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS. - ISSN 0278-0070. - 20:12(2001 Dec), pp. 1377-1388.

An efficient heuristic approach to solve the unate covering problem

R. Cordone
Primo
;
2001

Abstract

The paper presents a new approach to solve the unate covering problem based on exploitation of information provided by Lagrangean relaxation. In particular, main advantages of the proposed heuristic algorithm are the effective choice of elements to be included in the solution, 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 such. On the problems whose optimum is actually unknown, the best known result is strongly improved
Lagrangian relaxation ; heuristic algorithm ; two-level logic minimization ; unate covering problem
Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni
Settore INF/01 - Informatica
dic-2001
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/161228
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact