Benders subproblem feasible region dependent upon solution master problem

Question

Suppose I want to solve a naturally MINLP problem of the following form: $$ \min_{x,y} \{c'x + y \mid Ax \leq b, Dx + Ey \leq f, G(x)y\leq g, x \in \mathbb{Z}, y \in \mathbb{R}^+\} $$ Here $G(x)$ indicates that the matrix $G$ is dependent upon $x$. Thinking of Benders Decomposition, I would end up with a dual subproblem of the form (for a given $\bar{x}$) $$ \max_{y\mid \bar{x}} \{(f - D\bar{x})'u + g'v \mid E'u + G(\bar{x})'v \geq 1, \ u,v\in\mathbb{R}^+\} $$

However, now the feasible region of the subproblem depends upon $x$. Does this automatically implies that this approach does not make sense? I have only a basic understanding of Benders Decomposition, but I assume that there are bright minds that already have studied a setting like this in very much detail. Can someone point me in the right direction?

Answer 1

I always find it helpful to look at Benders decomposition from a primal view, as detailed in this presentation by Matteo Fischetti.

You can write $$ \min_{x,y} \{c'x + y \mid Ax \leq b, Dx + Ey \leq f, G(x)y\leq g, x \in \mathbb{Z}^n, y \in \mathbb{R}^+\} $$ as $$ \min_{x,y} \{c'x + \Phi(x) \mid Ax \leq b, x \in \mathbb{Z}^n\} $$ with $$ \Phi(x) = \min_{y} \{y \mid Ey \leq f - Dx, G(x)y\leq g, y \in \mathbb{R}^+\}. $$

In classical Benders decomposition (i.e., without the non-linear constraint $G(x)y \le g$), the function $\Phi(x)$ is the value function of a linear program when the right-hand side changes. From duality theory, it follows that this function is convex. Benders cuts can then be seen as supporting hyperplanes of the epigraph of $\Phi(x)$.

If the function $\Phi(x)$ is not convex, classical Benders cuts cannot be used. However, because $x \in \mathbb{Z}^n$, you could still use combinatorial Benders cuts, which only support the epigraph at the integer values of $x$ (which is the only thing you are interested in). See Laporte et al. (2002) and Codato & Fischetti (2006).