Scippy

SCIP

Solving Constraint Integer Programs

heuristics.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-2024 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 heuristics.h
26  * @ingroup PUBLICCOREAPI
27  * @brief methods commonly used by primal heuristics
28  * @author Gregor Hendel
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __SCIP_HEURISTICS_H__
34 #define __SCIP_HEURISTICS_H__
35 
36 #include "scip/def.h"
37 #include "scip/type_scip.h"
38 #include "scip/type_heur.h"
39 #include "scip/type_misc.h"
40 #include "scip/type_retcode.h"
41 #include "scip/type_sol.h"
42 #include "scip/type_var.h"
43 
44 #ifdef __cplusplus
45 extern "C" {
46 #endif
47 
48 /**@defgroup PublicSpecialHeuristicMethods Special Methods
49  * @ingroup PublicHeuristicMethods
50  * @brief methods commonly used by primal heuristics
51  *
52  * @{
53  */
54 
55 /** performs a diving within the limits of the @p diveset parameters
56  *
57  * This method performs a diving according to the settings defined by the diving settings @p diveset; Contrary to the
58  * name, SCIP enters probing mode (not diving mode) and dives along a path into the tree. Domain propagation
59  * is applied at every node in the tree, whereas probing LPs might be solved less frequently.
60  *
61  * Starting from the current LP solution, the algorithm selects candidates which maximize the
62  * score defined by the @p diveset and whose solution value has not yet been rendered infeasible by propagation,
63  * and propagates the bound change on this candidate.
64  *
65  * The algorithm iteratively selects the the next (unfixed) candidate in the list, until either enough domain changes
66  * or the resolve frequency of the LP trigger an LP resolve (and hence, the set of potential candidates changes),
67  * or the last node is proven to be infeasible. It optionally backtracks and tries the
68  * other branching direction.
69  *
70  * After the set of remaining candidates is empty or the targeted depth is reached, the node LP is
71  * solved, and the old candidates are replaced by the new LP candidates.
72  *
73  * @see heur_guideddiving.c for an example implementation of a dive set controlling the diving algorithm.
74  *
75  * @note the node from where the algorithm is called is checked for a basic LP solution. If the solution
76  * is non-basic, e.g., when barrier without crossover is used, the method returns without performing a dive.
77  *
78  * @note currently, when multiple diving heuristics call this method and solve an LP at the same node, only the first
79  * call will be executed, @see SCIPgetLastDiveNode().
80  */
81 SCIP_EXPORT
83  SCIP* scip, /**< SCIP data structure */
84  SCIP_DIVESET* diveset, /**< settings for diving */
85  SCIP_SOL* worksol, /**< non-NULL working solution */
86  SCIP_HEUR* heur, /**< the calling primal heuristic */
87  SCIP_RESULT* result, /**< SCIP result pointer */
88  SCIP_Bool nodeinfeasible, /**< is the current node known to be infeasible? */
89  SCIP_Longint iterlim, /**< nonnegative iteration limit for the LP solves, or -1 for dynamic setting */
90  int nodelimit, /**< nonnegative probing node limit or -1 if no limit should be used */
91  SCIP_Real lpresolvedomchgquot, /**< percentage of immediate domain changes during probing to trigger LP resolve or -1
92  if diveset specific default should be used */
93  SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
94  );
95 
96 /** get a sub-SCIP copy of the transformed problem */
97 SCIP_EXPORT
99  SCIP* sourcescip, /**< source SCIP data structure */
100  SCIP* subscip, /**< sub-SCIP used by the heuristic */
101  SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables to the corresponding
102  * target variables */
103  const char* suffix, /**< suffix for the problem name */
104  SCIP_VAR** fixedvars, /**< source variables whose copies should be fixed in the target SCIP environment, or NULL */
105  SCIP_Real* fixedvals, /**< array of fixing values for target SCIP variables, or NULL */
106  int nfixedvars, /**< number of source variables whose copies should be fixed in the target SCIP environment, or NULL */
107  SCIP_Bool uselprows, /**< should the linear relaxation of the problem defined by LP rows be copied? */
108  SCIP_Bool copycuts, /**< should cuts be copied (only if uselprows == FALSE) */
109  SCIP_Bool* success, /**< was the copying successful? */
110  SCIP_Bool* valid /**< pointer to store whether the copying was valid, or NULL */
111  );
112 
113 /** adds a trust region neighborhood constraint to the @p targetscip
114  *
115  * a trust region constraint measures the deviation from the current incumbent solution \f$x^*\f$ by an auxiliary
116  * continuous variable \f$v \geq 0\f$:
117  * \f[
118  * \sum\limits_{j\in B} |x_j^* - x_j| = v
119  * \f]
120  * Only binary variables are taken into account. The deviation is penalized in the objective function using
121  * a positive \p violpenalty.
122  *
123  * @note: the trust region constraint creates an auxiliary variable to penalize the deviation from
124  * the current incumbent solution. This variable can afterwards be accessed using SCIPfindVar() by its name
125  * 'trustregion_violationvar'
126  */
127 SCIP_EXPORT
129  SCIP* scip, /**< the SCIP data structure */
130  SCIP* subscip, /**< SCIP data structure of the subproblem */
131  SCIP_VAR** subvars, /**< variables of the subproblem, NULL entries are ignored */
132  SCIP_Real violpenalty /**< the penalty for violating the trust region */
133  );
134 
135 /** @} */
136 
137 #ifdef __cplusplus
138 }
139 #endif
140 
141 #endif
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
type definitions for miscellaneous datastructures
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
type definitions for return codes for SCIP methods
SCIP_RETCODE SCIPaddTrustregionNeighborhoodConstraint(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_Real violpenalty)
Definition: heuristics.c:1029
type definitions for primal heuristics
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, int nodelimit, SCIP_Real lpresolvedomchgquot, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:220
type definitions for problem variables
#define SCIP_Bool
Definition: def.h:91
type definitions for storing primal CIP solutions
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition: type_heur.h:73
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition: heuristics.c:951
#define SCIP_Real
Definition: def.h:173
#define SCIP_Longint
Definition: def.h:158
common defines and data types used in all packages of SCIP