1
$\begingroup$

In the benders decomposition, is it possible to decompose the master problem as follows and let the subproblem become the subproblem of the new subproblem? Let's say that we have the following problem.

$y$ is a binary variable, $x$ and $z$ are continuous and take values between $0$ and $1$.

$$\max_{x∈X, y∈Y}(cx - \min_{z∈Z(y)}dxz)$$

Is it possible to decompose it further, as follows?

\begin{align}\text{Master Problem:}&\quad\max_{y∈Y} θ\\\text{Subproblem 1}&\quad\max_{x∈X(y)} cx\\\text{Subproblem 2}&\quad\min_{z∈Z(y)} d\bar xz\end{align}

Subproblem 1 contains constraints that include $y$.

Subproblem 2 contains constraints that include $y$.

If yes, is there any sources to look up while developing the algorithm and constraints correctly to solve this problem? If not, what are the best ways to solve a large-scale master problem?

Edit: There was maximization in subproblem 2 by mistake, changed it to minimization. Edited the notation.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Why are you maximizing in subproblem 2? $\endgroup$
    – prubin ♦
    Dec 4, 2022 at 17:01
  • $\begingroup$ My mistake, it should be $$min_{z∈Z(x, y)} d\bar xz$$ $\endgroup$
    – user5245
    Dec 4, 2022 at 17:38
  • 1
    $\begingroup$ You shifted from $z\in Z$ to $z\in Z(x,y).$ Does the feasible region for $z$ (ignoring the inner objective) depend explicitly on either $x$ or $y$? $\endgroup$
    – prubin ♦
    Dec 4, 2022 at 19:53
  • $\begingroup$ In fact, in the first problem, it should be ${z∈Z(y)}$, too. We are not making any changes on the subproblem 2. Thanks for the warning. In subproblem 2, there exists a constraint that include variable $y$. $x$ variable only exists on the objective function of the subproblem 2. So, the feasible region for $z$ depends on variable $y$. It should be ${z∈Z(y)}$. I edited the main post, it should be correct now. $\endgroup$
    – user5245
    Dec 5, 2022 at 7:51
  • $\begingroup$ @prubin Sorry to bother again, but do you have any idea for the problem? $\endgroup$
    – user5245
    Dec 6, 2022 at 14:33

1 Answer 1

Reset to default
1
$\begingroup$

You have an undefined symbol $\bar{x}$ in subproblem 2. Assuming that is the $x\in X$ from subproblem 1, I don't think you can apply Benders, because in subproblem 2 you have both the objective function and the right hand side depending on a candidate solution to the master problem ($x$ in the objective, $y$ in the RHS). One or the other would be OK, but not (as far as I know) both.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, you are correct about the symbol in subproblem 2. I see, I think I should utilize heuristics maybe to solve this master problem then. $\endgroup$
    – user5245
    Dec 6, 2022 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.