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-2023 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file heur_trustregion.h
26  * @ingroup PRIMALHEURISTICS
27  * @brief Large neighborhood search heuristic for Benders' decomposition based on trust region methods
28  * @author Stephen J. Maher
29  *
30  * The Trust Region heuristic draws upon trust region methods for solving optimization problems, especially in the
31  * context of Benders' decomposition. This heuristic has been developed to improve the heuristic performance of the
32  * Benders' decomposition algorithm within SCIP.
33  *
34  * The Trust Region heuristic copies the original SCIP instance and adds a constraint to penalize changes from the
35  * incumbent solution. Consider a problem that includes a set of binary variables \f$\mathcal{B}\f$. Given a feasible
36  * solution \f$\hat{x}\f$ to the original problem, we define the set \f$\mathcal{B}^{+}\f$ as the index set for the
37  * binary variables that are 1 in the input solution and \f$\mathcal{B}^{-}\f$ as the index set for binary variables
38  * that are 0. The trust region constraint, which is added to the sub-SCIP, is given by
39  *
40  * \f[
41  * \sum_{i \in \mathcal{B}^{+}}(1 - x_{i}) + \sum_{i \in \mathcal{B}^{-}}x_{i} \le \theta
42  * \f]
43  *
44  * The variable \f$\theta\f$ measure the distance, in terms of the binary variables, of candidate solutions to the input
45  * solution.
46  *
47  * In addition, an upper bounding constraint is explicitly added to enforce a minimum improvement from the heuristic,
48  * given by \f$f(x) \le f(\hat{x}) - \epsilon\f$. The parameter \f$\epsilon \ge 0\f$ denotes the minimum improvement
49  * that must be achieved by the heuristic.
50  *
51  * The objective function is then modified to \f$f(x) + M\theta\f$, where \f$M\f$ is a parameter for penalizing the
52  * distance of solutions from the input solution \f$\hat{x}\f$.
53  *
54  * If a new incumbent solution is found by this heuristic, then the Trust Region heuristic is immediately
55  * re-executed with this new incumbent solution.
56  */
57 
58 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
59 
60 #ifndef __SCIP_HEUR_TRUSTREGION_H__
61 #define __SCIP_HEUR_TRUSTREGION_H__
62 
63 #include "scip/def.h"
64 #include "scip/type_retcode.h"
65 #include "scip/type_scip.h"
66 
67 #ifdef __cplusplus
68 extern "C" {
69 #endif
70 
71 /** creates local branching primal heuristic and includes it in SCIP
72  *
73  * @ingroup PrimalHeuristicIncludes
74  */
75 SCIP_EXPORT
77  SCIP* scip /**< SCIP data structure */
78  );
79 
80 #ifdef __cplusplus
81 }
82 #endif
83 
84 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for return codes for SCIP methods
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPincludeHeurTrustregion(SCIP *scip)
common defines and data types used in all packages of SCIP