Finding the minimum of $|S_1-S_2|+|S_3-S_4|+|S_5-S_6|+|S_7-S_8|$ where $S$ is a sum of $x,y$, and $z$.

92 Views Asked by At

Consider $24$ positive numbers; $x_1, \dots, x_8,y_1, \dots, y_8,z_1, \dots, z_8$.

Let

$$M=|\text{sum of }(\text{one }x, \text{one }y, \text{one }z)-\text{sum of }(\text{different }x,\text{different }x,\text{different }z)|$$

$$+|\text{sum of }(\text{different }x,\text{different }y,\text{different }z)-\text{sum of }(\text{different }x,\text{different }y,\text{different }z)|$$

$$+|\text{sum of }(\text{different }x,\text{different }y,\text{different }z)-\text{sum of }(\text{different }x,\text{different }y,\text{different }z)|$$

$$+|\text{sum of }(\text{different }x,\text{different }y,\text{different }z)-\text{sum of }(\text{different }x,\text{different }y,\text{different }z)|$$

Clarification: the word "different" indicates that any of the $24$ numbers must be used (exactly) one time.

How can I find the minimum possible value of $M$ (without a software)?


Example:

enter image description here

With the help of EXCEL, I found that

$$M=|(x_2+y_1+z_1)-(x_1+y_5+z_3)|$$

$$+|(x_3+y_3+z_5)-(x_5+y_8+z_2)|$$

$$+|(x_4+y_7+z_7)-(x_7+y_4+z_8)|$$

$$+|(x_8+y_2+z_4)-(x_6+y_6+z_6)|=1.50$$

is the minimum possible value of $M$.

I am not sure if this answer is correct or not. I just included this example so that my problem will be understood.

What I did using EXCEL;

I found the $512$ possible sums, that is, I found

$x_1+y_1+z_1,x_1+y_1+z_2, \dots, x_1+y_1+z_8,x_2+y_2+z_1,x_2+y_2+z_2, \dots, x_2,y_2,z_8, \dots, x_8+y_8,z_1, x_8+y_8+z_2, \dots, x_8+y_8+z_8$

then I paired them.


If there is any good trick without using software, it would be great.

1

There are 1 best solutions below

1
On

I don't know any trick, but I used integer linear programming to find that the minimum is $0$: \begin{align} |21.00 + 11.70 + 3.60 -18.00 -10.80 -7.50| &= 0 \\ |15.45 + 9.90 + 12.15 -21.45 -12.00 -4.05| &= 0 \\ |18.30 + 10.35 + 6.45 -13.35 -16.80 -4.95| &= 0 \\ |14.25 + 14.70 + 9.45 -19.05 -12.00 -7.35| &= 0 \end{align}

For $i\in I:=\{1,\dots,8\}$ and $j\in J:=\{1,\dots,3\}$, let $a_{i,j}$ be the entry in row $i$ and column $j$. Let $G:=\{1,\dots,4\}$ be the groups. Let binary decision variables $p_{i,j,g}$ and $n_{i,j,g}$ indicate whether entry $(i,j)$ appears in group $g$ with a positive sign or negative sign, respectively. The problem is to minimize $$\sum_{g \in G} \left|\sum_{i\in I} \sum_{j\in J} a_{i,j} (p_{i,j,g} - n_{i,j,g})\right|$$ subject to linear constraints: \begin{align} \sum_{g \in G} (p_{i,j,g} + n_{i,j,g}) &= 1 &&\text{for $i\in I$ and $j \in J$} \tag1 \\ \sum_{i \in I} p_{i,j,g} &= 1 &&\text{for $j \in J$ and $g \in G$} \tag2 \\ \sum_{i \in I} n_{i,j,g} &= 1 &&\text{for $j \in J$ and $g \in G$} \tag3 \end{align}

Constraint $(1)$ assigns each entry to exactly one group. Constraint $(2)$ assigns one positive entry per column and group. Constraint $(3)$ assigns one negative entry per column and group.

The absolute value objective can be linearized in the standard way.