Difficulty solving subproblems: overcoming degeneracy

Describes ways to overcome degeneracy as a source of difficulty in solving subproblems.

There are classes of MIPs that produce very difficult subproblems, for example, if the subproblems are dual degenerate. In such a case, a different optimizer, such as the primal simplex or the barrier optimizer, may be better suited to your problem than the default dual simplex optimizer for subproblems. These alternatives are discussed in Unsatisfactory optimization of subproblems. You may also consider a stronger dual simplex pricing algorithm, such as dual steepest-edge pricing (that is, the parameter DPriInd or CPX_PARAM_DPRIIND set to the value 2).

If the subproblems are dual degenerate, then consider using the primal simplex optimizer for the subproblems. You make this change by setting the MIP subproblem algorithm parameter (NodeAlg, CPX_PARAM_SUBALG) to 1 (one).

A different option is to solve as few subproblems of the original model as possible by switching to solution polishing after you find a first feasible solution. This strategy is appropriate if obtaining good integer solutions is more important than obtaining a proof of optimality. For details about how to apply solution polishing, see Solution polishing.