Math Grouping Optimization

Question

I have roughly 10 employees assigned a random cost (for this example, lets say $0-$500). I'm trying to optimize grouping the employees into 3 groups. Every employee in the group must be paid the same amount, the highest cost of the employee in that group. There is no requirement for how many employees in each group.

Example table;

Employee	Cost
1	120
2	10
3	400
4	0
5	0
6	420
7	80
8	180
9	270
10	410

Example Non-Optimized Solution)

Group 1 Employees 4, 5, 2 (Cost 30 based on employee 2 costing $10)

Group 2 Employees 7, 1 (Cost 240 based on employee 1 costing $120)

Group 3 Employees 8, 9, 3, 10, 6 (Cost 2100 based on employee 6 costing $420)

Total Cost = $2,370

Any advice on how to break down this problem greatly appreciated!

Answer 1

This question has nothing whatsoever to do with group theory, which is a branch of abstract mathematics dealing with symmetries, transformations, and such.

Anyway, the way to visualize your problem is as follows:

You search through the two "splitting positions" to minimize the combined area of the three colored rectangles (total cost).

I wonder if the following pseudo-greedy algorithm is optimal:

• Assign the initial partitions above employee 1 and above employee 9.
• Compute the total cost.
• Take a step up (for the lower partition threshold); Separately, take a step down (for the higher partition threshold); Choose which of those two steps leads to the smallest new total cost.
• Repeat the above operation until neither proposed step reduces the total cost.
• Terminate

Answer 2

Another way is using an optimization solver with binary variables $ x_{e,g}= 1$ if employee $e$ is assigned to group $g=\{1,2,3\}$, else 0 and a continuous variable $0 \le K_g$ that represents the cost.
So define objective to minimize $\sum_g K_g $ with constraints
$\sum_g x_{e,g}= 1 \quad \forall e $
$ 1\le \sum_e x_{e,g} \quad \forall g$
$ c_{e}x_{e,g} \le K_g \quad \forall e \ \ \forall g$ where $c_e$ is given cost of an employee $e$
The last constraint captures the highest cost of employee in the group.