Trouble finding more than one feasible solution

Describes remedies for failure to find more than one feasible solution.

For some models, 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 and will eventually be proven optimal. In that case, there are no better solutions.

One possible approach to finding more feasible solutions is to increase the frequency of the node heuristic, by setting the parameter MIP heuristic frequency (HeurFreq, CPX_PARAM_HEURFREQ) to a value such as 10, 5, or even 1. This heuristic can be expensive, so exercise caution when setting this parameter to values less than 10.

Another approach to finding more feasible solutions is to try a node selection strategy alternative. Setting the parameter MIP node selection strategy (NodeSel , CPX_PARAM_NODESEL) to 2 invokes a best-estimate search, which sometimes does a better job of locating good quality feasible solutions than the default node selection strategy.

The settings 1 (one) and 4 of the MIP emphasis switch (MIPEmphasis, CPX_PARAM_MIPEMPHASIS) both address the issue of finding feasible solutions. These parameter settings are also worth considering for this symptom of difficulty finding more than one feasible solution.

Solution polishing also helps you find additional solutions. A good strategy in this respect is to let branch and cut find the first feasible solution and then let solution polishing improve it. For instructions to apply this strategy, see Finding a first solution to improve by polishing.