Matlab intlinprog metrics differ, solver data identical

1 view (last 30 days)
FM
FM on 24 Nov 2020
Edited: FM on 25 Nov 2020
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).

Sign in to answer this question.

Answers (0)

Categories

Find more on Solver Outputs and Iterative Display in Help Center and File Exchange

Tags

Products


Release

R2019a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!