The company I work for has been developing an application for real-time control of sewer networks. Every 5 minutes, a MILP problem is built or updated, then solved using Gurobi.

For mid-sized cities, this works well. But for larger cities, the MILP problems get bigger and of course more time is required to find an acceptable solution.

My question : can anyone suggest me methods to find a good approximate solution instead of THE optimal solution? The method must be able to find a solution fast, so calculation time is an issue as important as the quality of the solution.

Actually, we can solve a MILP problem to its optimal value $F$, or we can find an approximate solution by doing this :

  • We replace half of the binary variables with continuous variables varying between 0 and 1;
  • We find a first optimal solution to this modified problem. Let's define $F_1$ as the optimal value of the objective function.
  • In the original problem, we set the binary variables to their optimal values from the previous problem;
  • The approximate solution is found by solving this last problem. Let's define $F_2$ as the optimal value of the objective function.

The quality of the solution depends on the range between $F_1$ and $F_2$ since $F_1 \leq F \leq F_2$. This method has been giving relatively good results, but I'm pretty sure there may be other methods to find an approximate solution. I googled "approximate solution MILP", but I'm not sure how reliable my findings are, and how fast a sub-optimal solution can be found.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.