MATLAB: “linprog stopped because it exceeded its allocated memory” with the dual-simplex algorithm

dual-simplexlinprogmemory

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)
end
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!

Best Answer

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.
Related Question