Mean-Standard Deviation Model for Minimum Cost Flow Problem
Sponsor
Data-Supported Transportation Operations and Planning University Transportation Center; National Science Foundation, Grant/Award Numbers: CMMI-1826320/1826337, CMMI-1562109/1562291, CMMI-1254921.
Published In
Networks
Document Type
Citation
Publication Date
12-7-2022
Abstract
We study the mean-standard deviation minimum cost flow (MSDMCF) problem, where the objective is minimizing a linear combination of the mean and standard deviation of flow costs. Due to the nonlinearity and nonseparability of the objective, the problem is not amenable to the standard algorithms developed for network flow problems. We prove that the solution for the MSDMCF problem coincides with the solution for a particular mean-variance minimum cost flow (MVMCF) problem. Leveraging this result, we propose bisection (BSC), Newton–Raphson (NR), and a hybrid (NR-BSC)—method seeking to find the specific MVMCF problem whose optimal solution coincides with the optimal solution for the given MSDMCF problem. We further show that this approach can be extended to solve more generalized nonseparable parametric minimum cost flow problems under certain conditions. Computational experiments show that the NR algorithm is about twice as fast as the CPLEX solver on benchmark networks generated with NETGEN.
Rights
© 2022 Wiley Periodicals LLC.
Locate the Document
DOI
10.1002/net.22135
Persistent Identifier
https://archives.pdx.edu/ds/psu/39032
Citation Details
Gokalp, C., Boyles, S. D., & Unnikrishnan, A. (2019). Mean‐standard deviation model for minimum cost flow problem. Networks.