2
$\begingroup$

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.

Thanks.

$\endgroup$

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.