Combinatorial optimization (find partitions)

Question

A problem arose to solve the problem with a solution that became impracticable. Well, I have a set of 12 elements that represent quantities: $$\Omega = \{16, 132, 135, 135, 136, 138, 138, 139, 301, 334, 355, 361\}$$ I can join elements, get subsets, of this set such that the sum of the elements does not exceed 533, for example, the sum of the first 4 elements of the set is equal to 418, so I have a subset $S$ that does not accept any more elements.

The problem is basically to find the $\Omega$ partition that has the least number of elements possible and variance is minimal.

As an illustration, consider the two possible partitions,

$$S_1 = \{ \{16, 132, 135, 135\}, \{136, 138, 138\}, \{139, 301\}, \{334\}, \{355\}, \{361\}\}$$

$$S_2 = \{ \{16, 138, 138, 139\}, \{135, 135, 136\}, \{132, 361\}, \{301\}, \{334\}, \{355\}\}$$

The associated totals, sum of the elements of the subsets, to each element for the two partitions are respectively

$$T_1 = \{418, 412, 440, 334, 355, 361\}$$ $$T_2 = \{431, 406, 493, 301, 334, 355\}$$

Which has as variances $\sigma^2_{T_1} = 4952,267$ and $\sigma^2_{T_2} = 1780,667$.

Therefore, partition $S_2$ is preferable.

I know that my partition has to have only 6 elements and when using my approach, generate all partitions and search for the optimal partition, it was computationally infeasible.

I wonder if there is a better approach, any text on something like that, any tips?

Sorry for the informality and abuse of notation, thank you in advance!

Answer 1

In what follows, I'm interpreting "variance" to mean "population variance" rather than "sample variance", a minor distinction. Rob used sample variance; the population variance of his solution is 1048.89.

The optimal partition seems to be $$\lbrace\lbrace 16, 138, 138, 139\rbrace, \lbrace 136, 301\rbrace, \lbrace 135, 334 \rbrace, \lbrace 135, 355 \rbrace, \lbrace 132, 361\rbrace\rbrace$$with group sums $$\lbrace 431, 437, 469, 490, 493\rbrace$$and (population) variance 672. Ordinarily I would hesitate to say "optimal" since you have multiple criteria (smallest number of subsets, minimum variance), but in this case the minimum feasible number of subsets is five and the smallest possible variance is 672, so this wins on both criteria.

You mentioned "I know that my partition has to have only 6 elements". Is this a constraint? If so, Rob's solution is optimal.

The solution was obtained using a quadratic programming model that minimizes variance for a fixed number of sets in the partition, solving the model for 1, 2, ..., 12 partition sets. This took about 2 seconds total using CPLEX 12.10 (Java API).

I was slightly surprised to note that the minimum variance increased monotonically with the number of sets in the partition.

Answer 2

One approach to approximate the problem is to minimize the range, which you can do via integer linear programming as follows. Let $a_i$ be the value of item $i$. Let binary decision variable $x_{i,g}$ indicate whether item $i$ is assigned to group $g$. The problem is to minimize $u-\ell$ subject to \begin{align} \sum_{g} x_{i,g} &= 1 &&\text{for all $i$} \\ \ell \le \sum_{i} a_i x_{i,g} &\le u &&\text{for all $g$}\\ \sum_{i} a_i x_{i,g} &\le 533 &&\text{for all $g$} \end{align} The first constraint assigns each item to exactly one group. The second constraint models the range objective. The third constraint enforces the upper bound of 533 on each group.

One optimal partition of the items turns out to be $$\{ \{16,334\}, \{361\}, \{355\}, \{132,301\}, \{135,138,139\}, \{135,136,138\}\},$$ with group sums $$\{350, 361, 355, 433, 412, 409\}$$ and objective value $z^*=433-350=83$. The resulting variance is $1258.7$.