MATLAB Answers

"linprog stopped because it exceeded its allocated memory" with the dual-simplex algorithm

10 views (last 30 days)
Andres Alban
Andres Alban on 22 Jan 2019
Answered: Derya on 22 Jan 2019
I have a linear program with a parameter T that specifies the size of the problem. The number of variables and constraints increases linearly with T. I am solving the LP with linprog and the dual-simplex algorithm. I can solve it with T=10 without any issues. However, I need to solve it with T=100 and in this case, the output of the function is "Linprog stopped because it exceeded its allocated memory." For T=100, the number of variables is 400 and the number of constraints is 202 which is not a big problem and I have checked that I have plenty of memory available. I can solve the problem when I change the algorithm to interior-point without any issues. I do not see a reason why the dual-simplex method would run out of memory for such a small problem.
Here is my code and you can check that the problem is well-behaved by changing the algorithm to interior-point
T = 100;
m = 2*(T+1); % Number of constraints
% Objective coefficients
f = [ones(1,2*T) zeros(1,2*T)];
% Equality constraints
Aeq = zeros(m,4*T);
beq = zeros(1,m);
Aeq(1,2*T+1) = 1; % v0 = 0
beq(1) = 0;
Aeq(2,3*T+1) = 1; % x0 = 1
beq(2) = 0;
Aeq(m-1,[2*T-1,2*T,3*T]) = [1,-1,1]; % v(T-1) + a(T-1) = 0
beq(m-1) = 0;
Aeq(m,[3*T,4*T]) = [1,1]; % x(T-1) + v(T-1) = 1
beq(m) = 1;
for i = 1:(T-1)
Aeq(i+2,[2*i-1,2*i,2*T+i,2*T+i+1]) = [1,-1,1,-1]; % v(t) + a(t) = v(t+1)
Aeq((T-1)+i+2,[2*T+i,3*T+i,3*T+i+1]) = [1,1,-1]; % x(t) + v(t) = x(t+1)
lb = [zeros(1,2*T) -ones(1,2*T)*inf];
options = optimoptions('linprog','Display','iter','Algorithm','dual-simplex');
[x,fval,exitflag,output] = linprog(f,[],[],Aeq,beq,lb,[],options);
How can I get the dual-simplex method to work in this case? Is there any issue with code?
Thank you!

Accepted Answer

Derya on 22 Jan 2019
Hello Andres.
Actually, you have uncovered a bug in the presolving phase of the dual-simplex code. I apologize for the inconvenience. We'll fix the issue in an upcoming release. Meanwhile, to solve your problem using the dual-simplex algorithm, you can turn off the presolving (or preprocessing) by typing:
options.Preprocess = 'none';
Note that 'Preprocess' does not show in the options display, because it is a “hidden” option. Changing it from it's default setting is not recommended except as a workaround for a rare bug condition in presolving phase.
Thank you very much for your question and providing the reproduction example for the bug.
Kind Regards,
Derya Ozyurt
Developer at The MathWorks, Inc.

More Answers (0)

Community Treasure Hunt

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

Start Hunting!