After some more investigation, I conclude that the new default 'dual-simplex-highs' algorithm used by linprog/intlinprog is flawed, if not buggy, at least in this specific test case in the above question.
Chasing what is wrong with 'dual-simplex-highs' in linprog
86 visualizzazioni (ultimi 30 giorni)
Mostra commenti meno recenti
Bruno Luong
il 12 Set 2024
Modificato: Matt J
il 21 Ott 2024 alle 22:45
I try to see why 'dual-simplex-highs' algorithm fails and 'dual-simplex-legacy' works OK on this specific LP problem of size 467.
The linear programming involves only linear equality constraints, and lower bounds x >= 0 on some components of x (but not all of them).
The Aeq size is 211 x 467 and the condion number is not high at all IMO (about 10). So I consider it is not a difficult problem numerically (?).
'dual-simplex-legacy' able to find the solution, however not the default algorithm 'dual-simplex-highs', the output does not help much what is wrong.
Can someone tell me where I could investigate further to the cause?
load('linprog_test.mat')
size(Aeq)
cond(full(Aeq))
linprogopt = optimset('Algorithm', 'dual-simplex-legacy');
[lpsol, ~, exitflag, out] = linprog(c, [], [], Aeq, beq, LB, UB, linprogopt)
linprogopt = optimset('Algorithm', 'dual-simplex-highs');
[lpsol, ~, exitflag, out] = linprog(c, [], [], Aeq, beq, LB, UB, linprogopt)
8 Commenti
Matt J
il 21 Ott 2024 alle 15:05
Modificato: Matt J
il 21 Ott 2024 alle 22:45
This seems like a more applicable test of whether the problem is well-conditioned. There does appear to be some sensitivity to it, though of course it may depend on epsilon
load('linprog_test.mat')
epsilon=1e-6;
linprogopt = optimoptions('linprog','Display','none','Algorithm','dual-simplex-legacy');
[lpsol0, ~, exitflag, out] = linprog(c, [], [], Aeq, beq, LB, UB, linprogopt);
size(lpsol0)
dev=inf(1,10);
for i=1:numel(dev)
[lpsol,~,exitflag] = linprog(c+randn(size(c))*epsilon, [], [], Aeq, beq, LB, UB, linprogopt);
if exitflag~=1, continue; end
dev(i)=norm(lpsol-lpsol0,inf);
end
dev
Risposta accettata
Derya
il 8 Ott 2024 alle 20:17
Hello all,
Thank you for providing the data for the failing problem, Bruno. And I'm sorry for the inconvenience.
As you noted there are two issues here: exitflag/interations/message inconsistency and dual-simplex-highs not finding a solution. We'll resolve the inconsistency in the exit condition shortly. We'll also address the issue with the dual-simplex algorithm (of HiGHS) that gets stuck at the initial iteration probably due to some automatic scaling done during the algorithm. Note that presolve doesn't do reductions in this case and is not the culprit:
Presolve : Reductions: rows 211(-0); columns 467(-0); elements 8741(-0) - Not reduced
Problem not reduced by presolve: solving the LP
Kind Regards,
Derya
Più risposte (2)
Catalytic
il 13 Set 2024
intlinprog offers some additional diagnostic output -
load('linprog_test.mat')
intlinprog(c,[], [], [], Aeq, beq, LB, UB)
Vedere anche
Categorie
Scopri di più su Systems of Nonlinear Equations in Help Center e File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!