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

7 次查看（过去 30 天）
Andres Alban
Andres Alban 2019-1-22
评论： yienng wang 2021-11-10
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!

请先登录，再回答此问题。

采纳的回答

Derya
Derya 2019-1-22
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.

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Linear Programming and Mixed-Integer Linear Programming 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by