Robust minimum cost flow problem under consistent flow constraints

Christina Büsing (), Arie M. C. A. Koster () and Sabrina Schmitz ()
Additional contact information
Christina Büsing: RWTH Aachen University
Arie M. C. A. Koster: RWTH Aachen University
Sabrina Schmitz: RWTH Aachen University

Annals of Operations Research, 2022, vol. 312, issue 2, No 5, 722 pages

Abstract: Abstract The robust minimum cost flow problem under consistent flow constraints (RobMCF $$\equiv $$ ≡ ) is a new extension of the minimum cost flow (MCF) problem. In the RobMCF $$\equiv $$ ≡ problem, we consider demand and supply that are subject to uncertainty. For all demand realizations, however, we require that the flow value on an arc needs to be equal if it is included in the predetermined arc set given. The objective is to find feasible flows that satisfy the equal flow requirements while minimizing the maximum occurring cost among all demand realizations. In the case of a finite discrete set of scenarios, we derive structural results which point out the differences with the polynomial time solvable MCF problem in networks with integral demands, supplies, and capacities. In particular, the Integral Flow Theorem of Dantzig and Fulkerson does not hold. For this reason, we require integral flows in the entire paper. We show that the RobMCF $$\equiv $$ ≡ problem is strongly $$\mathcal {NP}$$ NP -hard on acyclic digraphs by a reduction from the (3, B2)-Sat problem. Further, we demonstrate that the RobMCF $$\equiv $$ ≡ problem is weakly $$\mathcal {NP}$$ NP -hard on series-parallel digraphs by providing a reduction from Partition. If in addition the number of scenarios is constant, we propose a pseudo-polynomial algorithm based on dynamic programming. Finally, we present a special case on series-parallel digraphs for which we can solve the RobMCF $$\equiv $$ ≡ problem in polynomial time.

Keywords: Minimum cost flow problem; Equal flow problem; Robust flows; Series-parallel digraphs; Dynamic programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-04426-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:312:y:2022:i:2:d:10.1007_s10479-021-04426-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-021-04426-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().