Inverse Generalized Maximum Flow Problems

Mathematics

Javad Tayyebi¹  Adrian Deaconu² 

[1] Department of Industrial Engineering, Birjand University of Technology, Birjand 9719866981, Iran;Department of Mathematics and Computer Science, Transilvania University, Brasov 500091, Romania;

关键词: generalized maximum flow;    inverse optimization;    np-hardness;    hamming distance;   

DOI  :  10.3390/math7100899

来源: DOAJ

【 摘 要 】

A natural extension of maximum flow problems is called the generalized maximum flow problem taking into account the gain and loss factors for arcs. This paper investigates an inverse problem corresponding to this problem. It is to increase arc capacities as less cost as possible in a way that a prescribed flow becomes a maximum flow with respect to the modified capacities. The problem is referred to as the generalized maximum flow problem (IGMF). At first, we present a fast method that determines whether the problem is feasible or not. Then, we develop an algorithm to solve the problem under the max-type distances in $O(mn·logn)$ time. Furthermore, we prove that the problem is strongly NP-hard under sum-type distances and propose a heuristic algorithm to find a near-optimum solution to these NP-hard problems. The computational experiments show the accuracy and the efficiency of the algorithm.

【 授权许可】

Unknown