  Since its inception, Benders Decomposition (BD) has been successfully applied
to a wide range of large-scale mixed-integer (linear) problems. The key element
of BD is the derivation of Benders cuts, which are often not unique. In this
paper, we introduce a novel unifying Benders cut selection technique based on a
geometric interpretation of cut ``depth'', produce deepest Benders cuts based
on $\ell_p$-norms, and study their properties. Specifically, we show that
deepest cuts resolve infeasibility through minimal deviation (in a distance
sense) from the incumbent point, are relatively sparse, and may produce
optimality cuts even when classical Benders would require a feasibility cut.
Leveraging the duality between separation and projection, we develop a Guided
Projections Algorithm for producing deepest cuts while exploiting the
combinatorial structure and decomposability of problem instances. We then
propose a generalization of our Benders separation problem, which not only
brings several well-known cut selection strategies under one umbrella, but
also, when endowed with a homogeneous function, enjoys several properties of
geometric separation problems. We show that, when the homogeneous function is
linear, the separation problem takes the form of the Minimal Infeasible
Subsystems (MIS) problem. As such, we provide systematic ways of selecting the
normalization coefficients of the MIS method, and introduce a Directed
Depth-Maximizing Algorithm for deriving these cuts. Inspired by the geometric
interpretation of distance-based cuts and the repetitive nature of two-stage
stochastic programs, we introduce a tailored algorithm to further facilitate
deriving these cuts. Our computational experiments on various benchmark
problems illustrate effectiveness of deepest cuts in reducing both computation
time and number of Benders iterations, and producing high quality bounds at
early iterations.
