The dual formulation of this problem is the max multi-commodity flow problem where we have that for every pair (si,ti) we define the set of paths Pi(e) that include edge e. The dual variables of the multi cut formulation are the flow of commodity i on path P. fi(p) system. Solving this system in not completely trivial because we have an exponential number of constraints. we can follow different possibilities. A possibility is that of using the ellipsoid algorithm since we can easily find a violated constraint in this formulation by making a shortest path computation.

---