Robust minimum cost flow problem under consistent flow constraints

Artikel

The robust minimum cost flow problem under consistent flow constraints (RobMCF≡\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\equiv $$\end{document}) is a new extension of the minimum cost flow (MCF) problem. In the RobMCF≡\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\equiv $$\end{document} 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≡\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\equiv $$\end{document} problem is strongly NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {NP}$$\end{document}-hard on acyclic digraphs by a reduction from the (3, B2)-Sat problem. Further, we demonstrate that the RobMCF≡\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\equiv $$\end{document} problem is weakly NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {NP}$$\end{document}-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≡\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\equiv $$\end{document} problem in polynomial time.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Journal: Annals of Operations Research ; ISSN: 1572-9338 ; Volume: 312 ; Year: 2021 ; Issue: 2 ; Pages: 691-722 ; New York, NY: Springer US

Klassifikation und Themen

• Klassifikation: Allgemeines, Wissenschaft
• Thema: Minimum cost flow problem ; Equal flow problem ; Robust flows ; Series-parallel digraphs ; Dynamic programming

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Büsing, Christina ; Koster, Arie M. C. A. ; Schmitz, Sabrina
• Ereignis: Veröffentlichung
• (wer): Springer US
• (wo): New York, NY
• (wann): 2021

Weitere Informationen

• DOI: doi:10.1007/s10479-021-04426-0
• Letzte Aktualisierung: 10.03.2025, 11:42 MEZ