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