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.