How do I split a vector in half such that the sum of the terms in each half are a minimum?

Question

I've been struggling with this problem for several days now, perhaps because I am approaching it the wrong way. Hopefully someone can help me see the light!

PROBLEM

Consider that there are four cups of pennies. Each cup has a random amount of pennies.

I need to determine how to split the cups into two groups, two cups in each group, such that the total pennies in one group less the total pennies in the second group is a minimum, and ideally zero.

It is very simple to solve this problem if I knew the amount of pennies in each cup. So I want to use linear algebra to help me determine those amounts. Once I have the amounts, I can run trial summations on a fast computer to find an optimum division of the cups.

I cast the problem in the context of four cups. But the practical application I am trying to solve might have 32 cups, so the number of combinations that would need to be tested is $\binom{32}{16}$, which is over 60 million. Doing that manually would take forever.

MATHEMATICAL APPROACH

Assume $A$ is a vector that represents the unknown number of pennies in each cup, $B$ is a multitude of vectors that assign each cup to a group, and $C$ is the difference in total pennies between the groups of cups.

$$A=C\cdot B^{-1}$$

While I believe I have the problem setup correctly, the determinant of $B$ is always zero given the requirements of $B$. So I can't determine the number of pennies in each cup.

Conditions;

$$n\in\{2\cdot\mathbb{Z}\}\mid n\geqslant2\ $$

$$A=[\left|a_1\right|... \left|a_n\right|]$$

$$C=\begin{bmatrix} c_{1}\\ \vdots \\ c_{n}\\ \end{bmatrix}$$

$$B=\begin{bmatrix} B_{x}\\ B_{y}\\ \end{bmatrix}$$

$$B_x=\begin{bmatrix} b_{1,1} \dots b_{n,1} \\ \vdots \\ b_{1,\frac{n}{2}} \dots b_{n,\frac{n}{2}} \\ \end{bmatrix}$$

$$B_{y}=-B_x$$

with the further limitation that all terms in $B_x$ are arbitrarily assigned either +1 or -1, and each column vector in $B_x$ is unique.

By assigning $B_y$ = -$B_x$ ,each column of $B$ is guaranteed to have one set of $\frac{n}{2}$ terms = 1 and another equal size set of $\frac{n}{2}$ terms = -1.

Given that all terms in $A$ are positive, the balanced column vectors of $B$ effectively separates the $A$ vector into two equal length vectors; a positive vector group and negative vector group. The ultimate goal is to find a column vector, not necessarily in $B$, that creates a minimum summation of all terms in $A$. But if the determinant of $B$ is always zero, I don't see how to solve my problem. Am I making a mistake or is there a better way to approach the problem?

Any thoughts?

Answer 1

This sounds like the subset sum problem, which is NP-complete. You can solve it via integer linear programming as follows. Let $n_i$ be the number of pennies in cup $i$. Let binary variable $x_i$ indicate whether the pennies in cup $i$ are assigned to group A. The rest will be assigned to group B. The problem is to minimize $z$ subject to: \begin{align} z &\ge \sum_i n_i x_i \\ z &\ge \sum_i n_i (1-x_i) \\ \sum_i x_i &= 16 \end{align} This formulation is a linear way to minimize the maximum number of pennies in the two groups. Because the total number of pennies is constant, minimizing the maximum is equivalent to minimizing the difference.

If the $n_i$ are not distinct, with frequencies $f_i$, you can instead replace the binary variables with (fewer) nonnegative integer variables $x_i$ that represent the number of times that $n_i$ appears in group A. The new linear constraints are: \begin{align} z &\ge \sum_i n_i x_i \\ z &\ge \sum_i n_i (f_i-x_i) \\ \sum_i x_i &= 16 \\ 0 \le x_i &\le f_i \end{align} This both reduces the problem size and helps eliminate symmetry. For the problem data provided, there are 15 distinct frequencies, and an optimal solution looks like this: $$ \begin{matrix} i &n_i &f_i &x_i\\ \hline 1 &968 &1 &1 \\ 2 &972 &1 &1 \\ 3 &984 &4 &0 \\ 4 &988 &3 &3 \\ 5 &992 &3 &3 \\ 6 &996 &2 &1 \\ 7 &1000 &1 &1 \\ 8 &1004 &5 &1 \\ 9 &1008 &1 &1 \\ 10 &1012 &4 &0 \\ 11 &1016 &2 &0 \\ 12 &1020 &1 &0 \\ 13 &1032 &2 &2 \\ 14 &1044 &1 &1 \\ 15 &1052 &1 &1 \\ \end{matrix} $$

Answer 2

Presenting a quadratic binary optimization apporach:

Let $x_i=1$ if object $i$ belongs to group $1$ and $x_i=-1$ if it belongs to group $2$.

Let the value be $v_i$.

Hence, we want to minimize $$\min_i \left(\sum_iv_ix_i\right)^2=\sum_i v_i^2 +\sum_{i<j}2v_iv_jx_ix_j$$

subject to $$\sum_i x_i=0$$

$$x_i \in \{1,-1\}$$

If you have access to a QUBO(quadratic unconstrained programming optimization) solver. To convert it to an unconstrained problem, we want to solve

$$\min_i \sum_i v_i^2 + 2\sum_{i<j}2v_iv_jx_ix_j + A\sum_i x_i$$

where $A$ is a parameter that we have to tune to make sure that the constraint is satisfied and to convert the variable to binary, just use the transformation $y_i = \frac{x_i+1}2$.

Remark: While we can theoretically derived a large value for $A$ that is equivalent to the original problem, a large value might not be suitable when it comes to real life solver. I might want to first set it to a large value then reduce it slowly.

Also, on this page, a heuristic with $O(n^2)$ time complexity and $O(n)$ space complexity is proposed to obtain a feasible solution.