A heuristic and an exact method for the gate matrix connection cost minimization problem (Articolo in rivista)

Type
Label
  • A heuristic and an exact method for the gate matrix connection cost minimization problem (Articolo in rivista) (literal)
Anno
  • 2013-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1111/itor.12025 (literal)
Alternative label
  • L. De Giovanni, G. Massi, F. Pezzella, M.E. Pfetsch, G. Rinaldi and P. Ventura (2013)
    A heuristic and an exact method for the gate matrix connection cost minimization problem
    in International transactions in operational research; John Wiley & Sons, Ltd., Chichester (Regno Unito)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • L. De Giovanni, G. Massi, F. Pezzella, M.E. Pfetsch, G. Rinaldi and P. Ventura (literal)
Pagina inizio
  • 627 (literal)
Pagina fine
  • 643 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 20 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali
  • 17 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Dipartimento di Matematica, Università degli studi di Padova, via Trieste, 63, 35121 Padova, Italy Dipartimento di Ingegneria dell'Informazione, Università Politecnica delle Marche - via Brecce Bianche 12, Ancona, Italy Research Group Optimization, Department of Mathematics, Technische Universitaet Darmstadt, Dolivosstraße 15, 64293 Darmstadt, Germany Istituto di Analisi dei Sistemi ed Informatica \"Antonio Ruberti\" del CNR, viale Manzoni 30, 00185 Roma, Italy (literal)
Titolo
  • A heuristic and an exact method for the gate matrix connection cost minimization problem (literal)
Abstract
  • In many applications, a sequencing of patterns (electronic circuit nodes, cutting patterns, product orders, etc.) has to be found in order to optimize some given objective function, giving rise to the so-called open stack problems. We focus on a problem related to the optimization of gate matrix layouts: electronic circuits are obtained by connecting gates and one seeks a gate layout permutation that minimizes connection costs under restrictions on the circuit area. In the literature, the connection costs and circuit area are also known as time of open stacks and maximum number of open stacks, respectively. We propose a genetic algorithm providing heuristic solutions and a branch-and-cut algorithm based on a new linear integer programming formulation that represents, to the best of our knowledge, the first exact method proposed in the literature. The algorithms have been tested on real instances and on data sets from the literature. The computational results give evidence that the proposed methods provide solutions that improve the ones found by the approaches presented in the literature. (literal)
Editore
Prodotto di
Autore CNR

Incoming links:


Autore CNR di
Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Editore di
data.CNR.it