1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 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.c
17 * @ingroup OTHER_CFILES
18 * @brief methods for primal heuristics
19 * @author Tobias Achterberg
20 * @author Timo Berthold
21 */
22
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24
25 #include <assert.h>
26 #include <string.h>
27
28 #include "scip/def.h"
29 #include "scip/set.h"
30 #include "scip/clock.h"
31 #include "scip/paramset.h"
32 #include "scip/primal.h"
33 #include "scip/scip.h"
34 #include "scip/heur.h"
35 #include "scip/pub_message.h"
36 #include "scip/pub_misc.h"
37 #include "scip/misc.h"
38
39 #include "scip/struct_heur.h"
40
41 /** compares two heuristics w.r.t. to their delay positions and priorities */
42 SCIP_DECL_SORTPTRCOMP(SCIPheurComp)
43 { /*lint --e{715}*/
44 SCIP_HEUR* heur1 = (SCIP_HEUR*)elem1;
45 SCIP_HEUR* heur2 = (SCIP_HEUR*)elem2;
46
47 assert(heur1 != NULL);
48 assert(heur2 != NULL);
49
50 if( heur1->delaypos == heur2->delaypos )
51 if( heur1->priority != heur2->priority )
52 return heur2->priority - heur1->priority; /* prefer higher priorities */
53 else
54 return (strcmp(heur1->name, heur2->name)); /* tiebreaker */
55 else if( heur1->delaypos == -1 )
56 return +1; /* prefer delayed heuristics */
57 else if( heur2->delaypos == -1 )
58 return -1; /* prefer delayed heuristics */
59 else if( heur1->ncalls * heur1->freq > heur2->ncalls * heur2->freq )
60 return +1;
61 else if( heur1->ncalls * heur1->freq < heur2->ncalls * heur2->freq )
62 return -1;
63 else
64 return heur1->delaypos - heur2->delaypos; /* prefer lower delay positions */
65 }
66
67 /** compares two heuristics w.r.t. to their priority values */
68 SCIP_DECL_SORTPTRCOMP(SCIPheurCompPriority)
69 {
70 return SCIPheurGetPriority((SCIP_HEUR*)elem2) -
71 SCIPheurGetPriority((SCIP_HEUR*)elem1);
72 }
73
74 /** comparison method for sorting heuristics w.r.t. to their name */
75 SCIP_DECL_SORTPTRCOMP(SCIPheurCompName)
76 {
77 return strcmp(SCIPheurGetName((SCIP_HEUR*)elem1), SCIPheurGetName((SCIP_HEUR*)elem2));
78 }
79
80 /** method to call, when the priority of a heuristic was changed */
81 static
82 SCIP_DECL_PARAMCHGD(paramChgdHeurPriority)
83 { /*lint --e{715}*/
84 SCIP_PARAMDATA* paramdata;
85
86 paramdata = SCIPparamGetData(param);
87 assert(paramdata != NULL);
88
89 /* use SCIPsetHeurPriority() to mark the heuristics unsorted */
90 SCIP_CALL( SCIPsetHeurPriority(scip, (SCIP_HEUR*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
91
92 return SCIP_OKAY;
93 }
94
95 /** resets diving statistics */
96 static
97 void resetDivesetStats(
98 SCIP_DIVESETSTATS* divesetstats /**< dive set statistics */
99 )
100 {
101 assert(divesetstats != NULL);
102
103 divesetstats->nlpiterations = 0L;
104 divesetstats->totaldepth = 0L;
105 divesetstats->totalsoldepth = 0L;
106 divesetstats->totalnnodes = 0L;
107 divesetstats->totalnbacktracks = 0L;
108 divesetstats->minsoldepth = INT_MAX;
109 divesetstats->maxsoldepth = -1;
110 divesetstats->mindepth = INT_MAX;
111 divesetstats->maxdepth = -1;
112 divesetstats->nlps = 0;
113 divesetstats->nsolsfound = 0;
114 divesetstats->nbestsolsfound = 0;
115 divesetstats->nconflictsfound = 0;
116 divesetstats->ncalls = 0;
117 divesetstats->nsolcalls = 0;
118 }
119
120 /* resets diving settings counters */
121 SCIP_RETCODE SCIPdivesetReset(
122 SCIP_DIVESET* diveset, /**< diveset to be reset */
123 SCIP_SET* set /**< global SCIP settings */
124 )
125 {
126 int d;
127
128 assert(diveset != NULL);
129 assert(diveset->randnumgen != NULL);
130
131 /* reset diveset statistics for all contexts */
132 for( d = 0; d < 3; ++d )
133 {
134 resetDivesetStats(diveset->divesetstats[d]);
135 }
136
137 /* reset the random number generator */
138 SCIPrandomSetSeed(diveset->randnumgen, (unsigned int) SCIPsetInitializeRandomSeed(set, diveset->initialseed));
139
140 return SCIP_OKAY;
141 }
142
143 /** update dive set statistics */
144 static
145 void updateDivesetstats(
146 SCIP_DIVESETSTATS* divesetstats, /**< dive set statistics */
147 int depth, /**< the depth reached this time */
148 int nprobingnodes, /**< the number of probing nodes explored this time */
149 int nbacktracks, /**< the number of backtracks during probing this time */
150 SCIP_Longint nsolsfound, /**< number of new solutions found this time */
151 SCIP_Longint nbestsolsfound, /**< number of new best solutions found this time */
152 SCIP_Longint nconflictsfound, /**< number of new conflicts found this time */
153 SCIP_Bool leavesol /**< has the diving heuristic reached a feasible leaf */
154 )
155 {
156 divesetstats->totaldepth += depth;
157 divesetstats->mindepth = MIN(divesetstats->mindepth, depth);
158 divesetstats->maxdepth = MAX(divesetstats->maxdepth, depth);
159 divesetstats->totalnnodes += nprobingnodes;
160 divesetstats->totalnbacktracks += nbacktracks;
161 divesetstats->ncalls++;
162
163 /* update solution statistics only if a solution was found */
164 if( leavesol )
165 {
166 divesetstats->totalsoldepth += depth;
167 divesetstats->minsoldepth = MIN(divesetstats->minsoldepth, depth);
168 divesetstats->maxsoldepth = MAX(divesetstats->maxsoldepth, depth);
169 divesetstats->nsolcalls++;
170 }
171
172 divesetstats->nsolsfound += nsolsfound;
173 divesetstats->nbestsolsfound += nbestsolsfound;
174 divesetstats->nconflictsfound += nconflictsfound;
175 }
176
177 /** returns the dive set statistics for the given context */
178 static
179 SCIP_DIVESETSTATS* divesetGetStats(
180 SCIP_DIVESET* diveset, /**< diveset to be reset */
181 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
182 )
183 {
184 assert(diveset != NULL);
185 assert(divecontext == SCIP_DIVECONTEXT_ADAPTIVE ||
186 divecontext == SCIP_DIVECONTEXT_SINGLE ||
187 divecontext == SCIP_DIVECONTEXT_TOTAL);
188
189 return diveset->divesetstats[(int)divecontext];
190 }
191
192 /** update diveset statistics and global diveset statistics */
193 void SCIPdivesetUpdateStats(
194 SCIP_DIVESET* diveset, /**< diveset to be reset */
195 SCIP_STAT* stat, /**< global SCIP statistics */
196 int depth, /**< the depth reached this time */
197 int nprobingnodes, /**< the number of probing nodes explored this time */
198 int nbacktracks, /**< the number of backtracks during probing this time */
199 SCIP_Longint nsolsfound, /**< number of new solutions found this time */
200 SCIP_Longint nbestsolsfound, /**< number of new best solutions found this time */
201 SCIP_Longint nconflictsfound, /**< number of new conflicts found this time */
202 SCIP_Bool leavesol, /**< has the diving heuristic reached a feasible leaf */
203 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
204 )
205 {
206 int c;
207 SCIP_DIVECONTEXT updatecontexts[] = {SCIP_DIVECONTEXT_TOTAL, divecontext};
208
209 assert(diveset != NULL);
210 assert(divecontext == SCIP_DIVECONTEXT_ADAPTIVE || divecontext == SCIP_DIVECONTEXT_SINGLE);
211
212 /* update statistics for total context and given context */
213 for( c = 0; c < 2; ++c )
214 {
215 updateDivesetstats(divesetGetStats(diveset, updatecontexts[c]), depth, nprobingnodes,
216 nbacktracks, nsolsfound, nbestsolsfound, nconflictsfound, leavesol);
217 }
218
219 stat->totaldivesetdepth += depth;
220 stat->ndivesetcalls++;
221 }
222
223 /** append diveset to heuristic array of divesets */
224 static
225 SCIP_RETCODE heurAddDiveset(
226 SCIP_HEUR* heur, /**< the heuristic to which this dive setting belongs */
227 SCIP_DIVESET* diveset /**< pointer to the freshly created diveset */
228 )
229 {
230 assert(heur != NULL);
231 assert(diveset != NULL);
232 assert(diveset->heur == NULL);
233
234 diveset->heur = heur;
235
236 if( heur->divesets == NULL )
237 {
238 assert(heur->ndivesets == 0);
239 SCIP_ALLOC( BMSallocMemoryArray(&heur->divesets, 1) );
240 }
241 else
242 {
243 assert(heur->ndivesets > 0);
244 SCIP_ALLOC( BMSreallocMemoryArray(&heur->divesets, heur->ndivesets + 1) ); /*lint !e776 I expect no overflow here */
245 }
246
247 /* append diveset to the end of the array */
248 heur->divesets[heur->ndivesets] = diveset;
249 heur->ndivesets++;
250
251 return SCIP_OKAY;
252 }
253
254 /** create a set of diving heuristic settings */
255 SCIP_RETCODE SCIPdivesetCreate(
256 SCIP_DIVESET** divesetptr, /**< pointer to the freshly created diveset */
257 SCIP_HEUR* heur, /**< the heuristic to which this dive setting belongs */
258 const char* name, /**< name for the diveset, or NULL if the name of the heuristic should be used */
259 SCIP_SET* set, /**< global SCIP settings */
260 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
261 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
262 SCIP_Real minreldepth, /**< minimal relative depth to start diving */
263 SCIP_Real maxreldepth, /**< maximal relative depth to start diving */
264 SCIP_Real maxlpiterquot, /**< maximal fraction of diving LP iterations compared to node LP iterations */
265 SCIP_Real maxdiveubquot, /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
266 * where diving is performed (0.0: no limit) */
267 SCIP_Real maxdiveavgquot, /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
268 * where diving is performed (0.0: no limit) */
269 SCIP_Real maxdiveubquotnosol, /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
270 SCIP_Real maxdiveavgquotnosol,/**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
271 SCIP_Real lpresolvedomchgquot,/**< percentage of immediate domain changes during probing to trigger LP resolve */
272 int lpsolvefreq, /**< LP solve frequency for (0: only if enough domain reductions are found by propagation)*/
273 int maxlpiterofs, /**< additional number of allowed LP iterations */
274 unsigned int initialseed, /**< initial seed for random number generation */
275 SCIP_Bool backtrack, /**< use one level of backtracking if infeasibility is encountered? */
276 SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered instead of the slower but
277 * more general constraint handler diving variable selection? */
278 SCIP_Bool ispublic, /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
279 SCIP_DIVETYPE divetypemask, /**< bit mask that represents the supported dive types by this dive set */
280 SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), /**< method for candidate score and rounding direction */
281 SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)) /**< callback to check availability of dive set at the current stage, or NULL if always available */
282 )
283 {
284 int c;
285 char paramname[SCIP_MAXSTRLEN];
286 const char* divesetname;
287 SCIP_DIVESET* diveset;
288
289 assert(divesetptr != NULL);
290 assert(set != NULL);
291 assert(divesetgetscore != NULL);
292 assert(heur != NULL);
293 assert(blkmem != NULL);
294
295 SCIP_ALLOC( BMSallocBlockMemory(blkmem, divesetptr) );
296 diveset = *divesetptr;
297
298 /* allocate random number generator. Note that we must make explicit use of random seed initialization because
299 * we create the random number generator directly, not through the public SCIP API
300 */
301 diveset->initialseed = initialseed;
302
303 /* simply use 0 as initial seed, the seed is reset in SCIPdivesetReset, anyway */
304 SCIP_CALL( SCIPrandomCreate(&diveset->randnumgen, blkmem, 0) );
305
306 /* for convenience, the name gets inferred from the heuristic to which the diveset is added if no name is provided */
307 divesetname = (name == NULL ? SCIPheurGetName(heur) : name);
308 SCIP_ALLOC( BMSduplicateMemoryArray(&diveset->name, divesetname, strlen(divesetname)+1) );
309 diveset->heur = NULL;
310
311 /* scoring callbacks */
312 diveset->divesetgetscore = divesetgetscore;
313 diveset->divesetavailable = divesetavailable;
314
315 SCIP_CALL( heurAddDiveset(heur, diveset) );
316 diveset->sol = NULL;
317 diveset->divetypemask = divetypemask;
318 diveset->ispublic = ispublic;
319
320 /* allocate memory for diveset statistics */
321 for( c = 0; c < 3; ++c )
322 {
323 SCIP_DIVESETSTATS** divesetstatsptr = &diveset->divesetstats[c];
324 SCIP_ALLOC( BMSallocBlockMemory(blkmem, divesetstatsptr) );
325 }
326
327 SCIP_CALL( SCIPdivesetReset(diveset, set) );
328
329 /* add collection of diving heuristic specific parameters */
330 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/minreldepth", diveset->name);
331 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
332 paramname, "minimal relative depth to start diving",
333 &diveset->minreldepth, TRUE, minreldepth, 0.0, 1.0, NULL, NULL) );
334
335 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxreldepth", diveset->name);
336 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
337 "maximal relative depth to start diving",
338 &diveset->maxreldepth, TRUE, maxreldepth, 0.0, 1.0, NULL, NULL) );
339
340 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxlpiterquot", diveset->name);
341 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
342 paramname,
343 "maximal fraction of diving LP iterations compared to node LP iterations",
344 &diveset->maxlpiterquot, FALSE, maxlpiterquot, 0.0, SCIP_REAL_MAX, NULL, NULL) );
345
346 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxlpiterofs", diveset->name);
347 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem,
348 paramname,
349 "additional number of allowed LP iterations",
350 &diveset->maxlpiterofs, FALSE, maxlpiterofs, 0, INT_MAX, NULL, NULL) );
351
352 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveubquot", diveset->name);
353 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
354 paramname,
355 "maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)",
356 &diveset->maxdiveubquot, TRUE, maxdiveubquot, 0.0, 1.0, NULL, NULL) );
357
358 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveavgquot", diveset->name);
359 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
360 paramname,
361 "maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)",
362 &diveset->maxdiveavgquot, TRUE, maxdiveavgquot, 0.0, SCIP_REAL_MAX, NULL, NULL) );
363
364 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveubquotnosol", diveset->name);
365 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
366 paramname,
367 "maximal UBQUOT when no solution was found yet (0.0: no limit)",
368 &diveset->maxdiveubquotnosol, TRUE, maxdiveubquotnosol, 0.0, 1.0, NULL, NULL) );
369
370 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdiveavgquotnosol", diveset->name);
371 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem,
372 paramname,
373 "maximal AVGQUOT when no solution was found yet (0.0: no limit)",
374 &diveset->maxdiveavgquotnosol, TRUE, maxdiveavgquotnosol, 0.0, SCIP_REAL_MAX, NULL, NULL) );
375
376 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/backtrack", diveset->name);
377 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem,
378 paramname,
379 "use one level of backtracking if infeasibility is encountered?",
380 &diveset->backtrack, FALSE, backtrack, NULL, NULL) );
381
382 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/lpresolvedomchgquot", diveset->name);
383 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname,
384 "percentage of immediate domain changes during probing to trigger LP resolve",
385 &diveset->lpresolvedomchgquot, FALSE, lpresolvedomchgquot, 0.0, SCIP_REAL_MAX, NULL, NULL) );
386
387 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/lpsolvefreq", diveset->name);
388 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem,
389 paramname,
390 "LP solve frequency for diving heuristics (0: only after enough domain changes have been found)",
391 &diveset->lpsolvefreq, FALSE, lpsolvefreq, 0, INT_MAX,
392 NULL, NULL) );
393
394 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/onlylpbranchcands", diveset->name);
395 SCIP_CALL( SCIPsetAddBoolParam(set, messagehdlr, blkmem,
396 paramname,
397 "should only LP branching candidates be considered instead of the slower but "
398 "more general constraint handler diving variable selection?",
399 &diveset->onlylpbranchcands, FALSE, onlylpbranchcands, NULL, NULL) );
400
401 return SCIP_OKAY;
402 }
403
404 /** get the heuristic to which this diving setting belongs */
405 SCIP_HEUR* SCIPdivesetGetHeur(
406 SCIP_DIVESET* diveset /**< diving settings */
407 )
408 {
409 return diveset->heur;
410 }
411
412 /** get the working solution of this dive set */
413 SCIP_SOL* SCIPdivesetGetWorkSolution(
414 SCIP_DIVESET* diveset /**< diving settings */
415 )
416 {
417 assert(diveset != NULL);
418
419 return diveset->sol;
420 }
421
422 /** set the working solution for this dive set */
423 void SCIPdivesetSetWorkSolution(
424 SCIP_DIVESET* diveset, /**< diving settings */
425 SCIP_SOL* sol /**< new working solution for this dive set, or NULL */
426 )
427 {
428 assert(diveset != NULL);
429
430 diveset->sol = sol;
431 }
432
433 /** get the name of the dive set */
434 const char* SCIPdivesetGetName(
435 SCIP_DIVESET* diveset /**< diving settings */
436 )
437 {
438 assert(diveset != NULL);
439
440 return diveset->name;
441 }
442
443 /** get the minimum relative depth of the diving settings */
444 SCIP_Real SCIPdivesetGetMinRelDepth(
445 SCIP_DIVESET* diveset /**< diving settings */
446 )
447 {
448 return diveset->minreldepth;
449 }
450
451 /** get the maximum relative depth of the diving settings */
452 SCIP_Real SCIPdivesetGetMaxRelDepth(
453 SCIP_DIVESET* diveset /**< diving settings */
454 )
455 {
456 return diveset->maxreldepth;
457 }
458
459 /** get the number of successful runs of the diving settings */
460 SCIP_Longint SCIPdivesetGetSolSuccess(
461 SCIP_DIVESET* diveset, /**< diving settings */
462 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
463
464 )
465 {
466 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
467
468 assert(divesetstats != NULL);
469
470 return 10 * divesetstats->nbestsolsfound + divesetstats->nsolsfound;
471 }
472
473 /** get the number of calls to this dive set */
474 int SCIPdivesetGetNCalls(
475 SCIP_DIVESET* diveset, /**< diving settings */
476 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
477 )
478 {
479 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
480
481 assert(divesetstats != NULL);
482
483 return divesetstats->ncalls;
484 }
485
486 /** get the number of calls successfully terminated at a feasible leaf node */
487 int SCIPdivesetGetNSolutionCalls(
488 SCIP_DIVESET* diveset, /**< diving settings */
489 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
490 )
491 {
492 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
493
494 assert(diveset != NULL);
495
496 return divesetstats->nsolcalls;
497 }
498
499 /** get the minimum depth reached by this dive set */
500 int SCIPdivesetGetMinDepth(
501 SCIP_DIVESET* diveset, /**< diving settings */
502 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
503 )
504 {
505 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
506
507 assert(divesetstats != NULL);
508
509 return divesetstats->mindepth;
510 }
511
512 /** get the maximum depth reached by this dive set */
513 int SCIPdivesetGetMaxDepth(
514 SCIP_DIVESET* diveset, /**< diving settings */
515 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
516 )
517 {
518 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
519
520 assert(divesetstats != NULL);
521
522 return divesetstats->maxdepth;
523 }
524
525 /** get the average depth this dive set reached during execution */
526 SCIP_Real SCIPdivesetGetAvgDepth(
527 SCIP_DIVESET* diveset, /**< diving settings */
528 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
529 )
530 {
531 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
532
533 assert(divesetstats != NULL);
534
535 return (divesetstats->ncalls == 0 ? 0.0 : divesetstats->totaldepth / (SCIP_Real)divesetstats->ncalls);
536 }
537
538 /** get the minimum depth at which this dive set found a solution */
539 int SCIPdivesetGetMinSolutionDepth(
540 SCIP_DIVESET* diveset, /**< diving settings */
541 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
542 )
543 {
544 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
545
546 assert(divesetstats != NULL);
547
548 return divesetstats->minsoldepth;
549 }
550
551 /** get the maximum depth at which this dive set found a solution */
552 int SCIPdivesetGetMaxSolutionDepth(
553 SCIP_DIVESET* diveset, /**< diving settings */
554 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
555 )
556 {
557 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
558
559 assert(divesetstats != NULL);
560
561 return divesetstats->maxsoldepth;
562 }
563
564 /** get the average depth at which this dive set found a solution */
565 SCIP_Real SCIPdivesetGetAvgSolutionDepth(
566 SCIP_DIVESET* diveset, /**< diving settings */
567 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
568 )
569 {
570 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
571
572 assert(divesetstats != NULL);
573
574 return (divesetstats->nsolcalls == 0 ? 0.0 : divesetstats->totalsoldepth / (SCIP_Real)divesetstats->nsolcalls);
575 }
576
577 /** get the total number of LP iterations used by this dive set */
578 SCIP_Longint SCIPdivesetGetNLPIterations(
579 SCIP_DIVESET* diveset, /**< diving settings */
580 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
581 )
582 {
583 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
584
585 assert(divesetstats != NULL);
586
587 return divesetstats->nlpiterations;
588 }
589
590 /** get the total number of probing nodes used by this dive set */
591 SCIP_Longint SCIPdivesetGetNProbingNodes(
592 SCIP_DIVESET* diveset, /**< diving settings */
593 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
594 )
595 {
596 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
597
598 assert(divesetstats != NULL);
599
600 return divesetstats->totalnnodes;
601 }
602
603 /** get the total number of backtracks performed by this dive set */
604 SCIP_Longint SCIPdivesetGetNBacktracks(
605 SCIP_DIVESET* diveset, /**< diving settings */
606 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
607 )
608 {
609 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
610
611 assert(divesetstats != NULL);
612
613 return divesetstats->totalnbacktracks;
614 }
615
616 /** get the total number of conflicts found by this dive set */
617 SCIP_Longint SCIPdivesetGetNConflicts(
618 SCIP_DIVESET* diveset, /**< diving settings */
619 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
620 )
621 {
622 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
623
624 assert(divesetstats != NULL);
625
626 return divesetstats->nconflictsfound;
627 }
628
629 /** get the total number of solutions (leaf and rounded solutions) found by the dive set */
630 SCIP_Longint SCIPdivesetGetNSols(
631 SCIP_DIVESET* diveset, /**< diving settings */
632 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
633 )
634 {
635 SCIP_DIVESETSTATS* divesetstats = divesetGetStats(diveset, divecontext);
636
637 assert(divesetstats != NULL);
638
639 return divesetstats->nsolsfound;
640 }
641
642
643 /** get the maximum LP iterations quotient of the diving settings */
644 SCIP_Real SCIPdivesetGetMaxLPIterQuot(
645 SCIP_DIVESET* diveset /**< diving settings */
646 )
647 {
648 return diveset->maxlpiterquot;
649 }
650
651 /** get the maximum LP iterations offset of the diving settings */
652 int SCIPdivesetGetMaxLPIterOffset(
653 SCIP_DIVESET* diveset /**< diving settings */
654 )
655 {
656 return diveset->maxlpiterofs;
657 }
658
659 /** get the maximum upper bound quotient parameter of the diving settings if no solution is available */
660 SCIP_Real SCIPdivesetGetUbQuotNoSol(
661 SCIP_DIVESET* diveset /**< diving settings */
662 )
663 {
664 return diveset->maxdiveubquotnosol;
665 }
666
667 /** get the average quotient parameter of the diving settings if no solution is available */
668 SCIP_Real SCIPdivesetGetAvgQuotNoSol(
669 SCIP_DIVESET* diveset /**< diving settings */
670 )
671 {
672 return diveset->maxdiveavgquotnosol;
673 }
674 /** get the maximum upper bound quotient parameter of the diving settings if an incumbent solution exists */
675 SCIP_Real SCIPdivesetGetUbQuot(
676 SCIP_DIVESET* diveset /**< diving settings */
677 )
678 {
679 return diveset->maxdiveubquot;
680 }
681
682 /** get the average upper bound quotient parameter of the diving settings if an incumbent solution exists */
683 SCIP_Real SCIPdivesetGetAvgQuot(
684 SCIP_DIVESET* diveset /**< diving settings */
685 )
686 {
687 return diveset->maxdiveavgquot;
688 }
689
690 /** should backtracking be applied? */
691 SCIP_Bool SCIPdivesetUseBacktrack(
692 SCIP_DIVESET* diveset /**< diving settings */
693 )
694 {
695 return diveset->backtrack;
696 }
697
698 /** returns the LP solve frequency for diving LPs (0: dynamically based on number of intermediate domain reductions) */
699 int SCIPdivesetGetLPSolveFreq(
700 SCIP_DIVESET* diveset /**< diving settings */
701 )
702 {
703 assert(diveset != NULL);
704
705 return diveset->lpsolvefreq;
706 }
707
708 /** returns the random number generator of this \p diveset for tie-breaking */
709 SCIP_RANDNUMGEN* SCIPdivesetGetRandnumgen(
710 SCIP_DIVESET* diveset /**< diving settings */
711 )
712 {
713 assert(diveset != NULL);
714 assert(diveset->randnumgen != NULL);
715
716 return diveset->randnumgen;
717 }
718
719 /** returns the domain reduction quotient for triggering an immediate resolve of the diving LP (0.0: always resolve)*/
720 SCIP_Real SCIPdivesetGetLPResolveDomChgQuot(
721 SCIP_DIVESET* diveset /**< diving settings */
722 )
723 {
724 assert(diveset != NULL);
725
726 return diveset->lpresolvedomchgquot;
727 }
728
729 /** should only LP branching candidates be considered instead of the slower but
730 * more general constraint handler diving variable selection?
731 */
732 SCIP_Bool SCIPdivesetUseOnlyLPBranchcands(
733 SCIP_DIVESET* diveset /**< diving settings */
734 )
735 {
736 assert(diveset != NULL);
737
738 return diveset->onlylpbranchcands;
739 }
740
741 /** returns TRUE if dive set supports diving of the specified type */
742 SCIP_Bool SCIPdivesetSupportsType(
743 SCIP_DIVESET* diveset, /**< diving settings */
744 SCIP_DIVETYPE divetype /**< bit mask that represents the supported dive types by this dive set */
745 )
746 {
747 assert(diveset != NULL);
748
749 return (divetype & diveset->divetypemask);
750 }
751
752 /** is this dive set publicly available (ie., can be used by other primal heuristics?) */
753 SCIP_Bool SCIPdivesetIsPublic(
754 SCIP_DIVESET* diveset /**< diving settings */
755 )
756 {
757 assert(diveset != NULL);
758
759 return diveset->ispublic;
760 }
761
762 /** updates LP related diveset statistics */
763 static
764 void updateDivesetstatsLP(
765 SCIP_DIVESETSTATS* divesetstats, /**< diving settings */
766 SCIP_Longint niterstoadd /**< additional number of LP iterations to be added */
767 )
768 {
769 assert(divesetstats != NULL);
770
771 divesetstats->nlpiterations += niterstoadd;
772 divesetstats->nlps++;
773 }
774
775 /** update diveset LP statistics, should be called after every LP solved by this diving heuristic */
776 void SCIPdivesetUpdateLPStats(
777 SCIP_DIVESET* diveset, /**< diving settings */
778 SCIP_STAT* stat, /**< global SCIP statistics */
779 SCIP_Longint niterstoadd, /**< additional number of LP iterations to be added */
780 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
781 )
782 {
783 assert(diveset != NULL);
784 assert(divecontext == SCIP_DIVECONTEXT_ADAPTIVE || divecontext == SCIP_DIVECONTEXT_SINGLE);
785
786 /* update statistics for total context and given context */
787 updateDivesetstatsLP(divesetGetStats(diveset, divecontext), niterstoadd);
788 updateDivesetstatsLP(divesetGetStats(diveset, SCIP_DIVECONTEXT_TOTAL), niterstoadd);
789
790 stat->ndivesetlpiterations += niterstoadd;
791 stat->ndivesetlps++;
792 }
793
794 /** frees memory of a diveset */
795 static
796 void divesetFree(
797 SCIP_DIVESET** divesetptr, /**< general diving settings */
798 BMS_BLKMEM* blkmem /**< block memory for parameter settings */
799 )
800 {
801 int c;
802 SCIP_DIVESET* diveset = *divesetptr;
803
804 assert(diveset != NULL);
805 assert(diveset->name != NULL);
806 assert(diveset->randnumgen != NULL);
807
808 SCIPrandomFree(&diveset->randnumgen, blkmem);
809
810 /* free all diveset statistics */
811 for( c = 0; c < 3; ++c )
812 {
813 SCIP_DIVESETSTATS** divesetstatsptr = &diveset->divesetstats[c];
814 BMSfreeBlockMemory(blkmem, divesetstatsptr);
815 }
816
817 BMSfreeMemoryArray(&diveset->name);
818 BMSfreeBlockMemory(blkmem, divesetptr);
819 }
820
821 /** get the candidate score and preferred rounding direction for a candidate variable */
822 SCIP_RETCODE SCIPdivesetGetScore(
823 SCIP_DIVESET* diveset, /**< general diving settings */
824 SCIP_SET* set, /**< SCIP settings */
825 SCIP_DIVETYPE divetype, /**< the type of diving that should be applied */
826 SCIP_VAR* divecand, /**< the candidate for which the branching direction is requested */
827 SCIP_Real divecandsol, /**< LP solution value of the candidate */
828 SCIP_Real divecandfrac, /**< fractionality of the candidate */
829 SCIP_Real* candscore, /**< pointer to store the candidate score */
830 SCIP_Bool* roundup /**< pointer to store whether preferred direction for diving is upwards */
831 )
832 {
833 assert(diveset->divesetgetscore != NULL);
834 assert(candscore != NULL);
835 assert(roundup != NULL);
836 assert(divecand != NULL);
837 assert(divetype & diveset->divetypemask);
838
839 SCIP_CALL( diveset->divesetgetscore(set->scip, diveset, divetype, divecand, divecandsol, divecandfrac,
840 candscore, roundup) );
841
842 return SCIP_OKAY;
843 }
844
845 /** check specific preconditions for diving, e.g., if an incumbent solution is available */
846 SCIP_RETCODE SCIPdivesetIsAvailable(
847 SCIP_DIVESET* diveset, /**< diving heuristic settings */
848 SCIP_SET* set, /**< SCIP settings */
849 SCIP_Bool* available /**< pointer to store if the diving can run at the current solving stage */
850 )
851 {
852 assert(set != NULL);
853 assert(diveset != NULL);
854 assert(available != NULL);
855
856 if( diveset->divesetavailable == NULL )
857 *available = TRUE;
858 else
859 {
860 *available = FALSE;
861 SCIP_CALL( diveset->divesetavailable(set->scip, diveset, available) );
862 }
863
864 return SCIP_OKAY;
865 }
866
867
868
869 /** copies the given primal heuristic to a new scip */
870 SCIP_RETCODE SCIPheurCopyInclude(
871 SCIP_HEUR* heur, /**< primal heuristic */
872 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
873 )
874 {
875 assert(heur != NULL);
876 assert(set != NULL);
877 assert(set->scip != NULL);
878
879 if( heur->heurcopy != NULL )
880 {
881 SCIPsetDebugMsg(set, "including heur %s in subscip %p\n", SCIPheurGetName(heur), (void*)set->scip);
882 SCIP_CALL( heur->heurcopy(set->scip, heur) );
883 }
884
885 return SCIP_OKAY;
886 }
887
888 /** internal method for creating a primal heuristic */
889 static
890 SCIP_RETCODE doHeurCreate(
891 SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */
892 SCIP_SET* set, /**< global SCIP settings */
893 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
894 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
895 const char* name, /**< name of primal heuristic */
896 const char* desc, /**< description of primal heuristic */
897 char dispchar, /**< display character of primal heuristic */
898 int priority, /**< priority of the primal heuristic */
899 int freq, /**< frequency for calling primal heuristic */
900 int freqofs, /**< frequency offset for calling primal heuristic */
901 int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */
902 SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed */
903 SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */
904 SCIP_DECL_HEURCOPY ((*heurcopy)), /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
905 SCIP_DECL_HEURFREE ((*heurfree)), /**< destructor of primal heuristic */
906 SCIP_DECL_HEURINIT ((*heurinit)), /**< initialize primal heuristic */
907 SCIP_DECL_HEUREXIT ((*heurexit)), /**< deinitialize primal heuristic */
908 SCIP_DECL_HEURINITSOL ((*heurinitsol)), /**< solving process initialization method of primal heuristic */
909 SCIP_DECL_HEUREXITSOL ((*heurexitsol)), /**< solving process deinitialization method of primal heuristic */
910 SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */
911 SCIP_HEURDATA* heurdata /**< primal heuristic data */
912 )
913 {
914 char paramname[SCIP_MAXSTRLEN];
915 char paramdesc[SCIP_MAXSTRLEN];
916
917 assert(heur != NULL);
918 assert(name != NULL);
919 assert(desc != NULL);
920 assert(freq >= -1);
921 assert(freqofs >= 0);
922 assert(heurexec != NULL);
923
924 SCIP_ALLOC( BMSallocMemory(heur) );
925 BMSclearMemory(*heur);
926
927 SCIP_ALLOC( BMSduplicateMemoryArray(&(*heur)->name, name, strlen(name)+1) );
928 SCIP_ALLOC( BMSduplicateMemoryArray(&(*heur)->desc, desc, strlen(desc)+1) );
929 (*heur)->dispchar = dispchar;
930 (*heur)->priority = priority;
931 (*heur)->freq = freq;
932 (*heur)->freqofs = freqofs;
933 (*heur)->maxdepth = maxdepth;
934 (*heur)->delaypos = -1;
935 (*heur)->timingmask = timingmask;
936 (*heur)->usessubscip = usessubscip;
937 (*heur)->heurcopy = heurcopy;
938 (*heur)->heurfree = heurfree;
939 (*heur)->heurinit = heurinit;
940 (*heur)->heurexit = heurexit;
941 (*heur)->heurinitsol = heurinitsol;
942 (*heur)->heurexitsol = heurexitsol;
943 (*heur)->heurexec = heurexec;
944 (*heur)->heurdata = heurdata;
945 SCIP_CALL( SCIPclockCreate(&(*heur)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
946 SCIP_CALL( SCIPclockCreate(&(*heur)->heurclock, SCIP_CLOCKTYPE_DEFAULT) );
947 (*heur)->ncalls = 0;
948 (*heur)->nsolsfound = 0;
949 (*heur)->nbestsolsfound = 0;
950 (*heur)->initialized = FALSE;
951 (*heur)->divesets = NULL;
952 (*heur)->ndivesets = 0;
953
954 /* add parameters */
955 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/priority", name);
956 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of heuristic <%s>", name);
957 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
958 &(*heur)->priority, TRUE, priority, INT_MIN/4, INT_MAX/4,
959 paramChgdHeurPriority, (SCIP_PARAMDATA*)(*heur)) ); /*lint !e740*/
960 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/freq", name);
961 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency for calling primal heuristic <%s> (-1: never, 0: only at depth freqofs)", name);
962 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
963 &(*heur)->freq, FALSE, freq, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
964 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/freqofs", name);
965 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency offset for calling primal heuristic <%s>", name);
966 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
967 &(*heur)->freqofs, FALSE, freqofs, 0, SCIP_MAXTREEDEPTH, NULL, NULL) );
968 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "heuristics/%s/maxdepth", name);
969 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal depth level to call primal heuristic <%s> (-1: no limit)", name);
970 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
971 &(*heur)->maxdepth, TRUE, maxdepth, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
972
973 return SCIP_OKAY;
974 }
975
976 /** creates a primal heuristic */
977 SCIP_RETCODE SCIPheurCreate(
978 SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */
979 SCIP_SET* set, /**< global SCIP settings */
980 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
981 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
982 const char* name, /**< name of primal heuristic */
983 const char* desc, /**< description of primal heuristic */
984 char dispchar, /**< display character of primal heuristic */
985 int priority, /**< priority of the primal heuristic */
986 int freq, /**< frequency for calling primal heuristic */
987 int freqofs, /**< frequency offset for calling primal heuristic */
988 int maxdepth, /**< maximal depth level to call heuristic at (-1: no limit) */
989 SCIP_HEURTIMING timingmask, /**< positions in the node solving loop where heuristic should be executed */
990 SCIP_Bool usessubscip, /**< does the heuristic use a secondary SCIP instance? */
991 SCIP_DECL_HEURCOPY ((*heurcopy)), /**< copy method of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
992 SCIP_DECL_HEURFREE ((*heurfree)), /**< destructor of primal heuristic */
993 SCIP_DECL_HEURINIT ((*heurinit)), /**< initialize primal heuristic */
994 SCIP_DECL_HEUREXIT ((*heurexit)), /**< deinitialize primal heuristic */
995 SCIP_DECL_HEURINITSOL ((*heurinitsol)), /**< solving process initialization method of primal heuristic */
996 SCIP_DECL_HEUREXITSOL ((*heurexitsol)), /**< solving process deinitialization method of primal heuristic */
997 SCIP_DECL_HEUREXEC ((*heurexec)), /**< execution method of primal heuristic */
998 SCIP_HEURDATA* heurdata /**< primal heuristic data */
999 )
1000 {
1001 assert(heur != NULL);
1002 assert(name != NULL);
1003 assert(desc != NULL);
1004 assert(freq >= -1);
1005 assert(freqofs >= 0);
1006 assert(heurexec != NULL);
1007
1008 SCIP_CALL_FINALLY( doHeurCreate(heur, set, messagehdlr, blkmem, name, desc, dispchar, priority, freq, freqofs,
1009 maxdepth, timingmask, usessubscip, heurcopy, heurfree, heurinit, heurexit, heurinitsol, heurexitsol, heurexec,
1010 heurdata), (void) SCIPheurFree(heur, set, blkmem) );
1011
1012 return SCIP_OKAY;
1013 }
1014
1015 /** calls destructor and frees memory of primal heuristic */
1016 SCIP_RETCODE SCIPheurFree(
1017 SCIP_HEUR** heur, /**< pointer to primal heuristic data structure */
1018 SCIP_SET* set, /**< global SCIP settings */
1019 BMS_BLKMEM* blkmem /**< block memory */
1020 )
1021 {
1022 int d;
1023 assert(heur != NULL);
1024 if( *heur == NULL )
1025 return SCIP_OKAY;
1026 assert(!(*heur)->initialized);
1027 assert(set != NULL);
1028 assert((*heur)->divesets != NULL || (*heur)->ndivesets == 0);
1029
1030 /* call destructor of primal heuristic */
1031 if( (*heur)->heurfree != NULL )
1032 {
1033 SCIP_CALL( (*heur)->heurfree(set->scip, *heur) );
1034 }
1035
1036 for( d = 0; d < (*heur)->ndivesets; ++d )
1037 {
1038 assert((*heur)->divesets[d] != NULL);
1039 divesetFree(&((*heur)->divesets[d]), blkmem);
1040 }
1041 BMSfreeMemoryArrayNull(&(*heur)->divesets);
1042 SCIPclockFree(&(*heur)->heurclock);
1043 SCIPclockFree(&(*heur)->setuptime);
1044 BMSfreeMemoryArrayNull(&(*heur)->name);
1045 BMSfreeMemoryArrayNull(&(*heur)->desc);
1046 BMSfreeMemory(heur);
1047
1048 return SCIP_OKAY;
1049 }
1050
1051 /** initializes primal heuristic */
1052 SCIP_RETCODE SCIPheurInit(
1053 SCIP_HEUR* heur, /**< primal heuristic */
1054 SCIP_SET* set /**< global SCIP settings */
1055 )
1056 {
1057 int d;
1058 assert(heur != NULL);
1059 assert(set != NULL);
1060
1061 if( heur->initialized )
1062 {
1063 SCIPerrorMessage("primal heuristic <%s> already initialized\n", heur->name);
1064 return SCIP_INVALIDCALL;
1065 }
1066
1067 if( set->misc_resetstat )
1068 {
1069 SCIPclockReset(heur->setuptime);
1070 SCIPclockReset(heur->heurclock);
1071
1072 heur->delaypos = -1;
1073 heur->ncalls = 0;
1074 heur->nsolsfound = 0;
1075 heur->nbestsolsfound = 0;
1076
1077 set->heurssorted = FALSE;
1078 set->heursnamesorted = FALSE;
1079 }
1080
1081 if( heur->heurinit != NULL )
1082 {
1083 /* start timing */
1084 SCIPclockStart(heur->setuptime, set);
1085
1086 SCIP_CALL( heur->heurinit(set->scip, heur) );
1087
1088 /* stop timing */
1089 SCIPclockStop(heur->setuptime, set);
1090 }
1091
1092 /* reset dive sets */
1093 for( d = 0; d < heur->ndivesets; ++d )
1094 {
1095 assert(heur->divesets[d] != NULL);
1096 SCIP_CALL( SCIPdivesetReset(heur->divesets[d], set) );
1097 }
1098
1099 heur->initialized = TRUE;
1100
1101 return SCIP_OKAY;
1102 }
1103
1104 /** calls exit method of primal heuristic */
1105 SCIP_RETCODE SCIPheurExit(
1106 SCIP_HEUR* heur, /**< primal heuristic */
1107 SCIP_SET* set /**< global SCIP settings */
1108 )
1109 {
1110 assert(heur != NULL);
1111 assert(set != NULL);
1112
1113 if( !heur->initialized )
1114 {
1115 SCIPerrorMessage("primal heuristic <%s> not initialized\n", heur->name);
1116 return SCIP_INVALIDCALL;
1117 }
1118
1119 if( heur->heurexit != NULL )
1120 {
1121 /* start timing */
1122 SCIPclockStart(heur->setuptime, set);
1123
1124 SCIP_CALL( heur->heurexit(set->scip, heur) );
1125
1126 /* stop timing */
1127 SCIPclockStop(heur->setuptime, set);
1128 }
1129 heur->initialized = FALSE;
1130
1131 return SCIP_OKAY;
1132 }
1133
1134 /** informs primal heuristic that the branch and bound process is being started */
1135 SCIP_RETCODE SCIPheurInitsol(
1136 SCIP_HEUR* heur, /**< primal heuristic */
1137 SCIP_SET* set /**< global SCIP settings */
1138 )
1139 {
1140 assert(heur != NULL);
1141 assert(set != NULL);
1142
1143 if( heur->delaypos != -1 )
1144 {
1145 heur->delaypos = -1;
1146 set->heurssorted = FALSE;
1147 }
1148
1149 /* call solving process initialization method of primal heuristic */
1150 if( heur->heurinitsol != NULL )
1151 {
1152 /* start timing */
1153 SCIPclockStart(heur->setuptime, set);
1154
1155 SCIP_CALL( heur->heurinitsol(set->scip, heur) );
1156
1157 /* stop timing */
1158 SCIPclockStop(heur->setuptime, set);
1159 }
1160
1161 return SCIP_OKAY;
1162 }
1163
1164 /** informs primal heuristic that the branch and bound process data is being freed */
1165 SCIP_RETCODE SCIPheurExitsol(
1166 SCIP_HEUR* heur, /**< primal heuristic */
1167 SCIP_SET* set /**< global SCIP settings */
1168 )
1169 {
1170 assert(heur != NULL);
1171 assert(set != NULL);
1172
1173 /* call solving process deinitialization method of primal heuristic */
1174 if( heur->heurexitsol != NULL )
1175 {
1176 /* start timing */
1177 SCIPclockStart(heur->setuptime, set);
1178
1179 SCIP_CALL( heur->heurexitsol(set->scip, heur) );
1180
1181 /* stop timing */
1182 SCIPclockStop(heur->setuptime, set);
1183 }
1184
1185 return SCIP_OKAY;
1186 }
1187
1188 /** should the heuristic be executed at the given depth, frequency, timing, ... */
1189 SCIP_Bool SCIPheurShouldBeExecuted(
1190 SCIP_HEUR* heur, /**< primal heuristic */
1191 int depth, /**< depth of current node */
1192 int lpstateforkdepth, /**< depth of the last node with solved LP */
1193 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */
1194 SCIP_Bool* delayed /**< pointer to store whether the heuristic should be delayed */
1195 )
1196 {
1197 SCIP_Bool execute;
1198
1199 if( ((heur->timingmask & SCIP_HEURTIMING_BEFOREPRESOL) && heurtiming == SCIP_HEURTIMING_BEFOREPRESOL)
1200 || ((heur->timingmask & SCIP_HEURTIMING_DURINGPRESOLLOOP) && heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP) )
1201 {
1202 /* heuristic may be executed before/during presolving. Do so, if it was not disabled by setting the frequency to -1 */
1203 execute = heur->freq >= 0;
1204 }
1205 else if( (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDONODE) == 0
1206 && (heurtiming == SCIP_HEURTIMING_AFTERLPNODE || heurtiming == SCIP_HEURTIMING_AFTERLPPLUNGE) )
1207 {
1208 /* heuristic was skipped on intermediate pseudo nodes: check, if a node matching the execution frequency lies
1209 * between the current node and the last LP node of the path
1210 */
1211 execute = (heur->freq > 0 && depth >= heur->freqofs
1212 && ((depth + heur->freq - heur->freqofs) / heur->freq
1213 != (lpstateforkdepth + heur->freq - heur->freqofs) / heur->freq));
1214 }
1215 else
1216 {
1217 /* heuristic may be executed on every node: check, if the current depth matches the execution frequency and offset */
1218 execute = (heur->freq > 0 && depth >= heur->freqofs && (depth - heur->freqofs) % heur->freq == 0);
1219 }
1220
1221 /* if frequency is zero, execute heuristic only at the depth level of the frequency offset */
1222 execute = execute || (depth == heur->freqofs && heur->freq == 0);
1223
1224 /* compare current depth against heuristic's maximal depth level */
1225 execute = execute && (heur->maxdepth == -1 || depth <= heur->maxdepth);
1226
1227 /* if the heuristic was delayed, execute it anyway */
1228 execute = execute || (heur->delaypos >= 0);
1229
1230 /* if the heuristic should be called after plunging but not during plunging, delay it if we are in plunging */
1231 if( execute
1232 && ((heurtiming == SCIP_HEURTIMING_AFTERLPNODE
1233 && (heur->timingmask & SCIP_HEURTIMING_AFTERLPNODE) == 0
1234 && (heur->timingmask & SCIP_HEURTIMING_AFTERLPPLUNGE) > 0)
1235 || (heurtiming == SCIP_HEURTIMING_AFTERPSEUDONODE
1236 && (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDONODE) == 0
1237 && (heur->timingmask & SCIP_HEURTIMING_AFTERPSEUDOPLUNGE) > 0)) )
1238 {
1239 /* the heuristic should be delayed until plunging is finished */
1240 execute = FALSE;
1241 *delayed = TRUE;
1242 }
1243
1244 /* execute heuristic only if its timing mask fits the current point in the node solving process */
1245 execute = execute && (heur->timingmask & heurtiming) > 0;
1246
1247 return execute;
1248 }
1249
1250 /** calls execution method of primal heuristic */
1251 SCIP_RETCODE SCIPheurExec(
1252 SCIP_HEUR* heur, /**< primal heuristic */
1253 SCIP_SET* set, /**< global SCIP settings */
1254 SCIP_PRIMAL* primal, /**< primal data */
1255 int depth, /**< depth of current node */
1256 int lpstateforkdepth, /**< depth of the last node with solved LP */
1257 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */
1258 SCIP_Bool nodeinfeasible, /**< was the current node already detected to be infeasible? */
1259 int* ndelayedheurs, /**< pointer to count the number of delayed heuristics */
1260 SCIP_RESULT* result /**< pointer to store the result of the callback method */
1261 )
1262 {
1263 SCIP_Bool execute;
1264 SCIP_Bool delayed;
1265
1266 assert(heur != NULL);
1267 assert(heur->heurexec != NULL);
1268 assert(heur->freq >= -1);
1269 assert(heur->freqofs >= 0);
1270 assert(heur->maxdepth >= -1);
1271 assert(set != NULL);
1272 assert(set->scip != NULL);
1273 assert(primal != NULL);
1274 assert(depth >= 0 || heurtiming == SCIP_HEURTIMING_BEFOREPRESOL || heurtiming == SCIP_HEURTIMING_DURINGPRESOLLOOP);
1275 assert(ndelayedheurs != NULL);
1276 assert(result != NULL);
1277
1278 *result = SCIP_DIDNOTRUN;
1279
1280 delayed = FALSE;
1281 execute = SCIPheurShouldBeExecuted(heur, depth, lpstateforkdepth, heurtiming, &delayed);
1282
1283 if( delayed )
1284 {
1285 assert(!execute);
1286 *result = SCIP_DELAYED;
1287 }
1288
1289 if( execute )
1290 {
1291 SCIP_Longint oldnsolsfound;
1292 SCIP_Longint oldnbestsolsfound;
1293
1294 SCIPsetDebugMsg(set, "executing primal heuristic <%s> in depth %d (delaypos: %d)\n", heur->name, depth, heur->delaypos);
1295
1296 oldnsolsfound = primal->nsolsfound;
1297 oldnbestsolsfound = primal->nbestsolsfound;
1298
1299 /* start timing */
1300 SCIPclockStart(heur->heurclock, set);
1301
1302 /* call external method */
1303 SCIP_CALL( heur->heurexec(set->scip, heur, heurtiming, nodeinfeasible, result) );
1304
1305 /* stop timing */
1306 SCIPclockStop(heur->heurclock, set);
1307
1308 /* evaluate result */
1309 if( *result != SCIP_FOUNDSOL
1310 && *result != SCIP_DIDNOTFIND
1311 && *result != SCIP_DIDNOTRUN
1312 && *result != SCIP_DELAYED
1313 && *result != SCIP_UNBOUNDED )
1314 {
1315 SCIPerrorMessage("execution method of primal heuristic <%s> returned invalid result <%d>\n",
1316 heur->name, *result);
1317 return SCIP_INVALIDRESULT;
1318 }
1319 if( *result != SCIP_DIDNOTRUN && *result != SCIP_DELAYED )
1320 heur->ncalls++;
1321 heur->nsolsfound += primal->nsolsfound - oldnsolsfound;
1322 heur->nbestsolsfound += primal->nbestsolsfound - oldnbestsolsfound;
1323
1324 /* update delay position of heuristic */
1325 if( *result != SCIP_DELAYED && heur->delaypos != -1 )
1326 {
1327 heur->delaypos = -1;
1328 set->heurssorted = FALSE;
1329 }
1330 }
1331 assert(*result == SCIP_DIDNOTRUN || *result == SCIP_DELAYED || *result == SCIP_UNBOUNDED || heur->delaypos == -1);
1332
1333 /* check if the heuristic was (still) delayed */
1334 if( *result == SCIP_DELAYED || heur->delaypos >= 0 )
1335 {
1336 SCIPsetDebugMsg(set, "delaying execution of primal heuristic <%s> in depth %d (delaypos: %d), heur was%s delayed before, had delaypos %d\n",
1337 heur->name, depth, *ndelayedheurs, heur->delaypos >= 0 ? "" : " not", heur->delaypos);
1338
1339 /* mark the heuristic delayed */
1340 if( heur->delaypos != *ndelayedheurs )
1341 {
1342 heur->delaypos = *ndelayedheurs;
1343 set->heurssorted = FALSE;
1344 }
1345 (*ndelayedheurs)++;
1346 }
1347
1348 return SCIP_OKAY;
1349 }
1350
1351 /** gets user data of primal heuristic */
1352 SCIP_HEURDATA* SCIPheurGetData(
1353 SCIP_HEUR* heur /**< primal heuristic */
1354 )
1355 {
1356 assert(heur != NULL);
1357
1358 return heur->heurdata;
1359 }
1360
1361 /** sets user data of primal heuristic; user has to free old data in advance! */
1362 void SCIPheurSetData(
1363 SCIP_HEUR* heur, /**< primal heuristic */
1364 SCIP_HEURDATA* heurdata /**< new primal heuristic user data */
1365 )
1366 {
1367 assert(heur != NULL);
1368
1369 heur->heurdata = heurdata;
1370 }
1371
1372 /* new callback setter methods */
1373
1374 /** sets copy callback of primal heuristic */
1375 void SCIPheurSetCopy(
1376 SCIP_HEUR* heur, /**< primal heuristic */
1377 SCIP_DECL_HEURCOPY ((*heurcopy)) /**< copy callback of primal heuristic or NULL if you don't want to copy your plugin into sub-SCIPs */
1378 )
1379 {
1380 assert(heur != NULL);
1381
1382 heur->heurcopy = heurcopy;
1383 }
1384
1385 /** sets destructor callback of primal heuristic */
1386 void SCIPheurSetFree(
1387 SCIP_HEUR* heur, /**< primal heuristic */
1388 SCIP_DECL_HEURFREE ((*heurfree)) /**< destructor of primal heuristic */
1389 )
1390 {
1391 assert(heur != NULL);
1392
1393 heur->heurfree = heurfree;
1394 }
1395
1396 /** sets initialization callback of primal heuristic */
1397 void SCIPheurSetInit(
1398 SCIP_HEUR* heur, /**< primal heuristic */
1399 SCIP_DECL_HEURINIT ((*heurinit)) /**< initialize primal heuristic */
1400 )
1401 {
1402 assert(heur != NULL);
1403
1404 heur->heurinit = heurinit;
1405 }
1406
1407 /** sets deinitialization callback of primal heuristic */
1408 void SCIPheurSetExit(
1409 SCIP_HEUR* heur, /**< primal heuristic */
1410 SCIP_DECL_HEUREXIT ((*heurexit)) /**< deinitialize primal heuristic */
1411 )
1412 {
1413 assert(heur != NULL);
1414
1415 heur->heurexit = heurexit;
1416 }
1417
1418 /** sets solving process initialization callback of primal heuristic */
1419 void SCIPheurSetInitsol(
1420 SCIP_HEUR* heur, /**< primal heuristic */
1421 SCIP_DECL_HEURINITSOL ((*heurinitsol)) /**< solving process initialization callback of primal heuristic */
1422 )
1423 {
1424 assert(heur != NULL);
1425
1426 heur->heurinitsol = heurinitsol;
1427 }
1428
1429 /** sets solving process deinitialization callback of primal heuristic */
1430 void SCIPheurSetExitsol(
1431 SCIP_HEUR* heur, /**< primal heuristic */
1432 SCIP_DECL_HEUREXITSOL ((*heurexitsol)) /**< solving process deinitialization callback of primal heuristic */
1433 )
1434 {
1435 assert(heur != NULL);
1436
1437 heur->heurexitsol = heurexitsol;
1438 }
1439
1440 /** gets name of primal heuristic */
1441 const char* SCIPheurGetName(
1442 SCIP_HEUR* heur /**< primal heuristic */
1443 )
1444 {
1445 assert(heur != NULL);
1446
1447 return heur->name;
1448 }
1449
1450 /** gets description of primal heuristic */
1451 const char* SCIPheurGetDesc(
1452 SCIP_HEUR* heur /**< primal heuristic */
1453 )
1454 {
1455 assert(heur != NULL);
1456
1457 return heur->desc;
1458 }
1459
1460 /** gets display character of primal heuristic */
1461 char SCIPheurGetDispchar(
1462 SCIP_HEUR* heur /**< primal heuristic */
1463 )
1464 {
1465 assert(heur != NULL);
1466
1467 return heur->dispchar;
1468 }
1469
1470 /** returns the timing mask of the heuristic */
1471 SCIP_HEURTIMING SCIPheurGetTimingmask(
1472 SCIP_HEUR* heur /**< primal heuristic */
1473 )
1474 {
1475 assert(heur != NULL);
1476
1477 return heur->timingmask;
1478 }
1479
1480 /** sets new timing mask for heuristic */
1481 void SCIPheurSetTimingmask(
1482 SCIP_HEUR* heur, /**< primal heuristic */
1483 SCIP_HEURTIMING timingmask /**< new timing mask of heuristic */
1484 )
1485 {
1486 assert(heur != NULL);
1487
1488 heur->timingmask = timingmask;
1489 }
1490
1491 /** does the heuristic use a secondary SCIP instance? */
1492 SCIP_Bool SCIPheurUsesSubscip(
1493 SCIP_HEUR* heur /**< primal heuristic */
1494 )
1495 {
1496 assert(heur != NULL);
1497
1498 return heur->usessubscip;
1499 }
1500
1501 /** gets priority of primal heuristic */
1502 int SCIPheurGetPriority(
1503 SCIP_HEUR* heur /**< primal heuristic */
1504 )
1505 {
1506 assert(heur != NULL);
1507
1508 return heur->priority;
1509 }
1510
1511 /** sets priority of primal heuristic */
1512 void SCIPheurSetPriority(
1513 SCIP_HEUR* heur, /**< primal heuristic */
1514 SCIP_SET* set, /**< global SCIP settings */
1515 int priority /**< new priority of the primal heuristic */
1516 )
1517 {
1518 assert(heur != NULL);
1519 assert(set != NULL);
1520
1521 heur->priority = priority;
1522 set->heurssorted = FALSE;
1523 }
1524
1525 /** gets frequency of primal heuristic */
1526 int SCIPheurGetFreq(
1527 SCIP_HEUR* heur /**< primal heuristic */
1528 )
1529 {
1530 assert(heur != NULL);
1531
1532 return heur->freq;
1533 }
1534
1535 /** sets frequency of primal heuristic */
1536 void SCIPheurSetFreq(
1537 SCIP_HEUR* heur, /**< primal heuristic */
1538 int freq /**< new frequency of heuristic */
1539 )
1540 {
1541 assert(heur != NULL);
1542
1543 heur->freq = freq;
1544 }
1545
1546 /** gets frequency offset of primal heuristic */
1547 int SCIPheurGetFreqofs(
1548 SCIP_HEUR* heur /**< primal heuristic */
1549 )
1550 {
1551 assert(heur != NULL);
1552
1553 return heur->freqofs;
1554 }
1555
1556 /** gets maximal depth level for calling primal heuristic (returns -1, if no depth limit exists) */
1557 int SCIPheurGetMaxdepth(
1558 SCIP_HEUR* heur /**< primal heuristic */
1559 )
1560 {
1561 assert(heur != NULL);
1562
1563 return heur->maxdepth;
1564 }
1565
1566 /** gets the number of times, the heuristic was called and tried to find a solution */
1567 SCIP_Longint SCIPheurGetNCalls(
1568 SCIP_HEUR* heur /**< primal heuristic */
1569 )
1570 {
1571 assert(heur != NULL);
1572
1573 return heur->ncalls;
1574 }
1575
1576 /** gets the number of primal feasible solutions found by this heuristic */
1577 SCIP_Longint SCIPheurGetNSolsFound(
1578 SCIP_HEUR* heur /**< primal heuristic */
1579 )
1580 {
1581 assert(heur != NULL);
1582
1583 return heur->nsolsfound;
1584 }
1585
1586 /** gets the number of new best primal feasible solutions found by this heuristic */
1587 SCIP_Longint SCIPheurGetNBestSolsFound(
1588 SCIP_HEUR* heur /**< primal heuristic */
1589 )
1590 {
1591 assert(heur != NULL);
1592
1593 return heur->nbestsolsfound;
1594 }
1595
1596 /** is primal heuristic initialized? */
1597 SCIP_Bool SCIPheurIsInitialized(
1598 SCIP_HEUR* heur /**< primal heuristic */
1599 )
1600 {
1601 assert(heur != NULL);
1602
1603 return heur->initialized;
1604 }
1605
1606 /** enables or disables all clocks of \p heur, depending on the value of the flag */
1607 void SCIPheurEnableOrDisableClocks(
1608 SCIP_HEUR* heur, /**< the heuristic for which all clocks should be enabled or disabled */
1609 SCIP_Bool enable /**< should the clocks of the heuristic be enabled? */
1610 )
1611 {
1612 assert(heur != NULL);
1613
1614 SCIPclockEnableOrDisable(heur->setuptime, enable);
1615 SCIPclockEnableOrDisable(heur->heurclock, enable);
1616 }
1617
1618 /** gets time in seconds used in this heuristic for setting up for next stages */
1619 SCIP_Real SCIPheurGetSetupTime(
1620 SCIP_HEUR* heur /**< primal heuristic */
1621 )
1622 {
1623 assert(heur != NULL);
1624
1625 return SCIPclockGetTime(heur->setuptime);
1626 }
1627
1628 /** gets time in seconds used in this heuristic */
1629 SCIP_Real SCIPheurGetTime(
1630 SCIP_HEUR* heur /**< primal heuristic */
1631 )
1632 {
1633 assert(heur != NULL);
1634
1635 return SCIPclockGetTime(heur->heurclock);
1636 }
1637
1638 /** returns array of divesets of this primal heuristic, or NULL if it has no divesets */
1639 SCIP_DIVESET** SCIPheurGetDivesets(
1640 SCIP_HEUR* heur /**< primal heuristic */
1641 )
1642 {
1643 assert(heur != NULL);
1644
1645 return heur->divesets;
1646 }
1647
1648 /** returns the number of divesets of this primal heuristic */
1649 int SCIPheurGetNDivesets(
1650 SCIP_HEUR* heur /**< primal heuristic */
1651 )
1652 {
1653 assert(heur != NULL);
1654
1655 return heur->ndivesets;
1656 }
1657
1658 /** Perform breadth-first (BFS) search on the variable constraint graph.
1659 *
1660 * The result of the algorithm is that the \p distances array contains the correct distances for
1661 * every variable from the start variables. The distance of a variable can then be accessed through its
1662 * problem index (calling SCIPvarGetProbindex()).
1663 * Hence, The method assumes that the length of \p distances is at least
1664 * SCIPgetNVars().
1665 * Variables that are not connected through constraints to the start variables have a distance of -1.
1666 *
1667 * Limits can be provided to further restrict the breadth-first search. If a distance limit is given,
1668 * the search will be performed until the first variable at this distance is popped from the queue, i.e.,
1669 * all variables with a distance < maxdistance have been labeled by the search.
1670 * If a variable limit is given, the search stops after it completes the distance level at which
1671 * the limit was reached. Hence, more variables may be actually labeled.
1672 * The start variables are accounted for those variable limits.
1673 *
1674 * If no variable variable constraint graph is provided, the method will create one and free it at the end
1675 * This is useful for a single use of the variable constraint graph. For several consecutive uses,
1676 * it is advised to create a variable constraint graph via SCIPvariableGraphCreate().
1677 */
1678 SCIP_RETCODE SCIPvariablegraphBreadthFirst(
1679 SCIP* scip, /**< SCIP data structure */
1680 SCIP_VGRAPH* vargraph, /**< pointer to the variable graph, or NULL to let the function create a local graph */
1681 SCIP_VAR** startvars, /**< array of start variables to calculate distance from */
1682 int nstartvars, /**< number of starting variables, at least 1 */
1683 int* distances, /**< array to keep distance in vargraph from start variables for every variable */
1684 int maxdistance, /**< maximum distance >= 0 from start variable (INT_MAX for complete BFS) */
1685 int maxvars, /**< maximum number of variables to compute distance for */
1686 int maxbinintvars /**< maximum number of binary or integer variables to compute distance for */
1687 )
1688 {
1689 SCIP_VAR** vars;
1690
1691 int* queue;
1692 int nvars;
1693 int i;
1694 int currlvlidx;
1695 int nextlvlidx;
1696 int increment = 1;
1697 int currentdistance;
1698 int nbinintvarshit;
1699 int nvarshit;
1700 int nbinvars;
1701 int nintvars;
1702 int nbinintvars;
1703 SCIP_VAR** varbuffer;
1704 SCIP_Bool localvargraph;
1705
1706 assert(scip != NULL);
1707 assert(startvars != NULL);
1708 assert(nstartvars >= 1);
1709 assert(distances != NULL);
1710 assert(maxdistance >= 0);
1711
1712 /* get variable data */
|
(1) Event cond_false: |
Condition "(_restat_ = SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL)) != SCIP_OKAY", taking false branch. |
|
(2) Event if_end: |
End of if statement. |
1713 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
1714 nbinintvars = nbinvars + nintvars;
1715
|
(3) Event cond_false: |
Condition "(queue = BMSallocBufferMemoryArray_call(SCIPbuffer(scip), (size_t)(ptrdiff_t)nvars, 4UL /* sizeof (*queue) */, "/sapmnt/home1/d029903/my_work/SCIPSoPlex_coverity/scipoptsuite-8.0.1/scip/src/scip/heur.c", 1716)) == NULL", taking false branch. |
|
(4) Event cond_false: |
Condition "(_restat_ = (((queue = BMSallocBufferMemoryArray_call(SCIPbuffer(scip), (size_t)(ptrdiff_t)nvars, 4UL /* sizeof (*queue) */, "/sapmnt/home1/d029903/my_work/SCIPSoPlex_coverity/scipoptsuite-8.0.1/scip/src/scip/heur.c", 1716)) == NULL) ? SCIP_NOMEMORY : SCIP_OKAY)) != SCIP_OKAY", taking false branch. |
|
(5) Event if_end: |
End of if statement. |
1716 SCIP_CALL( SCIPallocBufferArray(scip, &queue, nvars) );
|
(6) Event cond_false: |
Condition "(varbuffer = BMSallocClearBufferMemoryArray_call(SCIPbuffer(scip), (size_t)(ptrdiff_t)nvars, 8UL /* sizeof (*varbuffer) */, "/sapmnt/home1/d029903/my_work/SCIPSoPlex_coverity/scipoptsuite-8.0.1/scip/src/scip/heur.c", 1717)) == NULL", taking false branch. |
|
(7) Event cond_false: |
Condition "(_restat_ = (((varbuffer = BMSallocClearBufferMemoryArray_call(SCIPbuffer(scip), (size_t)(ptrdiff_t)nvars, 8UL /* sizeof (*varbuffer) */, "/sapmnt/home1/d029903/my_work/SCIPSoPlex_coverity/scipoptsuite-8.0.1/scip/src/scip/heur.c", 1717)) == NULL) ? SCIP_NOMEMORY : SCIP_OKAY)) != SCIP_OKAY", taking false branch. |
|
(8) Event if_end: |
End of if statement. |
1717 SCIP_CALL( SCIPallocClearBufferArray(scip, &varbuffer, nvars) );
1718
1719 /* create a variable graph locally for this method, if none is provided */
|
(9) Event cond_true: |
Condition "vargraph == NULL", taking true branch. |
|
(10) Event var_compare_op: |
Comparing "vargraph" to null implies that "vargraph" might be null. |
| Also see events: |
[no_write_call][var_deref_op] |
1720 if( vargraph == NULL )
1721 {
|
(11) Event no_write_call: |
Although "SCIPvariableGraphCreate" does overwrite "vargraph" on some paths, it also contains at least one feasible path which does not overwrite it. |
|
(12) Event cond_false: |
Condition "(_restat_ = SCIPvariableGraphCreate(scip, &vargraph, 0, 1., NULL)) != SCIP_OKAY", taking false branch. |
|
(13) Event if_end: |
End of if statement. |
| Also see events: |
[var_compare_op][var_deref_op] |
1722 SCIP_CALL( SCIPvariableGraphCreate(scip, &vargraph, FALSE, 1.0, NULL) );
1723 localvargraph = TRUE;
|
(14) Event if_fallthrough: |
Falling through to end of if statement. |
1724 }
1725 else
|
(15) Event if_end: |
End of if statement. |
1726 localvargraph = FALSE;
1727
1728 SCIPhashtableRemoveAll(vargraph->visitedconss);
1729
1730 /* initialize distances to -1 */
1731 for( i = 0; i < nvars; ++i )
1732 {
1733 queue[i] = -1;
1734 distances[i] = -1;
1735 }
1736
1737 nvarshit = 0;
1738 nbinintvarshit = 0;
1739 /* initialize distances for starting variables and add them to the queue */
1740 for( i = 0; i < nstartvars; ++i )
1741 {
1742 int probindex = SCIPvarGetProbindex(startvars[i]);
1743 assert(probindex >= 0);
1744 /* start variables have a distance of 0 */
1745 distances[probindex] = 0;
1746 queue[i] = probindex;
1747 nvarshit++;
1748
1749 if( probindex < nbinintvars )
1750 nbinintvarshit++;
1751 }
1752 currlvlidx = 0;
1753 nextlvlidx = nvars - 1;
1754
1755 /* loop over the queue and pop the next variable, starting with start variables */
1756 do
1757 {
1758 SCIP_VAR* currvar;
1759 int c;
1760 int varpos;
1761
1762 currvar = vars[queue[currlvlidx]];
1763 varpos = SCIPvarGetProbindex(currvar);
1764 currentdistance = distances[varpos];
1765 assert(currentdistance >= 0);
1766
1767 /* distances must only be computed up to maxdistance */
1768 assert(currentdistance <= maxdistance);
1769
1770 /* check for termination because maximum distance has been reached */
1771 if( currentdistance == maxdistance )
1772 break;
1773
1774 assert(varpos >= 0);
1775
1776 /* loop over variable constraints and enqueue variables that were not visited yet */
1777 for( c = 0; c < vargraph->nvarconss[varpos]; ++c )
1778 {
1779 int nconsvars;
1780 int v;
1781 SCIP_Bool success;
1782 SCIP_CONS* cons = vargraph->varconss[varpos][c];
1783
1784 /* check first if this constraint has already been visited */
1785 if( SCIPhashtableExists(vargraph->visitedconss, (void *)cons) )
1786 continue;
1787
1788 /* request number of constraint variables */
1789 SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) );
1790
1791 if( !success )
1792 continue;
1793
1794 /* collect constraint variables in buffer */
1795 SCIP_CALL( SCIPgetConsVars(scip, cons, varbuffer, nvars, &success) );
1796
1797 if( !success )
1798 continue;
1799
1800 /* collect previously unvisited variables of the constraint and enqueue them for breadth-first search */
1801 for( v = 0; v < nconsvars; ++v )
1802 {
1803 SCIP_VAR* nextvar = varbuffer[v];
1804 int nextvarpos;
1805 assert(nextvar != NULL);
1806 if( !SCIPvarIsActive(nextvar) )
1807 continue;
1808
1809 nextvarpos = SCIPvarGetProbindex(nextvar);
1810 assert(nextvarpos >= 0);
1811
1812 /* insert variables that were not considered yet into the next level queue */
1813 if( distances[nextvarpos] == -1 )
1814 {
1815 distances[nextvarpos] = currentdistance + 1;
1816 queue[nextlvlidx] = nextvarpos;
1817 nextlvlidx -= increment;
1818
1819 nvarshit++;
1820 if( nextvarpos < nbinintvars )
1821 ++nbinintvarshit;
1822 }
1823 } /* end constraint variables loop */
1824
1825 /* mark the constraint as visited */
1826 SCIP_CALL( SCIPhashtableInsert(vargraph->visitedconss, (void *)cons) );
1827 } /* end constraint loop */
1828
1829 queue[currlvlidx] = -1;
1830 currlvlidx += increment;
1831
1832 /* check if we need to swap current and next level index and reverse the increment */
1833 if( currlvlidx == nvars || currlvlidx == 0 || queue[currlvlidx] == -1 || currlvlidx == nextlvlidx )
1834 {
1835 /* break early if the distance has been determined for enough variables */
1836 if( nvarshit >= maxvars || nbinintvarshit >= maxbinintvars )
1837 break;
1838
1839 /* increment knows whether we are currently looping upwards (all variables with odd distance) or downwards the
1840 * queue
1841 */
1842 if( increment == +1 )
1843 {
1844 currlvlidx = nvars - 1;
1845 nextlvlidx = 0;
1846 increment = -1;
1847 }
1848 else
1849 {
1850 currlvlidx = 0;
1851 nextlvlidx = nvars - 1;
1852 increment = +1;
1853 }
1854 }
1855 }
1856 while( queue[currlvlidx] != -1 && distances[queue[currlvlidx]] >= currentdistance );
1857
1858 SCIPfreeBufferArray(scip, &varbuffer);
1859 SCIPfreeBufferArray(scip, &queue);
1860
1861 /* free also the variable graph, if it wasn't provided by the caller */
1862 if( localvargraph )
1863 {
1864 SCIPvariableGraphFree(scip, &vargraph);
1865 }
1866
1867 return SCIP_OKAY;
1868 }
1869
1870 /* fills variable graph data structure
1871 *
1872 * loops over global problem constraints and creates a mapping from the variables to their respective constraints
1873 */
1874 static
1875 SCIP_RETCODE fillVariableGraph(
1876 SCIP* scip, /**< SCIP data structure */
1877 SCIP_VGRAPH* vargraph, /**< variable graph data structure for breadth-first-search neighborhoods */
1878 SCIP_Bool relaxdenseconss, /**< should dense constraints (at least as dense as \p density) be
1879 * ignored by connectivity graph? */
1880 SCIP_Real relaxdensity, /**< density (with respect to number of variables) to relax constraint from graph */
1881 int* nrelaxedconstraints /**< pointer to store the number of constraints that were relaxed, or NULL if not needed */
1882 )
1883 {
1884 SCIP_CONS** conss;
1885 int nconss;
1886 int nvars;
1887 int c;
1888 int relaxlimit;
1889 SCIP_VAR** varbuffer;
1890
1891 assert(scip != NULL);
1892 assert(vargraph != NULL);
1893
1894 conss = SCIPgetConss(scip);
1895 nconss = SCIPgetNConss(scip);
1896
1897 nvars = SCIPgetNVars(scip);
1898 SCIP_CALL( SCIPallocBufferArray(scip, &varbuffer, nvars) );
1899
1900 if( nrelaxedconstraints != NULL )
1901 *nrelaxedconstraints = 0;
1902
1903 relaxlimit = (int)(relaxdensity * nvars);
1904
1905 for( c = 0; c < nconss; ++c )
1906 {
1907 int nconsvars;
1908 int v;
1909 SCIP_Bool success;
1910 SCIP_CONS* cons = conss[c];
1911
1912 /* we only consider constraints that are checkable */
1913 if( !SCIPconsIsChecked(cons) )
1914 continue;
1915
1916 /* request number of variables */
1917 SCIP_CALL( SCIPgetConsNVars(scip, cons, &nconsvars, &success) );
1918
1919 if( !success )
1920 continue;
1921
1922 /* relax constraints with density above the allowed number of free variables */
1923 if( relaxdenseconss && nconsvars >= relaxlimit )
1924 {
1925 if( nrelaxedconstraints != NULL )
1926 ++(*nrelaxedconstraints);
1927
1928 continue;
1929 }
1930
1931 /* collect constraint variables in buffer */
1932 SCIP_CALL( SCIPgetConsVars(scip, cons, varbuffer, nvars, &success) );
1933
1934 if( !success )
1935 continue;
1936
1937 /* loop over constraint variables and add this constraint to them if they are active */
1938 for( v = 0; v < nconsvars; ++v )
1939 {
1940 int varpos = SCIPvarGetProbindex(varbuffer[v]);
1941
1942 /* skip inactive variables */
1943 if( varpos == -1 )
1944 continue;
1945
1946 /* ensure array size */
1947 if( vargraph->varconssize[varpos] == vargraph->nvarconss[varpos] )
1948 {
1949 int newmem = SCIPcalcMemGrowSize(scip, vargraph->nvarconss[varpos] + 1);
1950
1951 assert(newmem > vargraph->varconssize[varpos]);
1952
1953 if( vargraph->varconss[varpos] == NULL )
1954 {
1955 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vargraph->varconss[varpos], newmem) );
1956 }
1957 else
1958 {
1959 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &vargraph->varconss[varpos], vargraph->varconssize[varpos], newmem) ); /*lint !e866*/
1960 }
1961 vargraph->varconssize[varpos] = newmem;
1962 }
1963
1964 assert(vargraph->nvarconss[varpos] < vargraph->varconssize[varpos]);
1965
1966 /* add constraint to constraint array for this variable */
1967 vargraph->varconss[varpos][vargraph->nvarconss[varpos]] = cons;
1968 vargraph->nvarconss[varpos] += 1;
1969 }
1970 }
1971
1972 /* free the buffer */
1973 SCIPfreeBufferArray(scip, &varbuffer);
1974
1975 return SCIP_OKAY;
1976 }
1977
1978 /** initialization method of variable graph data structure */
1979 SCIP_RETCODE SCIPvariableGraphCreate(
1980 SCIP* scip, /**< SCIP data structure */
1981 SCIP_VGRAPH** vargraph, /**< pointer to the variable graph */
1982 SCIP_Bool relaxdenseconss, /**< should dense constraints (at least as dense as \p density) be
1983 * ignored by connectivity graph? */
1984 SCIP_Real relaxdensity, /**< density (with respect to number of variables) to relax constraint from graph */
1985 int* nrelaxedconstraints /**< pointer to store the number of constraints that were relaxed, or NULL if not needed */
1986 )
1987 {
1988 int nvars;
1989 int nconss;
1990
1991 assert(scip != NULL);
1992 assert(vargraph != NULL);
1993
1994 nvars = SCIPgetNVars(scip);
1995 nconss = SCIPgetNConss(scip);
1996
1997 if( nvars == 0 )
1998 return SCIP_OKAY;
1999
2000 SCIP_CALL( SCIPallocBlockMemory(scip, vargraph) );
2001
2002 SCIP_CALL( SCIPhashtableCreate(&(*vargraph)->visitedconss, SCIPblkmem(scip), 2 * nconss, SCIPhashGetKeyStandard,
2003 SCIPhashKeyEqPtr, SCIPhashKeyValPtr, NULL) );
2004
2005 /* allocate and clear memory */
2006 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->varconss, nvars) );
2007 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->nvarconss, nvars) );
2008 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*vargraph)->varconssize, nvars) );
2009
2010 /* fill the variable graph with variable-constraint mapping for breadth-first search*/
2011 SCIP_CALL( fillVariableGraph(scip, *vargraph, relaxdenseconss, relaxdensity, nrelaxedconstraints) );
2012
2013 return SCIP_OKAY;
2014 }
2015
2016 /** deinitialization method of variable graph data structure */
2017 void SCIPvariableGraphFree(
2018 SCIP* scip, /**< SCIP data structure */
2019 SCIP_VGRAPH** vargraph /**< pointer to the variable graph */
2020 )
2021 {
2022 int nvars;
2023 int v;
2024 assert(scip != NULL);
2025 assert(vargraph != NULL);
2026
2027 nvars = SCIPgetNVars(scip);
2028
2029 for( v = nvars - 1; v >= 0; --v )
2030 {
2031 SCIPfreeBlockMemoryArrayNull(scip, &(*vargraph)->varconss[v], (*vargraph)->varconssize[v]); /*lint !e866*/
2032 }
2033
2034 /* allocate and clear memory */
2035 SCIPfreeBlockMemoryArray(scip, &(*vargraph)->varconssize, nvars);
2036 SCIPfreeBlockMemoryArray(scip, &(*vargraph)->nvarconss, nvars);
2037 SCIPfreeBlockMemoryArray(scip, &(*vargraph)->varconss, nvars);
2038
2039 SCIPhashtableFree(&(*vargraph)->visitedconss);
2040
2041 SCIPfreeBlockMemory(scip, vargraph);
2042 }
2043