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