We describe a new LP model for min s-t cut that is the smallest known LP formulation with respect to the number of variables (O(n) in our model vs O(n2) or even more for models in the literature). On the other hand, our model has O(n!) constraints, but we describe a fast cutting-plane algorithm to effectively separate over the exponentially many constraints. Overall, we prove that our model can be solved in polynomial time and, in fact, preliminary computational experiments suggest that the number of iterations needed for convergence is sublinear. Given that O(n) constraints are added in each iteration, the final LP appears to be of the smallest known size, with a linear number of variables and a close to linear number of constraints.
A new cutting plane algorithm for the min s-t cut problem
Lancia G.;
2026-01-01
Abstract
We describe a new LP model for min s-t cut that is the smallest known LP formulation with respect to the number of variables (O(n) in our model vs O(n2) or even more for models in the literature). On the other hand, our model has O(n!) constraints, but we describe a fast cutting-plane algorithm to effectively separate over the exponentially many constraints. Overall, we prove that our model can be solved in polynomial time and, in fact, preliminary computational experiments suggest that the number of iterations needed for convergence is sublinear. Given that O(n) constraints are added in each iteration, the final LP appears to be of the smallest known size, with a linear number of variables and a close to linear number of constraints.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
