Analytical approaches to the combinatorial optimization in linear placement problems

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 problems