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