Matlab intlinprog metrics differ, solver data identical
1 view (last 30 days)
Show older comments
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).
2 Comments
Answers (0)
See Also
Categories
Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!