Efficiently solving for many different RHS vectors

[Alex Bartik]

I'm using Gurobi  to solve the model:  min c*x s.t. A*x = b for many b's (i.e. a few million), but the same c and A.  Right now, I'm looping through all of the potential b's and solving each separately (for some background, I'm computing minimum travel times on a given transit network for different origin/destination combinations, so the b vector just includes a -1,1 for the origin/destination nodes and 0s for all other nodes).  However, I wonder if this is the most efficient way of doing this (for example, I think I'm repeating the same pre-solve step in every iteration, and maybe there's a way to avoid doing this).

I'd appreciate any ideas.

Thanks!

Alex

[Tobias Achterberg]

You should formulate the first version of your problem, solve it, then only modify the right hand side vector, and solve it again (using the dual simplex algorithm).
If all of your variables are continuous, this means that the previous optimal basis will be used as a warm-start basis for the subsequent dual simplex call, so that it will usually be much faster to solve the next problem than when you formulate and solve it from scratch.

If you have integer variables, then you are unfortunately out of luck. The only thing that can (and will) be kept after a problem modification are the solutions found in the previous optimization call. They will be checked for feasibility w.r.t. the new problem and used as new incumbent solutions if they are still feasible.

Best regards,

Tobias