Parametric Multiroute Flow and Its Application to Robust Network with k Edge Failures.
Parametric Multiroute Flow and Its Application to Robust Network with k Edge Failures.
复制标题
参数多路由流及其在具有 k 边故障的鲁棒网络中的应用。
DOI：
10.1007/978-3-319-09174-7_3
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
and Hiroshi Imai
中科院分区：
文献类型：
--
作者：
Jean-Francois Baffier;Vorapong Suppakitpaisarn;Hidefumi Hiraishi;and Hiroshi Imai
在这项工作中，我们研究了将实际值取最大路由流值的函数的属性，并将结果应用于解决鲁棒网络流问题。我们证明该函数是分段双曲函数，并修改参数优化技术（ES 算法）来找到该函数。算法的运行时间是，当 是我们网络的源-汇边缘连通性时， 是链路数， 是节点数。我们可以使用该算法的结果来解决针对边缘故障的两个最大流问题，称为最大 MLA 鲁棒流和最大 MLA 可靠流。当从函数中最优选择时，我们表明 max--route 流是特定类中图的两个问题的精确解。我们的数值实验表明，实验中生成的随机图属于该特定类别。给定参数边缘，我们还表明，将容量设为最大路由流量值的函数是分段线性的。因此，我们可以应用修改后的 ES 算法来查找该函数。
In this work, we investigate properties of the function taking the real valueto the max-route flow value, and apply the result to solve robust network flow problems. We show that the function is piecewise hyperbolic, and modify a parametric optimization technique, the ES algorithm, to find this function. The running time of the algorithm is, whenis a source-sink edge connectivity of our network,is the number of links, andis the number of nodes. We can use the result from that algorithm to solve two max-flow problems againstedge failures, referred to as max-MLA-robust flow and max-MLA-reliable flow. Whenis optimally chosen from the function, we show that the max--route flow is an exact solution of both problems for graphs in a specific class. Our numerical experiments show thatof random graphs generated in the experiment are in that specific class. Given a parametric edge, we also show that the function taking the capacity ofto the max--route flow value is linear piecewise. Hence we can apply our modified ES algorithm to find that function in.