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