Stochastic shortest path algorithm based on Lagrangian relaxation

Hwang, Leslie K.

Permalink

https://hdl.handle.net/2142/16806 Copy

Description

Title

Stochastic shortest path algorithm based on Lagrangian relaxation

Author(s)

Hwang, Leslie K.

Issue Date

2010-08-20T17:58:15Z

Director of Research (if dissertation) or Advisor (if thesis)

Wong, Martin D.F.

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Stochastic shortest path
• Variation
• Lagrangian relaxation

Abstract

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.

Graduation Semester

2010-08

Permalink

http://hdl.handle.net/2142/16806

Copyright and License Information

Copyright 2010 Leslie K. Hwang

Owning Collections