Thursday, 14:15 - 14:40 h, Room: H 3503


Per Olov Lindberg
Updating shortest path subproblem solutions in large scale optimization

Coauthor: Johan Holmgren


In many large scale optimization applications, one repetitively solves shortest path (SP) subproblems, with slowly varying and possibly converging characteristics. In such situations, it’s worthwhile to update the subproblem solutions, rather than solving from scratch.
In this paper we describe simplex-like updating of the SP trees, using thread labels.
We suggest three improvements to the standard approach:

  • Thread following link scan,
  • bucketed link scan, and
  • acyclic thread

    In thread following link scan, we only need a single traversal of the thread to find all entering links.
    In the bucketed link scan, we do partial pricing. Instead of scanning all arcs, we keep and update a "bucket'' of "promising'' links. This gives suboptimal subproblem solutions, but speeds up the convergence. Every now and then, we do a complete scan, and then add and delete links to/from the buckets.
    In acyclic thread, the thread is modified to scan an acyclic graph, i.e., the graph of bucket links. The acyclic thread scans the nodes in the graph-induced order, and does not need to be updated, unless new arcs are added.
    We will present computational results for small to large scale traffic assignment problems.


    Talk 3 of the contributed session Thu.2.H 3503
    "Paths, trees and flows" [...]
    Cluster 23
    "Telecommunications & networks" [...]


  •   The main criterion for them is your ability to repay any Wisconsin Payday Loans, they are not interested in your previous attempts, the current one is all that matters. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra In Canada influence on blood clots.