1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 scip_heur.c
17 * @ingroup OTHER_CFILES
18 * @brief public methods for primal heuristic plugins and divesets
19 * @author Tobias Achterberg
20 * @author Timo Berthold
21 * @author Gerald Gamrath
22 * @author Leona Gottwald
23 * @author Stefan Heinz
24 * @author Gregor Hendel
25 * @author Thorsten Koch
26 * @author Alexander Martin
27 * @author Marc Pfetsch
28 * @author Michael Winkler
29 * @author Kati Wolter
30 *
31 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
32 */
33
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
36 #include "scip/debug.h"
37 #include "scip/heur.h"
38 #include "scip/pub_message.h"
39 #include "scip/scip_heur.h"
40 #include "scip/set.h"
41 #include "scip/struct_mem.h"
42 #include "scip/struct_scip.h"
43 #include "scip/struct_set.h"
44
45 /** creates a primal heuristic and includes it in SCIP.
46 *
47 * @note method has all heuristic callbacks as arguments and is thus changed every time a new
48 * callback is added in future releases; consider using SCIPincludeHeurBasic() and setter functions
49 * if you seek for a method which is less likely to change in future releases
50 *
51 * @return \ref SCIP_OKAY is returned if everything worked. otherwise a suitable error code is passed. see \ref
52 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
53 *
54 * @pre This method can be called if @p scip is in one of the following stages:
55 * - \ref SCIP_STAGE_INIT
56 * - \ref SCIP_STAGE_PROBLEM
57 */
SCIPincludeHeur(SCIP * scip,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)58 SCIP_RETCODE SCIPincludeHeur(
59 SCIP* scip, /**< SCIP data structure */
60 const char* name, /**< name of primal heuristic */
61 const char* desc, /**< description of primal heuristic */
62 char dispchar, /**< display character of primal heuristic */
63 int priority, /**< priority of the primal heuristic */
64 int freq, /**< frequency for calling primal heuristic */
65 int freqofs, /**< frequency offset for calling primal heuristic */
66 int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */
67 SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed;
68 * see definition of SCIP_HEURTIMING for possible values */
69 SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */
70 SCIP_DECL_HEURCOPY ((*heurcopy)), /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
71 SCIP_DECL_HEURFREE ((*heurfree)), /**< destructor of primal heuristic */
72 SCIP_DECL_HEURINIT ((*heurinit)), /**< initialize primal heuristic */
73 SCIP_DECL_HEUREXIT ((*heurexit)), /**< deinitialize primal heuristic */
74 SCIP_DECL_HEURINITSOL ((*heurinitsol)), /**< solving process initialization method of primal heuristic */
75 SCIP_DECL_HEUREXITSOL ((*heurexitsol)), /**< solving process deinitialization method of primal heuristic */
76 SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */
77 SCIP_HEURDATA* heurdata /**< primal heuristic data */
78 )
79 {
80 SCIP_HEUR* heur;
81
82 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeHeur", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
83
84 /* check whether heuristic is already present */
85 if( SCIPfindHeur(scip, name) != NULL )
86 {
87 SCIPerrorMessage("heuristic <%s> already included.\n", name);
88 return SCIP_INVALIDDATA;
89 }
90
91 SCIP_CALL( SCIPheurCreate(&heur, scip->set, scip->messagehdlr, scip->mem->setmem,
92 name, desc, dispchar, priority, freq, freqofs, maxdepth, timingmask, usessubscip,
93 heurcopy, heurfree, heurinit, heurexit, heurinitsol, heurexitsol, heurexec, heurdata) );
94
95 SCIP_CALL( SCIPsetIncludeHeur(scip->set, heur) );
96
97 return SCIP_OKAY;
98 }
99
100 /** creates a primal heuristic and includes it in SCIP with its most fundamental callbacks.
101 * All non-fundamental (or optional) callbacks
102 * as, e. g., init and exit callbacks, will be set to NULL.
103 * Optional callbacks can be set via specific setter functions, see SCIPsetHeurCopy(), SCIPsetHeurFree(),
104 * SCIPsetHeurInit(), SCIPsetHeurExit(), SCIPsetHeurInitsol(), and SCIPsetHeurExitsol()
105 *
106 * @note if you want to set all callbacks with a single method call, consider using SCIPincludeHeur() instead
107 */
SCIPincludeHeurBasic(SCIP * scip,SCIP_HEUR ** heur,const char * name,const char * desc,char dispchar,int priority,int freq,int freqofs,int maxdepth,SCIP_HEURTIMING timingmask,SCIP_Bool usessubscip,SCIP_DECL_HEUREXEC ((* heurexec)),SCIP_HEURDATA * heurdata)108 SCIP_RETCODE SCIPincludeHeurBasic(
109 SCIP* scip, /**< SCIP data structure */
110 SCIP_HEUR** heur, /**< pointer to primal heuristic */
111 const char* name, /**< name of primal heuristic */
112 const char* desc, /**< description of primal heuristic */
113 char dispchar, /**< display character of primal heuristic */
114 int priority, /**< priority of the primal heuristic */
115 int freq, /**< frequency for calling primal heuristic */
116 int freqofs, /**< frequency offset for calling primal heuristic */
117 int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */
118 SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed;
119 * see definition of SCIP_HEURTIMING for possible values */
120 SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */
121 SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */
122 SCIP_HEURDATA* heurdata /**< primal heuristic data */
123 )
124 {
125 SCIP_HEUR* heurptr;
126
127 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeHeurBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
128
129 /* check whether heuristic is already present */
130 if( SCIPfindHeur(scip, name) != NULL )
131 {
132 SCIPerrorMessage("heuristic <%s> already included.\n", name);
133 return SCIP_INVALIDDATA;
134 }
135
136 SCIP_CALL( SCIPheurCreate(&heurptr, scip->set, scip->messagehdlr, scip->mem->setmem,
137 name, desc, dispchar, priority, freq, freqofs, maxdepth, timingmask, usessubscip,
138 NULL, NULL, NULL, NULL, NULL, NULL, heurexec, heurdata) );
139
140 assert(heurptr != NULL);
141
142 SCIP_CALL( SCIPsetIncludeHeur(scip->set, heurptr) );
143
144 if( heur != NULL )
145 *heur = heurptr;
146
147 return SCIP_OKAY;
148 }
149
150 /* new callback/method setter methods */
151
152 /** sets copy method of primal heuristic */
SCIPsetHeurCopy(SCIP * scip,SCIP_HEUR * heur,SCIP_DECL_HEURCOPY ((* heurcopy)))153 SCIP_RETCODE SCIPsetHeurCopy(
154 SCIP* scip, /**< SCIP data structure */
155 SCIP_HEUR* heur, /**< primal heuristic */
156 SCIP_DECL_HEURCOPY ((*heurcopy)) /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
157 )
158 {
159 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
160
161 assert(heur != NULL);
162
163 SCIPheurSetCopy(heur, heurcopy);
164
165 return SCIP_OKAY;
166 }
167
168 /** sets destructor method of primal heuristic */
SCIPsetHeurFree(SCIP * scip,SCIP_HEUR * heur,SCIP_DECL_HEURFREE ((* heurfree)))169 SCIP_RETCODE SCIPsetHeurFree(
170 SCIP* scip, /**< SCIP data structure */
171 SCIP_HEUR* heur, /**< primal heuristic */
172 SCIP_DECL_HEURFREE ((*heurfree)) /**< destructor of primal heuristic */
173 )
174 {
175 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
176
177 assert(heur != NULL);
178
179 SCIPheurSetFree(heur, heurfree);
180
181 return SCIP_OKAY;
182 }
183
184 /** sets initialization method of primal heuristic */
SCIPsetHeurInit(SCIP * scip,SCIP_HEUR * heur,SCIP_DECL_HEURINIT ((* heurinit)))185 SCIP_RETCODE SCIPsetHeurInit(
186 SCIP* scip, /**< SCIP data structure */
187 SCIP_HEUR* heur, /**< primal heuristic */
188 SCIP_DECL_HEURINIT ((*heurinit)) /**< initialize primal heuristic */
189 )
190 {
191 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
192
193 assert(heur != NULL);
194
195 SCIPheurSetInit(heur, heurinit);
196
197 return SCIP_OKAY;
198 }
199
200 /** sets deinitialization method of primal heuristic */
SCIPsetHeurExit(SCIP * scip,SCIP_HEUR * heur,SCIP_DECL_HEUREXIT ((* heurexit)))201 SCIP_RETCODE SCIPsetHeurExit(
202 SCIP* scip, /**< SCIP data structure */
203 SCIP_HEUR* heur, /**< primal heuristic */
204 SCIP_DECL_HEUREXIT ((*heurexit)) /**< deinitialize primal heuristic */
205 )
206 {
207 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
208
209 assert(heur != NULL);
210
211 SCIPheurSetExit(heur, heurexit);
212
213 return SCIP_OKAY;
214 }
215
216 /** sets solving process initialization method of primal heuristic */
SCIPsetHeurInitsol(SCIP * scip,SCIP_HEUR * heur,SCIP_DECL_HEURINITSOL ((* heurinitsol)))217 SCIP_RETCODE SCIPsetHeurInitsol(
218 SCIP* scip, /**< SCIP data structure */
219 SCIP_HEUR* heur, /**< primal heuristic */
220 SCIP_DECL_HEURINITSOL ((*heurinitsol)) /**< solving process initialization method of primal heuristic */
221 )
222 {
223 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
224
225 assert(heur != NULL);
226
227 SCIPheurSetInitsol(heur, heurinitsol);
228
229 return SCIP_OKAY;
230 }
231
232 /** sets solving process deinitialization method of primal heuristic */
SCIPsetHeurExitsol(SCIP * scip,SCIP_HEUR * heur,SCIP_DECL_HEUREXITSOL ((* heurexitsol)))233 SCIP_RETCODE SCIPsetHeurExitsol(
234 SCIP* scip, /**< SCIP data structure */
235 SCIP_HEUR* heur, /**< primal heuristic */
236 SCIP_DECL_HEUREXITSOL ((*heurexitsol)) /**< solving process deinitialization method of primal heuristic */
237 )
238 {
239 SCIP_CALL( SCIPcheckStage(scip, "SCIPsetHeurExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
240
241 assert(heur != NULL);
242
243 SCIPheurSetExitsol(heur, heurexitsol);
244
245 return SCIP_OKAY;
246 }
247
248 /** returns the primal heuristic of the given name, or NULL if not existing */
SCIPfindHeur(SCIP * scip,const char * name)249 SCIP_HEUR* SCIPfindHeur(
250 SCIP* scip, /**< SCIP data structure */
251 const char* name /**< name of primal heuristic */
252 )
253 {
254 assert(scip != NULL);
255 assert(scip->set != NULL);
256 assert(name != NULL);
257
258 return SCIPsetFindHeur(scip->set, name);
259 }
260
261 /** returns the array of currently available primal heuristics */
SCIPgetHeurs(SCIP * scip)262 SCIP_HEUR** SCIPgetHeurs(
263 SCIP* scip /**< SCIP data structure */
264 )
265 {
266 assert(scip != NULL);
267 assert(scip->set != NULL);
268
269 SCIPsetSortHeurs(scip->set);
270
271 return scip->set->heurs;
272 }
273
274 /** returns the number of currently available primal heuristics */
SCIPgetNHeurs(SCIP * scip)275 int SCIPgetNHeurs(
276 SCIP* scip /**< SCIP data structure */
277 )
278 {
279 assert(scip != NULL);
280 assert(scip->set != NULL);
281
282 return scip->set->nheurs;
283 }
284
285 /** sets the priority of a primal heuristic */
SCIPsetHeurPriority(SCIP * scip,SCIP_HEUR * heur,int priority)286 SCIP_RETCODE SCIPsetHeurPriority(
287 SCIP* scip, /**< SCIP data structure */
288 SCIP_HEUR* heur, /**< primal heuristic */
289 int priority /**< new priority of the primal heuristic */
290 )
291 {
292 assert(scip != NULL);
293 assert(scip->set != NULL);
294
295 SCIPheurSetPriority(heur, scip->set, priority);
296
297 return SCIP_OKAY;
298 }
299
300 /** create a diving set associated with a primal heuristic. The primal heuristic needs to be included
301 * before this method can be called. The diveset is installed in the array of divesets of the heuristic
302 * and can be retrieved later by accessing SCIPheurGetDivesets()
303 *
304 * @return \ref SCIP_OKAY is returned if everything worked. otherwise a suitable error code is passed. see \ref
305 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
306 *
307 * @pre This method can be called if @p scip is in one of the following stages:
308 * - \ref SCIP_STAGE_INIT
309 * - \ref SCIP_STAGE_PROBLEM
310 */
SCIPcreateDiveset(SCIP * scip,SCIP_DIVESET ** diveset,SCIP_HEUR * heur,const char * name,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_Bool specificsos1score,SCIP_DECL_DIVESETGETSCORE ((* divesetgetscore)),SCIP_DECL_DIVESETAVAILABLE ((* divesetavailable)))311 SCIP_RETCODE SCIPcreateDiveset(
312 SCIP* scip, /**< SCIP data structure */
313 SCIP_DIVESET** diveset, /**< pointer to created diving heuristic settings, or NULL if not needed */
314 SCIP_HEUR* heur, /**< primal heuristic to which the diveset belongs */
315 const char* name, /**< name for the diveset, or NULL if the name of the heuristic should be used */
316 SCIP_Real minreldepth, /**< minimal relative depth to start diving */
317 SCIP_Real maxreldepth, /**< maximal relative depth to start diving */
318 SCIP_Real maxlpiterquot, /**< maximal fraction of diving LP iterations compared to node LP iterations */
319 SCIP_Real maxdiveubquot, /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
320 * where diving is performed (0.0: no limit) */
321 SCIP_Real maxdiveavgquot, /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
322 * where diving is performed (0.0: no limit) */
323 SCIP_Real maxdiveubquotnosol, /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
324 SCIP_Real maxdiveavgquotnosol,/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
325 SCIP_Real lpresolvedomchgquot,/**< percentage of immediate domain changes during probing to trigger LP resolve */
326 int lpsolvefreq, /**< LP solve frequency for (0: only if enough domain reductions are found by propagation)*/
327 int maxlpiterofs, /**< additional number of allowed LP iterations */
328 unsigned int initialseed, /**< initial seed for random number generation */
329 SCIP_Bool backtrack, /**< use one level of backtracking if infeasibility is encountered? */
330 SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered instead of the slower but
331 * more general constraint handler diving variable selection? */
332 SCIP_Bool ispublic, /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
333 SCIP_Bool specificsos1score, /**< should SOS1 variables be scored by the diving heuristics specific score function;
334 * otherwise use the score function of the SOS1 constraint handler */
335 SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), /**< method for candidate score and rounding direction */
336 SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)) /**< callback to check availability of dive set at the current stage, or NULL if always available */
337 )
338 {
339 SCIP_DIVESET* divesetptr = NULL;
340 SCIP_CALL( SCIPcheckStage(scip, "SCIPcreateDiveset", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
341
342 /* create the diveset (this will add diving specific parameters for this heuristic) */
343 SCIP_CALL( SCIPdivesetCreate(&divesetptr, heur, name, scip->set, scip->messagehdlr, scip->mem->setmem,
344 minreldepth, maxreldepth, maxlpiterquot, maxdiveubquot, maxdiveavgquot, maxdiveubquotnosol,
345 maxdiveavgquotnosol, lpresolvedomchgquot, lpsolvefreq, maxlpiterofs, initialseed, backtrack,
346 onlylpbranchcands, ispublic, specificsos1score, divesetgetscore, divesetavailable) );
347
348 assert(divesetptr != NULL);
349 if( diveset != NULL )
350 *diveset = divesetptr;
351
352 return SCIP_OKAY;
353 }
354
355 /** check specific preconditions for diving, e.g., if an incumbent solution is available */
SCIPisDivesetAvailable(SCIP * scip,SCIP_DIVESET * diveset,SCIP_Bool * available)356 SCIP_RETCODE SCIPisDivesetAvailable(
357 SCIP* scip, /**< SCIP data structure */
358 SCIP_DIVESET* diveset, /**< diving heuristic settings */
359 SCIP_Bool* available /**< pointer to store if the diving can run at the current solving stage */
360 )
361 {
362 assert(scip != NULL);
363 assert(diveset != NULL);
364 assert(available != NULL);
365
366 SCIP_CALL( SCIPdivesetIsAvailable(diveset, scip->set, available) );
367
368 return SCIP_OKAY;
369 }
370