Dual simplex VS Barrier for Bender's feasibility cuts
Awaiting user input
Dear Gurobi,
I am implementing Bender's decomposition in a problem, during which I need to construct feasiblity cuts. Feasiblity cuts are constructed in case my bender's slave model is infeasible, using the information on the dual of constraints, their rhs and/or of the dual objective. I can construct them successfully if use dual simplex and set presolve to 0.
However, dual simplex takes substantially more time than Barrier in determining that my model is infeasible. The comparison is of the order of 1 hour with dual simplex to a couple of minutes with Barrier.
I would therefore like to switch to Barrier. But with Barrier I cannot retrieve the information I need for the feasibility cuts; asking for the dual objective returns an error, and asking for the dual of the constraints returns NaN.
Is there an option I could set so that I get the information I need from Barrier?
Alternatively, is there an option (like a feasibility tolerance) I could set to dual simplex so that it determines infeasibility earlier?
Another option I could consider would be to first perform an optimisation of the subproblem removing some constraints; that way, optimisation would probably end earlier and I would have a warm start basis that would hopefully make the run faster when I add back all the constraints.
Let me know if you believe I have other options. In case it affects the issue, I am using gurobi with julia jump.
Thank you in advance for looking into my question!
-
Hi Marilena,
Unfortunately barrier is not an feasible approach here. When your subproblem is infeasible you need to access the farkas dual and that requires InfUnbdInfo to be set to 1. The docs for InfUnbdInfo then say:
When this parameter is set additional information will be computed when a model is determined to be infeasible or unbounded, and a simplex basis is available (from simplex or crossover).
What this means is that if infeasibility is detected during the barrier algorithm, prior to crossover, then the farkas dual cannot be computed, and you have no control over when infeasibility will be detected.
You mentioned the following
I can construct them successfully if use dual simplex and set presolve to 0.
It should not be necessary to turn presolve off, and doing so will likely severely handicap the solve. You should also be able to use primal simplex, and setting ConcurrentMethod=3 will mean both dual and primal simplex are run in parallel, and you will potentially get a result faster. Have you experienced anything to suggest this wouldn't work?
- Riley
0 -
Dear Riley,
Thank you very much for your answer!
Indeed, you are right. With presolve on I can still retrieve the information I need. You are also right in that I can use the concurrent method and get what I need for the cuts, and I do get a result significantly faster. The acceleration occurs mainly for the first iteration; subsequent iterations seem to take up more time on average relative to dual simplex, but the overall running time has reduced substantially.
Thank you again!
Marilena
0 -
I have performed further tests with a Bender's decomposition algorithm with feasibility cuts (thus, with occasions that the slave problems are infeasible) and I have made some observations, the reasons for which are unclear to me.Initially, I used the concurrent method, without limiting the number of threads (set threads parameter to zero); solution time was ~300 seconds.
I then had to limit the number of threads to 4. My understanding is that, with this limitation, 1 thread would be occupied with primal simplex, 1 with dual simplex and the other 2 with barrier. Solution time increased almost ten times (>2700 seconds).
However, when I tried to solve the same problem choosing primal simplex as method, solution time decreased again, going back to approximately ~300 seconds.Could you help me understand this behaviour? I would expect that the concurrent method would be approximately as fast as the fastest of all three methods. This has been my understanding from the documentation as well as my experience up until now (albeit, with feasible models), but obviously this is not the case. Could this be related to the fact that the subrpoblem being solved is infeasible?
Moreover, it is puzzling to me why the selection of threads is affecting run time with the concurrent method, since a higher number of threads would not affect primal simplex. Finally, if the deceleration occurs because of higher memory requirements for the concurrent method, why is this an issue only when I limit the number of threads and not when I let them free?0 -
Hi Marilena,
I then had to limit the number of threads to 4. My understanding is that, with this limitation, 1 thread would be occupied with primal simplex, 1 with dual simplex and the other 2 with barrier.
This is correct.
However, when I tried to solve the same problem choosing primal simplex as method, solution time decreased again, going back to approximately ~300 seconds.
If we are running a single LP algorithm then the presolve routine will make changes to the model which benefit that algorithm. If we run concurrent LP then we have to strike a balance, but in particular there can be aspects of the presolved model which work well for barrier and not work well for the simplex algorithms. This is one reason why you may see better results by selecting primal simplex alone.
The other aspect to consider is performance variability. If you want to make an accurate comparison between setting 4 threads or leaving it at its default then you need to either test across many different instances of the model, or many different values of Seed. Ideally there is also nothing else running on the machine that would compete with Gurobi for CPU or RAM. See How can I make accurate comparisons?
I would tackle the obstacle of making an accurate comparison first, then if the results still suggest 4 threads is faster then we can explore a bit further.
- Riley
https://support.gurobi.com/hc/en-us/articles/26992650628369-How-can-I-make-accurate-comparisons
0
Please sign in to leave a comment.
Comments
4 comments