Robust transshipment problem under consistent flow constraints

DOI10.1002/NET.22184MaRDI QIDQ6180042zbMATH OpenFDO

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

Publication date 18 January 2024

Published in Networks (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

demand uncertaintyequal flow problemminimum cost flowrobust flowsseries-parallel digraphstransshipment problem

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06)

Abstract: In this paper, we study robust transshipment under consistent flow constraints. We consider demand uncertainty represented by a finite set of scenarios and characterize a subset of arcs as so-called fixed arcs. In each scenario, we require an integral flow that satisfies the respective flow balance constraints. In addition, on each fixed arc, we require equal flow for all scenarios. The objective is to minimize the maximum cost occurring among all scenarios. We show that the problem is strongly NP-hard on acyclic digraphs by a reduction from the $(3,B2)$-SAT problem. Furthermore, we prove that the problem is weakly NP-hard on series-parallel digraphs by a reduction from a special case of the extsc{Partition} problem. If in addition the number of scenarios is constant, we observe the pseudo-polynomial-time solvability of the problem. We provide polynomial-time algorithms for three special cases on series-parallel digraphs. Finally, we present a polynomial-time algorithm for pearl digraphs.

Recommendations

• Robust minimum cost flow problem under consistent flow constraints
• Complexity of strict robust integer minimum cost flow problems: an overview and further results
• The complexity of computing a robust flow
• On robust maximum flow with polyhedral uncertainty sets
• Robust flows over time: models and complexity results

Cites work

• Combinatorial optimization. Theory and algorithms.
• Computationally Related Problems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2090007 (Why is no real title available?)
• Integer equal flows
• Integer Programming with a Fixed Number of Variables
• Integrality in the multinetwork min‐cost equal‐flow problem
• Minimum cost flows with minimum quantities
• 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.
• 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 equal flow problem
• The maximum flow problem with disjunctive constraints
• The Price of Robustness
• The Recognition of Series Parallel Digraphs
• The robust network loading problem under hose demand uncertainty: formulation, polyhedral analysis, and computations

Cited in

(1)

• Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints

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

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