 # Gomory function

A recursively defined class of functions on $LaTeX: \mathbb{Q}^n$ to $LaTeX: \mathbb{Q}$ (rational n-vectors to rationals) using three operations: (1) non-negative, rational linear combinations, (2) integer rounding, and (3) maximum. Letting $LaTeX: R(v)$ be the integer round-up of $LaTeX: v$, i.e. the least integer not less than $LaTeX: v$, we say $LaTeX: f$ is a Gomory function if it is the identity function, $LaTeX: f(x)=x$, or if it has one of the following forms:

1. $LaTeX: f(x) = ag(x) + bh(x)$ for some $LaTeX: a, b \ge 0$ and rational;
2. $LaTeX: f(x) = R(g(x))$;
3. f $LaTeX: (x) = \max \{g(x), h(x)}$;
where $LaTeX: g$ and $LaTeX: h$ are Gomory functions. It can be shown this is equivalent to the point-wise maximum of finitely many Chvátal functions: $LaTeX: f(x) = \max{C_1(x), C_2(x), \ldots,C_k(x)\},$

where each $LaTeX: C_i$ is a Chvátal function.

This arises in integer linear programming in several ways. One fundamental result is that the optimal value as a function of $LaTeX: b$ is a Gomory function: $LaTeX: f^*(b) = \inf\{c^Tx: Ax = b, x \ge 0, \; x \in \mathbb{Z}^n \}.$

Here is an example: $LaTeX: \begin{array}{rcl} f^*(b_1, b_2) & = & \min \{ 7x_1 + 4x_2 + 3x_3 : \\

 & & \;\;\;\;\;\;\;\; 5x_1 + 3x_2 + 2x_3 = b_1 \\ & & \;\;\;\;\;\;\;\; x_1 + x_2 + x_3 = b_2 \\ & & \;\;\;\;\;\;\;\; x \in \mathbb{Z}^3, \; x \ge 0 \} \\ & = & \max \{ b_1 + b_2, \; \lceil b_1/2 - b_2 / 2 \rceil \}

\end{array}$

Note: The above definition assumes minimization; if the ILP is maximization, $LaTeX: R(.)$ would be round-down (i.e., greatest integer not exceeding the value), and condition 3 would be the point-wise minimum.