Corner polyhedron problem

From Glossary

Jump to: navigation, search

Gomory's relaxed IP that drops the non-negativity constraints of basic variables. Suppose LaTeX: x = (u,0) is a basic solution to the LP, LaTeX: \mbox{opt}\{c^Tx : Ax=b, \; x \ge 0\}, where LaTeX: u is the vector of basic variables. Then, the corner polyhedron problem is

LaTeX: \mbox{opt} \{d^Tv: u \in \mathbb{Z}^m, \; v \in \mathbb{Z}^{n-m}+, \; Bu + Nv =b\},

(dropping LaTeX: u \ge 0), where LaTeX: d is the reduced cost of LaTeX: v in the LP solution. (Note: LaTeX: c^Tx = d^Tv for all LaTeX: x=(u,v) such that LaTeX: Ax=b.)

Personal tools