heur_trustregion.h
Go to the documentation of this file.
18 * @brief Large neighborhood search heuristic for Benders' decomposition based on trust region methods
21 * The Trust Region heuristic draws upon trust region methods for solving optimization problems, especially in the
22 * context of Benders' decomposition. This heuristic has been developed to improve the heuristic performance of the
25 * The Trust Region heuristic copies the original SCIP instance and adds a constraint to penalize changes from the
26 * incumbent solution. Consider a problem that includes a set of binary variables \f$\mathcal{B}\f$. Given a feasible
27 * solution \f$\hat{x}\f$ to the original problem, we define the set \f$\mathcal{B}^{+}\f$ as the index set for the
28 * binary variables that are 1 in the input solution and \f$\mathcal{B}^{-}\f$ as the index set for binary variables
35 * The variable \f$\theta\f$ measure the distance, in terms of the binary variables, of candidate solutions to the input
38 * In addition, an upper bounding constraint is explicitly added to enforce a minimum improvement from the heuristic,
39 * given by \f$f(x) \le f(\hat{x}) - \epsilon\f$. The parameter \f$\epsilon \ge 0\f$ denotes the minimum improvement
42 * The objective function is then modified to \f$f(x) + M\theta\f$, where \f$M\f$ is a parameter for penalizing the
45 * If a new incumbent solution is found by this heuristic, then the Trust Region heuristic is immediately
49 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
Definition: struct_scip.h:59
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_RETCODE SCIPincludeHeurTrustregion(SCIP *scip)
Definition: heur_trustregion.c:567
type definitions for SCIP's main datastructure
common defines and data types used in all packages of SCIP
Definition: objbenders.h:33