CPLEX Performance Tuning for Mixed Integer Programs

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 11.0 or later. Many of these recommendations will also be effective with earlier versions of CPLEX. However, we would highly recommend that you upgrade to the most recent version of CPLEX if you are using an old version; doing so may yield more performance improvements than adjusting parameters of an old version. Also, if you are running a newer version of CPLEX on an old model that previously solved effectively with non-default parameter settings, try the default settings with the newer version. Refer to the 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 problems that involve the MIP algorithm directly.

1. Try default settings first.
2. Try CPLEX's automatic tuning tool.
3. Examine the node log for causes of slow performance.
4. Try setting probing to 3 (its most aggressive setting).
5. Experiment with the MIP emphasis parameter.
6. Make good use of CPLEX's MIP Start, RINS heuristic and solution polishing features.
7. Use aggressive settings for cut generation.
8. Consider non-default variable selection strategies
9. Use knowledge about the model to set particular parameters.
10. Consider using priority orders.
11. Consider adding cuts based on your knowledge of the model.
12. 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 starting with in version 6.5 (and notably in version 11.0), non default settings that worked best for older versions may hinder performance now.

2. Try CPLEX's automatic tuning tool .

Starting with version 11.0, CPLEX includes a tuning tool that will prompt CPLEX to run tuning tests with different parameter settings using information not available in the node log. This can yield performance improvements from non default settings that would otherwise be difficult to determine. It can also shed light on refinements to non default settings determined by the user, including those based on the guidelines in this technote. The tuning tool requires minimal effort from the user; just specify the amount of time allowed for each tuning run, and let it run in the background.

3. 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 CPLEX User Manual for additional examples and information.

4. Try setting probing to 3 (its most aggressive setting) .

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.

5. 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.

Back to top

6. 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.

7. 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, clique, disjunctive, lift and project, and local implied bound cuts parameters to 3.

8. Consider non-default variable selection strategies

When selecting a branching variable within CPLEX's branch and cut algorithm, there is a trade-off between more informed selections that require more computational effort and less informed selections that are computationally cheaper. More computationally intensive selection procedures may reduce the node count but also reduce the rate of node throughput. Less intensive procedures may increase the node count, but the improved node throughput may yield an overall performance improvement. Proper assessment of these trade-offs may yield faster performance than using CPLEX's default variable selection strategy.

The key here is the notion of strong branching, which can be computationally expensive but yield valuable information regarding branching. Strong branching at a node relaxation (root or child node) involves the selection of a subset of the integer-restricted variables with fractional values in the node relaxation solution. For each variable in this subset, CPLEX explores both the up and down branchings by running a modest number of simplex iterations, then using the results to assess the benefit of branching up or down on that variable. Setting the variableselect parameter to 3 does this at every node. The default variableselect setting, which typically is 2, does strong branching calculations at the root node in order to calculate pseudo costs for each variable. This really helps with subsequent branching, but it can be expensive. Setting the variableselect parameter to 4 computes much less expensive pseudo reduced costs. This can save time, particular at the root node when performing an optimization with limited total run time. Recent versions of CPLEX perform powerful computations when processing the root node, and many models solve to optimality (or close to it) at the root node. If most of the time is spent at the root node, CPLEX has very little time for branching, so the benefit of more informed branching decisions at the child nodes may not be worth the cost of the root node calculations. Note that this won't always be the case. Sometimes the strong branching calculations at the root node yield variable fixings (e.g., if CPLEX quickly discovers that the up branch on a binary variable is infeasible, it can immediately fix that variable to 0) that make CPLEX's heuristics more effective, or yield other performance improvements. So, do not always set the variableselect parameter to 4 with models that only run for a few nodes. But, for models where CPLEX spends a lot of time at the root node, consider setting the variable select parameter to 4 to see if performance improves. Similarly, for models where root node processing time is brief, node relaxations solve quickly, and lack of progress in the best node is an issue, consider the more computationally expensive setting of 3 for the variableselect parameter. This instructs CPLEX to perform strong branching calculations at the child nodes as well as the root node.

9. 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.

Back to top

10. 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.

11. 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. Click here for a paper that provides some guidelines regarding this open ended approach (or here for a preprinted version if you don't have easy access to a journal subscription for the previous link).

12. Consider reformulating the model.

Two formulations of the same model yield dramatically different results. For examples, read the article in the attached file below, or point your web browser to

http://portal.acm.org/citation.cfm?id=970083

for an article.

RethinkingMixedIntegeModelFormulations.pdf

Back to top