Divide N floats into M groups so that the sum of each group is as equal as possible?

Question

Given a list of N non-negative real numbers:

t = [2.99, 7.9, 24.58, ..., 3.1415, 40.4]

I want to partition the elements of $t$ into $M$ groups, $g_1$, $g_2$, ..., $g_M$, so that the sum of each group is as close as possible to $sum(t)/M$, i.e. minimizing the root mean square error:

Minimize: $\sqrt{\Sigma_i^M (sum(g_i) - sum(t)/M)^2 }$.

Do anyone know a close-to-optimal algorithm of doing this generally? Or do anyone know the name of this problem? (My google-fu failed me).

Background: $t$ represents time in seconds to run $N$ different tasks, and I want to schedule the $N$ tasks on $M$ different computers in such a way that all computers finish their tasks at the same time (or as close as possible).

Wouldn't your intended application suggest to minimize $\max_i\sum(g_i)$ instead? — Hagen von Eitzen, Dec 09 '18 at 17:53
This looks like a variant on the bin packing problem to me. It is known to be NP-hard in the general case, but there are approaches that are pretty good. — Ross Millikan, Dec 09 '18 at 17:57
@JeanMarie Yes, M is fix, for example "5", and not subject to change. — Penlect, Dec 09 '18 at 21:01
@HagenvonEitzen Good point, yes, minimizing your expression is also interesting. And now I'm curious if the optimal solution to that will automatically also be the optimal solution for the RMSE. — Penlect, Dec 09 '18 at 21:01

score 0 · Answer 1 · answered Sep 13 '20 at 15:30

Let $ M \leq N $. I try to reply to your question in terms of a problem of optimization attributable to a Boolean linear programming problem. You need $ m \cdot n $ Boolean variables to trace the assignment of task to computer: $ x_{i,j} $ is a Boolean variable whose value is 1 if i-th task is assigned to j-th computer, zero otherwise.

The objective function can be properly formulated as

$ \min \sum_{j,k=1}^m | g_j – g_k | $

where $ |.| $ is the absolute value.

Constraints:

$\left\{ \begin{array}{l} \sum_{j=1}^m x_{i,j} = 1 \forall i=1, \cdots , n \\ x_{ij} \in \left \{ 0 ; 1 \right \} \forall i,j \\ \end{array} \right. $

where

$ g_j = \sum_{i,j=1}^n t_i \cdot x_{i,j} $ is the service time for j-th computer

$ \sum_{j=1}^m x_{i,j} = 1 $ requires that i-th task is assigned to one and only one computer

$ x_{i,j} $ is a Boolean variable whose value is 1 if i-th task is assigned to j-th computer, 0 otherwise.

By means of $z_1, \cdots , z_m$ real variables, the problem can be formulated as a linear programming model.

$ \min \sum_{j=1}^m z_j $

subject to

$\left\{ \begin{array}{l} \sum_{j=1}^m x_{i,j} = 1 \forall i=1, \cdots , n \\ g_j – g_k \leq z_j \forall j,k=1, \cdots , m \\ g_j – g_k \geq - z_j \forall j,k=1, \cdots , m \\ x_{ij} \in \left \{ 0 ; 1 \right \} \forall i,j \\ \end{array} \right. $

Divide N floats into M groups so that the sum of each group is as equal as possible?

1 Answers1