An Attractor-Repeller Approach to Floorplanning
Miguel F. Anjos (anjosstanfordalumni.org)
Abstract: The floorplanning (or facility layout) problem consists in finding the optimal positions for a given set of modules of fixed area (but perhaps varying dimensions) within a facility such that the distances between pairs of modules that have a positive connection cost are minimized. This is a hard discrete optimization problem; even the restricted version where the shapes of the modules are fixed and the optimization is taken over a fixed finite set of possible module locations is NP-hard. In this paper, we extend the concept of target distance introduced by Etawil and Vannelli and apply it to derive the AR (Attractor-Repeller) model which is designed to improve upon the NLT method of van Camp et al. This new model is designed to find a good initial point for the Stage-3 NLT solver and has the advantage that it can be solved very efficiently using a suitable optimization algorithm. Because the AR model is not a convex optimization problem, we also derive a convex version of the model and explore the generalized target distance that arises in this derivation. Numerical results demonstrating the potential of our approach are presented.
Keywords: Facilities planning and design, Convex Programming, VLSI Macro-Cell Layout, Global Optimization
Category 1: Applications -- Science and Engineering (Multidisciplinary Design Optimization )
Category 2: Convex and Nonsmooth Optimization (Convex Optimization )
Citation: Mathematical Methods of Operations Research, Vol. 56(1):3-27, 2002.
Entry Submitted: 04/12/2001
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|