In the early stage of floorplan design, many modules have large flexibiliti
es in shape (soft modules). Handling soft modules in general nonslicing flo
orplan is a complicated problem. Many previous works have attempted to tack
le this problem using heuristics or numerical methods, but none of them can
solve it optimally and efficiently, In this paper, we show how this proble
m can be solved optimally by geometric programming using the Lagrangian rel
axation technique. The resulting Lagrangian relaxation subproblem is so sim
ple that the optimal size of each module can be computed in linear time. We
implemented this method in a simulated annealing framework based on the se
quence pair representation, The geometric program is invoked in every itera
tion of the annealing process to compute the optimal size of each module to
give the best packing. The execution time is much faster (at least 15 time
s faster for data sets with more than 50 modules) than that of the most upd
ated previous work by Murata and Kuh (1998). For a benchmark data with 49 m
odules, we take 3.7 h in total for the whole annealing process using a 600-
MHz Pentium m processor while the convex programming approach described by
Murata and Koh needs seven days using a 250-MHz DEC Alpha. Our technique wi
ll also be applicable to other floorplanning algorithms that use constraint
graphs to find module positions in the final packing.