Jeroslow formula

From Glossary

Jump to: navigation, search


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).


Views
Personal tools