#### Withdraw

Loading…

# Stochastic shortest path algorithm based on Lagrangian relaxation

#### Hwang, Leslie K.

Loading…

## 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
- 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#### Manage Files

Loading…

#### Edit Collection Membership

Loading…

#### Edit Metadata

Loading…

#### Edit Properties

Loading…

#### Embargoes

Loading…