Session: Nonconvex Optimization and Applications
Chair: Bissan Ghaddar
Cluster: Interplay Between Continuous and Discrete Optimization
Talk 1: Solution framework for the facility location problem under endogenous road congestion
Speaker: Marten Soer
Abstract: We consider a bi-level optimization problem, where the upper-level decision maker chooses locations of facilities, by minimizing the total system travel time of the lower-level decision makers. While the lower-level decision makers, in turn, choose their fastest routes to the facilities. When the number of lowerlevel decision makers is large, their route choices affect the road congestion and thus the travel times. This setup is inspired by locating remote offices within the highly congested road network of Mexico City, but it is also applicable to other problems, such as the placement of electric vehicle charging stations and modeling electricity networks. To the best of our knowledge, the current literature focuses on finding a heuristic solution approach due to the complexity of the problem, and no approximation or exact solution framework for large instances exist. We study the properties of the problem and introduce an approximation algorithm that allows evaluating the quality of existing solutions and obtaining new close-to-optimal solutions. Moreover, we conduct numerical experiments in real-life instances to illustrate the applicability of the proposed endogenous road congestion solution framework and the effect when opening facility locations.
Talk 2: Finding long TSP tours in the unit square using the FICO Xpress global optimization solver
Speaker: Imre Polik
Abstract: We will investigate the problem of finding a set of points in the unit square such that the length of the optimal TSP tour over them is maximal. We will look at some interesting duality relations and provide nonconvex quadratic computational formulations. Additionally, we will look at related problems such as matching and the minimum pairwise distance. The theory will enable us to conduct computational experiments with the FICO Xpress global optimization MINLP solver and to find previously unknown optimal configurations. We will present some theoretical results and formulate several conjectures.
Talk 3: Facial Reduction for Semidefinite Relaxations of Combinatorial Optimization Problems
Speaker: Hao Hu
Abstract: In this talk, we present new findings on facial reduction for semidefinite relaxations of combinatorial optimization problems. In semidefinite programming (SDP), Slater’s condition is crucial for both theoretical convergence guarantees and the practical performance of optimization algorithms. When Slater’s condition fails, facial reduction can restore it through a finite sequence of reformulations. However, these reformulations often involve solving auxiliary optimization problems that can be as challenging as the original. Recent research has therefore focused on developing more efficient strategies for performing facial reduction. In our work, we specifically consider SDP problems that arise as relaxations of combinatorial optimization problems. This perspective enables us to exploit the underlying combinatorial structure, allowing the development of novel and highly efficient facial reduction techniques. We also establish theoretical results demonstrating the effectiveness of our approach. Numerical experiments further show that applying our specialized facial reduction method significantly improves both the speed and accuracy of solving SDP problems.
