Wire routing is the problem of determining the physical locations of all wires interconnecting the circuit components on a chip. Since the wires cannot intersect with each other, they are competing for limited spaces, thus making routing a difficult combinatorial optimization problem.

The domain description: routing.t

Wire routing problems:

• A basic routing problem: rp0.t (with obstacles defined in obstacles0.t).
• A bus routing problem: rp1.0.t (with obstacles defined in obstacles1.0.t).
• A relaxed bus routing problem: rp1.1.t (with obstacles defined in obstacles1.1.t).
• Restricting the length of a wire: rp2.0.t (with obstacles defined in obstacles2.t).
• Restricting the total length of the wires: rp2.1.t (with obstacles defined in obstacles2.t).
• No adjacency: rp3.t (with obstacles defined in obstacles3.t).

For installation of ccalc, please look at ccalc's homepage. After you install ccalc, you should load the files for the problem to be experimented with. In the above, the files that contain the problem descriptions ``include'' the files that contain the domain descriptions and the definition of the obstacles. Therefore, it is sufficient to load the file that contains the problem description. For instance, the file "rp0.t" is loaded by the command

You can instruct ccalc to find a solution by the command:

Here is the output of ccalc 1.23 for the routing problems, using Sicstus Prolog and relsat.

For more information about our experiments with ccalc (in the transition mode) on these problems, see Wire Routing and Satisfiability Planning.