Scippy

SCIP

Solving Constraint Integer Programs

heur.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 2002-2022 Zuse Institute Berlin */
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.h
26  * @ingroup INTERNALAPI
27  * @brief internal methods for primal heuristics
28  * @author Tobias Achterberg
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __SCIP_HEUR_H__
34 #define __SCIP_HEUR_H__
35 
36 
37 #include "scip/def.h"
38 #include "blockmemshell/memory.h"
39 #include "scip/type_retcode.h"
40 #include "scip/type_result.h"
41 #include "scip/type_set.h"
42 #include "scip/type_primal.h"
43 #include "scip/type_heur.h"
44 #include "scip/pub_heur.h"
45 #include "scip/stat.h"
46 
47 #ifdef __cplusplus
48 extern "C" {
49 #endif
50 
51 /** create a set of diving heuristic settings */
53  SCIP_DIVESET** divesetptr, /**< pointer to the freshly created diveset */
54  SCIP_HEUR* heur, /**< the heuristic to which this dive setting belongs */
55  const char* name, /**< name for the diveset, or NULL if the name of the heuristic should be used */
56  SCIP_SET* set, /**< global SCIP settings */
57  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
58  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
59  SCIP_Real minreldepth, /**< minimal relative depth to start diving */
60  SCIP_Real maxreldepth, /**< maximal relative depth to start diving */
61  SCIP_Real maxlpiterquot, /**< maximal fraction of diving LP iterations compared to node LP iterations */
62  SCIP_Real maxdiveubquot, /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
63  * where diving is performed (0.0: no limit) */
64  SCIP_Real maxdiveavgquot, /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
65  * where diving is performed (0.0: no limit) */
66  SCIP_Real maxdiveubquotnosol, /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
67  SCIP_Real maxdiveavgquotnosol,/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
68  SCIP_Real lpresolvedomchgquot,/**< percentage of immediate domain changes during probing to trigger LP resolve */
69  int lpsolvefreq, /**< LP solve frequency for (0: only if enough domain reductions are found by propagation)*/
70  int maxlpiterofs, /**< additional number of allowed LP iterations */
71  unsigned int initialseed, /**< initial seed for random number generation */
72  SCIP_Bool backtrack, /**< use one level of backtracking if infeasibility is encountered? */
73  SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered instead of the slower but
74  * more general constraint handler diving variable selection? */
75  SCIP_Bool ispublic, /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
76  SCIP_DIVETYPE divetypemask, /**< bit mask that represents the supported dive types by this dive set */
77  SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), /**< method for candidate score and rounding direction */
78  SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)) /**< callback to check availability of dive set at the current stage, or NULL if always available */
79  );
80 
81 /** resets diving settings counters */
83  SCIP_DIVESET* diveset, /**< diveset to be reset */
84  SCIP_SET* set /**< global SCIP settings */
85  );
86 
87 /** update diveset statistics and global diveset statistics */
89  SCIP_DIVESET* diveset, /**< diveset to be reset */
90  SCIP_STAT* stat, /**< global SCIP statistics */
91  int depth, /**< the depth reached this time */
92  int nprobingnodes, /**< the number of probing nodes explored this time */
93  int nbacktracks, /**< the number of backtracks during probing this time */
94  SCIP_Longint nsolsfound, /**< number of new solutions found this time */
95  SCIP_Longint nbestsolsfound, /**< number of new best solutions found this time */
96  SCIP_Longint nconflictsfound, /**< number of new conflicts found this time */
97  SCIP_Bool leavesol, /**< has the diving heuristic reached a feasible leaf */
98  SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
99  );
100 
101 /** get the candidate score and preferred rounding direction for a candidate variable */
103  SCIP_DIVESET* diveset, /**< general diving settings */
104  SCIP_SET* set, /**< SCIP settings */
105  SCIP_DIVETYPE divetype, /**< the type of diving that should be applied */
106  SCIP_VAR* divecand, /**< the candidate for which the branching direction is requested */
107  SCIP_Real divecandsol, /**< LP solution value of the candidate */
108  SCIP_Real divecandfrac, /**< fractionality of the candidate */
109  SCIP_Real* candscore, /**< pointer to store the candidate score */
110  SCIP_Bool* roundup /**< pointer to store whether preferred direction for diving is upwards */
111  );
112 
113 /** check specific preconditions for diving, e.g., if an incumbent solution is available */
115  SCIP_DIVESET* diveset, /**< diving heuristic settings */
116  SCIP_SET* set, /**< SCIP settings */
117  SCIP_Bool* available /**< pointer to store if the diving can run at the current solving stage */
118  );
119 
120 /** update diveset LP statistics, should be called after every LP solved by this diving heuristic */
122  SCIP_DIVESET* diveset, /**< diving settings */
123  SCIP_STAT* stat, /**< global SCIP statistics */
124  SCIP_Longint niterstoadd, /**< additional number of LP iterations to be added */
125  SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
126  );
127 
128 /** copies the given primal heuristic to a new scip */
130  SCIP_HEUR* heur, /**< primal heuristic */
131  SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
132  );
133 
134 /** creates a primal heuristic */
136  SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */
137  SCIP_SET* set, /**< global SCIP settings */
138  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
139  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
140  const char* name, /**< name of primal heuristic */
141  const char* desc, /**< description of primal heuristic */
142  char dispchar, /**< display character of primal heuristic */
143  int priority, /**< priority of the primal heuristic */
144  int freq, /**< frequency for calling primal heuristic */
145  int freqofs, /**< frequency offset for calling primal heuristic */
146  int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */
147  SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed */
148  SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */
149  SCIP_DECL_HEURCOPY ((*heurcopy)), /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
150  SCIP_DECL_HEURFREE ((*heurfree)), /**< destructor of primal heuristic */
151  SCIP_DECL_HEURINIT ((*heurinit)), /**< initialize primal heuristic */
152  SCIP_DECL_HEUREXIT ((*heurexit)), /**< deinitialize primal heuristic */
153  SCIP_DECL_HEURINITSOL ((*heurinitsol)), /**< solving process initialization method of primal heuristic */
154  SCIP_DECL_HEUREXITSOL ((*heurexitsol)), /**< solving process deinitialization method of primal heuristic */
155  SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */
156  SCIP_HEURDATA* heurdata /**< primal heuristic data */
157  );
158 
159 /** calls destructor and frees memory of primal heuristic */
161  SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */
162  SCIP_SET* set, /**< global SCIP settings */
163  BMS_BLKMEM* blkmem /**< block memory */
164  );
165 
166 /** initializes primal heuristic */
168  SCIP_HEUR* heur, /**< primal heuristic */
169  SCIP_SET* set /**< global SCIP settings */
170  );
171 
172 /** calls exit method of primal heuristic */
174  SCIP_HEUR* heur, /**< primal heuristic */
175  SCIP_SET* set /**< global SCIP settings */
176  );
177 
178 /** informs primal heuristic that the branch and bound process is being started */
180  SCIP_HEUR* heur, /**< primal heuristic */
181  SCIP_SET* set /**< global SCIP settings */
182  );
183 
184 /** informs primal heuristic that the branch and bound process data is being freed */
186  SCIP_HEUR* heur, /**< primal heuristic */
187  SCIP_SET* set /**< global SCIP settings */
188  );
189 
190 /** should the heuristic be executed at the given depth, frequency, timing, ... */
192  SCIP_HEUR* heur, /**< primal heuristic */
193  int depth, /**< depth of current node */
194  int lpstateforkdepth, /**< depth of the last node with solved LP */
195  SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */
196  SCIP_Bool* delayed /**< pointer to store whether the heuristic should be delayed */
197  );
198 
199 /** calls execution method of primal heuristic */
201  SCIP_HEUR* heur, /**< primal heuristic */
202  SCIP_SET* set, /**< global SCIP settings */
203  SCIP_PRIMAL* primal, /**< primal data */
204  int depth, /**< depth of current node */
205  int lpstateforkdepth, /**< depth of the last node with solved LP */
206  SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */
207  SCIP_Bool nodeinfeasible, /**< was the current node already detected to be infeasible? */
208  int* ndelayedheurs, /**< pointer to count the number of delayed heuristics */
209  SCIP_RESULT* result /**< pointer to store the result of the callback method */
210  );
211 
212 /** sets priority of primal heuristic */
214  SCIP_HEUR* heur, /**< primal heuristic */
215  SCIP_SET* set, /**< global SCIP settings */
216  int priority /**< new priority of the primal heuristic */
217  );
218 
219 /** sets copy callback of primal heuristic */
220 void SCIPheurSetCopy(
221  SCIP_HEUR* heur, /**< primal heuristic */
222  SCIP_DECL_HEURCOPY ((*heurcopy)) /**< copy callback of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
223  );
224 
225 /** sets destructor callback of primal heuristic */
226 void SCIPheurSetFree(
227  SCIP_HEUR* heur, /**< primal heuristic */
228  SCIP_DECL_HEURFREE ((*heurfree)) /**< destructor of primal heuristic */
229  );
230 
231 /** sets initialization callback of primal heuristic */
232 void SCIPheurSetInit(
233  SCIP_HEUR* heur, /**< primal heuristic */
234  SCIP_DECL_HEURINIT ((*heurinit)) /**< initialize primal heuristic */
235  );
236 
237 /** sets deinitialization callback of primal heuristic */
238 void SCIPheurSetExit(
239  SCIP_HEUR* heur, /**< primal heuristic */
240  SCIP_DECL_HEUREXIT ((*heurexit)) /**< deinitialize primal heuristic */
241  );
242 
243 /** sets solving process initialization callback of primal heuristic */
244 void SCIPheurSetInitsol(
245  SCIP_HEUR* heur, /**< primal heuristic */
246  SCIP_DECL_HEURINITSOL ((*heurinitsol)) /**< solving process initialization callback of primal heuristic */
247  );
248 
249 /** sets solving process deinitialization callback of primal heuristic */
250 void SCIPheurSetExitsol(
251  SCIP_HEUR* heur, /**< primal heuristic */
252  SCIP_DECL_HEUREXITSOL ((*heurexitsol)) /**< solving process deinitialization callback of primal heuristic */
253  );
254 
255 /** enables or disables all clocks of \p heur, depending on the value of the flag */
257  SCIP_HEUR* heur, /**< the heuristic for which all clocks should be enabled or disabled */
258  SCIP_Bool enable /**< should the clocks of the heuristic be enabled? */
259  );
260 
261 #ifdef __cplusplus
262 }
263 #endif
264 
265 #endif
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
#define SCIP_DECL_HEURINITSOL(x)
Definition: type_heur.h:131
SCIP_RETCODE SCIPdivesetGetScore(SCIP_DIVESET *diveset, SCIP_SET *set, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup)
Definition: heur.c:831
void SCIPdivesetUpdateStats(SCIP_DIVESET *diveset, SCIP_STAT *stat, int depth, int nprobingnodes, int nbacktracks, SCIP_Longint nsolsfound, SCIP_Longint nbestsolsfound, SCIP_Longint nconflictsfound, SCIP_Bool leavesol, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:202
SCIP_RETCODE SCIPheurFree(SCIP_HEUR **heur, SCIP_SET *set, BMS_BLKMEM *blkmem)
Definition: heur.c:1025
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:106
void SCIPheurSetExitsol(SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: heur.c:1439
SCIP_RETCODE SCIPheurExec(SCIP_HEUR *heur, SCIP_SET *set, SCIP_PRIMAL *primal, int depth, int lpstateforkdepth, SCIP_HEURTIMING heurtiming, SCIP_Bool nodeinfeasible, int *ndelayedheurs, SCIP_RESULT *result)
Definition: heur.c:1260
SCIP_RETCODE SCIPheurInitsol(SCIP_HEUR *heur, SCIP_SET *set)
Definition: heur.c:1144
void SCIPheurSetPriority(SCIP_HEUR *heur, SCIP_SET *set, int priority)
Definition: heur.c:1521
#define SCIP_DECL_HEURCOPY(x)
Definition: type_heur.h:96
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define SCIP_DECL_HEUREXEC(x)
Definition: type_heur.h:162
type definitions for global SCIP settings
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:76
SCIP_RETCODE SCIPdivesetReset(SCIP_DIVESET *diveset, SCIP_SET *set)
Definition: heur.c:130
SCIP_RETCODE SCIPheurCreate(SCIP_HEUR **heur, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEURCOPY((*heurcopy)), SCIP_DECL_HEURFREE((*heurfree)), SCIP_DECL_HEURINIT((*heurinit)), SCIP_DECL_HEUREXIT((*heurexit)), SCIP_DECL_HEURINITSOL((*heurinitsol)), SCIP_DECL_HEUREXITSOL((*heurexitsol)), SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: heur.c:986
type definitions for return codes for SCIP methods
unsigned int SCIP_DIVETYPE
Definition: type_heur.h:63
#define SCIP_DECL_DIVESETGETSCORE(x)
Definition: type_heur.h:183
SCIP_RETCODE SCIPheurCopyInclude(SCIP_HEUR *heur, SCIP_SET *set)
Definition: heur.c:879
type definitions for primal heuristics
SCIP_Bool SCIPheurShouldBeExecuted(SCIP_HEUR *heur, int depth, int lpstateforkdepth, SCIP_HEURTIMING heurtiming, SCIP_Bool *delayed)
Definition: heur.c:1198
void SCIPheurSetCopy(SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: heur.c:1384
void SCIPheurSetFree(SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: heur.c:1395
#define SCIP_Bool
Definition: def.h:93
SCIP_RETCODE SCIPheurInit(SCIP_HEUR *heur, SCIP_SET *set)
Definition: heur.c:1061
SCIP_RETCODE SCIPdivesetIsAvailable(SCIP_DIVESET *diveset, SCIP_SET *set, SCIP_Bool *available)
Definition: heur.c:855
#define SCIP_DECL_DIVESETAVAILABLE(x)
Definition: type_heur.h:198
void SCIPheurEnableOrDisableClocks(SCIP_HEUR *heur, SCIP_Bool enable)
Definition: heur.c:1616
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition: type_heur.h:72
SCIP_RETCODE SCIPheurExit(SCIP_HEUR *heur, SCIP_SET *set)
Definition: heur.c:1114
#define SCIP_DECL_HEUREXIT(x)
Definition: type_heur.h:120
#define SCIP_DECL_HEURINIT(x)
Definition: type_heur.h:112
#define SCIP_Real
Definition: def.h:186
internal methods for problem statistics
result codes for SCIP callback methods
#define SCIP_DECL_HEURFREE(x)
Definition: type_heur.h:104
void SCIPdivesetUpdateLPStats(SCIP_DIVESET *diveset, SCIP_STAT *stat, SCIP_Longint niterstoadd, SCIP_DIVECONTEXT divecontext)
Definition: heur.c:785
SCIP_RETCODE SCIPheurExitsol(SCIP_HEUR *heur, SCIP_SET *set)
Definition: heur.c:1174
#define SCIP_Longint
Definition: def.h:171
void SCIPheurSetExit(SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: heur.c:1417
void SCIPheurSetInit(SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: heur.c:1406
type definitions for collecting primal CIP solutions and primal informations
public methods for primal heuristics
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:439
SCIP_RETCODE SCIPdivesetCreate(SCIP_DIVESET **divesetptr, SCIP_HEUR *heur, const char *name, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, SCIP_Real minreldepth, SCIP_Real maxreldepth, SCIP_Real maxlpiterquot, SCIP_Real maxdiveubquot, SCIP_Real maxdiveavgquot, SCIP_Real maxdiveubquotnosol, SCIP_Real maxdiveavgquotnosol, SCIP_Real lpresolvedomchgquot, int lpsolvefreq, int maxlpiterofs, unsigned int initialseed, SCIP_Bool backtrack, SCIP_Bool onlylpbranchcands, SCIP_Bool ispublic, SCIP_DIVETYPE divetypemask, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)))
Definition: heur.c:264
#define SCIP_DECL_HEUREXITSOL(x)
Definition: type_heur.h:142
void SCIPheurSetInitsol(SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: heur.c:1428
memory allocation routines