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.

A heuristic and an exact method for the gate matrix connection cost minimization problem

G Rinaldi;P Ventura
2013

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.
2013
Istituto di Analisi dei Sistemi ed Informatica ''Antonio Ruberti'' - IASI
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/20.500.14243/246525
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact