Ayuda en la programación, respuestas a preguntas / Matlab / Error de "No hay solución factible primordial" en GLPK - matlab, octava, programación lineal, glpk

Error 'No hay solución factible primordial' en GLPK - matlab, octava, programación lineal, glpk

Estoy resolviendo un problema de minimización para cubrir puntos 3D con líneas paralelas de ejes con GLPK. inicialmente me puse lb as 0 y ub as 1. Luego, después de obtener el resultado de GLPK, hago la primera fractional valor variable 0 y luego cambiar el lb y ub valores como:

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

aquí está mi código:

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,"nn");
fprintf(fid,"status=%d n",status);
fprintf(fid,"nn");

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,"nn");

if (isempty(frac_value))
fprintf(fid,"no fractional value")
fprintf(fid,"nn");
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=%dn",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,"nn");

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

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


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=%dn",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,"nn");
%fprintf(fid,"SP1min=%0.8f n",SP1min);
%fprintf(fid,"nn");
fprintf(fid,"status=%d n",status);
fprintf(fid,"nn");

LB1=SP1min

end

fclose(fid);

Aquí están mis puntos de entrada y valores de salida para estos puntos:

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

Realmente no entiendo por qué se está mostrando. no primal feasible solution status=10 cuando estoy cambiando el 1st fractional variable value 0. Cualquier ayuda al respecto será muy apreciada.

Respuestas

0 para la respuesta № 1

Podría resolver mi problema. Está sucediendo porque algunas de las variables tienen valor. 0.000000000000000027773 o 0.99999999999999999. Así que si hago un pre-procesamiento como hacer esos 0.000000000000027773 valores 0 o 0.99999999999999999 1 entonces GLPK da solución factible