Given the following problem: \begin{align} P: \min_{x,y}&\quad c^\top x+f^\top y\\ \text{s.t.}&\quad Ax+By=b\\ &\quad y\in Y\\ &\quad x\geq 0 \end{align} Problem $P$ is equivalent to: \begin{align} P': \min_{y}&\quad f^\top y+S(y)\\ \text{s.t.}&\quad y\in Y\\ \end{align} with \begin{align} S(y):\min_{x}&\quad c^\top x\\ \text{s.t.}&\quad Ax=b-By\\ &\quad x\geq 0 \end{align} The dual $\operatorname{SD}(y)$ of $S(y)$ is: \begin{align} \operatorname{SD}(y): \max_{u}&\quad(b-By)^\top u\\ \text{s.t.}&\quad A^\top u\leq c\\ &\quad u\mbox{ unrestricted} \end{align} Through classical Benders decomposition, problem $P'$ can be reformulated as: \begin{align} Q:\min_{y}&\quad f^\top y+z&\\ \text{s.t.}&\quad(\alpha^r_j)^\top(b-By)\leq 0&\forall j\in 1,\dots,J\\ &\quad(\alpha^p_i)^\top(b-By)\leq z&\forall i\in 1,\dots,I\\ &\quad y\in Y\\ \end{align} where $I$ and $J$ are respectively the set of extreme points and the set of extreme rays defining the feasible space of $\operatorname{SD}(y)$. Since $Q$ can be extremely large, the Benders decomposition algorithm iteratively solves a problem $Q'$ which is identical to $Q$ but where the sets $I$ and $J$ are replaced by $I'\subseteq I$ and $J'\subseteq J$. During every iteration of the algorithm, additional optimality and feasibility cuts are separated and added to $J$ and $I$ respectively.
The Classical Benders decomposition algorithm iteratively solves problem $Q'$, thereby obtaining a solution $\bar{y}$, and problem $\operatorname{SD}(\bar{y})$:
- Case 1: If $Q'$ is infeasible, then $P$ must be infeasible. If $Q'$ is unbounded (objective is $-\infty$) then $P$ is unbounded.
- Case 2: If $\operatorname{SD}(y)$ is infeasible, then $S(y)$ must be unbounded for some $\hat{y}\in Y$ or infeasible for all $y\in Y$. By extension, $P$ must be unbounded or infeasible.
- how to efficiently determine which of the two possible cases we ran into: unbounded or infeasible?
- Case 3: If $\operatorname{SD}(\bar{y})$ is feasible and bounded for some $\bar{y}\in Y$, optimality cut $\bar{u}^\top(b-By)\leq z$ is added to $I'$, where $\bar{u}$ is the optimal solution to $\operatorname{SD}(\bar{y})$.
- Case 4: If $\operatorname{SD}(\bar{y})$ is feasible and unbounded for some $\bar{y}\in Y$, there exists an extreme ray $\alpha^r$ s.t. $\alpha^r(b-B\bar{y})>0$. Feasibility cut $(\alpha^r)^\top(b-By)\leq 0$ is added to $J'$.
For Case 4, we need to determine an extreme ray $\alpha^r$. Since the recession cone $\operatorname{rec}(\operatorname{SD}(y))$ of $\operatorname{SD}(y)$ is given by $\operatorname{rec}(\operatorname{SD}(y))=\{u\in R^{n} \mid A^\top u\leq 0\}$, we can solve the optimization problem $\operatorname{ray}(y)$: \begin{align} \operatorname{ray}(y): \max_{u}&\quad(b-By)^\top u\\ \text{s.t.}&\quad(b-By)^\top u = 1\\ &\quad A^\top u\leq 0\\ &\quad u\mbox{ unrestricted} \end{align}
- To find the extreme ray, I presume that an actual implementation does not solve an LP like $\operatorname{ray}(y)$, but derives the ray directly from the information in the simplex tableau when solving $S(y)$ or $\operatorname{SD}(y)$?
- From a computational perspective, when solving the subproblem, is there an advantage to solving $S(y)$ instead of $\operatorname{SD}(y)$? Is there a preferred algorithm (e.g. primal simplex/dual simplex/..)?
- When embedding the Benders decomposition in a branch-and-bound search, when do you typically solve the subproblem (best practice)? (1) only at the integer nodes, (2) at all nodes (both fractional and integer), or (3) typically at the root node and at every integer node.
- Each time subproblem $\operatorname{SD}(\bar{y})$ is solved, do you generate a single cut, or multiple? E.g. there can exist multiple extreme points or rays.
