Chair: Luckny Zéphyr, Laval University, Canada
Exploiting Set-Based Structures to Accelerate Dynamic Programming Algorithms for the Elementary Shortest Path Problem with Resource Constraints
Troels Martin Range (firstname.lastname@example.org)
The Elementary Shortest Path Problem with Resource Constraints (ESPPRC) is the problem of identifying a least cost path through a network having real-valued arc costs such that the path is acyclic and a set of resource constraints are satisfied. ESPPRC arises as the pricing problem of the Dantzig-Wolfe decomposition of the Vehicle Routing Problem with Resource Constraints. The predominant approach for solving ESPPRC is dynamic programming which relies on extension of paths. If paths are allowed to revisit nodes then extensions to the same node can be compared by cost and resource consumption in order to eliminate dominated extensions. However, as a path is required to be acyclic it can never be extended back to an already visited node and dominance in resources and cost is not sufficient for eliminating a path. Instead an additional requirement is imposed that the dominant path has to be able to visit any reachable node of the dominated path. Consequently, the set of unreachable nodes for the dominant path has to be a subset of the set of unreachable nodes for the dominated path. Due to this requirement the number of undominated paths may increase drastically. A linear search through the undominated paths is typically commenced for checking dominance. But as the number of undominated paths can be very large this check may be time consuming. We present an alternative approach for checking dominance based on a prefix tree data structure. The approach enables us to exclusively identify paths having sets of unreachable nodes which are either subsets or supersets of a given set. In doing so, we reduce the number of dominance checks performed and thereby speedup the algorithm. We observe that for instances, resulting in a large number of undominated paths, this approach is significantly faster than the approach using a simple linear search.
Keywords: Elementary Shortest Path Problem with Resource Constraints, Dynamic Programming, Prefix Tree
Controlled approximation of the SDP Value Function for Multi-Reservoir Systems
Luckny Zéphyr (email@example.com), Pascal Lang (firstname.lastname@example.org), Bernard F. Lamond (email@example.com), Pascal Côté (Pascal.Cote@riotinto.com)
We present an approximation of the Stochastic Dynamic Programming (SDP) value function based on a partition of the state space into simplices. The vertices of such simplices form an irregular grid over which the value function is computed. Under convexity assumptions, lower and upper bounds are developed over the state space continuum. The partition is then reﬁned where the gap between these bounds is largest. This process readily provides a controllable trade-oﬀ between accuracy and solution time.
Keywords: Simplicial approximation, stochastic dynamic programming, reservoir systems