Mean‐standard deviation model for minimum cost flow problem
Mean‐standard deviation model for minimum cost flow problem
复制标题
DOI：
10.1002/net.22135
复制
发表时间：
2022-12
期刊：
影响因子：
2.1
通讯作者：
C. Gokalp;S. Boyles;A. Unnikrishnan
中科院分区：
文献类型：
--
作者：
C. Gokalp;S. Boyles;A. Unnikrishnan
我们研究了平均-标准差最小费用流(MSDMCF)问题，其中目标是最小化流费用的平均和标准差的线性组合。由于目标的非线性性和不可分离性，该问题不适用于为网络流问题开发的标准算法。证明了MSDMCF问题的解与一类特殊的均值-方差最小费用流问题的解是一致的。利用这一结果，我们提出了二分(BSC)、牛顿-拉夫森(NR)和混合(NR-BSC)方法，试图找到特定的MVMCF问题的最优解与给定MSDMCF问题的最优解重合。在一定条件下，我们进一步证明了该方法可以推广到求解更广义的不可分参数最小费用流问题。计算实验表明，在使用NETGEN生成的基准网络上，NR算法的速度大约是CPLEX求解器的两倍。
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.