Groupe d’études et de recherche en analyse des décisions

Recent Progress with Interior-Point/Cutting-Plane Methods in Combinatorial Optimization

Alexander Engau University of Colorado Denver, États-Unis

This presentation will give a broad overview of some of the recent enhancements of interior-point algorithms for the improved solution of linear/semidefinite relaxations in combinatorial optimization and binary quadratic programming. Our central topics are planned to cover general interior-point cutting-plane schemes, the efficient handling of free variables and large numbers of linear inequalities, and several warm-starting strategies. Considering applications from graph theory and combinatorics, facility layout design, and molecular biology, this talk will conclude with a brief discussion of selected computational results and summarize open questions for further research.