University of Illinois Urbana-Champaign

Stochastic shortest path algorithm based on Lagrangian relaxation

Hwang, Leslie K.

Content Files
Hwang_Leslie.pdf

Permalink

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

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
Date of Ingest
2010-08-20T17:58:15Z
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

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering