MILP Solution

[SaudxInu]

Hey,

I am trying a simplified version of MILP given the paper.

max A = sum_j a_j sum_i x_ij y_i L s.t. sum_j x_ij <= 1 for very i sum_i y_i <= 1 y_i * L <= sum_j Z_j x_ij for every i

where, L is load in QPS Z_j is throughput in QPS for model j x_ij is 1 if model j is loaded on worker i y_i is fraction of load assigned to worker i

I tried using MILP solvers but they are giving wrong answers for trivial cases.

How exactly are using Gurobi to find a solution and what is the solution when the solver is not able to find a solution to the optmization problem?

Please let me know if you have questions.

[sohaibahmad759]

Hi Saud,

Thanks for reaching out.

1. If you are getting an incorrect answer for a version of the MILP that you wrote, it could be due to several reasons, for example, you may be missing some constraints, your current constraints may not accurately capture your problem setting, or your variable types may be incorrect. For example, in the case of Proteus, x is a binary variable, y is a continuous variable constrained to be in the range [0,1], and so on. You can refer to the file algorithms/ilp.py in our repository to see how we have set up the MILP for our setting. Please ensure that your constraints and variables are correct and match the problem setting you are trying to solve.

2. If the constraints are correct and Gurobi returns an error saying that the constraints are infeasible, one likely possibility is that there may not be enough resources to handle the load you input into the system. In this case, you could either use more workers or reduce your load. In the case of Proteus, we address this in Section 4, under the subheading 'Solving the MILP'. If Proteus cannot serve the load even with the lowest accuracy model variants (i.e., the constraints are infeasible), the Gurobi model will not be in the GRB.OPTIMAL state after calling optimize() on it. In this case, we try to solve the MILP by decreasing the input load by a small amount (see lines 331-382 in algorithms/ilp.py).

[SaudxInu]

Hi Sohaib,

Thanks that helps.

PS: Anyone who wants to try out the code can get a free license from Gurobi that works for 2000 vars and 2000 constraints.