Speaker: Esra Koca (Department of Industrial Engineering at Sabancı University)
Title: Models and Algorithms for Discrete and Continuous Edge Improvement Problems
Date: 25h April 2025 (Friday)
Time: 13:30-14:30
Place: EA409
Abstract
This talk focuses on the edge improvement problem, where the traditional assumption of fixed edge traversal times in network flow problems is relaxed. Two variants are considered: one with discrete improvement options and another with continuous improvements within specified bounds. The study begins with an analysis of both variants on tree-shaped networks, followed by a more general treatment for arbitrary network topologies through mixed-integer programming (MIP) formulations. This work is the first to propose and compare formulations for the discrete variant and to present a mathematical model for the continuous version. To address scalability issues in large problem instances, we develop a Benders decomposition algorithm for the discrete case and adapt it as a heuristic to generate high-quality solutions for the continuous variant. Additionally, we devise an MIP formulation to compute lower bounds for the continuous edge improvement problem, leveraging McCormick envelopes and structural properties of optimal solutions. Computational experiments demonstrate that the proposed methods are effective: the decomposition algorithm outperforms alternative formulations for the discrete case, while the heuristic delivers strong results on large instances of the continuous variant.
Short Bio:
Esra Koca has been a faculty member in the Industrial Engineering Program at Sabancı University since 2015. She received her B.Sc. and M.Sc. degrees, and earned her Ph.D. in 2015, all in Industrial Engineering from Bilkent University. Her research focuses on developing efficient and exact solution methods for large-scale and complex optimization problems in production, transportation and service systems. She works on both deterministic and stochastic programming models, and her recent research focuses on optimization problems arising in shared mobility systems, disaster preparedness, network flow models, and inventory routing.