997. Flows over time with minimum peak cost
Invited abstract in session MB-55: Network Optimization 2, stream Network Optimization.
Monday, 10:30-12:00Room: Liberty 1.09
Authors (first author is the speaker)
| 1. | Mariia Anapolska
|
| RWTH Aachen University | |
| 2. | Emma Ahrens
|
| Lehr- und Forschungsgebiet Kombinatorische Optimierung, RWTH Aachen University | |
| 3. | Christina Büsing
|
| Lehr- und Forschungsgebiet Kombinatorische Optimierung, RWTH Aachen University | |
| 4. | Felix Engelhardt
|
| Research and Teaching Area Combinatorial Optimization, RWTH Aachen University | |
| 5. | Timo Gersing
|
| RWTH Aachen University | |
| 6. | Corinna Mathwieser
|
| RWTH Aachen University | |
| 7. | Sabrina Schmitz
|
| Combinatorial Optimization, RWTH Aachen University | |
| 8. | Sophia Wrede
|
| RWTH Aachen University |
Abstract
Flows over time extend the classical network flows by a temporal component: it takes a certain amount of time for particles to traverse every arc. We introduce a novel objective for flows over time called peak cost. The peak cost is a min-max type objective that describes the maximum cost a flow incurs at some moment of its time horizon, and thus models the amount of workforce or energy necessary to run a system at all times.
In the resulting optimisation problem, we focus on temporally repeated flows due to their tractability and hence study the complexity of the Minimum-Peak-Cost Temporally Repeated Flow problem (MPC-TRF). As some applications require integral solutions, we consider not only the general fractional version, but also the integral version of the problem.
We show that both the decision version and the optimisation version of integral MPC-TRF are strongly NP-hard, even under strong restrictions. At the same time, we identify two special cases for which, although the integral problem remains NP-hard for general demand values, an optimal maximum flow can be found in polynomial time: (i) unit-cost series-parallel networks and (ii) networks with a time horizon at least two times longer than the longest path in the network (with respect to the transit time). Furthermore, in the two listed cases, we provide polynomial-time solution approaches for the fractional version of MPC-TRF, the complexity of which in general remains open.
Keywords
- Network Flows
- Complexity and Approximation
- Combinatorial Optimization
Status: accepted
Back to the list of papers