0

We have N groups of objects. Objects could be triangles and rectangles (it's just an example to generalize question). Number of triangles and rectangles are not the same. Each group contains $r_{i}$ - rectangles, $t_{i}$ - triangles, so overall $k_{i} = t_{i} + r_{i}$ number of objects.

Problem: I want to divide these groups into three subgroups with ratio (80/10/10 percent of object per group). And at the same time I want, that ratio of triangles and rectangles will be approximately the same in each group (minimize difference between ration among all groups).

My attempts: Obviously, we may compute ratio $c_{i} = \frac{r_{i}}{t_{i}}$ for each group and check all variants, overall $3^{N}$. I wrote algorithm, that slightly better, than exhaustive search. Maybe we should use methods like https://en.m.wikipedia.org/wiki/Branch_and_bound ? (Which is also has complexity about $3^{N}$)

Ѕᴀᴀᴅ
  • 34,263
Nikita Artemenko
  • 77

1 Answers1

1

$ \sum_i \sum_{j=1}^3 t_{i,j} = \sum_it_i$
$ \sum_i \sum_{j=1}^3 r_{i,j} = \sum_ir_i$

$t_{i,1}+r_{i,1} = 8(t_{i,2}+r_{i,2}) = 8(t_{i,3}+r_{i,3}) \ \ \forall i$ where $t_{i,j}, r_{i,j}$ are vars $ \in R^+$ assigning triangles/rectangles to each of the 3 subgroups $j$ within each of the groups $i$

$ r_{i,j} = c_{i,j}t_{i,j} \ \ \forall j \in \{1,2,3\}, \ \ \forall i$ where $c_{i,j}$ is continuous variable $ \in R^+$

To minimize the difference between $c$s one way could be to minimize the range between $max(c_{i,j})$ and min So additional cosntraints
$ c_{i,j} \le l \ \forall j \ \forall i$
$ z \le c_{i,j}\ \forall j \ \forall i$
$l$, $z$ track the min & max values.
Then min $ l-z$

Sutanu Majumdar
  • 458