Scippy

SCIP

Solving Constraint Integer Programs

How to use reoptimization

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 \{0,1\}^{n}\;\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:

  1. disable conflict analysis based on dual information
  2. set the limit maxorigsol of stored solutions to zero because this is handled by a special solution tree provided by the reoptimization feature itself
  3. disable restarts (presolving/maxrestarts = 0)
  4. disable multi-aggegations (presolving/donotmultaggr = TRUE)
  5. disable dual reductions within presolvers and propagators (misc/allowdualreds = FALSE)
  6. disable propagation with current cutoff bound (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

  1. the stored search tree is too large,
  2. the objective functions changed too much, or
  3. the last $n$ optimal solution are updated solution of previous runs.

The thresholds to trigger a restart can be set by the user:

  1. reoptimization/maxsavednodes
  2. reoptimization/delay
  3. 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:

  1. Using the provided reader reader_diff the objective function can be changed via using the interactive shell
    SCIP> read new_obj.diff
    or by calling SCIPreadDiff().
  2. The objective function can be changed within the code. Therefore, the transformed problem needs to be freed by calling SCIPfreeTransform(). Afterwards, the objective coefficient of each variable can be changed by calling SCIPchgVarObj().

After changing the objective function the modified problem can be solved as usal.

Note
Currently, the reoptimization feature only supports pure binary and mixed binary programs. In case the original problem containts integer and implicit integer variables, reoptimization will be automatically disabled if there are still (implicit) integer variables after presolving the problem.

For more information on reoptimization we refer to

Jakob Witzig
Reoptimization Techniques in MIP Solvers
Master's Thesis, Technical University of Berlin, 2014.