An efficient method for large-scale slack allocation
Siddharth Joshi, Stephen Boyd · Engineering Optimization · 2009
This article concerns a timing or project graph, with given delays on the edges and given arrival times at the source and sink nodes. The arrival times at the other nodes are to be chosen; these determine the timing slacks, which must be non-negative, on the edges. The set of possible timing slacks is a polyhedron; to choose one, a separable concave utility function, such as the sum of the logarithms of the slacks, is maximized. This slack allocation problem, which can be given a simple statistical interpretation, is convex, and can be solved by a variety of methods. Gradient and coordinate ascent methods are simple and scale to large problems, but can converge slowly, depending on the topology and problem data. The Newton method, in contrast, reliably computes an accurate solution, but typically cannot scale beyond problems with a few thousand nodes. This article describes a custom truncated Newton method that efficiently computes an accurate solution, and scales to large graphs (say, with a million or more nodes). The method typically requires just a few hundred iterations, with each iteration requiring a few passes over the graph; in particular, the method has approximately linear complexity in the size of the problem. The same approach can be used to solve slack allocation problems with constraints, using an interior-point method that relies on the custom truncated Newton approach.