The integer linear programming solver does not give me the expected results

% A is a matrix N*N of ones and zeros
% B is a matrix N*1 of ones and zeros

N=14 ;
x = optimvar('x',N,1,"Type",'integer','LowerBound',0,'UpperBound',1);
opp = sum(x);
res1=x(7,1)==0;
res2=x(8,1)==0;
p = optimproblem("ObjectiveSense","minimize");
p.Objective = opp;
p.Constraints.Xk = A*x>=B;
p.Constraints.Xx = res1;
p.Constraints.Xc = res2;
Sol = solve(p,"Solver","intlinprog");

%i want to know if my syntax is wrong or what is the problem with the code,
%matrices A and B are saved in my workspace

[Mark Stone]

You should post the solver output log. And you should describe very clearly in what way the results are not expected.

If the inputs are small enough to post, you should do that as well, so that it beomes a reproducible example, which readers can run using intlinprog,or some other integer linear programming solver (of which there are many for MATLAB, some of which are much faster and better than intlinprog.).

[John D'Errico]

If you want help in this, you need to post the arrays A and B, since we cannot see what you did, or what is the problem.

Most likely, I see two very probable resolutions.

1. There are multiple solutions. intlinprog does not generate ALL solutions. If multiple solutions exist, it only needs to find one that satisfies the problem constraints and minimizes the objective.
2. There may be precision problems, that depend on the matrix A. Remember, when double precision arithmetic is involved, there can be problems. Double precision is not infinite precision.

But without knowing A and B, we can test nothing.

You might actually test all possible 0-1 solutions, since there are only 2^12 of them to care about. (Variables 7 and 8 are known to be zero.) That is trivially done, to verify if the solutino returned is truly the solution you think is the solutino, and to verify if there are multiple solutions.

[Torsten]

For random A and B, your code works.

If you have problems with the A and B you specified, you will have to post them.

% A is a matrix N*N of ones and zeros
% B is a matrix N*1 of ones and zeros

N=14 ;
A = randi(2,N,N)-1;
B = randi(2,N,1)-1;
x = optimvar('x',N,1,"Type",'integer','LowerBound',0,'UpperBound',1);
opp = sum(x);
res1=x(7,1)==0;
res2=x(8,1)==0;
p = optimproblem("ObjectiveSense","minimize");
p.Objective = opp;
p.Constraints.Xk = A*x>=B;
p.Constraints.Xx = res1;
p.Constraints.Xc = res2;
Sol = solve(p,"Solver","intlinprog");

Solving problem using intlinprog.
LP:                Optimal objective value is 1.500000.                                             

Heuristics:        Found 1 solution using ZI round.                                                 
                   Upper bound is 2.000000.                                                         
                   Relative gap is 0.00%.                                                          


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer
within tolerance, options.IntegerTolerance = 1e-05 (the default value).

[Mark Stone]

@John D'Errico In addition to everything you wrote, intlinprog only claims to find a solution to within a gap tolerance. Unless the actual final reported gap = 0, the solution which is calimed ot be "optimal", may not actually be optimal.

"Intlinprog stopped at the root node because the objective value is within a gap

tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default

value). The intcon variables are integer within tolerance,

options.IntegerTolerance = 1e-05 (the default value)."

Edit: Now that the soler output log has been posted, we see that the final gap is zero. So the above does not "explain" things in this case.

Edit 2: Based on the clarificaton from @Torsten , my Edit 1 can be ignored. So that puts non-zero gap in the reported "optimal" solition back in play as a potential reason for "unexpected" results.

[Mark Stone]

@sebastian marin quiceno Thank you for posting the solver log output. Now you need to clearly describe to us what is unexpected about the result.

Do you relalize that every time you run the program, it is generating different input data, and therefore the optimal x (argmin) and optimal objective value can also change? So if you analyzed one problem, then ran with new random matrices, you may get a different result.

Or are the random inputs just for illustration? if so, you are just confusing matters.

[John D'Errico]

@sebastian marin quiceno

but you are still not providing sufficient information to give you help.

Are you calling intlinprog properly? Well, yes. The code you executed does call intlinprog. And it exits with no failure. So you called it "properly".

That does not mean it is solving the problem you wanted to solve, since we see only how you called it. Since this is a pretty simple problem, it seems likely that you have properly set it up.

Providing random input matrices to the problem does not help, since most random matrices will be no problem at all, and you clearly asked this question BECAUSE you saw a problem and were confused. And there will be some sets of random inputs where no solution exists at all.

So. you THINK there is a problem. Clearly, you state there is something wrong. But WHAT problem do you think is there? Why did you ask this question in the first place? As you can see from the example you ran in your question, it returns a perfectly valid answer.

[Torsten]

@Mark Stone @John D'Errico

Sorry for the confusion. I included the random matrices to see whether there is a syntax error in the problem setup.

I restored the original post of @sebastian marin quiceno

[sebastian marin quiceno]

Thank you very much for the answers. sorry, I thought that was enough information. This code is to solve an electrical engineering problem. I want to optimize the number of measurer needed to locate on a network. The vector x represents the location of the measurer in the network, so then the intention is that the minimum number of necessary measurer be found through the restrictions. According to IEEE articles, the values of the vector x that give a solution are: 2.6 and 9. But instead with my code I get 2, 10 and 13. As I said before, matrix A is a matrix of ones and zeros, where 1 means that there is a connection between the network nodes and 0 means that there is not, for example: node 1 and node 3, if they are connected by a line, the value A(1,3)=A(3, 1)=1

and the matrix B is also a matrix of ones, but in B(7,1) = B(8,1) =0

[Torsten]

According to IEEE articles, the values of the vector x that give a solution are: 2.6 and 9. But instead with my code I get 2, 10 and 13.

Then evaluate your cost function and your constraints at the IEEE solution and see if the cost function value is really smaller than the one you got from intlinprog and if the constraints are satisfied.

[Mark Stone]

Following up on the comment by @Torsten , it is quite common that the optimal solution of a binary or integer Linear Programming problem is not unique. So as @Torsten wrote, you need to compare objective (cost function) values. If two different solutions both have the same objective value, but only one of them is deemed "acceptable", then the model is inadequate, and you need to chage the objective function and/ot the constraints. Many binary or integer Linear Programming problems have a hughe amount of symmetry, meaning any reshuffling among the symmetric entities, produces the same objective value. That might very well be the case here. intlibnprog especially, benfits in solution speed from symmetry breaking constraints - for instance, fi you have interchageable (identical) assets that can be placed in various locations, a symmetry breaing oonstraint could be that the lower the number asset, the "better" the location in terms of contribution to objective. That cuts off many optimal solutions, but does not degrade the optimal objective value. Some solvers, such as FIC Xpress "prefer" not to have symmetry brealking constraints, but intlinprog almost always does, and it could bethe difference between solivng in a minute or taking weeks, months or years. On the other hand, your problem is tiny, and you could brute force enumaerate and evaluate objective and constraint satisfaction for all 2^14 = 4096 points in short order. So no matter what you do on symmetry breaking, intlinprog shoudl sokve it very fast. If n is 30+, it might be a differrent story.