How to set stopping criteria in mixed integer programming?

Question

Frank Dou 2021-5-18

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/833098-how-to-set-stopping-criteria-in-mixed-integer-programming

评论： Frank Dou 2021-11-25

采纳的回答： Derya

在 MATLAB Online 中打开

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!

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Derya 2021-5-20

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Derya 2021-5-20

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/833098-how-to-set-stopping-criteria-in-mixed-integer-programming#answer_704838

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:

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

Kind Regards,

Derya