Difficulty Solving Subproblems
There are classes of MIPs that produce very difficult subproblems, for example, if the subproblems are dual degenerate. In such a case, an alternative optimizer, such as the primal simplex or the primal-dual barrier optimizer, may be better suited to your problem than the default dual simplex optimizer for subproblems.
If the subproblems are dual degenerate, then consider using the primal simplex optimizer for the subproblems. Set the subalgorithm parameter, as explained in Subalgorithm Parameter, to use the primal simplex optimizer.
Another effective strategy in overcoming dual degeneracy is to permanently perturb the problem. For subproblems that are dual degenerate, in the Interactive Optimizer, write out the perturbed problem as a DPE file with the command write filename.dpe substituting an appropriate file name. (A .dpe file is saved as a binary SAV format file.) Then you can read the saved file back in and solve it. The subproblem should then solve more cleanly and quickly.
In the case of DPE files solved by the dual simplex optimizer, any integer solution is also guaranteed to be an integer-feasible solution to the original problem. In most cases, the solution will be optimal or near-optimal as well.
If subproblems are taking many iterations per node to solve, consider using a stronger dual pricing algorithm, such as dual steepest-edge pricing.
In case you have selected the primal-dual barrier optimizer to solve the initial LP relaxation, you may want to apply it to the subproblems in one of two ways:
- This choice applies the primal-dual barrier optimizer to all subproblems.
- Recognizing that the barrier optimizer does not utilize a basis, this choice lets the dual simplex optimizer run for a predetermined number of iterations and then switches to the barrier optimizer for the subproblem. To use this choice, you need to set the simplex iteration limit to a reasonably low number of dual iterations.
If you limit the number of simplex iterations, the limit applies to all invocations of simplex optimizers, except crossover. Since the dual simplex optimizer will most often be the best method, try to specify a sufficient number of iterations before you force the switch to the barrier optimizer.
