From the separation to the intersection sub-problem in Benders decomposition models with prohibitively-many constraints

We consider a linear program over a polytope P described by prohibitively-many constraints. Given a ray direction 0→r, the intersection sub-problem asks to find: (i) the intersection point t∗r between the ray and the boundary of P and (ii) a constraint of P satisfied with equality by t∗r. In Porumbel, 2016, §2, we proposed a method based on the intersection sub-problem to optimize general linear programs. In this study, we use a classical Cutting-Planes method in which we simply replace the separation sub-problem with the intersection sub-problem. Although the intersection sub-problem is more complex, it is not necessarily computationally more expensive than the separation sub-problem and it has other advantages. The main advantage is that it can allow the Cutting Planes algorithm to generate a feasible solution (using t∗r∈P) at each iteration, which is not possible with a standard separation sub-problem. Solving the intersection sub-problem is equivalent to normalizing all cuts and separating; this interpretation leads to showing that the intersection sub-problem can find stronger cuts. We tested such ideas in a Benders decomposition model with prohibitively-many feasibility cuts. We show that under certain (mild) assumptions, the intersection sub-problem can be solved within the same asymptotic running time as the separation one. We present numerical results on a network design problem that asks to install a least-cost set of links needed to accommodate a one-to-many flow.