= Feasible-point box bound for a polyhedron with lines
{title2=$P\ne\varnothing\Longrightarrow P\cap[-R,R]^n\ne\varnothing$}
A nonempty <linear polyhedron> can have no extreme point. Intersect it with an orthant containing one feasible point, and minimize the sum of the signed coordinates there. The relevant sublevel sets are compact, so the minimum face has an extreme point, which is also extreme in the orthant intersection. The added signed-coordinate rows are integer rows with entries at most one. The <integer-matrix vertex coordinate bound> gives $R=n!\max(1,U)^n$. This supplies a bounded feasibility search even when the original polyhedron contains lines.
Back to article page
