Retour aux activités
Séminaire du GERAD

Decomposition methods for solving large-scale dynamic network flow problems


12 août 2019   14h00 — 15h00

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!

Andrea Lodi responsable


Salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour Montréal QC H3T 1J4 Canada

Organisme associé