Robust minimum cost flow problem under consistent flow constraints

DOI10.1007/S10479-021-04426-0MaRDI QIDQ2673801zbMATH OpenOpenAlexFDO

Authors Christina Büsing, Arie M. C. A. Koster, Sabrina Schmitz

Publication date 13 June 2022

Published in Annals of Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2008.02035

zbMATH Keywords

dynamic programmingminimum cost flow problemseries-parallel digraphsequal flow problemrobust flows

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39) Robustness in mathematical programming (90C17)

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 discrete set of scenarios, we derive structural results which point out the differences with the polynomial time solvable MCF problem on networks with integral 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 $mathcalNP$-hard on acyclic digraphs by a reduction from the $(3,B2)$-Sat problem. Further, we demonstrate that the RobMCF$equiv$ problem is weakly $mathcalNP$-hard on series-parallel digraphs by providing a reduction from Partition and a pseudo-polynomial algorithm based on dynamic programming. Finally, we propose a special case on series-parallel digraphs for which we can solve the RobMCF$equiv$ problem in polynomial time.

Recommendations

• Complexity of strict robust integer minimum cost flow problems: an overview and further results
• On robust maximum flow with polyhedral uncertainty sets
• Robust and adaptive network flows
• Minimum cost flows with minimum quantities
• Robust discrete optimization and network flows

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2090007 (Why is no real title available?)
• Affine recourse for the robust network design problem: between static and dynamic routing
• Algorithms for the simple equal flow problem
• Combinatorial optimization. Theory and algorithms.
• Computationally Related Problems
• Integer Programming with a Fixed Number of Variables
• Integer equal flows
• Minimum cost flow algorithms for series-parallel networks
• Minimum cost flows with minimum quantities
• Models and algorithms for robust network design with several traffic scenarios
• Multi-layer MPLS network design: The impact of statistical multiplexing
• Network flow optimization with minimum quantities
• Network flows. Theory, algorithms, and applications.
• Network models for vehicle and crew scheduling
• Network simplex algorithm for the general equal flow problem.
• Networks synthesis and optimum network design problems: Models, solution methods and applications
• Provisioning virtual private networks under traffic uncertainty
• Robust discrete optimization and network flows
• Robust network design: formulations, valid inequalities, and computations
• Single-commodity robust network design with finite and hose demand sets
• The Price of Robustness
• The Recognition of Series Parallel Digraphs
• The equal flow problem
• The maximum flow problem with disjunctive constraints
• The robust network loading problem under hose demand uncertainty: formulation, polyhedral analysis, and computations
• The robust network loading problem with dynamic routing
• Two-Stage Robust Network Flow and Design Under Demand Uncertainty

Cited in

(8)

• On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows
• Complexity of strict robust integer minimum cost flow problems: an overview and further results
• Algorithms and complexity for the almost equal maximum flow problem
• Robust transshipment problem under consistent flow constraints
• Integrality in the multinetwork min‐cost equal‐flow problem
• Mean‐standard deviation model for minimum cost flow problem
• Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints
• Robust Minimum-Cost Flow Problems Under Multiple Ripple Effect Disruptions

This page was built for publication: Robust minimum cost flow problem under consistent flow constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2673801)