Matlab intlinprog metrics differ, solver data identical

I'm seeing 2 disparate behaviours with when using Matlab's intlinprog optimizer. As luck would have it, it involves large-ish data sets. In 1 case, I do not set any of the intlinprog options, going with their defaults. In another case, I set:

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

The `intlinprog` output from the non-default options is:

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.                       

The output from the default options is:

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...>                

I manually stopped the execution because the default stopping conditions would have yielded a long search time.

Everything is identical up to the "Branch and Bound" section, but then the search is clearly not identical. To rule out numerical noise as the cause, I confirmed that all the `intlinprog` input arrays were identical using `isequaln`. In particular, arrays that do not exist in one case also don't exist in the other, e.g., Aeq, beq. In a similar manner, I ensured that the bevy of intlinprog options also matched, other than the 3 above. Unless there is a stochastic component of intlinprog of which I am unaware, the search should be identical.

What else can I check as the source of this discrepancy?

I am using Matlab 2019a.

Evidence that problem is innate to intlinprog

Here is a Test.m script that loads and shows features of the input array data, and the diary output. It clearly shows that that branch-and-bound starts at a different point, depending on whether the `RelativeGapTolerance` option is set. The optimization problem in question is a binary program.

% Test.m                                                       
%-------                                                       
diary off                                                      
dFN='Test.diary';                                              
if isfile(dFN); delete(dFN); end;                              
diary(dFN);                                                    
                                                               
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);                                           

Here is the output, showing the initial row of the branch-and-bound progress output for each case:

>> 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).                                         

[Matt J]

Are you running thes two versions on the same computer?

[FM]

Yes.