Gomory function

From Glossary

Jump to: navigation, search

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. fLaTeX: (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:

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:

f^*(b) = \inf\{c^Tx: Ax = b, x \ge 0, \; x \in \mathbb{Z}^n \}.

Here is an example:

f^*(b_1, b_2) & = & \min \{ 7x_1 + 4x_2 + 3x_3 : \\
<pre>             &   & \;\;\;\;\;\;\;\; 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 \}

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.

Personal tools