Groupe d’études et de recherche en analyse des décisions

Decomposition methods for solving large-scale dynamic network flow problems

Robert Curry Mathematics Department, United States Naval Academy, États-Unis

Robert Curry

Various network applications require dynamic flows to be transmitted according to a non-simultaneous schedule. In this talk, we consider a dynamic network flow problem that considers the presence of arc set up costs that may exist whenever an arc begins transmitting flow. This problem can be modeled by the minimum cost flow problem having arc-activation costs (MCF-A), in which arc \((i,j)\) is said to be activated on a path \(p\) when \((i,j)\) is included on \(p\) but not on \(p-1\). As an alternative to this mixed-integer programming approach, we employe a relaxation-based decomposition algorithm for obtaining upper and lower bounds that increases the number of paths in a schedule, as needed. Computational results show that our approach determines an optimal solution in significantly less time than a mixed-integer programming approach. Finally, we extend our algorithm to consider other network flow problems.

Bio: Rob Curry is an Assistant Professor in the Mathematics Department at the United States Naval Academy. His research concentrates on methodology and algorithmic approaches in network optimization, combinatorial optimization, and integer programming. In particular, he studies exact algorithms for large-scale network flow optimization problems having applications in energy systems, wireless sensor networks, and humanitarian logistics. His most recent work focuses on decomposition methods for variations of maximum flow and minimum cost flow problems in wireless sensor network settings. He received his B.S. in Industrial Engineering from the University of Arkansas (2013), his M.S. in Industrial & Systems Engineering from the University of Florida (2014), and his Ph.D. in Industrial Engineering from Clemson University (2018).


Entrée gratuite.
Bienvenue à tous!