Conference Agenda

Steiner tree packing problems under arbitrary constraints occur naturally in VLSI routing. Traditionally many of these problems are solved using rip-up and reroute algorithms which quickly yield solutions with good netlength, but often fail to obey all design rules. Straightforward SAT-based approaches can easily obey the design rules, but produce unusable results with regard to netlength. We present a new algorithm utilizing elements of both approaches. This algorithm quickly produces results with good netlength in practice, while providing a guarantee that the computed solution will obey all design rules.

We apply this algorithm in the context of transistor-level routing, which involves more complex design rules and higher packing densities than chip-level routing. We present results on a cell library for a commercial 2nm node.

We consider a recently proposed one-dimensional packing problem, called the overflow bin packing problem (OBPP). In this scenario, we are given a set of items (of known sizes) and a set of bins (of known capacities). Roughly speaking, the task is to assign the items to the bins in such a way that the total load of every bin is as close as possible to its capacity. In this talk, we first separate the problem under consideration from related partitioning problems, thus justifying its status as an independent branch of research. Subsequently, we review an assignment model known from the literature and investigate its theoretical properties. As a main result, we give a closed-form term for the associated LP bound and specify its worst-case performance ratio. In the second part, we then present a novel flow-based approach and show its numerical benefits by means of extensive computational tests with different benchmark sets. In particular, the new ILP formulation succeeds in solving all the considered instances to proven optimality in short time.