How to tell matlab that all x's to be found are either one or zero using "intlinprog"

I want to solve an integer linear programming problem and I want to tell the solver "intlinprog" that all x's in the problem (should find them) are either zero or one. I already made a lower and upper bound for x's but I do not want Matlab assumes any value in between, that is, all values must be either zero or one. Any idea? Thanks in advance

Answer 1

[John D'Errico]

Read the help?

>> help intlinprog
...

X = intlinprog(f,intcon,A,b) solves the problem with integer variables
  in the intcon vector and linear inequality constraints A*x <= b. intcon
  is a vector of positive integers indicating components of the solution
  X that must be integers. For example, if you want to constrain X(2) and
  X(10) to be integers, set intcon to [2,10].

So the second argument tells which variables are integer. If they are integer, and bounded between 0 and 1, does that not solve your problem?

[Matt J]

Ismael Commented:

Thanks John. So, according to the help, there is no need to add additional constraints for the X's to be zero or one as long as we write the limit bounds [0 1] with their incon as integer?

What I was concern about is that Matlab may assume some float values between the limit bounds (between zero and one) and then find the near integer values. I have a case with A=[50X50] and b=[50X1] and when I add a very small value to [b] (1X10-6), the X's that equal one changes from 10 to 15 with new locations of these X's. Also, my A is a sparse matrix that most of the elements are zero.

[John D'Errico]

That is all you can tell intlinprog, that they are integer, and either 0 or 1.

A being sparse is not relevant, since 50x50 is tiny. Sparsity generally gains you only if the problem is too large to work effectively in memory as a full matrix. In fact, if you use a sparse storage form here, it may even slow things down.

Though I have not looked at the algorithm, I can assure you that intlinprog is not doing something as simplistic as solving a fully real valued problem, and then just rounding the solution for the integer variables.

Anyway, it really is not that difficult to come up with a problem such that what you have seen will happen. (Apparently this is a followup question to one I saw Matt answer the other day.) It just means you have a difficult problem, caused I think by your insistence on strict inequality constraints, which is something that any optimizer will have a hell of a hard time solving.

In fact, it is easy to come up with a two variable problem where a tiny change in the right hand side of b (equivalent to changing <= to an < constraint) will result in a completely different solution. Now that I think of it, one variable is sufficient.