Same feasible set, different objective function

[cordo...@gmail.com]

Hello.

I have a fairly large LP problem (about 2 million variables and constraints) which I need to solve, change some objective function coefficients (a small amount of them, by a small value) and then solve again. Actually I have to do that many times. The feasible set remains the same for all problems.

My first try was to reuse the basis obtained in the first problem. But this only worked for very very small coefficients variations. As the problem is too big for the simplex method, it often exceeds the limit time when the variations are bigger.

Using GAMS I could employ their GUSS module to try to get a solution faster, without solving all instances independently. Do you have some feature like this?

Or else: the Gurobi documentation shows many parameters and heuristics for MILP, but not that many for LP problems. What could I use (aside from the basis) to, possibly, reuse information from past instances when solving my problem?

Thanks!

[Daniel Espinoza]

Gurobi does not have `heuristics` for LP; but we do offer primal and dual simplex, and barrier, and extensive preprocessing (which in many cases simplify the input problem quite a bit)

It might be the case that after preprocessing (done by default) the problem could be solve by barrier much faster than by simplex, the only way to see it is trying it.

Also, gurobi will keep the previous basis (and other information) to re-optimize a problem after a change; this is also done by default for simplex.

In the end, the only way to see is trying it.

Out of curiosity, where does your problem comes from?

If you find any performance issue, could you share a couple of these (perturbed) instances? Maybe we can find some good parameters or use it to improve performance for the next release.

Best

Daniel

[cordo...@gmail.com]

Daniel, thank you for your reply!

Em quarta-feira, 18 de janeiro de 2017 12:28:26 UTC-2, Daniel Espinoza escreveu:

Gurobi does not have `heuristics` for LP; but we do offer primal and dual simplex, and barrier, and extensive preprocessing (which in many cases simplify the input problem quite a bit)

It might be the case that after preprocessing (done by default) the problem could be solve by barrier much faster than by simplex, the only way to see it is trying it.

Also, gurobi will keep the previous basis (and other information) to re-optimize a problem after a change; this is also done by default for simplex.

I've already tried setting the method and the presolve parameters, besides the tolerances, crossover and some others. Indeed the barrier method is much faster. It seems I'm out of luck then :( 

In the end, the only way to see is trying it.

Out of curiosity, where does your problem comes from?

My problem comes from the oil industry (planning the production, import and export for some months ahead).

 

If you find any performance issue, could you share a couple of these (perturbed) instances? Maybe we can find some good parameters or use it to improve performance for the next release.

Actually, I think Gurobi is solving the problem very quickly. 2 million variables and constraints in less than 3 minutes in a mid-range computer is quite impressive. The problem arises when I have to solve a lot of these instances.

Anyway, I'll see if I can share the model with you. You know, NDA and all that...

Best

Daniel

[Daniel Espinoza]

Hi,

You could use the cloud if you really need to solve a lot of them quickly... now, regarding sharing models with Gurobi, we do have NDAs and all that for our customers; you can contact directly with support

Best

Daniel