• Issue 1, February 2008
• Inside This Issue:
• Product Updates
• Technical Articles
• ILOG CPLEX 11: Performance, Productivity, and Usability like nothing before
• Harness the Power of Your Multi-Core Machine with Parallel CPLEX
• Local Search Heuristics Enhance ILOG CPLEX Performance While Empowering Other Features
• Productivity Enhancements and Full Support for CPLEX 11: OPL 5.5
• New Age of Optimization Applications
• Questions and Answers
• Workshops and Events
• ILOG Optimization Team

• Optimization Resources
• ILOG Optimization Suite
• Engines
• ILOG CPLEX
• ILOG CP Optimizer
• Tools
• ILOG OPL-CPLEX Development System
• ILOG ODM
• Academic Program

Technical Articles

Local Search Heuristics Enhance ILOG CPLEX Performance
While Empowering Other Features

Ed Klotz, Principal Technical Support Engineer, ILOG, Inc.

Heuristic procedures for finding integer feasible solutions to mixed integer programs (MIPs) can be particularly helpful when the modeler needs to find good solutions quickly instead of provably optimal solutions. They also can help explicitly prove optimality by enabling the optimizer to prune nodes from the branch and bound tree more effectively. And, they can implicitly help prove optimality by permitting the use of MIP strategies that would be otherwise ineffective due to lack of integer feasible solutions.

MIP Heuristics can involve numerous tactics, including fixing variables, limited branching and searching for special structure. One of the most effective heuristic methods is local search. Local search heuristics need an integer feasible solution as input, then define a (typically small) subset of the model variables in which to search for a better solution. In many cases the search involves creating a small MIP sub-problem, the solution of which defines an improved integer feasible solution. Different local search heuristics define different subsets of variables.

Recent versions of ILOG CPLEX have benefited greatly from the implementation of local search heuristics. ILOG CPLEX 9.0 added support for the Relaxation Induced Neighborhood Search (RINS) Heuristic. The RINS Heuristic defines the subset of variables in which to search as the ones whose solution values differ in the incumbent solution and the node LP to which the heuristic is applied. Subsequently, version 10.0 supported Solution Polishing, a combination of the RINS Heuristic and an heuristic based on genetic algorithms that use several methods to combine groups of integer feasible solutions. Methods used include searching among variables whose values differ in pairs of solutions and groups of solutions, as well as some mutation of solutions involving randomization of the search space.

While the availability of an integer feasible solution to initiate the local search heuristics poses a challenge on some models, the local search heuristics have been extended to features that help ILOG CPLEX find such an initial integer feasible solution quickly. Enhancements include MIP starting solutions, a solution repair heuristic for partial and infeasible MIP starting solutions, and other MIP heuristics based on methods other than local search. Recent versions of ILOG CPLEX find integer feasible solutions early in the optimization on many more models than older versions.

Since it solves a small MIP sub-problem, the RINS heuristic may require significant additional run time. Therefore, by default ILOG CPLEX applies the heuristic periodically but infrequently, as it can effectively find integer feasible solutions on most models using other, computationally cheaper methods. However, when ILOG CPLEX's defaults don't find many integer feasible solutions, consider applying the RINS Heuristic more often. To specify a particular frequency, set the RINS Heuristic parameter to the number of nodes between applications.

Solution Polishing occurs after the branch and bound algorithm terminates (provided an integer feasible solution is available). To enable Solution Polishing, use ILOG CPLEX's polishing time limit parameter to specify a positive polishing time value.

On models where good solutions are needed quickly, more aggressive use of the RINS Heuristic or Solution Polishing can dramatically improve the optimality gap of the final integer feasible solution ILOG CPLEX finds. These features by themselves typically won't help prove optimality, but the RINS Heuristic can facilitate proving optimality by providing a tighter incumbent cutoff value with which to prune nodes in the branch and bound tree. These features are likely to be effective particularly on models where adjusting small subsets of the variables is likely to improve an existing integer feasible solution. For example, in a knapsack problem, one may be able to improve the objective function by removing a pair of objects from the knapsack and replacing them with 3 others, while leaving all other objects unchanged.

While they are primarily designed to improve progress in the best integer solution, the RINS and Solution Polishing heuristics can also help with models needing more progress in the bound on the optimal integer objective function value. By increasing the number of integer feasible solutions ILOG CPLEX finds, these heuristics often enable using more aggressive settings of other parameters to improve the best bound. For example, setting ILOG CPLEX's MIP Emphasis parameter to 3 instructs ILOG CPLEX to focus on strategies that improve the best bound value. However, because those strategies don't account for feasibility, they may result in significantly fewer integer feasible solutions. By using the RINS or Solution Polishing, one can compensate for the loss in integer feasible solutions that might otherwise occur by just emphasizing improvement in the best bound value. Another example of synergies between these heuristics and other parameter settings involves models where, regardless of the algorithm applied, the node LPs are extremely difficult to solve. In such cases, the slow node processing rate hampers performance even if ILOG CPLEX ultimately makes excellent node and branching variable selections. One can improve the node throughput by only running the branch and bound algorithm to the first integer feasible solution, then relying on Solution Polishing to improve that solution. While this typically won't solve a model to optimality, it can effectively find good solutions quickly on models where branch and bound struggles because it cannot process enough nodes in the amount of time available for the optimization.

Summarizing, local search heuristics such as RINS and Solution Polishing can enhance ILOG CPLEX MIP performance directly by finding more integer feasible solutions during the course of the optimization. They can also indirectly improve performance through synergies with other parameters. This can be particularly useful on models where more progress in both the best integer and best bound is needed. If you have models with these characteristics where you need faster performance than ILOG CPLEX's default settings, consider making more aggressive use of these heuristics.

Additional Reading:

1. Exploring relaxation induced neighborhoods to improve MIP solutions, Emilie Danna, Edward Rothberg, and Claude Le Pape, Mathematical Programming, Vol. 102, No.1, pp. 71-91, 2005.

2. An evolutionary algorithm for polishing Mixed Integer Programming Solutions, Edward Rothberg, INFORMS Journal On Computing, Vol. 19, No. 4, pp. 534-541, Fall 2007.