Frédéric Meunier - Geoffrion's theorem beyond finiteness and rationality

Speaker: Frédéric Meunier

Title: Geoffrion's theorem beyond finiteness and rationality

Room: A707

Date: 30/03/2026

Abstract:

Geoffrion's theorem is a fundamental result from mathematical programming assessing the quality of Lagrangian relaxation, a standard technique to get bounds for integer programs. An often implicit condition is that the set of feasible solutions is finite or described by rational linear constraints. However, we show through concrete examples that the conclusion of Geoffrion's theorem does not necessarily hold when this condition is dropped. We then provide sufficient conditions ensuring the validity of the result even when the feasible set is not finite and cannot be described using finitely-many rational linear constraints. Joint work with Santanu Dey and Diego A. Morán R.