intlinprog quits due to incorrect Relative Gap

I am calling intlinprog indirectly using Problem-Based Approach (https://www.mathworks.com/help/optim/problem-based-approach.html). In PBA, the "solve" function calls intlinprog on behalf of the user.

I've run a few variations of my problem, and the outputs seem to make sense. I then ran into a variation whose output seems incomprehensible:

LP: Optimal objective value is -111.937682.       
                                                  
Optimal solution found.                           
                                                  
Intlinprog stopped at the root node because       
the objective value is within a gap tolerance     
of the optimal value,                             
options.RelativeGapTolerance = 0.01 (the          
selected value). The intcon variables are         
integer within tolerance,                         
options.IntegerTolerance = 1e-05 (the default     
value).                                           
                                                  
RETURN VALUES                                     
                                                  
fval = 111.0559                                   
exitflag = OptimalSolution                        
output = struct with fields:                      
        relativegap: 15.5046                      
        absolutegap: 17.3740                      
      numfeaspoints: 1                            
           numnodes: 0                            
    constrviolation: 2.2204e-16                   
            message: 'Optimal solution found.     
                     Intlinprog stopped at the    
                     root node because the        
                     objective value is within    
                     a gap tolerance of the       
                     optimal value,               
                     options.RelativeGapTolerance 
                     = 0.01 (the selected         
                     value). The intcon           
                     variables are integer        
                     within tolerance,            
                     options.IntegerTolerance     
                     = 1e-05 (the default         
                     value).'                     
             solver: 'intlinprog'                 

The output indicates that intlinprog quits because the Relative Gap is within the 1% threshold. However, it is clearly above 15%.

What can I do to sleuth this down further? I am using MATLAB 2019a.

Answer 1

[FM]

TMW suggest scaling the data so as to reduce the dynamic range. What I found to work was to rescale the objective function so that the nonzero coefficient with the smallest magnitude was 1.0. I also went through each inequality constraint, rescaling so that the smallest coefficient was 1.0 (I treated the right-hand-side constant as a coefficient as well).