A novel approach to subgraph selection with multiple weights on arcs

Mohammad Ali Raayatpanah (), Salman Khodayifar (), Thomas Weise () and Panos Pardalos ()
Additional contact information
Mohammad Ali Raayatpanah: Kharazmi University
Salman Khodayifar: Institute for Advanced Studies in Basic Sciences (IASBS)
Thomas Weise: Hefei University
Panos Pardalos: University of Florida

Journal of Combinatorial Optimization, 2022, vol. 44, issue 1, No 12, 242-268

Abstract: Abstract In this paper, an extension of the minimum cost flow problem is considered in which multiple incommensurate weights are associated with each arc. In the minimum cost flow problem, flow is sent over the arcs of a graph from source nodes to sink nodes. The goal is to select a subgraph with minimum associated costs for routing the flow. The problem is tractable when a single weight is given on each arc. However, in many real-world applications, several weights are needed to describe the features of arcs, including transit cost, arrival time, delay, profit, security, reliability, deterioration, and safety. In this case, finding an optimal solution becomes difficult. We propose a heuristic algorithm for this purpose. First, we compute the relative efficiency of the arcs by using data envelopment analysis techniques. We then determine a subgraph with efficient arcs using a linear programming model, where the objective function is based on the relative efficiency of the arcs. The flow obtained satisfies the arc capacity constraints and the integrality property. Our proposed algorithm has polynomial runtime and is evaluated in rigorous experiments.

Keywords: Network optimization; Data envelopment analysis; Efficiency; Linear programming; Combinatorial optimization (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00823-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:44:y:2022:i:1:d:10.1007_s10878-021-00823-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00823-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().