 # Jeroslow formula

This arises in mixed integer linear programming as an extension of Gomory functions. Consider the following standard form

MILP: $LaTeX: \max \{ c^T x + d^T y : Ax + Dy = b, \, (x, y) \ge 0, \,x \in \mathbb{Z}^n\},$

where $LaTeX: \mbox{rank}(D)=m$ ( $LaTeX: m$ is the number of rows). Let $LaTeX: \{B^k\}$ be the set of bases of $LaTeX: D$ such that there exists $LaTeX: \{u^k\}$ to satisfy the dual conditions: $LaTeX: u^k B \ge d$ and $LaTeX: u^k B^k = d^k$. Let $LaTeX: \lfloor v \rfloor$ denote the floor (or round-down) function, and define $LaTeX: \lfloor v\rfloor_k = B^k \lfloor (B^k)^{-1} v \rfloor$. Let $LaTeX: V_k$ be the set of integer linear combinations of vectors spanned by a dual feasible basis, $LaTeX: B^k$: $LaTeX: V_k = \{v: (B^k)^{-1} v \in \mathbb{Z}^m\}.$

Let $LaTeX: V = \cap_k V_k$, and define $LaTeX: U_k = \{v \in V_k : (B^k)^{-1}v \ge 0, \, (B^k)^{-1}u \neq 0, \, 0 \le (B^k)^{-1}u \le (B^k)^{-1}v \Rightarrow u \not\in V \},$

Let G be a Gomory function on $LaTeX: \mathbb{R}^m$. A Jeroslow formula (or function) for given $LaTeX: D$ is: $LaTeX: J(v) = \max_k \left( \max \{G(w) + u^k (v - w): w \in V, \, \lfloor v \rfloor_k - w \in U_k \} \right).$