How to set stopping criteria in mixed integer programming?

Hi guys~

Recently, I am using mixed integer programming to solve a problem.

Actually, I want to let it stop when Relative gap is less than 2%.

So I set according to https://www.mathworks.com/help/optim/ug/intlinprog.html#btv2x05

options = optimoptions(@intlinprog,'RelativeGapTolerance',0.2,'Display','iter')
[x,fval]=intlinprog(f,iint,A,b,[],[],lb,ub,[],options);

Yet, it seems like this setting doesn't work. It have been running for 30min...

Any suggetions? Thank you very much!

[Derya]

I assume 'RelativeGapTolerance',0.02, for the output underneath the setting of options.

Answer 1

[Derya]

Hello Frank,

The stopping tolerance is automatically modified to

tolerance = min(1/(1+|L|), RelativeGapTolerance)

As described in https://www.mathworks.com/help/optim/ug/intlinprog.html#btv2x05.

I estimate the lower bound, L, for your problem at around 96, so intlinprog tolerance for stopping on relative gap would be around 0.01, i.e. 1%. It looks like intlinprog cannot reduce the gap from 1.54% in the following 30 minutes.

You have couple of options:

1. Increase AbsoluteGapTolerance, e.g. to 2.
2. Divide the objective function by a factor 2 or more, perhaps 10.
3. Set CutGeneration and/or Heuristics to 'intermediate' and see if this reduces the time to solution.

Kind Regards,

Derya

[Frank Dou]

Btw, how could I find the running time complexity of the solver

[x,fval]=intlinprog(f,iint,A,b,[],[],lb,ub,[],options);

Thank you very much!