Why does Matlab's `intlinprog` return near-integers for integer variables?

Question

My background is not linear programming. I am delving into Matlab's Mixed Integer Linear Programming (intlinprog), motivated by the aim to apply it properly rather than advancing the science of the underlying engine.

According to the intlinprog page, in the Limitations section, the solution seems to be sought in the non-integer space, and is deemed to satisfy the integer constraints if the ostensibly integer variables have a very small non-integer part.

Why does it do this? Why doesn't it just search the integer space, as one might do in a combinatoric problem? That way, there is no question of whether the resulting solution is close enough to being integer.

Answer 1

The underlying algorithm of intlinprog is based on a procedure called "Branch and Bound" (BnB). In this algorihmic framework, the solution space is not literally "searched" but rather the integrality constraints are handled implicitly. This scheme has proven to be the most efficient algorithm for general MILP problems. (Of course there are a number of algorithms for specific problems that work be different priciples, and treat integer quantities truly as intergers, e.g., graph/network algorithms).

Continuous relaxations play a prominent role in BnB: After removing ("relaxing") the integrality contraints on the variables, the problem that remains is just a linear optimization problem which can be solved very efficiently. During that branch and bound procedure, a sequence of such continuous relaxations are solved, each with different bounds on the integer variables.

Now these subproblems are solved with floating point arithmetic, and naturally the outcome cannot be guraranteed to be integer. Hence most MILP solvers have a settable tolerance that controls the meaning of "integer".

An outline of the different algorithmic components behind intlinprog is given in the documentation.