Formulating a problem as a mixed-integer conic program

Question

I have the following integer optimisation problem, and I wonder whether it can be reformulated as a conic program that can be solved with, e.g., Mosek. Suppose the $n$-dimensional vectors $a, b$ and $c$ are fixed. I want to solve

$$ \max~(a \cdot x)\prod_{i}b_i^{x_i} + (a \cdot y)\prod_{i}b_i^{y_i} $$ $$ \text{s.t. }\ x, y \in \{0,1\}^n, $$ $$ x_i + y_i \leq c_i,\ \forall i \in [n], $$ $$ \sum_{i} x_i \leq 10, \sum_{i} y_i \leq 10. $$

My first attempt at solving this problem was to reformulate the problem so that it can be solved by SCIP. Unfortunately, SCIP takes far too long on instances that I need to solve.

Focusing on the simpler objective $\max~(a \cdot x)\prod_{i}b_i^{x_i}$ (so ignoring $y$ entirely), I managed to formulate the problem as a mixed-integer conic program, and Mosek was able to solve this much more quickly. My hope is that reformulating the original general problem will yield a similar speedup. But I've not been able to achieve this so far - any insights would be greatly appreciated. Alternatively, if there is some other clever reformulation, I would also be very interested to hear about this.

Here's my conic reformulation for the simpler objective, in case it helps. I use the fact that $\log((a \cdot x)\prod_{i}b_i^{x_i}) = \log(a\cdot x) + x_i \log b_i$.

$$ \max \ w $$ $$ \text{s.t. }w = l + x \cdot \log(b), $$ $$ l \leq \log(z), $$ $$ z = a \cdot x, $$ $$ x_i \leq c_i, \forall i \in [n], $$ $$ \sum_{i}x_i \leq 10. $$ In particular, the constraint $l \leq \log(z)$ corresponds to the conic constraint $ (z,1,l) \in K_{exp}$. Is it possible to somehow extend this reformulation to the original problem?

Answer 1

The only option I see is to exploit the fact that $x$ is binary, so in each step of each product you are either multiplying $1$ or $b_i$ on top of what you already had.

If $s,t$ are continuous variables, $z$ is a binary variable and $b$ is a constant then you can write the condition

$$t = b^zs$$

as two implications (https://docs.mosek.com/modeling-cookbook/mio.html#indicator-constraints)

$$z=1 \implies t=bs,$$ $$z=0 \implies t=s,$$

and with big-M that is

$$-M(1-z)\leq t-bs\leq M(1-z),$$ $$-Mz\leq t-s\leq Mz.$$

Now you need to add a long chain of these to express each product step by step and you have a mixed-integer linear problem. However (1) you should make sure that the objective does not get too large, in your first model it was tamed by the logarithm, but now it might explode, depending on the $b$ and (2) I am worried that this model may be very inefficient.