Analyzing MIP solution quality

Describes analysis of the quality of a solution of a MIP optimization.

CPLEX can also display information about the quality of a MIP solution. Here is a sample, typical of such quality information.

MILP objective                                -2.1989035553e+06
MILP solution norm |x| (Total, Max)            1.95445e+10  1.68134e+08
MILP solution error (Ax=b) (Total, Max)        3.90105e+05  8.14760e+03
MILP x bound error (Total, Max)                0.00000e+00  0.00000e+00
MILP x integrality error (Total, Max)          1.96296e-06  9.81482e-07
MILP slack bound error (Total, Max)            8.27493e-08  2.95847e-09

Because a MIP solution lacks an associated unique basis matrix, no measures of dual variable solution quality or reduced cost solution quality are available for a MIP solution. However, as you see in that sample, CPLEX provides norms of primal variable values, bound violations, and associated residuals in much the same way as for LP solutions. For more detail about those qualities, see the topic Interpreting solution quality

Furthermore, the integrality error declares the maximum amount by which the solution value of a variable restricted to be integral has violated its integrality restriction. By default, CPLEX uses a default value of integrality tolerance of 1e-05. (You can adjust this value by means of the integrality tolerance parameter.)

The MILP slack bound error recomputes the slack or artificial variable values based on the structural variable values in the solution. The MILP slack bound error corresponds to the slack values that would be obtained from all the slack values in the basis of the fixed LP associated with the MILP solution. Any resulting violation of the bounds of these slack variables that exceeds the feasibility tolerance indicates potential for better solution quality if you address ill-conditioning in the model.

The slack bound error differs from the primal residual solution error Ax - b. Specifically, the slack bound error involves recomputing the slacks; in contrast, the primal residual solution error computes residuals based on the structural and slack values obtained from the node relaxation or heuristic from which the final integer solution was computed. These two metrics (slack bound error and primal residual solution error), along with the integrality error, are the most important measures of MIP solution quality.

As an example of analyzing the quality of a solution, consider this model:

10000x + y >= 10000
x >= 1
y >= 0 
x,y integer

For the solution x = 1 - 1e-10, y = 0, the integrality error is 1e-10. The MIP slack bound violation is obtained by comparing the lefthand side of the solution value, 10000*(1-1e-10), to the righthand side of 10000. The difference implies a value of -1e-6 for the surplus variable on the constraint, a slack bound violation of 1e-6. In other words, constraint coefficients larger than one can magnify a bound violation for a structural variable into a larger slack bound violation.