MINLP with large number of binary variables

Question

I am working on the following formulation.

max $ \Bigg(\sum_{n \in N}\sum_{i \in C}\ y_{in} \bigg(\ f_{in} ( \pmb{\beta}) - g_{in}\bigg) \Bigg)$

such that

$\sum_{i \in C} y_{in} = 1 \qquad \forall n \in N$

$y_{in} \in \{0,1\}$

$\pmb{\beta} \in [\pmb{\beta_{min}}, \pmb{\beta_{max}}]$

where deision variabels are $\pmb{\beta}$ and $y_{in}$. $f_{in}( \pmb{\beta})$ is a concave function and $g_{in}$ is a penalty term which is independent of $\pmb{\beta}$.

Since for large data, I will have NxC $y_{in}$. My questions are:

1. How can I efficiently solve this problem for a large number of binary variables?

2. Can traditional solvers handle this kind of formulation?

I would really appreciate some advice on problem formulation as well as on solution approach.

Thanks!

Answer 1

You can try solving each

$$B_{in}=\max_{\beta}f_{in}(\beta)-g_{in}, ~ \forall (i,n)\in C\times N$$

because $f$ is a concave function and have one variable only (well-known problem). After that you return a matrix $B$ of these solution. Your problem is equvalent to:

$$\sum_{n=1}^{N}\max_{i\in C}\{B_{in}\}$$

I think this is efficient enough. I prefer Newton's method, but without more assumptions about $f$ I recommend you use the bisection method.