In ILOG CPLEX, a heuristic is a procedure that tries to produce good or approximate solutions to a problem quickly but which lacks theoretical guarantees. In the context of solving a MIP, a heuristic is a method that may produce one or more solutions, satisfying all constraints and all integrality conditions, but lacking an indication of whether it has found the best solution possible.

ILOG CPLEX provides these families of heuristics to find integer solutions at nodes (including the root node) during the branch & cut procedure:

Being integrated into branch & cut, these heuristic solutions gain the same advantages toward a proof of optimality as any solution produced by branching, and in many instances, they can speed the final proof of optimality, or they can provide a suboptimal but high-quality solution in a shorter amount of time than by branching alone. With default parameter settings, ILOG CPLEX automatically invokes the heuristics when they seem likely to be beneficial.

Node Heuristic

The node heuristic employs techniques to try to construct a feasible solution from the current (fractional) branch & cut node. This feature is controlled by the parameter HeurFreq. At its default value of 0 (zero), ILOG CPLEX dynamically sets the frequency with which the heuristic is invoked. The setting -1 turns the feature off. A positive value specifies the frequency (in node count) with which the heuristic will be called. For example, if the HeurFreq parameter is set to 20, then the node heuristic will be applied at node 0, node 20, node 40, and so on.

Relaxation Induced Neighborhood Search (RINS) Heuristic

Relaxation induced neighborhood search (RINS) is a heuristic that explores a neighborhood of the current incumbent solution to try to find a new, improved incumbent. It formulates the neighborhood exploration as another MIP (known as the subMIP), and truncates the subMIP optimization by limiting the number of nodes explored in the search tree.

Two parameters apply specifically to RINS: RINSHeur and SubMIPNodeLim.

RINSHeur controls how often RINS is invoked, in a manner analogous to the way that HeurFreq works. A setting of 100, for example, means that RINS is invoked every 100th node in the tree, while -1 turns it off. The default setting is 0 (zero), which means that ILOG CPLEX decides when to apply it; with this automatic setting, RINS is applied very much less frequently than the node heuristic is applied because RINS typically consumes more time. Also, with the default setting, RINS is turned entirely off if the node heuristic has been turned off via a HeurFreq setting of -1; with any other RINSHeur setting than 0 (zero), the HeurFreq setting does not affect RINS frequency.

SubMIPNodeLim restricts the number of nodes searched in the subMIP during application of the relaxation induced neighborhood search (RINS) heuristic. Its default is 500 is satisfactory in most situations, but you can set this parameter to any positive integer if you need to tune performance for your problem.

Solution Polishing

Solution polishing can be used to improve the best known solution at the end of branch & cut if optimality has not been proven. Alternatively, it can used instead of the branch & cut algorithm if an initial solution can be found at the root node. If Solution Polishing is used as an alternative algorithm to branch & cut, optimality may not be proven, even if the optimal solution is found.

A parameter enables you to specify the amount of time ILOG CPLEX spends polishing the best solution found. The default value of this parameter is 0.0, so that by default no separate polishing phase is performed. The parameter accepts any nonnegative value, to set a limit in seconds.

If a MIP optimization has located a feasible solution and already terminated, you can invoke polishing alone in the same application call or interactive session by following these steps:

Remember to leave the advanced indicator parameter at its default value of 1 (one) so that the polishing will proceed from the advanced start.

As with the RINS heuristic, the subMIP node-limit parameter also controls aspects of the work that solution polishing performs.

Solution polishing always requires the presence of a feasible solution from which to start. If the feasible solution came from a MIP start, it must be consistent with any dual presolve reductions that ILOG CPLEX makes. Therefore, in order for polishing to work on a MIP start, you may need to disable some combination of dual presolve reductions, nonlinear presolve reductions, or symmetry reductions. For details about the parameters to disable those features, see the ILOG CPLEX Parameter Reference Manual, especially these pages:

Solution polishing is much more time-intensive than any of the other heuristics, but can yield better solutions in some situations.