SCIP
Solving Constraint Integer Programs
heur_trustregion.h File Reference
Detailed Description
Large neighborhood search heuristic for Benders' decomposition based on trust region methods.
The Trust Region heuristic draws upon trust region methods for solving optimization problems, especially in the context of Benders' decomposition. This heuristic has been developed to improve the heuristic performance of the Benders' decomposition algorithm within SCIP.
The Trust Region heuristic copies the original SCIP instance and adds a constraint to penalize changes from the incumbent solution. Consider a problem that includes a set of binary variables \(\mathcal{B}\). Given a feasible solution \(\hat{x}\) to the original problem, we define the set \(\mathcal{B}^{+}\) as the index set for the binary variables that are 1 in the input solution and \(\mathcal{B}^{-}\) as the index set for binary variables that are 0. The trust region constraint, which is added to the sub-SCIP, is given by
\[ \sum_{i \in \mathcal{B}^{+}}(1 - x_{i}) + \sum_{i \in \mathcal{B}^{-}}x_{i} \le \theta \]
The variable \(\theta\) measure the distance, in terms of the binary variables, of candidate solutions to the input solution.
In addition, an upper bounding constraint is explicitly added to enforce a minimum improvement from the heuristic, given by \(f(x) \le f(\hat{x}) - \epsilon\). The parameter \(\epsilon \ge 0\) denotes the minimum improvement that must be achieved by the heuristic.
The objective function is then modified to \(f(x) + M\theta\), where \(M\) is a parameter for penalizing the distance of solutions from the input solution \(\hat{x}\).
If a new incumbent solution is found by this heuristic, then the Trust Region heuristic is immediately re-executed with this new incumbent solution.
Definition in file heur_trustregion.h.
Go to the source code of this file.
Functions | |
| SCIP_EXPORT SCIP_RETCODE | SCIPincludeHeurTrustregion (SCIP *scip) |