1 — 14:00 — From the Relaxation Method to Chubanov’s Algorithm, from ACCPM to Tall LPs.
Jean-Luis Goffin made numerous notable contributions through his academic career. In this talk we highlight two themes: (1) The Relaxation Method, that was more recently rediscovered and in variants proved to be polynomial time algorithms to solve linear inequalities and linear optimization (LO) problems; (2) The Analytic Center Cutting Plane Method (ACCPM), that can be put in the context of the recently expanding interest in solving “Tall LO” problems.
2 — 14:30 — A personal view of primal-dual interior-point algorithms for large-scale optimization and some recent developments
This presentation will have two main ingredients. One ingredient lies in the in the area of primal-dual interior-point algorithms for large-scale convex optimization and it will be a summary of recent research results my co-authors and I have obtained. The other ingredient will be a summary of how some of my research work over the last 30+ years relates to Jean-Louis Goffin's outstanding contributions.
3 — 15:00 — Analytic Centres and Mixed Integer Programming
J-L Goffin's work on ACCPM inspired a number of approaches in solving mixed integer programming problems. We explore, exact, heuristic, and decomposition based approaches, as well as recent work on inverse integer optimization.
4 — 15:30 — Local center cutting plane methods framework
Centering methods are best known for solving convex nondifferentiable optimization problems which have a polynomial bound on the number of iterations, i.e., the number of calls to the separation oracle. These methods solve, at each iteration, an optimization problem that is often nonlinear, aiming to find a primal-dual center of the approximation polyhedron. While preserving the advantages of these methods, this paper presents a novel primal approach by integrating the Centering (interior point) methods into the Improved Primal Simplex decomposition. We propose a new procedure to generate columns/cutting planes. Specifically, we optimize in the subspace spanned by columns associated with non-degenerate variables of the current solution, where the optimization is efficient and we do not need to calculate a center. If we cannot improve the objective value, we enhance the quality of generated columns in the complementary subspace using a "local center". This novel way of generating columns (or cuts) allows us to reduce the number of calls to the procedure for finding centers.