Scippy

SCIP

Solving Constraint Integer Programs

heur_trustregion.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_trustregion.h
17  * @ingroup PRIMALHEURISTICS
18  * @brief Large neighborhood search heuristic for Benders' decomposition based on trust region methods
19  * @author Stephen J. Maher
20  *
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
23  * Benders' decomposition algorithm within SCIP.
24  *
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
29  * that are 0. The trust region constraint, which is added to the sub-SCIP, is given by
30  *
31  * \f[
32  * \sum_{i \in \mathcal{B}^{+}}(1 - x_{i}) + \sum_{i \in \mathcal{B}^{-}}x_{i} \le \theta
33  * \f]
34  *
35  * The variable \f$\theta\f$ measure the distance, in terms of the binary variables, of candidate solutions to the input
36  * solution.
37  *
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
40  * that must be achieved by the heuristic.
41  *
42  * The objective function is then modified to \f$f(x) + M\theta\f$, where \f$M\f$ is a parameter for penalizing the
43  * distance of solutions from the input solution \f$\hat{x}\f$.
44  *
45  * If a new incumbent solution is found by this heuristic, then the Trust Region heuristic is immediately
46  * re-executed with this new incumbent solution.
47  */
48 
49 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
50 
51 #ifndef __SCIP_HEUR_TRUSTREGION_H__
52 #define __SCIP_HEUR_TRUSTREGION_H__
53 
54 #include "scip/def.h"
55 #include "scip/type_retcode.h"
56 #include "scip/type_scip.h"
57 
58 #ifdef __cplusplus
59 extern "C" {
60 #endif
61 
62 /** creates local branching primal heuristic and includes it in SCIP
63  *
64  * @ingroup PrimalHeuristicIncludes
65  */
68  SCIP* scip /**< SCIP data structure */
69  );
70 
71 #ifdef __cplusplus
72 }
73 #endif
74 
75 #endif
#define SCIP_EXPORT
Definition: def.h:100
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for return codes for SCIP methods
SCIP_EXPORT SCIP_RETCODE SCIPincludeHeurTrustregion(SCIP *scip)
type definitions for SCIP&#39;s main datastructure
common defines and data types used in all packages of SCIP