EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
4229. Formulations and Algorithms for the Edge Improvement Problems
Invited abstract in session WA-25: Topics in Integer Programming I, stream Combinatorial Optimization.
Wednesday, 8:30-10:00Room: 011 (building: 208)
Authors (first author is the speaker)
| 1. | Esra Koca
|
| Industrial Engineering, Sabanci University | |
| 2. | Burak Pac
|
| Industrial Engineering, Gebze Technical University |
Abstract
We explore the edge improvement problem, relaxing the fixed edge traversal times assumption in traditional network flow problems. We consider two versions: discrete edge improvement, limited to a discrete set, and continuous edge improvement, where values can vary within a given range. Initially, we analyze both versions on a tree-shaped network, discussing their computational complexity. For more complex networks, we develop mixed-integer programming (MIP) formulations for both versions. This study is the first to propose and compare different formulations for the discrete edge improvement problem and to present one for the continuous version. Since our models underperform for medium and large problem instances, we introduce a Benders decomposition algorithm to solve the discrete problem. Additionally, we use it heuristically to find high-quality solutions for the continuous edge improvement problem efficiently. We also devise an MIP formulation to determine lower bounds for the continuous problem, leveraging McCormick envelopes and optimal solution properties. Our experiments show that the Benders decomposition algorithm outperforms other formulations for the discrete edge improvement problem, while the heuristic method proposed for the continuous problem provides quite good results even for large instances.
Keywords
- Programming, Mixed-Integer
- Mathematical Programming
- Network Flows
Status: accepted
Back to the list of papers