Inverse Generalized Maximum Flow Problems

Javad Tayyebi and Adrian Deaconu
Additional contact information
Javad Tayyebi: Department of Industrial Engineering, Birjand University of Technology, Birjand 9719866981, Iran
Adrian Deaconu: Department of Mathematics and Computer Science, Transilvania University, Brasov 500091, Romania

Mathematics, 2019, vol. 7, issue 10, 1-15

Abstract: 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 ( m n · log n ) 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.

Keywords: generalized maximum flow; inverse optimization; NP-hardness; Hamming distance (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/10/899/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/10/899/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:10:p:899-:d:270721

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().