Selecting variables

Describes trade-offs around variable selection and options of the parameter to control selection of the next variable.

After a node has been selected, the variable selection parameter influences which variable is chosen for branching at that node. (For documentation of that parameter, see MIP variable selection strategy in the CPLEX Parameters Reference Manual.)

When CPLEX selects a branching variable during execution of the 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 can reduce the node count, but also reduce the rate of node throughput. Less intensive procedures can increase the node count, but that improved node throughput can yield an improvement in overall performance. If you can properly assess these trade-offs for your model, you can achieve faster performance than the default variable selection strategy in CPLEX.

The key here is the concept of strong branching, which can be computationally expensive, but which can yield valuable information about branching. The idea behind strong branching at a node relaxation (root node or child node) is 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 branches by running a modest number of simplex iterations; CPLEX then uses the results to assess the benefit of branching up or down on that variable.

Setting the MIP variable selection strategy parameter to 3 does this at every node.

The default of the MIP variable selection strategy parameter (which is typically 2) computes strong branching data at the root node in order to calculate pseudo costs for each variable. These pseudo costs really help with subsequent branching, but their calculation can be expensive. Setting the parameter to 4 computes much less expensive pseudo reduced costs. This choice can save time, particularly at the root node when you have asked CPLEX to perform an optimization with limited total run time.

Recent versions of CPLEX perform powerful computations when processing the root node, and consequently many models solve to optimality (or close to optimality) at the root node. If most of the time is spent at the root node, CPLEX has little time left then for branching, so the benefit of more informed branching decisions at the child node probably may not be worth the cost of those root node calculations.

Note that this situation will not always be the case, though.

Sometimes, strong branching calculations at the root yield variable fixings. For example, if CPLEX quickly discovers that the up branch on a binary variable is infeasible, CPLEX can immediately fix that variable to 0 (zero). These variable fixings yielded by strong branching calculations can make heuristics more effective, or can yield other performance improvements.

So, do not always set the MIP variable selection strategy parameter to 4 with models that run for only a few nodes. But, for models where CPLEX seems to spend a lot time at the root node, consider setting the parameter to 4 to see whether that helps.

Similarly, for models where root node processing time is brief, node relaxations solve quickly, and lack of progress toward the best node is an issue, consider the more computationally expensive setting of 3 for the MIP variable selection strategy parameter. This setting instructs CPLEX to perform strong branching calculations at the child nodes as well as at the root node.

The following table summarizes the settings for this parameter.