Quadratic 0/1 optimization and a decomposition approach for the placement of electronic circuits

Quadratic 0/1 optimization and a decomposition approach for the placement of electronic circuits

0.00 Avg rating0 Votes
Article ID: iaor19951863
Country: Netherlands
Volume: 63
Issue: 3
Start Page Number: 257
End Page Number: 279
Publication Date: Feb 1994
Journal: Mathematical Programming
Authors: , , ,
Keywords: manufacturing industries
Abstract:

The placement problem in the layout design of electronic circuits consists of finding a nonoverlapping assignment of rectangular cells to positions on the chip so that wireability is guaranteed and certain technical constraints are met. This problem can be modelled as a quadratic 0/1-program subject to linear constraints. The authors will present a decomposition approach to the placement problem and give results above NP-hardness and the existence of •-approximative algorithms for the involved optimization problems. A graph theoretic formulation of these problems will enable them to develop approximative algorithms. Finally the authors will present details of the implementation of the present approach and compare it to industrial state of the art placement routines.

Reviews

Required fields are marked *. Your email address will not be published.