2017/05/23 by Fabian Mies, Mies, Fabian, Britta Peis +3
Computer Science · Engineering · #Advanced Multi-Objective Optimization Algorithms #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1705.08161
openalex publication_date 2017/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Real world networks are often subject to severe uncertainties which need to be addressed by any reliable prescriptive model. In the context of the maximum flow problem subject to arc failure, robust models have gained particular attention. For a path-based model, the resulting optimization problem is assumed to be difficult in the literature, yet the complexity status is widely unknown. We present a computational approach to solve the robust flow problem to optimality by simultaneous primal and dual separation, the practical efficacy of which is shown by a computational study. Furthermore, we introduce a novel model of robust flows which provides a compromise between stochastic and robust optimization by assigning probabilities to groups of scenarios. The new model can be solved by the same computational techniques as the robust model. A bound on the generalization error is proven for the case that the probabilities are determined empirically. The suggested model as well as the computational approach extend to linear optimization problems more general than robust flows.