# Linprogr in Matlab not finding a solution when a solution exists

15 views (last 30 days)
CT on 14 Aug 2019
Answered: Derya on 15 Aug 2019
I am solving a linear programming in Matlab using linprogr. All the matrices are attached.
clear
rng default
f=zeros(size(x,1),1);
possible_solution = linprog(f,Aineq,bineq,Aeq,beq, lb, ub);
The output is
No feasible solution found.
Linprog stopped because no point satisfies the constraints.
From some theory behind the problem, I know that the vector x (uploaded together with the other matrices) should be a solution of linprog(f,Aineq,bineq,Aeq,beq, lb, ub).
In fact, x seems to satisfy all the constraints, except the equality constraints. However, regarding the equality constraints, the maximum absolute difference between Aeq*x and beq is around 3*10^(-15). Hence, also the equality constraints are almost satisfied by x.
check_lb=sum(x>=0)==size(x,1);
check_ub=sum(x<=1)==size(x,1);
check_ineq=(sum(Aineq*x<=bineq)==size(Aineq,1));
check_eq=max(abs((Aeq*x-beq)));
Therefore, my question is: why linprog(f,Aineq,bineq,Aeq,beq, lb, ub) does not find x as solution? It does not seem to be a problem of the equality constraints, because if I remove the inequality constraints and run
rng default
possible_solution_no_inequalities = linprog(f,[],[],Aeq,beq, lb, ub);
the program finds a solution. Is it a matter of numerical precision? How can I control for that?

Bruno Luong on 14 Aug 2019
Edited: Bruno Luong on 14 Aug 2019
It looks to me LINPROG is flawed or buggy in your case. I try to remove suspected constraints and change beq so that the equality is satisfied by x, and LINPROG still fails.
f=zeros(size(x,1),1);
Aeq = round(Aeq);
beq = Aeq*x;
keep = max(abs(Aineq),[],2)>1e-10;
all(x>=lb)
all(x<=ub)
all(Aineq*x<=bineq)
all(Aeq*x==beq)
% This will fail to return solution
options = optimoptions('linprog','Algorithm','interior-point','ConstraintTolerance',1e-3);
xlinprog = linprog(f,Aineq(keep,:),bineq(keep,:),Aeq,beq, lb, ub, options);
But if I call QUADPROG it will returns a solution
% This will returns a solution
H = sparse(size(x,1),size(x,1));
CT on 14 Aug 2019
Thanks. I tried to call gurobi from Matlab (in place of linprogr): gurobi always finds a solution.

Derya on 15 Aug 2019
Hello CT,
linprog with 'Preprocess' option set to 'none' will give you a solution. Then, by decreasing the 'ConstraintTolerance' you may get a solution with better feasibility measures. Since the problem is numerically challenging(*) you may need to examine any solution found (by any solver) carefully.
Thank you very much for providing the example. Using it, we'll try to improve linprog so that it can solve these type of problems with its default settings.
Kind Regards,
Derya
(*)
1. there are very small coefficient in matrices which are below some of the tolerances used in our numerical algorithms.
2. the ratio between the largest and smallest absolute values of coefficients in the constraint matrices is large.