In solving linear programming problems, I limit the type of each element of Matrix x to integer, but the solved x element contains decimals

clc, clear, a = importdata('data2_10.xlsx');

a(isnan(a))=0; %把不确定值NaN替换为0

M=10^7; w=ones(14)*M;

for i=1:14

for j=1:14

if i~=j, w(i,j)=sum(a(:,i).*a(:,j)); end

end

end

n=15; w(n,n)=M; prob=optimproblem;

x=optimvar('x',n,n,'Type','integer','LowerBound',0,'UpperBound',1);

u=optimvar('u',n,'LowerBound',0) %序号变量

prob.Objective=sum(sum(w.*x));

prob.Constraints.con1=[sum(x,2)==1; sum(x,1)'==1; u(1)==0];

con2 = optimconstr(n*(n-1)); k=0;

for i=1:n

for j=2:n

k=k+1; con2(k)=u(i)-u(j)+n*x(i,j)<=n-1;

end

end

prob.Constraints.con2 = con2;

prob.Constraints.con3 = [1<=u(2:end)'; u(2:end)'<=14];

[sol, fval, flag]=solve(prob)

xx=sol.x; [i,j]=find(xx);

fprintf('xij=1对应的行列位置如下：\n')

ij=[i'; j']

Answer 1

[Rishi]

Hi 晓辉,

I understand from your question that even though you specify the type of each element to be integer for the matrix 'x', you get decimal values in the solution.

This happens because when you set the data type constaint to integer, the output actually has a tolerance value by which the solution can deviate from an integer value. Simply put, if the tolerance value is 't', and your solution variable is 's', then the value of 's' can range from 'i' +/- 't', where 'i' is any integer.

This tolerance value is specified by the parameter 'IntegerTolerance', which can be set or changed using 'optimoptions'. The default value of 'IntegerTolerance' is 1e-5, and it can be set from 1e-6 to 1e-3 in MATLAB R2023b. I have updated your code by setting this tolerance to 1e-6, and the output shows that most of the values are now integers. Also, I have taken a random matrix ranging from -10 to 10 as 'a'.

a = -10 + 20*rand(14,14);
a(isnan(a))=0; %把不确定值NaN替换为0
M=10^7; w=ones(14)*M;
for i=1:14
    for j=1:14
        if i~=j, w(i,j)=sum(a(:,i).*a(:,j)); end
    end
end
n=15; w(n,n)=M; prob=optimproblem; 
x=optimvar('x',n,n,'Type','integer','LowerBound',0,'UpperBound',1);
u=optimvar('u',n,'LowerBound',0)  %序号变量
prob.Objective=sum(sum(w.*x));
prob.Constraints.con1=[sum(x,2)==1; sum(x,1)'==1; u(1)==0];
con2 = optimconstr(n*(n-1)); k=0;
for i=1:n
    for j=2:n
        k=k+1; con2(k)=u(i)-u(j)+n*x(i,j)<=n-1;
    end
end
prob.Constraints.con2 = con2;
prob.Constraints.con3 = [1<=u(2:end)'; u(2:end)'<=14];
options = optimoptions(prob);
options.IntegerTolerance = 1e-06;
[sol, fval, flag]=solve(prob)
xx=sol.x; [i,j]=find(xx); 
fprintf('xij=1对应的行列位置如下：\n')
ij=[i'; j'];

Here is the screenshot of the output:

You can learn more about 'optimoptions' and other parameters available for solver of type 'intlinprog' from the below documentations:

https://www.mathworks.com/help/releases/R2023b/optim/ug/optim.problemdef.optimizationproblem.optimoptions.html

https://www.mathworks.com/help/releases/R2023b/optim/ug/intlinprog.html#:~:text=%27basic%27-,IntegerTolerance,-Real%20from%201e

Furthermore, MATLAB R2024a has an updated range for 'IntegerTolerance' from 1e-10 to 1e-3, so you can consider upgrading your version if you need more precision. Here is the documentation for the same.

https://www.mathworks.com/help/optim/ug/intlinprog.html#:~:text=%27basic%27-,IntegerTolerance,-Real%20from%201e

Hope this helps!

[晓辉]

Thank you for your answer, but I changed the code your way and the result matrix still has decimals in it, And some decimal and integer deviation is very large, the following is my modified code, and then I also sent this xlsx file, please have a look

clc, clear, a = importdata('data2_10.xlsx');

a(isnan(a))=0; %把不确定值NaN替换为0

M=10^7; w=ones(14)*M;

for i=1:14

for j=1:14

if i~=j, w(i,j)=sum(a(:,i).*a(:,j)); end

end

end

n=15; w(n,n)=M; prob=optimproblem;

x=optimvar('x',n,n,'Type','integer','LowerBound',0,'UpperBound',1);

u=optimvar('u',n,'LowerBound',0) %序号变量

prob.Objective=sum(sum(w.*x));

prob.Constraints.con1=[sum(x,2)==1; sum(x,1)'==1; u(1)==0];

con2 = optimconstr(n*(n-1)); k=0;

for i=1:n

for j=2:n

k=k+1; con2(k)=u(i)-u(j)+n*x(i,j)<=n-1;

end

end

prob.Constraints.con2 = con2;

prob.Constraints.con3 = [1<=u(2:end)'; u(2:end)'<=14];

options = optimoptions(prob);

options.IntegerTolerance = 1e-6;

[sol, fval, flag]=solve(prob)

xx=sol.x; [i,j]=find(xx);

fprintf('xij=1对应的行列位置如下：\n')

ij=[i'; j']

Here is the file data2_10.xlsx, Thank you!

[Rishi]

Hi,

I ran the code on the xlsx file provided by you, and found the following output, which is the same as yours. I've attached the screenshot below:

As can be seen in the output, the data in decimal is actually very small of the order 10^-16 and 10^-17, hence is within the tolerance limits.

I hope this clarifies your doubt.

[晓辉]

Okey, I see, thank you very much.