Circuit Partitioning Via Set Partitioning and Column Generation

Moshe Eben-Chaime, Craig A. Tovey, Jane C. Ammons

Operations Research · 1996 · Volume 44 · Issue 1

Abstract

In this paper, a new application of the methodology of set partitioning formulation augmented with heuristic column generation is presented. An efficient method for the partitioning of large-scale electronic circuits is developed based on this methodology. Circuit partitioning constitutes a major step of the physical design phase of electronic circuits, the fundamental components of electronic products. The major advantage of the scheme presented here is to provide a framework for an effective integration of most existing circuit partitioning methods. Another attractive feature of the current approach is the incorporation of interactive optimization: The circuit designer controls the operation of the procedure and enhances its performance by suggesting and/or requiring specific partitions. Following the development of the model, the solution approach is presented and computational results are reported for several benchmark circuits.

Keywords

industries, electronic: electronic circuits product design, programming, integer, algorithms: set partitioning with column generation, programming, integer, applications: application to electronic circuit partitioning

Enable JavaScript for citation tools and additional paper interactions.