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

Journal article


Publication Details

Author(s): Jünger M, Martin A, Reinelt G, Weismantel R
Journal: Mathematical Programming
Publication year: 1994
Volume: 63
Pages range: 257 - 279
ISSN: 1436-4646
Language: English


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. We 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 us to develop approximative algorithms. Finally we will present details of the implementation of our approach and compare it to industrial state of the art placement routines.



FAU Authors / FAU Editors

Martin, Alexander Prof. Dr.
Economics - Discrete Optimization - Mathematics (EDOM)


External institutions with authors

Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB)
Universität Köln


How to cite

APA:
Jünger, M., Martin, A., Reinelt, G., & Weismantel, R. (1994). Quadratic 0/1 optimization and a decomposition approach for the placement of electronic circuits. Mathematical Programming, 63, 257 - 279.

MLA:
Jünger, Michael, et al. "Quadratic 0/1 optimization and a decomposition approach for the placement of electronic circuits." Mathematical Programming 63 (1994): 257 - 279.

BibTeX: 

Last updated on 2018-10-08 at 05:24

Share link