Some methods to address problem of non-convex MINLP with binary and real variables

109 Views Asked by At

I have an optimization problem which is considered hard to solve because of it is non-convex MINLP problem with the general form as follows:

$f(x,y) = a(x) + b(x)c(y)$

where $x \in \{0,1\}$ and $y \subset \mathbb{R}$. As you can see that my problem contains the multiplication of $b(x)$ (where $x$ is binary variable) and $c(y)$ (where $y$ is continuous variable). As far as I know, we can use Bender's decomposition to solve this problem, however, that method should be separable to the binary and real variable. Based on my problem, what is the best method and how to separate the multiplication part thus I can solve the problem using typical Bender's decomposition or any other possible methods?

1

There are 1 best solutions below

0
On

Considering your problem as $\mathrm{min}\, a(x)+b(x)c(y)$, you can do a Benders decomposition, with master problem as $\mathrm{min}\,a(x) + \eta$, and subproblem as $\mathrm{min}\, b(\hat{x})c(y): \pi$.

The Benders cuts inserted into the master problem are $\eta \geq \pi^k(b(x)c(y^k)$ where $k = \{1,\dots,\text{number of iterations}\}$

This is basically a reformulation in your problem, because you don't have constraints. Otherwise, you need to be careful in insert the correct type of Benders cut (optimality or feasibility).