The reoptimization feature of SCIP can be used to solve a sequence of optimization problems \((P_{i})_{i \in I}\) with
\[ (P_i) \quad \min \{ c_i^T x \;|\; A^ix \geq b^i,\; x_{j} \in \mathbb{Z}\;\forall j \in \mathcal{I} \} \]
such that between two problems \(P_i\) and \(P_{i+1}\) the space of solutions gets restricted and/or the objective fuction changes. To use reoptimization the user has to change the parameter reoptimization/enable
to TRUE
before the solving process of the first problem of the sequence starts, i.e., in stage SCIP_STAGE_INIT
or SCIP_STAGE_PROBLEM
. This can be done via the interactive shell or by calling SCIPenableReoptimization(). In both cases SCIP changes some parameters and fixes them:
maxorigsol
of stored solutions to zero because this is handled by a special solution tree provided by the reoptimization feature itselfpresolving/maxrestarts = 0
)presolving/donotmultaggr = TRUE
)misc/allowdualreds = FALSE
)misc/allowobjprop = FALSE
)In contrast to the presolving and propagating methods that are using dual information, performing strong branching is allowed. The bound tightenings resulting from strong branching are handeled in a special way. After changing the objective function and solving the modified problem the feasible region that was pruned by strong branching will be reconstructed within the tree.
If the reoptimization feature is enabled SCIP tries to reuse the search tree, especially the search frontier at the end of the solving process, to speed up the solving process of the following problems. Therefore, the current release provides the branching rule branch_nodereopt
to reconstruct the tree. SCIP triggers a restart of the reoptimization, i.e., solving the problem from scratch, if
The thresholds to trigger a restart can be set by the user:
reoptimization/maxsavednodes
reoptimization/delay
reoptimization/forceheurrestart
Before SCIP discards all the stored information and solves the problem from scratch it tries to compress the search tree. Therefore, the current release provides compression heuristics that try to find a good and much smaller representation of the current search tree.
After a problem in the sequence of optimization problems was solved, the objective function can be changed in two ways:
reader_diff
the objective function can be changed via using the interactive shell After changing the objective function the modified problem can be solved as usal.
For more information on reoptimization we refer to