Duality in convex minimum cost flow problems on infinite networks and hypernetworks

Duality in convex minimum cost flow problems on infinite networks and hypernetworks

0.00 Avg rating0 Votes
Article ID: iaor20173431
Volume: 70
Issue: 2
Start Page Number: 98
End Page Number: 115
Publication Date: Sep 2017
Journal: Networks
Authors: ,
Keywords: combinatorial optimization, networks, networks: flow, programming: convex, heuristics
Abstract:

Minimum cost flow problems on infinite networks arise, for example, in infinite‐horizon sequential decision problems such as production planning. Strong duality for these problems was recently established for linear costs using an infinite‐dimensional Simplex algorithm. Here, we use a different approach to derive duality results for convex costs. We formulate the primal and dual problems in appropriately paired sequence spaces such that weak duality and complementary slackness can be established using finite‐dimensional proof techniques. We then prove, using a planning horizon proof technique, that the absence of a duality gap between carefully constructed finite‐dimensional truncations of the primal problem and their duals is preserved in the limit. We then establish that strong duality holds when optimal solutions to the finite‐dimensional duals are bounded. These theoretical results are illustrated via an infinite‐horizon shortest path problem. We also extend our results to infinite hypernetworks and apply this generalization to an infinite‐horizon stochastic shortest path problem.

Reviews

Required fields are marked *. Your email address will not be published.