Geoffrion's theorem beyond finiteness and rationality
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914089689677824 |
|---|---|
| author | Dey, Santanu S. Meunier, Frédéric Ramirez, Diego Moran |
| author_facet | Dey, Santanu S. Meunier, Frédéric Ramirez, Diego Moran |
| contents | 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 linear constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_10966 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Geoffrion's theorem beyond finiteness and rationality Dey, Santanu S. Meunier, Frédéric Ramirez, Diego Moran Optimization and Control Discrete Mathematics 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 linear constraints. |
| title | Geoffrion's theorem beyond finiteness and rationality |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2510.10966 |