Solve Algorithmic Problems

The task is to investigate and find a solution for a variation of the number partitioning problem. Given a set of numbers U and a number k, determine if it is possible to divide U into k separate subsets with the same sum for each subgroup. This issue is related to the multi-way partitioning problem.

For Instance, if we have U = {2,4,6,8,10} and k = 3, it is possible to form the subsets {2,8}, {4,6}, and {10}, which all have the same sum.

Instance U = {6,20,27,30,42,43,52,56,58,63,64,68,78,80,83,89,93,94,95,99}, k = 4

1. Produce a Mixed Integer Programming formulation of the problem and use it to solve a small instance with Excel Solver. Use the Instance above.

2. Develop a heuristic approach for finding approximate solutions to more prominent problem instances. This should include an analysis of the computational efficiency in terms of time and memory usage. Implement the heuristic algorithm using a programming language of your choice and test its performance. One tip for this section is to begin with a primary method and improve upon it. Keep in mind that even advanced meta-heuristics often rely on more straightforward ways.