CPLEX Performance Tuning for Mixed Integer Programs

http://www-01.ibm.com/support/docview.wss?uid=swg21400023

Question How do I select non default parameters to tune CPLEX's performance on a difficult mixed integer program?

Answer

Because of the combinatorial nature of integer programs, CPLEX users may have more trouble getting good performance with integer programs than with linear or quadratic programs. CPLEX has many parameters that allow users to customize the way the CPLEX branch and bound algorithm operates. While this variety of parameters provides many different ways to improve performance, a user cannot realistically experiment with all the possible combinations of parameter settings. Therefore, we recommend the following tactics for solving MIPs with CPLEX 10.0 or later. Many of these recommendations will also be effective with earlier versions of CPLEX. Refer to the ILOG CPLEX User Manual if you need additional information about any of the terms mentioned. Before trying to improve performance, you first need to locate the current performance bottleneck. CPLEX provides a node log that shows the progress of its branch and bound algorithm on a MIP. Be sure to look at the node log to help locate the performance bottleneck. In some cases you may find that slow node LP solve times cause the slow performance. In that case, the suggestions in the CPLEX Performance Tuning for Linear Programs FAQ may help. This document focuses on performance issues that involve the MIP algorithm directly. 1.  Try default settings first. 2.  Try setting probing to 3. 3.  Experiment with the MIP emphasis parameter. 4.  Make good use of CPLEX's MIP Start, RINS heuristic and solution polishing features. 5.  Use aggressive settings for cut generation. 6.  Use knowledge about the model to set particular parameters. 7.  Examine the node log for causes of slow performance. 8.  Consider using priority orders. 9.  Consider adding cuts based on your knowledge of the model. 10.  Consider reformulating the model. 1. Try default settings first. The default settings of CPLEX work well on most problems. Always try default settings with the current version of CPLEX. Longtime CPLEX users may have found that other settings worked better for older versions, like CPLEX 4.0 and 5.0. However, with the major improvements to the integer programming algorithm in version 6.5 through 10.0, non default settings that worked best for older versions may hinder performance now. 2. Try setting probing to 3. Probing can dramatically improve performance, although it may also consume significant amounts of time. It helps on problems with binary variables rather than general integer variables. Starting with CPLEX 10.0, the probing time limit parameter can help when aggressive levels of probing are effective but take too long. Stopping aggressive probing before completion can still yield a significant number of binary variable fixings. 3. Experiment with the MIP Emphasis parameter. If you don't need an optimal solution, set the MIP Emphasis parameter to 1 so that CPLEX finds more feasible solutions. You may also want to set a suitable mip gap value to instruct CPLEX to stop as soon as it has a solution within a specified percentage of optimality. For example, set the mipgap parameter to .05 if you want CPLEX to stop as soon as it has a solution within 5 percent of optimality. Conversely, setting the MIP Emphasis parameter to 2 or 3 can help when CPLEX makes good progress finding integer solutions, but performance stalls due to lack of progress in the Best Node value that provides a bound on the best possible integer solution objective value. Both these settings try to make more progress in the Best Node value, but setting 3 puts even less emphasis on finding a solution. 4.Make good use of CPLEX's MIP Start, RINS heuristic and solution polishing features . CPLEX 9.0 and 10.0 added new features that can help find feasible solutions much faster. Support of partial and infeasible MIP starts, solution repair, the RINS heuristic, and solution polishing are all very useful features by themselves. However, perhaps more importantly, they enable additional MIP tuning tactics that might otherwise be ineffective. For example, setting CPLEX's MIP emphasis parameter to 3 can dramatically improve progress in the best node, but often at the expense of finding feasible solutions. However, by providing a partial or infeasible MIP start, using solution repair to translate it into a feasible solution, and using the RINS heuristic to improve upon that solution, you may be able to compensate for the lack of feasibles that would otherwise result from setting the MIP emphasis parameter to 3. Solution polishing is a local search heuristic that can help when run with the MIP emphasis parameter set to 1, as it can improve feasible solutions quickly. Consider it also as an alternative to the branch and bound algorithm when solving node LPs comprises the majority of run time and limits progress. For such cases, try running branch and bound for a limited amount of time to obtain at least one feasible solution, then use solution polishing to improve the solutions. While this won't help move the best node, it can help for models where you need good solutions quickly, and progress in the best node seems unlikely. 5. Use aggressive settings for cut generation. Try setting the cuts parameter to 2 (set mip cuts all 2 in the CPLEX Interactive Optimizer) to increase cut generation and hence tighten the MIP that CPLEX actually optimizes. You may also want to set the cover or disjunctive cuts parameters to 3. 6. Use knowledge about the model to set particular parameters. If none of these settings work well, specific knowledge of the problem may suggest particular parameter settings. For example, you may know that the nature of your problem is such that branching up on fractional variables will yield good feasible solutions quickly. 7. Examine the node log for causes of slow performance. By setting the MIP display parameter to values ranging from 2-5, you can get detailed information about the progress of the MIP optimization in the CPLEX node log. This information often sheds light on the cause of slow performance. For example, you may find that CPLEX spends most of its time solving the root LP relaxation. In that case, consider setting the startalgorithm parameter to a non default value. Or, you may find that CPLEX spends a lot of time applying the node heuristic, but that the heuristic never finds a good feasible solution. In that case, turn the node heuristic off. Look at the MIP Troubleshooting section of the ILOG CPLEX User Manual for additional examples and information. 8. Consider using priority orders. Priority orders instruct CPLEX to branch on integer variables with higher priority first. They typically require some knowledge of the model to create and can dramatically improve performance. They are particularly useful on models involving time periods; give higher priority to the integer variables corresponding to activities in the earlier time periods. They also help on models with integer variables that depend on other integer variables. For those models, try giving higher priority to the independent variables. 9. Consider adding cuts based on your knowledge of the model. CPLEX does a good job of performing a mathematical examination of your model to derive cuts. But, CPLEX ultimately views your problem as a generic integer program. It may not be aware of certain logical aspects of your model. You, or your customer, may be aware of these, and hence can add cuts to the model that CPLEX could never determine. 10. Consider reformulating the model. Two formulations of the same model yield dramatically different results. For an example, point your web browser to http://portal.acm.org/citation.cfm?id=970083 for an article.