TolGapRel (RelativeGAp) in intlinprog

Dear All,

I am using intlinprog for my 0-1 ILP model. Since it doesn't need to be that accurate, I can allow it to stop at a fairly high Relative Gap. However I noticed two issues using the TolGapRel option:

1. When I set it to for example 5e-1, the solver will stop when the relative gap between the upper and lower boundary is less or equal to 0.005 (0.5%) contrary to the MathWorks Documentation which says:

TolGapRel=(U-L)/(U+1) which in fact is a factor 100 smaller, since this value in the range [0, 1] I cannot set the TolGapRel at a value > 1%.

2. This second issue is for me the even more important: when I set the TolGapRel at a value for instance 5e-1 the solver will not stop the solve process if it already found values which have a TolGapRel < 5e-1 before it started with the branch and bound process and just continue in the branch and bound process until it hits the standard value of 1e-4.

Are these bugs in the TolGapRel option? Can I solve these issues?

Kind regards, R. Cornelissen

Answer 1

[Derya]

Hello Robbert,

The value of TolGapRel is not in percentages. However, the relative gap in the iterative display is given in percentages.

I believe the confusion comes from the fact that intlinprog reduces the effective relative gap tolerance when the objective function values are high. For instance, if you set TolGapRel to 0.05 (5%) but your objective function value for the initial LP is in the order of 1e8, intlinprog chooses a relative gap tolerance near 1e-8.

I think this behavior should be noted in the documentation.

Assuming that your problems have large objective function values, one possible solution is scaling the objective function. Another solution would be to use the absolute gap tolerance (TolGapAbs) that corresponds to your relative tolerance, instead of TolGapRel.

Kind Regards,

Derya

[robbert]

Great thanks for this answer, reducing the objective function by a factor of 1000 worked. One more question, would it be possible to run the branch and bound process on multi-cores? I guess the process is quite suitable for it.

[Derya]

Hi Robbert,

Currently, intlinprog doesn't utilize multi-cores.

Kind Regards,

Derya