Linprog Error - Matrix Coefficients are too Large

I'm trying to use linprog to calculate the smallest amount of time to accumulate gear damage targets in a mechanical durability test. I have 7 cases (maneuvers) which each generate a certain amount of damage (there are 5 damage equations). I would like to determine how many cycles of each case to perform to reach all 5 damage targets in the shortest amount of time possible.

lb=zeros(7,1);
lb(1)=4000;
lb(2)=70000;
lb(3)=70000;
lb(4)=90000;
lb(5)=40000;
lb(6)=340000;
lb(7)=390000;

ub=inf(7,1);
ub(1)=5000;
ub(2)=80000;
ub(3)=80000;
ub(4)=100000;
ub(5)=50000;
ub(6)=350000;
ub(7)=400000;

A=zeros(0,7);
b=zeros(0,0);

Aeq=zeros(5,7); % Equations 
Aeq(1,[1,2,3,4,5,6,7])=[2.56e13,8.55e12,0,8.79e12,0,1.5e12,4.58e11];
Aeq(2,[1,2,3,4,5,6,7])=[0,0,5.9e12,0,1.41e13,9.25e11,2.04e11];
Aeq(3,[1,2,3,4,5,6,7])=[9.67e32,1.42e31,0,3.29e30,0,1e31,3.63e31];
Aeq(4,[1,2,3,4,5,6,7])=[0,0,5.17e31,0,2.86e32,2.75e30,4.09e30];
Aeq(5,[1,2,3,4,5,6,7])=[1.57e21,9.515e20,9.515e20,1.165e21,1.165e21,8.67e19,1.688e21];

beq=zeros(5,1); % Damage Targets
beq(1)=1.87e18;
beq(2)=1.07e18;
beq(3)=1.98e37;
beq(4)=1.24e37;
beq(5)=7.19e26;

f=zeros(7,1); % The time it takes for each cycle to be performed
f(1)=28.2;
f(2)=22.8;
f(3)=19.2;
f(4)=45.6;
f(5)=23.5;
f(6)=2.8;
f(7)=1;

[x fval] = linprog(f,A,b,Aeq,beq,lb,ub)

I get the following error:

Error using linprog (line 345)

LINPROG stopped because some objective or constraint matrix coefficients are too large in magnitude.

Error in Attempt2 (line 146)

[x fval] = linprog(f,A,b,Aeq,beq,lb,ub)

I'm not sure why it won't solve as I know there are solutions within the bounds I have specified. Is this just a case of the damage coefficients being too large?

Thank you!

Answer 1

[Alan Weiss]

The default linprog algorithm is the same as a portion of the intlinprog algorithm, a dual-simplex method. For this algorithm, large coefficients are disallowed. I suggest that you scale some of your coefficients to be in a smaller range and then rescale the solution afterward. Or, switch to the 'interior-point' algorithm. Still, solvers struggle with poorly-scaled problems, so you will probably get more reliable answers if you scale your coefficients.

One more thing: pass A and b as [] instead of zero matrices.

Alan Weiss

MATLAB mathematical toolbox documentation

[Luka Celic]

Hi Alan,

Thank you for your reply. I am assuming that scaling and rescaling the coefficients in this problem is not as simple as dividing the large values by 10^20 for example and then multiplying them again once the algorithm is done solving (I've tried this and the solver is saying there are no solutions in the given range when I know there are). Do you have any tips on how to do this?

Thank you!

Luka

[Alan Weiss]

Your Aeq and beq matrices can be divided by, say 1e20 with no change in their meaning. There is nothing that else to do other than dividing each row of each matrix by an appropriate large value.

Alan Weiss

MATLAB mathematical toolbox documentation

[Luka Celic]

I've tried this now, but I'm receiving a 'No feasible solution found. Linprog stopped because no point satisfies the constraints.' message when attempting to solve even though I know there are solutions within the constraints (I've done the calculations by trial and error in excel). Is there anything I'm missing in my logic to solving this problem?

Thanks!

Luka

[Alan Weiss]

The problem as you gave it is infeasible. You can see this by calculating

Aeq*lb - beq

You get all positive entries. (I suggest that you scale things first to avoid numerical issues.) This means that, even with the entries of x as small as the lower bound allows, they are still larger than the linear constraints would want (all entries of Aeq are nonnegative, so the only way to get the entries of Aeq*x to be as small as beq is to have some be less than their lower bounds).

If you think that you have some point that works, well, all I can guess is that the very large scale causes numerical issues in Excel and leads to a spurious solution. But the problem, as given, is infeasible.

Alan Weiss

MATLAB mathematical toolbox documentation

[Luka Celic]

I've scaled the numbers and changed the lower bounds to zero. Now the Aeq*lb - beq expression is negative.

lb=zeros(7,1);
lb(1)=0;
lb(2)=0;
lb(3)=0;
lb(4)=0;
lb(5)=0;
lb(6)=0;
lb(7)=0;

ub=inf(7,1);
ub(1)=5000;
ub(2)=80000;
ub(3)=80000;
ub(4)=100000;
ub(5)=50000;
ub(6)=350000;
ub(7)=400000;

>> Aeq*lb-beq

ans =

   1.0e+12 *

   -0.0000
   -0.0000
   -1.9800
   -1.2400
   -0.0000
   
 

However, I still get a "No feasible solution found" error. Is there something else I am doing wrong with this problem?

Thank you!

Luka

[Alan Weiss]

Your problem is, doubtless, still infeasible. See Check Linear Constraints.

Alan Weiss

MATLAB mathematical toolbox documentation