Stochastic shortest path algorithm based on Lagrangian relaxation

Stochastic shortest path;Variation;Lagrangian relaxation

Hwang, Leslie K. ; Wong ; Martin D.F.

关键词: Stochastic shortest path;    Variation;    Lagrangian relaxation;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/16806/Hwang_Leslie.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

In VLSI circuit design, graph algorithms are widely used and graph structure can model many problems. As technology continues to scale into nanometer design, the effects of process variation become more crucial and design parameters also change. Hence, taking stochastic variations into account, probability distributions are used as edge weights to form statistical graph structures. General applications in VLSI circuit design, such as timing analysis, buffer insertion, and maze routing, can be formulated as shortest path problems using a statistical graph model. The solution of any such graph problem will surely have a statistical distribution for its cost function value. The mean and variance, square of standard deviation, values are used as a pair of weight values on a graph to represent the stochastic distribution on each edge. For the stochastic shortest path problem, we observe that the objective functions can be formulated using mean and standard deviation values of the resulting probability distribution and general cost functions are nonlinear. To solve for the nonlinear cost function, we intentionally insert a constraint on the variance. Several candidate paths will be achieved by varying the bound value on the constraint. With fixed bound value, the Lagrangian relaxation method is applied to find the feasible solution to the constrained shortest path problem. During Lagrangian relaxation, a feasible solution close to the optimal is achieved through subgradient optimization. Among the candidate paths obtained, the best solution becomes the ultimate solution of our algorithm for the original cost function under parameter variation. The algorithm presented in this work can handle any graph structures, arbitrary edge weight distributions and general cost functions.