Tuning Integer Linear Programming

Some “Integer” Solutions Are Not Integers

Often, some supposedly integer-valued components of the solution x(intcon) are not precisely integers. intlinprog considers as integers all solution values within IntegerTolerance of an integer.

To round all supposed integers to be precisely integers, use the round function.

x(intcon) = round(x(intcon));

Caution

Rounding can cause solutions to become infeasible. Check feasibility after rounding:

max(A*x - b) % see if entries are not too positive, so have small infeasibility
max(abs(Aeq*x - beq)) % see if entries are near enough to zero
max(x - ub) % positive entries are violated bounds
max(lb - x) % positive entries are violated bounds

Large Components Not Integer Valued

intlinprog does not enforce that solution components be integer valued when their absolute values exceed 2.1e9. When your solution has such components, intlinprog warns you. If you receive this warning, check the solution to see whether supposedly integer-valued components of the solution are close to integers.

Large Coefficients Disallowed

intlinprog does not allow components of the problem, such as coefficients in f or ub, to exceed 1e20 in absolute value, or components of A or Aeq to exceed 1e15 in absolute value. If you try to run intlinprog with such a problem, intlinprog issues an error.

If you get this error, sometimes you can scale the problem to have smaller coefficients:

• For coefficients in f that are too large, try multiplying f by a small positive scaling factor.

• For constraint coefficients that are too large, try multiplying all bounds and constraint matrices by the same small positive scaling factor.

References

[1] Williams, H. Paul. Model Building in Mathematical Programming, 5th Edition. Wiley, 2013.