Optimization: principles and algorithms, by Michel Bierlaire
|
Algorithm 24.1: unsaturated path. More...
Go to the source code of this file.
Functions | |
function | unsaturatedPath (in adj, in orig, in dest, in lb, in ub, in flow, in printlevel) |
Find an unsaturated path from o to d. More... | |
function | buildPathBackward (in layer, in dest, in arcs) |
Build the path by traversing the layers backward. More... | |
function | printLayers (in layer, in arcs) |
Print the layers. More... | |
Algorithm 24.1: unsaturated path.
Implementation of algorithm 24.1 of [1]
Definition in file unsaturatedPath.m.
function buildPathBackward | ( | in | layer, |
in | dest, | ||
in | arcs | ||
) |
Build the path by traversing the layers backward.
layer | list of layers. Each layer contains an array of nodes, arcs and directions. |
dest | destination node to reach |
arcs | A matrix containing the upstream and downstream nodes of each arc. Each row corresponds to an arc. Column 1 contains the upstream node and column 2 the downstream. Output of prepareNetwork. |
function printLayers | ( | in | layer, |
in | arcs | ||
) |
Print the layers.
layer | list of layers. Each layer contains an array of nodes, arcs and directions. |
arcs | A matrix containing the upstream and downstream nodes of each arc. Each row corresponds to an arc. Column 1 contains the upstream node and column 2 the downstream. Output of prepareNetwork. |
function unsaturatedPath | ( | in | adj, |
in | orig, | ||
in | dest, | ||
in | lb, | ||
in | ub, | ||
in | flow, | ||
in | printlevel | ||
) |
Find an unsaturated path from o to d.
adj | adjacency matrix of the network. Each nonzero entry corresponds to an arc. The value of the entry is the ID of the arc. |
orig | the origin node |
dest | the destination node |
lb | the lower bound on the flow |
ub | the upper bound on the flow |
flow | the current flow vector |
printlevel | If different from 0, the layers are printed. (Default: 0) |