Analytical approaches to the combinatorial optimization in linear placement problems
- 1 June 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 8 (6) , 630-639
- https://doi.org/10.1109/43.31519
Abstract
A class of combinatorial optimization problems dealing with placing circuit elements on a single row in order to minimize certain costs associated with the placements is formulated and solved. This analytical formulation of the linear placement problem proceeds with the restriction that all nets are two-point nets. The objective function considered is the sum of the squared wire-lengths. The properties of the formulation are discussed and used to show why certain mathematical programming techniques fail in solving the problems. Solution techniques are presented wherein the search for an optimal solution proceeds within the infeasible region and moves toward the feasible region following the trajectories in which the cost (objective function) tends to be optimal. This important difference of the technique from the previously known heuristics and the associated analysis of complex mathematical structures of the linear placement problems is felt to be important in probing further research in combinatorial optimization problemsKeywords
This publication has 9 references indexed in Scilit:
- Automatic Placement A Review of Current TechniquesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Module Placement Based on Resistive Network OptimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1984
- Linear Ordering and Application to PlacementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- An efficient algorithm for the two-dimensional placement problem in electrical circuit layoutIEEE Transactions on Circuits and Systems, 1981
- Restart procedures for the conjugate gradient methodMathematical Programming, 1977
- Suboptimum solution of the back-board ordering with channel capacity constraintIEEE Transactions on Circuits and Systems, 1977
- Clustering and linear placementPublished by Association for Computing Machinery (ACM) ,1972
- Efficient partitioning of componentsPublished by Association for Computing Machinery (ACM) ,1968
- Variational methods for the solution of problems of equilibrium and vibrationsBulletin of the American Mathematical Society, 1943