Scippy

SCIP

Solving Constraint Integer Programs

Separating violated constraints

In this file a constraint handler checking solutions for feasibility and separating violated model constraints is implemented. The separation problem for the cut inequalities described in Problem description and solving approach can be solved by a max-flow algorithm in polynomial time. Regarding the variable values of a given LP solution as capacities on the edges, one can check for each \( t \in T \setminus \{r\} \), with \( r \) being the root, whether the minimal \( (r, t) \)-cut is less than one. In this case, a violated cut inequality has been found, otherwise none exists. In order to calculate such a minimal cut an adaptation of Hao and Orlin's preflow-push algorithm (see A Faster Algorithm for Finding the Minimum Cut in a Directed Graph) is used. Furthermore, the file implements a dual ascent heuristic, based on a concept described in "A dual ascent approach for Steiner tree problems on a directed graph." by R. Wong.