Why does a binary or integer variable take on a noninteger value in the solution?

Answer

This is a consequence of the integrality tolerance parameter, CPX_PARAM_EPINT (default value: 1e-5).

This parameter specifies the amount by which an integer variable can violate its integrality requirement. The default value of the integrality tolerance is fine for most MIPs.

Certain mixed integer problems have constraints of the form:

M = 100000  // or some other large number
var <= M * binary;
90000 >= var >= 0;

The intention is to express:
If 'binary' is zero, var will be forced to 0.
If 'binary' is one, var can take on nonzero value <= 90000.

However, the tolerance can pose a problem when an integer variable is multiplied by a large factor; the (tolerance * factor) is large enough to allow var to take on a nonzero value (often called trickle flow).

For instance, with a tolerance of 1e-5, one legal solution is:

var = 1
M = 100000
binary = 0.00001

There are four things you can do to minimize these effects:

• You can decrease the integrality tolerance.
  Variables will need to be closer to an integer value to be considered integer feasible. Any value of tolerance that is less than the reciprocal of the largest coefficient that multiplies a binary variable should work. You should be careful with this, however, if your problem has a lot of roundoff noise. CPLEX 9.0 will support arbitrarily small values for the integrality tolerance, including 0. Previous versions allowed a minimum integrality tolerance of 1e-9. Keep in mind that numerical roundoff due to finite precision floating point computations may prevent CPLEX from achieving an integrality tolerance of 0. But, in practice, this setting achieves its aim in many models and reduces the integrality violations to near the machine tolerance (around 1e-15) on many others.
• You can reduce the value of M in these constraints.
  Because the integrality tolerance is always nonzero, the value of the big constant used in these constraints must be chosen very carefully. Try to scale down the model so that M is as small as possible without violating the meaning of the constraint. For example, if you can derive an upper bound on var in the above constraint, use that value for M.
• You can reformulate these constraints using special ordered sets (SOSs).
  Constraints involving big M values frequently can be expressed using special ordered sets. If so, the equivalent constraints with the special ordered sets no longer have any big M values. For example, the constraints

  x1 - M * z1 <= 0
  x2 - M * z2 <= 0
  z1 + z2     <= 1
  x1, x2 >= 0; z1, z2 binary
  

  can be replaced by simply specifying x1 and x2 as a type 1 special ordered set. This reformulation not only removes the big Ms, but it reduces the problem size. However, keep in mind that some of CPLEX's more advanced MIP features operate on binary variables but not on special ordered sets. So, this reformulation may result in slower performance despite the reduction in model size and removal of the big M values. Nonetheless, if removal of the big Ms is essential to ensure the correctness of the results, then consider this tactic.
• Starting with CPLEX 10.0, you can use indicator constraints to reformulate these constraints.
  For example, instead of

  M = 100000  // or some other large number
  var <= M * binary;
  90000 >= var >= 0;
  

  use the indicator constraint

  binary = 0 --> var <= 0;
  90000 >= var >= 0;
  

  This removes the big M from the formulation. Note that, as with special ordered sets, some of the more advanced features of CPLEX do not operate on indicator constraints, so this reformulation may slow performance. But, if removal of the big Ms is essential to ensure the correctness of the results, then consider this tactic. For more information on when to use indicator variables, click here.