= Path-constraint separation by shortest paths
{title2=$\sum_{e\in p}x_e\geq1\quad(p:s\leadsto 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>.
Back to article page
