Path-constraint separation by shortest paths (${\sum }_{e\in p}{x}_e\ge 1(p:s⇝t)$)

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.