linprog: no feasible solution found when defining lower boundaries

When running linprog as follows "No No feasible solution found. Linprog stopped because no point satisfies the constraints.":

N=100;

M= 262144;

coef_obj_func = ones(N,1) ;

A = 2M by N matrix (can not attach it as it exceeds the max allowable attachment size)

b_tot = 2*M by 1 matrix (can not attach it as it exceeds the max allowable attachment size)

Aeq = [];

beq = [];

lb = zeros(N,1)

ub = ones (N,1)

options=optimoptions('linprog','Algorithm','dual-simplex','Display','iter','Diagnostics','on')

[solution_obj_fun,values,exitflag,output]=linprog(coef_obj_func,A,b_tot,[],[],lb,ub,options);

I tried reducing N and M, but still it seems the lb forms the issue. When I put lb=[], a solution can be found. However I am sure that there is a solution when N and M are low AND lb=zeros.

Can someone help me how to relax the problem/preprocess the data set with large N and M so that an optimal solution can be found?

Thanks in advance,

Hanne

Answer 1

[John D'Errico]

I don't understand what is the issue. linprog apparently says that the only solutions to your problem exist when some of the unknowns are less than zero, or perhaps larger than 1. We are not told if solutions exist when the lower bounds are not set, of course, but by implication from your question...

You've created a complicated problem that has no solution in the realm you want to find a solution. Perhaps you've made a mistake in the equations, setting up the problem. Is that possible? Of course it is, since what you tell us makes no sense, in that b_tot is incompatible in size with the problem you have posed.

That is, we have been told that A is 2*M by N, and that b_tot is n*Mx1. There are N=100 unknowns, so the unknown vector is of size 100x1.

These equations will be used to satisfy the inequality constraints

A*x >= b_tot

A*x will be a vector of length 2*Mx1. That is how matrix multiplication works. So I must assume that the unknown variable n is probably 2? If not, then linprog should fail immediately due to another error as a size compatibility check.

But if you are not careful enough to tell us the correct situation, then the odds are decent that you made a mistake somewhere in your code too. I cannot know that. I'll assume the undefined value of n just happens to be 2. Or, I suppose n could be just a typo, but n and 2 fall very far apart on the keyboard.

Regardless, linprog has told you the situation. Just because you want a solution to exist in the unit cube is not relevant. Linprog says that no feasible solution lives there. Perhaps this could be an issue of double precision, in that the equations have some nasty looking coefficients that cause this failure. But we don't get to see any information that would tell us if this is true.

You tell us only that the lower bounds cause the problem. So if you define no lower bounds at all, setting lb = [], is a solution found? One that has some of the unknowns less than zero? Or does linprog then tell you the problem is unbounded? Have you tried it by setting lower bounds that are some sufficiently negative value? Does a solution exist then?

Nothing says that every problem we formulate has a nice solution. Mathematics does not work that way. Sometimes a mistake is made in writing down the equations. Sometimes it is just that no solution exists, and your model of the process has flaws. Sometimes there are numerical probems in how you formulated the equations. But from a distance we can never know what it is.