12
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Kevin Dalmeijer Mar 28 at 18:44
  • 1
    $\begingroup$ Whether Benders (or something Benders-like) is workable may depend on the nature of $G()$. $\endgroup$ – prubin Mar 28 at 19:22
8
$\begingroup$

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).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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}$? $\endgroup$ – prubin Mar 28 at 19:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Kevin Dalmeijer Mar 28 at 19:33

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.