# Benders subproblem feasible region dependent upon solution master problem

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?

• Is $y$ a scalar or a vector? It seems to be scalar in the objective and the variable definition, but $G(x)y \le g$ seems to imply a vector. Mar 28, 2020 at 18:44
• Whether Benders (or something Benders-like) is workable may depend on the nature of $G()$.
– prubin
Mar 28, 2020 at 19:22

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).
• If $G(x)$ is sufficiently annoying (for instance, you get it by looking up one of a rather arbitrary set of matrices based on the values of $x$), and if the subproblem is infeasible at $x=\bar{x}$, will you be able to do any better than a "no-good" cut to remove $\bar{x}$?
• I agree, only using combinatorial Benders cuts is basically adding no-good cuts in this case. This may still be a good strategy. In addition, I would try to find a convex lowerbounding function for $\Phi(x)$ (some sort of relaxation), and add cuts for this. Mar 28, 2020 at 19:33