• Gurobi Staff

Hi Carlos,

It seems that you are iteratively solving many related problems.
What algorithm have you implemented? Maybe you are using an external package to solve this?

The first thing I am noticing is the line:

Optimal solution found at node 45785 - now completing solution pool...

This means that non-default parameters are being used (setting the PoolSearchMode or related parameters)
Does the algorithm require multiple solutions?

Cheers,
David

Hello David!

Yes, I am interested in many solutions at the same time. The concept of this MILP is to have a network and find the minimal cut set that renders the network unable to produce biomass. Every solution found is added as a constraint so it does not come up again.

To your first question, I have developed the problem formulation in python and I am using the gurobi api to solve it. After retreving the solutions I add them as constraints as explained above and then optimize the problem again.

But I found that larger time limits gave me better results that optimizing many times with smaller time limits, I do not know if this is clear.

My goal is to try and reduce the computational time if possible.

• Gurobi Staff

Hi Carlos,

I think I understand: so are you adding constraints to remove all the previously found solutions?
In that case, it is expected that the problem gets harder and harder as the process goes on.
What is the end goal? Surely you will end up with an infeasible problem? If you have a reference (paper or book) for this algorithm maybe this will be a bit clearer.

As far as Gurobi parameters go, I can probably recommend MIPFocus = 2 or 3 as a good incumbent is found easily (typically within the first 1s or so) but the bound takes a lot of effort to improve (which is why longer times help).

Cheers,
David

Hello again David,

I can give you a quick layout of how it is intend to work, we launch the optimization problem and gurobi is very good at finding solutions of length 1, we add does constraints and try to solve for the solutions of length 2 and so on. The length is a parameter that we can change, we are doing our benchmarks to see how many time does it take to solve with differents lengths.

If the optimization returns no solution the algorithm stops or optimality is reached and the length of the solution is the desired one.

Yes, I have set the MIPFocus to 3 and I having good results.

So, I come up with some questions,

I am currentry using these parameters:

integralityTolerance = 1e-5
# Setting gurobi parameters
env = interface.Env(empty=True)
env.setParam(
"OptimalityTol", integralityTolerance
)  # equivalent to mip.tolerances.integrality
env.setParam("Heuristics", 0.1)  # equivalent to mip.strategy.heuristicfreq
env.setParam("RINS", 150)  # equivalent to mip.strategy.rinsheur
env.setParam("MIPFocus", 3)  # equivalent to emphasis.mip
env.setParam("TimeLimit", max(1, timelimit))  # equivalent to timelimit
env.setParam("PoolSolutions", 10000)  # store up to 10,000 solutions
env.setParam("PoolGap", 0.01)  # allow up to 1% gap from optimal solution
env.setParam("PoolSearchMode", 1)  # focus on finding diverse solutions
env.setParam("Cutoff", cutoff)  # stop after finding maxKOLength solutions

Carlos
• Gurobi Staff

Hi Carlos,

Cool, thanks for the extra info.

I would consider removing the Heuristics + RINS parameters.
If this doesn't harm the model, MIPFocus 3 should be enough.
Also, I would leave OptimalityTol also out, if you want to control the integrality tolerance you can use IntFeasTol.

This is a tricky problem though. Some other things I would try:

• Strengthen the model somehow using the information from the solution (maybe reduce the size of the next graph?). Try different ways of cutting off the solution.
• Reformulating your SOS constraints or playing around with PreSOS1Encoding/PreSOS2Encoding (depending on the type of constraint that you have). This may result in a model that converges faster.
• Maybe also play around with Presolve.

Cheers,
David

Sounds amazing David, thanks for the suggestion.

Could there be a way to given a timelimit status, resend the same problem with the known solutions. Instead of adding them as constraints, more like a wam start. Talking to you I came up with that idea.

• Gurobi Staff

Hi Carlos,

That is possible but it won't help with speeding up the bound (the current bottleneck) as with MIP start you will be providing a new incumbent (which I suspect is already the optimal value and this is found fairly easily).

Cheers,
David

Hey David,

Thanks for commenting back, I have some updates.

The PreSOS1Encoding with value 2 is giving me better results. So many thanks for the suggestion, I have also implemented a piece of code that sets the bounds of some variables to zero if a condition is met.

But I am stilling getting long computational times for > 10,000 seconds for some problems.

Why can gurobi find the optimal in  problems the first problems but then it cannot,

Is it that at first it uses the variables directly and the it needs to do combinations of variables?

Thanks David,

Carlos

• Gurobi Staff

Hi Carlos,

The PreSOS1Encoding with value 2 is giving me better results. So many thanks for the suggestion, I have also implemented a piece of code that sets the bounds of some variables to zero if a condition is met.

Nice!

Why can gurobi find the optimal in  problems the first problems but then it cannot,

Is it that at first it uses the variables directly and the it needs to do combinations of variables?

Indeed, it seems that this problem gets much harder as the length increases.
This is sometimes called combinatorial explosion, i.e. problems get exponentially harder as you increase the length. You can see this in your log as the number of unexplored nodes in your tree grows and remains quite high (probably for a while even in your 10000s runs), this indicates that the solver will probably struggle.

You should explore alternative formulations for your problem. It is possible that better/different formulations (or even solution procedures!) exist in the literature that lead to tighter relaxations.

Un saludo,
David