0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for this excellent idea! The good news is that the values of $b$ can be bounded (say by 1), and the number of 1 entries in $x$ is bounded by $10$, so we can let $M=10*max(u)$. The bad news is that I implemented the model and it seems to run quite slowly. I'll keep thinking - thank you for this nudge in the right direction. $\endgroup$
    – grapher
    Feb 22, 2022 at 10:05
  • $\begingroup$ How is your progress $\endgroup$ Jun 1, 2023 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.