Scippy

SCIP

Solving Constraint Integer Programs

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