In one of my projects - I have a scenario where I need to implement an algorithm that can perform load balancing. Now, unlike the general load balancing problem present in CS theory (which is NP rigid), where the task is to distribute M-loads on N servers (M → N), so that the maximum load on any one server is minimized, the case I deal with is a little more general. In my case, the load balancing problem is more general in the sense - it has more restrictions in the form: - such and such a task can only be assigned to such a server (say, for example, the task M_ {i} has special security requirements and, therefore, can only be allocated / executed on the secure server N_ {j}.
Now I looked at the Kleinberg / Tardos book, and I found section (11.7) about the more general problem of load balancing (load balancing with restrictions), and I found that this problem is an exact match for the situation I was in. The problem of balancing the total load was converted from IP to LP using the fact that LP can lead to fractional assignment of jobs to machines that were subsequently rounded by adding extra O (MN) time for the process. It was shown that this approximation solution is 2 times the minimum possible.
Can someone point me to the C / Java / Python / MATLAB code where this algorithm was implemented? Since the KL book is unlikely to provide any examples or example of pseudo / actual code, it is difficult to make the algorithm internalize completely. As for the part of linear programming of the problem - which option is suitable for it - Simplex / Interior Point? What is the difference when the complexity of this part of the LP is added to the problem (to the partial part of the reassignment)? Unfortunately, the KL book is not very thorough in these aspects.
Some C / Java / Python / MATLAB code examples (or pointers to code) showing the real implementation of this complete algorithm will be very useful.
Editing: original work - "David B. Schmoys, Eva Tardos: an approximation algorithm for the generalized assignment problem", mathematical program 62: 461-474 (1993) "