Back to activities
GERAD seminar

Decomposition methods for solving large-scale dynamic network flow problems

iCalendar

Aug 12, 2019   02:00 PM — 03:00 PM

Robert Curry Mathematics Department, United States Naval Academy, United States

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).


Free entrance.
Welcome to everyone!

Andrea Lodi organizer

Location

Room 4488
André-Aisenstadt Building
Université de Montréal Campus
2920, chemin de la Tour
Montréal QC H3T 1J4
Canada

Associated organization

Research Axes

Research applications