next up previous
Next: VLSI Floorplan Optimization Up: Portability versus Efficiency?

Previous: Introduction


As an application problem domain, we have chosen the class of discrete optimization problems, which can be defined in terms of finding a solution path in a tree or graph from an initial (root) state to a goal node.

Many applications in planning and scheduling can be formulated with this model: the cutting stock problem [2], the bin packing problem, vehicle routing, VLSI floorplan optimization [1,27], satisfiability problems, the traveling salesman problem [6], the N N-puzzle [7], and partial constraint satisfaction problems [3]. All of them are known to be NP-hard.

For our benchmarks, we have chosen two typical applications with different solution techniques: the VLSI floorplan optimization problem, which is solved with a depth-first branch-and-bound strategy, and the N N--puzzle, which is solved with an iterative-deepening search. Both are based on depth-first search (DFS), which traverses the decision tree in a top-down manner from left to right. DFS is commonly used in combinatorial optimization problems, because it needs only storage space in trees of depth d and width w.

Tue May 16 19:29:30 MET DST 1995