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

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!

Answer 1

[Derya]

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.

[yienng wang]

Thanks so much, I have met exactly the same question.