Exploring the discrete and continuous edge improvement problems: Models and algorithms

Esra Koca and A. Burak Paç

European Journal of Operational Research, 2025, vol. 323, issue 2, 441-454

Abstract: In this paper, we investigate the edge improvement problem where the fixed edge traversal time assumption of the traditional network flow problems is relaxed. We consider two variants of the problem: one where improvement decisions are restricted to a discrete set (discrete edge improvement problem), and the other where they can take any value within a specified range (continuous edge improvement problem). We first analyze both problem variants on a tree-shaped network and discuss their computational complexities. For the general case, where the underlying network has no special structure, we provide mixed-integer programming (MIP) formulations for both versions of the problem. To the best of our knowledge, this study is the first to propose and compare different formulations for the discrete edge improvement problem and to present a formulation for the continuous edge improvement problem. Since the developed models do not perform well for medium and large problem instances, we introduce a Benders decomposition algorithm to solve the discrete edge improvement problem. Additionally, we employ it heuristically to find high-quality solution for the continuous edge improvement problem within reasonable times. We also devise an MIP formulation to find lower bounds for the continuous edge improvement problem, leveraging the McCormick envelopes and optimal solution properties. Our experiments demonstrate that the Benders decomposition algorithm outperforms the other formulations for the discrete edge improvement problem, while the heuristic method proposed for the continuous edge improvement problem provides quite well results even for large problem instances.

Keywords: Networks; Network improvement; Mixed integer programming; Benders decomposition; McCormick envelopes (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724009937
Full text for ScienceDirect subscribers only

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:eee:ejores:v:323:y:2025:i:2:p:441-454

DOI: 10.1016/j.ejor.2024.12.051

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().