Geoffrion's theorem beyond finiteness and rationality

Santanu S. Dey, Frédéric Meunier, Diego Alejandro Morán Ramírez

Geoffrion's Theorem Beyond Finiteness and Rationality

Geoffrion’s theorem is a cornerstone of mathematical optimization that guarantees the tightness of Lagrangian relaxation for integer programs, provided the feasible set is finite or rational. This research demonstrates that the theorem can fail in more general settings—such as infinite sets or non-rational polyhedra—and establishes new sufficient conditions to ensure the theorem remains valid "beyond finiteness and rationality."

The Problem: When Lagrangian Relaxation Fails

In integer programming, Lagrangian relaxation is used to find lower bounds for difficult minimization problems by moving "hard" constraints into the objective function with a penalty. Geoffrion’s Theorem (1974) is the theoretical backbone of this method, stating that the best possible lower bound from Lagrangian relaxation ($v^L$) is exactly equal to the optimal value of the problem when the discrete set of points $X$ is replaced with its convex hull ($v^*$).

However, the original proof assumes $X$ is either finite or the set of integer points in a rational polyhedron. The authors identify a gap: in the real world, irrational coefficients can arise in non-linear or geometry-based optimization. When these standard assumptions are dropped, the "integrality property" of Lagrangian relaxation may no longer hold.

Counterexamples and Geometric Insights

The authors provide elegant examples where the Lagrangian bound $v^L$ is strictly worse than the convex hull bound $v^*$. These failures often stem from the fact that the convex hull of integer points in non-rational polyhedra may not be closed or may have "gaps" on the boundary.

Visualization of non-rational constraints in 2D.

Interestingly, dimension matters. The authors prove that for any integer program in $\mathbb{R}^2$, the Lagrangian bound remains tight despite non-rationality. However, in higher dimensions, the theorem can collapse entirely.

A 3D counterexample where the Lagrangian bound fails.

In the 3D counterexample shown above, the authors demonstrate a case where $v^L = -\infty$ while $v^* = 0$, representing a total collapse of the bound's utility in the absence of rationality.

New Theoretical Generalizations

Using tools from convex analysis, the paper establishes several new sufficient conditions for the theorem to hold:

  • Slater's Condition: The theorem typically fails only when the feasible region lies exactly on the boundary of the convex hull of $X$. If the constraints intersect the relative interior of the convex hull, the theorem holds regardless of rationality.
  • Local Polyhedrality: If a set's intersection with any bounded box is a polytope (locally polyhedral), the theorem holds, provided an optimal solution exists.
  • Single Rational Constraint: If the "linking" constraints ($Ax \ge b$) consist of a single rational row, the theorem holds even if the underlying set $X$ is non-rational.

Key Results

  • Theorem 1.2: If the closure of the convex hull of $X$ is locally polyhedral and an optimal solution exists, then $v^L = \bar{v}^*$.
  • Theorem 1.3: For any integer program in $\mathbb{R}^2$, the Lagrangian bound is always equal to the convex hull bound ($v^L = \bar{v}^*$).
  • Theorem 1.4: If the system $Ax \ge b$ is a rational single-row system, the standard Geoffrion equality $v^L = v^* = \bar{v}^*$ is maintained.

Limitations and Future Directions

The research notes that it is currently unknown if these results hold when an optimal solution is not attained (i.e., only an infimum exists). Furthermore, while a single rational constraint row is covered, it remains an open question whether the result extends to multiple rational constraints when $X$ is non-rational. These "wild" settings suggest that further generalizations may require more advanced tools from the geometry of numbers.

Summary updated

BibTeX
@article{dey2026geoffrion,
  author = {Santanu S. Dey and Frédéric Meunier and Diego Alejandro Morán Ramírez},
  title = {{Geoffrion's theorem beyond finiteness and rationality}},
  journal = {Oper. Res. Lett.},
  year = {2026},
  doi = {10.1016/j.orl.2025.107395},
}
Figure