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

Question

当使用Matlab的intlinprog优化器时，我看到了两种完全不同的行为。幸运的是，它涉及大量的数据集。在1种情况下，我不设置任何intlinprog options，使用它们的默认值。在另一种情况下，我设置：

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的所有isequaln输入阵列是相同的。特别是，在一种情况下不存在的数组在另一种情况下也不存在，例如，Aeq、beq。这两种情况的数据都是通过在调用intlinprog之前保存工作区来捕获的。

以类似的方式，我确保了intlinprog选项的数量也是匹配的，除了上面的3。除非有一个我不知道的intlinprog的随机成分，搜索应该是相同的。

作为这种差异的根源，我还能查到什么？

我正在使用Matlab2019a。

证明问题是intlinprog 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设置为默认值，则可能会出现不同的搜索路径。