Trouble Finding More than One Feasible Solution

For some models, ILOG CPLEX finds an integer feasible solution early in the process and then does not find a better one for quite a while. One possibility, of course, is that the first feasible solution is optimal. In that case, there are no better solutions.

The more common reason for this behavior, though, is the default best-bound variable selection strategy. This strategy concentrates on exploring nodes that are high in the branch & cut tree for the purpose of proving optimality more quickly.

One easy setting to try is the MIP emphasis parameter. It's described in Feasibility and Optimality. A setting of 1 leads to a greater emphasis on finding feasible solutions during the course of optimization.

If you want to keep the default emphasis on proving optimality, the most useful parameter for altering the default strategy, in the hope of finding new feasible solutions more frequently, is the backtrack parameter. To set its value:

By setting this value closer to 1.0, you force branch & cut to dive deeper into the tree, where integer feasible solutions are more likely to be found.

Another approach to finding more feasible solutions is to increase the frequency of the node heuristic. To set its value:

This heuristic can be expensive, so exercise caution when setting this parameter to values less than 10.

A final approach to finding more feasible solutions is to try an alternate node selection strategy. To set the strategy:

Values 2 and 3 use node estimates to select nodes and thus sometimes produce more frequent feasible solutions.


Previous Page: Too Much Time at Node 0  Return to Top Next Page: Large Number of Unhelpful Cuts