Meaning of "Intlinprog stopping at the root node"

Question

ilke ALTIN 2020-11-29

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/667838-meaning-of-intlinprog-stopping-at-the-root-node

评论： ilke ALTIN 2020-11-29

Hello,

When I use intlinprog for my 3D assignment problem which is an NP hard linear integer program, I get the following message almost every time:

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value,

options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance,

options.IntegerTolerance = 1e-05 (the default value).

The solution is integer as expected and seems to be correct. What I would like to ask is intlinprog stopping at the root node. What shall I understand from this message? I assume that intlinprog uses a branch and bound like algorithm, which shall search for the solution in many possible branches. Could anyone please guide me regarding this message?

Best Regards,

ilke

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

Ameer Hamza 2020-11-29

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/667838-meaning-of-intlinprog-stopping-at-the-root-node#answer_559273

编辑：Ameer Hamza 2020-11-29

It is a term defined in the LP algorithms. Rood node is the relaxed LP problem. It is difficult to describe everything in this answer so you can find the detail at this link: https://www.mathworks.com/help/optim/ug/mixed-integer-linear-programming-algorithms.html

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

ilke ALTIN 2020-11-29

Thank you very much, after checking the link that you have shared I have realized that the problem that I have defined has the same solution for intlinprog, and linprog because linprog also finds integer solutions. I believe that is the reason the intlinprog finds the solution at the root node.

请先登录，再进行评论。