'No primal feasible solution' GLPK 错误

Question

我正在解决一个最小化问题，用 GLPK 覆盖轴平行线的 3d 点。最初我设置 lb as 0 和 ub as 1。然后在获得 GLPK 结果后，我将第一个 fractional 变量值设置为 0 然后将 lb 和 ub 值更改为：

i) lb will be 1 for the variable values 1 ii) ub will be 0 for the variable values 0

这是我的代码：

fid=fopen('output2.txt','w');
%input points are given below   
numberOfPoints=size(points,1)
fprintf(fid,'numberofpoints=%d \n',numberOfPoints);

xy=unique(points(:,[1,2]),'rows');
yz=unique(points(:,[2,3]),'rows');
xz=unique(points(:,[1,3]),'rows');
L=size(xy,1)+size(yz,1)+size(xz,1);     %number of lines
Axy=zeros(size(points,1),size(xy,1));
Ayz=zeros(size(points,1),size(yz,1));
Axz=zeros(size(points,1),size(xz,1));

for i=1:size(points,1)
    for j=1:size(xy,1)
        if(points(i,[1,2])==xy(j,:))
            Axy(i,j)=1;
        endif
    end
end
Axy;

for i=1:size(points,1)
    for j=1:size(yz,1)
        if(points(i,[2,3])==yz(j,:))
            Ayz(i,j)=1;
        endif
    end
end
Ayz;

for i=1:size(points,1)
    for j=1:size(xz,1)
        if(points(i,[1,3])==xz(j,:))
            Axz(i,j)=1;
        endif
    end
end
Axz;

Acat=cat(2,Axy,Ayz);

A=cat(2,Acat,Axz);          %constraint matrix
c=ones(1,size(A,2))';           %objective function co-efficients matrix
b=ones(1,size(A,1))';           %constraints' right hand side value matrix
lb=zeros(1,size(A,2));          %variable lower bound matrix
ub=ones(1,size(A,2));           %variable upper bound matrix

for i=1:size(A,1)
    ctype(i)="L";
end
ctype;

for i=1:size(A,2)
    vartype(i)="C";
end
vartype;
s = 1;



[xmin, fmin, status] = glpk (c, A, b, lb, ub, ctype, vartype, s);%GLPK function

fprintf(fid,'fmin=%0.8f \n',fmin);
fprintf(fid,'\n\n');    
fprintf(fid,'status=%d \n',status);
fprintf(fid,'\n\n');

NumberofNodes = 1;
frac_value=intersect(find(xmin >0) , find(xmin < 1))    ;   %positions of fractional variables
%fprintf(fid,'frac_value=%d \n',frac_value);
%fprintf(fid,'\n\n');

    if (isempty(frac_value)) 
    fprintf(fid,'no fractional value')
    fprintf(fid,'\n\n');
        break;


else


round_value=frac_value(1);
xmin_SP1=xmin;
ub1=ub;
fprintf(fid,'ub1=%d \n',ub1);
fprintf(fid,'\n');
lb1=lb;
fprintf(fid,'lb1=%d\n',lb1);
fprintf(fid,'\n');


xmin_SP1(round_value)=0;            %making the first fractional value 0
NumberofNodes =NumberofNodes +1;
%   fprintf(fid,'xmin_SP1=%0.8f \n',xmin_SP1);
%   fprintf(fid,'\n\n');

one_value_SP1=find ( xmin_SP1== 1 );        %variables with value 1
%   fprintf(fid,'one_value_SP1=%d \n',one_value_SP1);
%   fprintf(fid,'\n\n');

    zero_value_SP1=find ( xmin_SP1==0);     %variables with value 0
%   fprintf(fid,'zero_value_SP1=%d \n',zero_value_SP1);
%   fprintf(fid,'\n\n');


ub1(zero_value_SP1)=0   ;       %changing ub for 0 values
fprintf(fid,'ub1=%d \n',ub1);
fprintf(fid,'\n');
%   fprintf(fid,'numberofub=%d \n',size(ub,2));
%   fprintf(fid,'\n');


lb1(one_value_SP1)=1 ;          %changing lb for 1 values
fprintf(fid,'lb1=%d\n',lb1);
fprintf(fid,'\n');
%   fprintf(fid,'numberoflb=%d \n',size(lb,2));
%   fprintf(fid,'\n');


[xminSP1, SP1min, status] = glpk (c, A, b, lb1, ub1, ctype, vartype, s)     ;   %GLPK function
%size(xmin_SP1,1);
fprintf(fid,'xmin_SP1=%0.8f \n',xminSP1);
fprintf(fid,'\n\n');
%fprintf(fid,'SP1min=%0.8f \n',SP1min);
%fprintf(fid,'\n\n');
fprintf(fid,'status=%d \n',status);
fprintf(fid,'\n\n');

LB1=SP1min

end

fclose(fid);

这是我的输入点和这些点的输出值：

points=

1   1   1   
2   1   1   
4   1   1   
1   2   1   
2   2   1   
3   2   1   
4   2   1   
2   3   1   
3   3   1   
4   3   1   
3   4   1   
4   4   1   
1   1   2   
3   1   2   
4   1   2   
1   2   2   
2   2   2   
3   2   2   
4   2   2   
1   3   2   
2   3   2   
4   3   2   
1   4   2   
2   4   2   
3   4   2   
4   4   2   
1   1   3   
2   1   3   
3   1   3   
4   1   3   
1   2   3   
2   2   3   
3   2   3   
4   2   3   
2   3   3   
3   3   3   
4   3   3   
1   4   3   
2   4   3   
3   4   3   
1   1   4   
2   1   4   
3   1   4   
4   1   4   
1   2   4   
2   2   4   
3   2   4   
4   2   4   
1   3   4   
2   3   4   
3   3   4   
1   4   4   
3   4   4   

numberofpoints=53 
fmin=16.00000000 


status=0 

initial ub:
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 

initial lb:
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0

changed ub for variable values 0:
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=0 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=1 
ub1=0 
ub1=1 
ub1=0 
ub1=1 
ub1=1 
ub1=0 
ub1=1 
ub1=0 
ub1=1 
ub1=0 
ub1=1 
ub1=1 
ub1=0 
ub1=1 
ub1=1 
ub1=0 
ub1=0 
ub1=1 
ub1=0 
ub1=0 
ub1=1 
ub1=1 
ub1=0 
ub1=0 
ub1=0 
ub1=0 
ub1=1 
ub1=0 
ub1=1 
ub1=0 
ub1=1 
ub1=0 

changed lb for variable values 1:   
lb1=1
lb1=1
lb1=1
lb1=1
lb1=1
lb1=0
lb1=1
lb1=1
lb1=1
lb1=1
lb1=1
lb1=1
lb1=1
lb1=1
lb1=1
lb1=1
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0
lb1=0

variable values showing NA as status=10(no primal feasible solution)
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 
xmin_SP1=NA 


*******Result for SP1 node 2********

status=10

我真的不明白为什么我改1st fractional variable value 0的时候显示no primal feasible solution status=10。对此的任何帮助将不胜感激。

Answer 1

我可以解决我的问题。这是因为一些变量的值是 0.000000000000000027773 或 0.99999999999999999。因此，如果我做一些预处理，比如使那些 0.000000000000027773 值 0 或 0.99999999999999999 1 那么 GLPK 给出可行的解决方案

'No primal feasible solution' GLPK 错误

'No primal feasible solution' error in GLPK

matlab

linear-programming

octave

glpk