Separation oracle
= Separation oracle
A <separation oracle> either certifies that a supplied point belongs to a convex feasible set or returns a violated linear inequality whose half-space contains the whole feasible set. Its running time can be small even when the set has exponentially many defining inequalities. Together with rational encoding bounds and an outer bound, this permits <polynomial time> <ellipsoid method> feasibility and optimization.