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.
After testing nonnegative edge coordinates and any explicit box or budget inequalities, treat those coordinates as lengths. A shortest path of length below one supplies a violated path inequality; a minimum length at least one certifies all path inequalities. If no source-to-target path exists, all those inequalities are vacuous. Thus a polynomial time shortest path problem calculation separates an exponentially constrained linear program.
Articles by others on the same topic
There are currently no matching articles.