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: | Jnger M., Reinelt G., Martin A., Weismantel R. |
Keywords: | manufacturing industries |
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