5
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ This paper (authored by then-CPLEX developers) has a lot of implementation details, good practices, and references regarding Benders decomposition. $\endgroup$ – mtanneau Jan 27 at 14:33
5
$\begingroup$
  1. Yes, there is no need to solve 𝑟𝑎𝑦(𝑦) to obtain an extreme ray as you mentioned. In CPLEX, for example, you can use a method called getRay (see here).

  2. You can solve the primal problem using a suitable algorithm (primal simplex, dual simplex, etc, whichever is faster for your problem) and then get the dual values (using getDual or getDuals), or you can solve the dual problem directly. It is important to note that the dual values you get from the two approaches can be different. In a numerical study, I observed that hundreds of instances of a problem are solved at least twice faster if the dual values are obtained from solving the dual problem directly. But the reverse can also happen depending on the problem. So this should be checked. The reason is that different dual values can result in different cuts, and in the afformentioned case, the quality of the cuts obtained where quite different.

  3. In the cases I have seen, the first approach (solving only at the integer nodes) has been a better option. Having said that, you can take a two-phase approach to accelerate the Benders decomposition approach: In the first phase, you solve the LP-relaxation of the problem by a cutting plane approach (i.e., the clasical implementation of Benders decomposition where at each iteration cuts are added to remove the optimal solution of the LP in the previous iteration). Once the LP-relaxation is solved, you keep the generated Benders cuts in the master problem and proceed with the modern implementation of Benders decomposition (I borrowed the word 'modern' from the keynote presentation of Matteo Fischetti in ISMP2018).

  4. If you can generate multiple (different) cuts then you can examine whether it is good to add them all or only a subset of them. The multi-cut version of Benders decomposition is usually considered as an improvement technique. Note that the single-cut version of the algorithm can actually outperform the multi-cut version (see e.g., this paper).

$\endgroup$
1
  • $\begingroup$ Do you also know, in case 2, how to efficiently determine which of the two possible cases we ran into: unbounded or infeasible? $\endgroup$ – Joris Kinable Feb 3 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.