Matlab intlinprog度量不同，求解器数据相同

Question

使用Matlab时，我看到了两种不同的行为intlinprog优化器。幸运的是，它涉及大量的数据集。在1种情况下，我不设置任何intlinprog选项，与他们的违约。在另一种情况下，我设置：

MaxTime = 1e5; // Seconds of search time
MaxNodes = 1e7;
RelativeGapTolerance = 1.5e-2;

非默认选项的intlinprog输出为：

LP:                Optimal objective value is -357.115403.
Heuristics:        Found 3 solutions using rounding.
Upper bound is -335.773578.
Relative gap is 11.77%.
Cut Generation:    Applied 32 cover cuts, 19 mir cuts,
and 1 Gomory cut.
Lower bound is -375.424457.
Relative gap is 11.77%.
Heuristics:        Found 1 solution using rounding.
Upper bound is -343.770009.
Relative gap is 9.18%.
Heuristics:        Found 14 solutions using rounding.
Upper bound is -365.852376.
Relative gap is 2.61%.
Branch and Bound:
nodes     total   num int        integer       relative
explored  time (s)  solution           fval        gap (%)
10000     88.99        21  -3.688905e+02   1.733665e+00
18380    123.86        22  -3.702995e+02   1.347593e+00
RelativeGapTolerance met.  Stopping.

默认选项的输出为：

LP:                Optimal objective value is -357.115403.
Heuristics:        Found 3 solutions using rounding.
Upper bound is -335.773578.
Relative gap is 11.77%.
Cut Generation:    Applied 32 cover cuts, 19 mir cuts,
and 1 Gomory cut.
Lower bound is -375.424457.
Relative gap is 11.77%.
Heuristics:        Found 1 solution using rounding.
Upper bound is -343.770009.
Relative gap is 9.18%.
Heuristics:        Found 14 solutions using rounding.
Upper bound is -365.852376.
Relative gap is 2.61%.
Branch and Bound:
nodes     total   num int        integer       relative
explored  time (s)  solution           fval        gap (%)
10000     88.53        21  -3.685595e+02   1.824775e+00
20000    127.96        21  -3.685595e+02   1.824775e+00
<...INTERRUPTED FROM SHELL COMMAND LINE...>

我手动停止了执行，因为默认停止条件会导致很长的搜索时间。

一切都是一样的，直到"；分支和绑定"；部分，但是搜索显然不完全相同。将数字噪声排除为原因，我确认所有的intlinprog输入阵列使用CCD_ 5相同。特别是不存在的数组在一种情况下也不存在于另一种情况中，例如Aeq、beq。这两种情况的数据都是通过在调用intlinprog之前保存工作空间来获取的。

在以类似的方式，我确保了intlinprog选项也匹配，除了上面的3个。除非存在随机intlinprog的组件，我不知道，搜索应该是完全相同的

我还能查到什么是这种差异的来源？

我使用的是Matlab 2019a。

问题是intlinprog固有的证据

下面是一个Test.m脚本，它加载并显示输入的特性数组数据和日志输出。它清楚地表明分支和绑定从不同的点开始，这取决于RelativeGapTolerance选项已设置。中的优化问题问题是一个二进制程序。

% Test.m
%-------
clear classes
clear java
load('ILPprobStruc.mat');
disp('ILPprob='); disp(ILPprob);
disp('Call intlinprog without setting RelativeGapTolerance.')
ILPprob.options = optimoptions( @intlinprog, 'MaxNodes',1e4 );
intlinprog(ILPprob);

clear classes
clear java
load('ILPprobStruc.mat');
disp('Call intlinprog with RelativeGapTolerance=1.5e-2.')
ILPprob.options = optimoptions( @intlinprog , ...
'MaxNodes',1e4 , 'RelativeGapTolerance',1.5e-2 );
intlinprog(ILPprob);

这是输出，显示了分支的初始行和每种情况的绑定进度输出：

>> Test
ILPprob= f: [1642×1 double]
intcon: [1×1642 double]
bineq: [482×1 double]
lb: [1×1642 double]
ub: [1×1642 double]
solver: "intlinprog"
Aineq: [482×1642 double]
Call intlinprog without setting RelativeGapTolerance.
LP:                Optimal objective value is -357.115403.
Heuristics:        Found 3 solutions using rounding.
Upper bound is -335.773578.
Relative gap is 11.77%.
Cut Generation:    Applied 32 cover cuts, 19 mir cuts,
and 1 Gomory cut.
Lower bound is -375.424457.
Relative gap is 11.77%.
Heuristics:        Found 1 solution using rounding.
Upper bound is -343.770009.
Relative gap is 9.18%.
Heuristics:        Found 14 solutions using rounding.
Upper bound is -365.852376.
Relative gap is 2.61%.
Branch and Bound:
nodes     total   num int        integer       relative
explored  time (s)  solution           fval        gap (%)
10000     97.30        21  -3.685595e+02   1.824775e+00
Solver stopped prematurely. Integer feasible point found.
Intlinprog stopped because it reached the maximum number of nodes,
options.MaxNodes = 10000 (the selected value). The intcon
variables are integer within tolerance, options.IntegerTolerance =
1e-05 (the default value).
Call intlinprog with RelativeGapTolerance=1.5e-2.
LP:                Optimal objective value is -357.115403.
Heuristics:        Found 3 solutions using rounding.
Upper bound is -335.773578.
Relative gap is 11.77%.
Cut Generation:    Applied 32 cover cuts, 19 mir cuts,
and 1 Gomory cut.
Lower bound is -375.424457.
Relative gap is 11.77%.
Heuristics:        Found 1 solution using rounding.
Upper bound is -343.770009.
Relative gap is 9.18%.
Heuristics:        Found 14 solutions using rounding.
Upper bound is -365.852376.
Relative gap is 2.61%.
Branch and Bound:
nodes     total   num int        integer       relative
explored  time (s)  solution           fval        gap (%)
10000     98.74        21  -3.688905e+02   1.733665e+00
Solver stopped prematurely. Integer feasible point found.
Intlinprog stopped because it reached the maximum number of nodes,
options.MaxNodes = 10000 (the selected value). The intcon
variables are integer within tolerance, options.IntegerTolerance =
1e-05 (the default value).

Answer 1

MathWorks解释说RelativeGapTolerance确实会影响搜索策略。因此，如果将RelativeGapTolerance设置为远离其默认值，则可以预期不同的搜索路径。