Civil Engineering Reference
In-Depth Information
Algorithm CONSTRAINT
-
GENERATION
-
WITH
-
BOUNDS
{
P = target clock period;
= the
heap;
{
s = current vertex;
and
and
= current register weight;
do
{
if break;
;
if
continue;
if
add a period edge
with weight
else {
{
if
{
if
heap-insert
}
}
}
} while
}
}
Solving the linear program.
Like (10.17), the LP in (10.24) is also a dual
of a minimum cost network flow problem. We found that it could be solved
very efficiently using the network simplex algorithm from [BJS77]. The network
simplex method is a graph based adaptation of the LP simplex method that
exploits the network structure to achieve very good efficiency. The upper and
lower bounds on the variables provide an initial feasible spanning tree. This
tree has two levels only, with the host node as the root and all other nodes as
leaves. To prevent cycling we construct the initial basis to be strongly feasible
by using the appropriate bound (upper or lower) to connect a node to the root
(host node). It is easy to maintain strongly feasible trees during the simplex
operations, and details are given in [BJS77].
Using the first eligible arc pivot rule with a wraparound arc list from [AMO93]
(page 417) gives significant improvements in the run time. The dual variables
( variables) are directly available from the min cost flow solution.
