Minimize sum of products of partition

Question

I have a set of positive integer numbers $A = \{a_1,\dots,a_N\}$ and I need to find a partition of $A$ into two sets, such that the sum of their products is minimal, i.e., $$ \min_{X,Y : X \cup Y = A} \prod_{x \in X} x + \prod_{y \in Y} y. $$ Is there any good approximation/heuristic algorithm to solve this problem?

Answer 1

You can get an upper bound by instead minimizing $$2\max\left(\prod_{x\in X} x, \prod_{x\in A \setminus X} x\right).$$ Equivalently, minimize $$\max\left(\sum_{x\in X} \log x, \sum_{x\in A \setminus X} \log x\right),$$ which you can linearize as follows. Let binary decision variable $s_a$ indicate whether $a \in X$, and let continuous decision variable $z$ represent the maximum of the two sums of logs. The problem is to minimize $z$ subject to \begin{align} z &\ge \sum_{a\in A} (\log a) s_a \\ z &\ge \sum_{a\in A} (\log a)(1 - s_a) \end{align}

---

See https://oeis.org/A127180 for optimal values for the original problem when $A=\{1,\dots,n\}$. The resulting sum of products $$\prod_{a\in A: s_a=1} a + \prod_{a\in A: s_a = 0} a$$ obtained from solving the linearized problem agrees with the optimal values found there.