Intlinprog can not find feasible solution even though there is one
40 次查看(过去 30 天)
显示 更早的评论
I am currently using the 'intlinprog' solver to solve a MIP problem. In some cases, I got the following result
"No feasible folution found."
"Intlinprog stopped because no point satisfies the constraint."
However, I do have one solution, which I already testet and it satisfies the linear constraint, integer constraint, and also the lower and upper bound constraint.
Then I set this "feasible" solution as the initial point x0 for the solver. It still gave me the same message.
Afterwards, I followed the suggestion (https://support.gurobi.com/hc/en-us/community/posts/360056102052-Test-if-the-start-solution-is-feasible) and also defined the lower and upper bound of the variable exactly as this feasible solution. This means that in the feasible space there is only this point. After adding all these constraints, "intlinprog" finally found the feasible point.
Can any one please help me? Is there something that I have missed to configure??
load('Asen.mat')
load('a.mat')
% Extract the dimension of Asen, the transform matrix
% m - row number
% n - column number
m = size(Asen,1);
n = size(Asen,2);
% Artificially generate the result 'ob'
ob = Asen*a;
% define value of M in big M-constriant
M = 1e5;
% define the indicies of two variables in 'intlinprog'
xvar = 1:n;
yvar = n+1:2*n;
% set the intcon variable to the indicies of y -> put integer constraint on y
intcon = yvar;
% intcon = [];
% set lower and upper bound of both variales
% x will be positive but not greater than M, since y should be binary vector, it is constraint by bound 0<=y<=1
lb = zeros(2*n,1);
ub = ones(2*n,1);
ub(xvar) = M;
% Construct linear equality and inequality constraints
% The inequality constraint defined by A and b make y to be 1 when x~=0, and y to be 0 when x==0
Atemp = eye(n);
A = [Atemp, -M*Atemp];
b = zeros(n,1);
% The equality constraint defined by Aeq and beq put the constraint Asen*x==ob.
Aeq = [Asen,zeros(m,n)];
beq = ob;
% Objective function in 'inlinprog': counting the number of nonzeros(calculating the sum of y vector)
f = [zeros(n,1);ones(n,1)];
%optimize
option = optimoptions('intlinprog','IntegerTolerance',1e-6,'ConstraintTolerance',1e-3,'CutGeneration','advanced');
[xLinInt, fval, exitFlagInt, output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,[],option);
% extract the variable x if there is a solution
if ~isempty(xLinInt)
xval = xLinInt(xvar);
end
First a vector 'a' in length 103 is loaded. 'Asen' is a predefined matrix with dimension 202*103. Then 'ob' is obtained with 'ob=Asen*a'. The solver 'intlinprog' is supposed to find the sparsest solution 'a' satisfying 'ob=Asen*a', which is not necessarily be the original 'a' resulting 'b'. In the model, variable 'x' represent the value of 'a', binary variable 'y' in the solver represents the nonzeroness of 'x'. The objective function is to count the number of nonzero elements in x, which equals to the sum of all elements in y.
The matrix 'Asen' I used is in the attachment along with vector 'a'.
It is very strange that Matlab 2019a is not able to find a single solution. At least the original vector a I used to generate should be one feasible solution.
9 个评论
Walter Roberson
2020-5-2
Unfortunately all of the useful parts of intlinprog are inside .p files, so I cannot track to see why the difficulty is showing up.
回答(4 个)
Matt J
2020-5-4
编辑:Matt J
2020-5-4
This version finds a solution. Basically, I pre-normalize max(Asen(:)) and max(a(:)) to 1 so that the constraint matrix elements don't vary so widely in order of magnitude:
load('Asen.mat')
load('a.mat')
Asen(~any(Asen,2),:)=[]; %get rid of all-zero rows
Asen=Asen/max(Asen(:)); %normalize
M0 = 1e5;
ob = Asen*a/M0; %Normalize upper bound of a(i) to 1
M=1;
m = size(Asen,1);
n = size(Asen,2);
% define the indicies of two variables in 'intlinprog'
xvar = 1:n;
yvar = n+1:2*n;
% set the intcon variable to the indicies of y -> put integer constraint on y
intcon = yvar;
% intcon = [];
% set lower and upper bound of both variales
% x will be positive but not greater than M, since y should be binary vector, it is constraint by bound 0<=y<=1
lb = zeros(2*n,1);
ub = ones(2*n,1);
ub(xvar) = M;
% Construct linear equality and inequality constraints
% The inequality constraint defined by A and b make y to be 1 when x~=0, and y to be 0 when x==0
Atemp = eye(n);
A = [Atemp, -M*Atemp];
b = zeros(n,1);
% The equality constraint defined by Aeq and beq put the constraint Asen*x==ob.
Aeq = [Asen,zeros(m,n)];
beq = ob;
% Objective function in 'inlinprog': counting the number of nonzeros(calculating the sum of y vector)
f = [zeros(n,1);ones(n,1)];
%optimize
option = optimoptions('intlinprog');
[xLinInt, fval, exitFlagInt, output] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,[],option);
% extract the variable x if there is a solution
if ~isempty(xLinInt)
xval = xLinInt(xvar)*M0; %Restore original scale by multiplying with M0.
end
2 个评论
Matt J
2020-5-4
编辑:Matt J
2020-5-4
The equation Asen*x=ob actually only have one solution a because rank(Asen)=n and the number of rows m is greater than the number of columns n, basically an overdetermined but consistent system...This may cause the failuer of intlinprog.
I'm sure that can happen depending on the intlinprog algorithm parameters that you set, but note that the rank is subjective. You have used the default tolerance to calculate the rank, but with a different tolerance, it will be smaller than n,
>> n-rank(Asen,1e-6)
ans =
6
After running the above code, the xval doesn't fullfill the euqlity constraint.
The equality constraint is fulfulled to the default tolerance,
>> norm(Aeq*xLinInt-beq)
ans =
1.4583e-08
You can tighten the constraint tolerance if you wish, but I think it is more appropriate to assess the solution in terms of percent error. The percent error of the current solution is already quite small both according to the L2-norm and the sup-norm,
>> norm(Asen*xval-Asen*a,inf)/norm(Asen*a,inf)*100
ans =
4.4702e-04
>> norm(Asen*xval-Asen*a)/norm(Asen*a)*100
ans =
7.8977e-05
Man Sun
2020-5-8
1 个评论
Matt J
2020-5-8
编辑:Matt J
2020-5-8
They both find the solution.
When I run these suggestions, I obtain
>> n-fval
ans =
4.0000
whereas the solution you claim is the unique one should satisfy n=fval. As I mentioned here, you should not expect rank() to give you an objective prediction of what the solution space will be.
Mario Malic
2020-5-1
编辑:Mario Malic
2020-5-1
I am not sure if this comment will be useful at all, since I don't understand the code completely. (Not great in optimization either, so someone else might be able to provide better comment)
For me - Line 23 throws an error.
I'll refer to the objective function, if you're trying to minimize it, what is the parameter that affects its value? The variable n doesn't change at all. So, for whatever x it is, its value will stay the same.
Suggestions that you could try:
- don't use some constraints, just replace their entry with []
- try with an initial point x0
Matt J
2020-5-2
Aside from the error mentioned by Mario, the line
A = [Atemp, -M*Atemp];
is overwriting your original A matrix (the one contained in A.mat). Therefore, none of your constraints represent the condition A*a=b.
I have the vague impression that you are trying to do linearly constrained L1 norm minimization. If so, you might be interested in my minL1lin utility on the File Exchange, which already provides this functionality.
9 个评论
Walter Roberson
2020-5-3
norm(, 1) is in theory not differentiable because of the abs() and it is best to avoid theoretical issues.
Have you looked at expressing using problem based optimization? sum() is supported for that.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Get Started with Optimization Toolbox 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!