Scippy

SCIP

Solving Constraint Integer Programs

heur_conflictdiving.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_conflictdiving.c
17  * @ingroup DEFPLUGINS_HEUR
18  * @brief LP diving heuristic that chooses fixings w.r.t. conflict locks
19  * @author Jakob Witzig
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
25 #include "scip/heuristics.h"
26 #include "scip/pub_heur.h"
27 #include "scip/pub_message.h"
28 #include "scip/pub_misc.h"
29 #include "scip/pub_var.h"
30 #include "scip/scip_heur.h"
31 #include "scip/scip_mem.h"
32 #include "scip/scip_numerics.h"
33 #include "scip/scip_param.h"
34 #include "scip/scip_sol.h"
35 #include "scip/scip_solvingstats.h"
36 #include <string.h>
37 
38 #define HEUR_NAME "conflictdiving"
39 #define HEUR_DESC "LP diving heuristic that chooses fixings w.r.t. conflict locks"
40 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING
41 #define HEUR_PRIORITY -1000100
42 #define HEUR_FREQ 10
43 #define HEUR_FREQOFS 0
44 #define HEUR_MAXDEPTH -1
45 #define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE
46 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
47 #define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY | SCIP_DIVETYPE_SOS1VARIABLE /**< bit mask that represents all supported dive types */
48 #define DIVESET_ISPUBLIC FALSE /**< is this dive set publicly available (ie., can be used by other primal heuristics?) */
49 #define DEFAULT_RANDSEED 151 /**< default random seed */
50 
51 /*
52  * Default parameter settings
53  */
54 
55 #define DEFAULT_MINRELDEPTH 0.0 /**< minimal relative depth to start diving */
56 #define DEFAULT_MAXRELDEPTH 1.0 /**< maximal relative depth to start diving */
57 #define DEFAULT_MAXLPITERQUOT 0.15 /**< maximal fraction of diving LP iterations compared to node LP iterations */
58 #define DEFAULT_MAXLPITEROFS 1000 /**< additional number of allowed LP iterations */
59 #define DEFAULT_MAXDIVEUBQUOT 0.8 /**< maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound)
60  * where diving is performed (0.0: no limit) */
61 #define DEFAULT_MAXDIVEAVGQUOT 0.0 /**< maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound)
62  * where diving is performed (0.0: no limit) */
63 #define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 /**< maximal UBQUOT when no solution was found yet (0.0: no limit) */
64 #define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 /**< maximal AVGQUOT when no solution was found yet (0.0: no limit) */
65 #define DEFAULT_BACKTRACK TRUE /**< use one level of backtracking if infeasibility is encountered? */
66 #define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15/**< percentage of immediate domain changes during probing to trigger LP resolve */
67 #define DEFAULT_LPSOLVEFREQ 0 /**< LP solve frequency for diving heuristics */
68 #define DEFAULT_ONLYLPBRANCHCANDS FALSE /**< should only LP branching candidates be considered instead of the slower but
69  * more general constraint handler diving variable selection? */
70 #define DEFAULT_LOCKWEIGHT 0.75 /**< weight used in a convex combination of conflict and variable locks */
71 #define DEFAULT_LIKECOEF FALSE /**< perform rounding like coefficient diving */
72 #define DEFAULT_MAXVIOL TRUE /**< prefer rounding direction with most violation */
73 #define DEFAULT_MINCONFLICTLOCKS 5 /**< threshold for penalizing the score */
74 
75 /* locally defined heuristic data */
76 struct SCIP_HeurData
77 {
78  SCIP_SOL* sol; /**< working solution */
79  SCIP_Real lockweight; /**< weight factor to combine conflict and variable locks */
80  SCIP_Bool likecoefdiving; /**< use the same rounding strategy like coefficent diving */
81  SCIP_Bool maxviol; /**< rounding into potentially infeasible direction */
82  int minconflictlocks; /**< threshold for penalizing the score */
83 };
84 
85 /*
86  * Callback methods
87  */
88 
89 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
90 static
91 SCIP_DECL_HEURCOPY(heurCopyConflictdiving)
92 { /*lint --e{715}*/
93  assert(scip != NULL);
94  assert(heur != NULL);
95  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
96 
97  /* call inclusion method of constraint handler */
99 
100  return SCIP_OKAY;
101 }
102 
103 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
104 static
105 SCIP_DECL_HEURFREE(heurFreeConflictdiving) /*lint --e{715}*/
106 { /*lint --e{715}*/
107  SCIP_HEURDATA* heurdata;
109  assert(heur != NULL);
110  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
111  assert(scip != NULL);
112 
113  /* free heuristic data */
114  heurdata = SCIPheurGetData(heur);
115  assert(heurdata != NULL);
116 
117  SCIPfreeBlockMemory(scip, &heurdata);
118  SCIPheurSetData(heur, NULL);
119 
120  return SCIP_OKAY;
121 }
122 
123 
124 /** initialization method of primal heuristic (called after problem was transformed) */
125 static
126 SCIP_DECL_HEURINIT(heurInitConflictdiving) /*lint --e{715}*/
127 { /*lint --e{715}*/
128  SCIP_HEURDATA* heurdata;
130  assert(heur != NULL);
131  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
132 
133  /* get heuristic data */
134  heurdata = SCIPheurGetData(heur);
135  assert(heurdata != NULL);
136 
137  /* create working solution */
138  SCIP_CALL( SCIPcreateSol(scip, &heurdata->sol, heur) );
139 
140  return SCIP_OKAY;
141 }
142 
143 
144 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
145 static
146 SCIP_DECL_HEUREXIT(heurExitConflictdiving) /*lint --e{715}*/
147 { /*lint --e{715}*/
148  SCIP_HEURDATA* heurdata;
150  assert(heur != NULL);
151  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
152 
153  /* get heuristic data */
154  heurdata = SCIPheurGetData(heur);
155  assert(heurdata != NULL);
156 
157  /* free working solution */
158  SCIP_CALL( SCIPfreeSol(scip, &heurdata->sol) );
159 
160  return SCIP_OKAY;
161 }
162 
163 /** execution method of primal heuristic */
164 static
165 SCIP_DECL_HEUREXEC(heurExecConflictdiving) /*lint --e{715}*/
166 { /*lint --e{715}*/
167  SCIP_HEURDATA* heurdata;
168  SCIP_DIVESET* diveset;
169 
170  heurdata = SCIPheurGetData(heur);
171  assert(heurdata != NULL);
172 
173  assert(SCIPheurGetNDivesets(heur) > 0);
174  assert(SCIPheurGetDivesets(heur) != NULL);
175  diveset = SCIPheurGetDivesets(heur)[0];
176  assert(diveset != NULL);
177 
178  *result = SCIP_DELAYED;
179 
180  /* don't run if no conflict constraints where found */
181  if( SCIPgetNConflictConssFound(scip) == 0 )
182  return SCIP_OKAY;
183 
184  SCIP_CALL( SCIPperformGenericDivingAlgorithm(scip, diveset, heurdata->sol, heur, result, nodeinfeasible, -1L, SCIP_DIVECONTEXT_SINGLE) );
185 
186  return SCIP_OKAY;
187 }
188 
189 #define MIN_RAND 1e-06
190 #define MAX_RAND 1e-05
191 
192 /** calculate score variant 1: use rounding strategy like coefficent diving */
193 static
195  SCIP* scip, /**< SCIP data structure */
196  SCIP_HEURDATA* heurdata, /**< heuristic data */
197  SCIP_RANDNUMGEN* rng, /**< random number generator of the diveset */
198  SCIP_DIVETYPE divetype, /**< divetype of the heuristic */
199  SCIP_VAR* cand, /**< diving candidate */
200  SCIP_Real candsol, /**< diving candidate solution */
201  SCIP_Real candsfrac, /**< fractionality of the candidate solution */
202  SCIP_Real* score, /**< pointer to store the score */
203  SCIP_Bool* roundup /**< pointer to store whether the candidate should be rounded upwards */
204  )
205 {
206  SCIP_Real upweight;
207  SCIP_Real downweight;
208  SCIP_Bool mayrounddown;
209  SCIP_Bool mayroundup;
210  int nconflictlocksdown;
211  int nconflictlocksup;
212  int nlocksdown;
213  int nlocksup;
214 
215  /* get conflict locks */
216  nconflictlocksup = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_CONFLICT);
217  nconflictlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_CONFLICT);
218 
219  /* get variable locks */
221  nlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_MODEL);
222 
223  /* combine conflict and variable locks */
224  upweight = heurdata->lockweight * nconflictlocksup + (1.0 - heurdata->lockweight) * nlocksup;
225  downweight = heurdata->lockweight * nconflictlocksdown + (1.0 - heurdata->lockweight) * nlocksdown;
226 
227  /* check whether there exists a direction w/o any locks */
228  mayrounddown = SCIPisZero(scip, upweight);
229  mayroundup = SCIPisZero(scip, downweight);
230 
231  if( mayrounddown || mayroundup )
232  {
233  /* choose rounding direction:
234  * - if variable may be rounded in both directions, round corresponding to the fractionality
235  * - otherwise, round in the infeasible direction
236  */
237  if( mayrounddown && mayroundup )
238  {
239  assert(divetype != SCIP_DIVETYPE_SOS1VARIABLE || heurdata->lockweight > 0);
240 
241  /* try to avoid variability; decide randomly if the LP solution can contain some noise */
242  if( SCIPisEQ(scip, candsfrac, 0.5) )
243  *roundup = (SCIPrandomGetInt(rng, 0, 1) == 0);
244  else
245  *roundup = (candsfrac > 0.5);
246  }
247  else
248  *roundup = mayrounddown;
249  }
250  else
251  {
252  /* the candidate may not be rounded */
253  *roundup = (SCIPisGT(scip, downweight, upweight) || (SCIPisEQ(scip, downweight, upweight) && candsfrac > 0.5));
254  }
255 
256  if( *roundup )
257  {
258  switch( divetype )
259  {
261  candsfrac = 1.0 - candsfrac;
262  break;
264  if( SCIPisFeasPositive(scip, candsol) )
265  candsfrac = 1.0 - candsfrac;
266  break;
267  default:
268  SCIPerrorMessage("Error: Unsupported diving type\n");
269  SCIPABORT();
270  return SCIP_INVALIDDATA; /*lint !e527*/
271  } /*lint !e788*/
272 
273  /* add some noise to avoid ties */
274  *score = upweight + SCIPrandomGetReal(rng, MIN_RAND, MAX_RAND);
275  }
276  else
277  {
278  if( divetype == SCIP_DIVETYPE_SOS1VARIABLE && SCIPisFeasNegative(scip, candsol) )
279  candsfrac = 1.0 - candsfrac;
280 
281  /* add some noise to avoid ties */
282  *score = downweight + SCIPrandomGetReal(rng, MIN_RAND, MAX_RAND);
283  }
284 
285  /* penalize too small fractions */
286  if( SCIPisEQ(scip, candsfrac, 0.01) )
287  {
288  /* try to avoid variability; decide randomly if the LP solution can contain some noise.
289  * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for scaling the score
290  */
292  (*score) *= 0.01;
293  }
294  else if( candsfrac < 0.01 )
295  (*score) *= 0.1;
296 
297  /* prefer decisions on binary variables */
298  if( !SCIPvarIsBinary(cand) )
299  *score = -1.0 / *score;
300 
301  return SCIP_OKAY;
302 }
303 
304 /** calculate score variant 2: use a rounding strategy that tends towards infeasibility */
305 static
307  SCIP* scip, /**< SCIP data structure */
308  SCIP_HEURDATA* heurdata, /**< heuristic data */
309  SCIP_RANDNUMGEN* rng, /**< random number generator of the diveset */
310  SCIP_DIVETYPE divetype, /**< divetype of the heuristic */
311  SCIP_VAR* cand, /**< diving candidate */
312  SCIP_Real candsol, /**< diving candidate solution */
313  SCIP_Real candsfrac, /**< fractionality of the candidate solution */
314  SCIP_Real* score, /**< pointer to store the score */
315  SCIP_Bool* roundup /**< pointer to store whether the candidate should be rounded upwards */
316  )
317 {
318  SCIP_Real conflictlocksum;
319  SCIP_Real upweight;
320  SCIP_Real downweight;
321  SCIP_Bool mayrounddown;
322  SCIP_Bool mayroundup;
323  int nlocksup;
324  int nlocksdown;
325  int nconflictlocksup;
326  int nconflictlocksdown;
327 
328  assert(scip != NULL);
329  assert(heurdata != NULL);
330  assert(rng != NULL);
331 
332  /* get conflict locks */
333  nconflictlocksup = SCIPvarGetNLocksUpType(cand, SCIP_LOCKTYPE_CONFLICT);
334  nconflictlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_CONFLICT);
335  conflictlocksum = nconflictlocksup + nconflictlocksdown;
336 
337  /* get variable locks */
339  nlocksdown = SCIPvarGetNLocksDownType(cand, SCIP_LOCKTYPE_MODEL);
340 
341  /* combine conflict and variable locks */
342  upweight = heurdata->lockweight * nconflictlocksup + (1.0 - heurdata->lockweight) * nlocksup;
343  downweight = heurdata->lockweight * nconflictlocksdown + (1.0 - heurdata->lockweight) * nlocksdown;
344 
345  /* check whether there exists a rounding direction w/o any locks */
346  mayrounddown = SCIPisZero(scip, upweight);
347  mayroundup = SCIPisZero(scip, downweight);
348 
349  /* variable can be rounded in exactly one direction and we try to go into the feasible direction */
350  if( mayrounddown || mayroundup )
351  {
352  /* choose rounding direction:
353  * - if variable may be rounded in both directions, round corresponding to the fractionality
354  * - otherwise, round in the feasible direction
355  */
356  if( mayrounddown && mayroundup )
357  {
358  assert(divetype != SCIP_DIVETYPE_SOS1VARIABLE || heurdata->lockweight > 0);
359 
360  /* try to avoid variability; decide randomly if the LP solution can contain some noise */
361  if( SCIPisEQ(scip, candsfrac, 0.5) )
362  *roundup = (SCIPrandomGetInt(rng, 0, 1) == 0);
363  else
364  *roundup = (candsfrac > 0.5);
365  }
366  else
367  *roundup = mayroundup;
368  }
369  else
370  {
371  assert(!mayrounddown);
372 
373  /* both rounding directions have a different amount of locks */
374  if( !SCIPisEQ(scip, upweight, downweight) )
375  {
376  *roundup = (heurdata->maxviol ? SCIPisGT(scip, upweight, downweight) : SCIPisLT(scip, upweight, downweight));
377  }
378  /* break ties with lp fractionality != 0.5 */
379  else if( !SCIPisEQ(scip, candsfrac, 0.5) )
380  {
381  *roundup = (candsfrac > 0.5);
382  }
383  /* break tie randomly */
384  else
385  {
386  *roundup = (SCIPrandomGetInt(rng, 0, 1) == 1);
387  }
388  }
389 
390  if( *roundup )
391  {
392  switch( divetype )
393  {
395  candsfrac = 1.0 - candsfrac;
396  break;
398  if( SCIPisFeasPositive(scip, candsol) )
399  candsfrac = 1.0 - candsfrac;
400  break;
401  default:
402  SCIPerrorMessage("Error: Unsupported diving type\n");
403  SCIPABORT();
404  return SCIP_INVALIDDATA; /*lint !e527*/
405  } /*lint !e788*/
406 
407  /* add some noise to avoid ties */
408  *score = upweight + SCIPrandomGetReal(rng, MIN_RAND, MAX_RAND);
409  }
410  else
411  {
412  if( divetype == SCIP_DIVETYPE_SOS1VARIABLE && SCIPisFeasNegative(scip, candsol) )
413  candsfrac = 1.0 - candsfrac;
414 
415  /* add some noise to avoid ties */
416  *score = downweight + SCIPrandomGetReal(rng, MIN_RAND, MAX_RAND);
417  }
418 
419  /* penalize too few conflict locks */
420  if( conflictlocksum > 0 && conflictlocksum < heurdata->minconflictlocks )
421  (*score) *= 0.1;
422 
423  /* penalize if no conflict locks exist at all */
424  if( conflictlocksum == 0 )
425  (*score) *= 0.01;
426 
427  /* penalize too small fractions */
428  if( SCIPisEQ(scip, candsfrac, 0.01) )
429  {
430  /* try to avoid variability; decide randomly if the LP solution can contain some noise.
431  * use a 1:SCIP_PROBINGSCORE_PENALTYRATIO chance for scaling the score
432  */
434  (*score) *= 0.01;
435  }
436  else if( candsfrac < 0.01 )
437  (*score) *= 0.01;
438 
439  /* prefer decisions on binary variables */
440  if( !SCIPvarIsBinary(cand) )
441  *score = -1.0 / *score;
442 
443  return SCIP_OKAY;
444 }
445 
446 
447 /** returns a score for the given candidate -- the best candidate maximizes the diving score */
448 static
449 SCIP_DECL_DIVESETGETSCORE(divesetGetScoreConflictdiving)
450 {
451  SCIP_HEUR* heur;
452  SCIP_HEURDATA* heurdata;
453  SCIP_RANDNUMGEN* rng;
454 
455  rng = SCIPdivesetGetRandnumgen(diveset);
456  assert(rng != NULL);
457 
458  heur = SCIPdivesetGetHeur(diveset);
459  assert(heur != NULL);
460 
461  heurdata = SCIPheurGetData(heur);
462  assert(heurdata != NULL);
463 
464  if( heurdata->likecoefdiving )
465  {
466  SCIP_CALL( getScoreLikeCoefdiving(scip, heurdata, rng, divetype, cand, candsol, candsfrac, score, roundup) );
467  }
468  else
469  {
470  SCIP_CALL( getScore(scip, heurdata, rng, divetype, cand, candsol, candsfrac, score, roundup) );
471  }
472 
473  /* check, if candidate is new best candidate: prefer unroundable candidates in any case */
474  assert( (0.0 < candsfrac && candsfrac < 1.0) || SCIPvarIsBinary(cand) || divetype == SCIP_DIVETYPE_SOS1VARIABLE );
475 
476  return SCIP_OKAY;
477 }
478 
479 /*
480  * heuristic specific interface methods
481  */
482 
483 #define divesetAvailableConflictdiving NULL
484 
485 /** creates the conflictdiving heuristic and includes it in SCIP */
487  SCIP* scip /**< SCIP data structure */
488  )
489 {
490  SCIP_HEURDATA* heurdata;
491  SCIP_HEUR* heur;
492 
493  /* create conflictdiving primal heuristic data */
494  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
495 
496  /* include primal heuristic */
498  HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecConflictdiving, heurdata) );
499 
500  assert(heur != NULL);
501 
502  /* set non-NULL pointers to callback methods */
503  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyConflictdiving) );
504  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeConflictdiving) );
505  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitConflictdiving) );
506  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitConflictdiving) );
507 
508  /* create a diveset (this will automatically install some additional parameters for the heuristic)*/
512  DIVESET_ISPUBLIC, DIVESET_DIVETYPES, divesetGetScoreConflictdiving, divesetAvailableConflictdiving) );
513 
514  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/maxviol", "try to maximize the violation",
515  &heurdata->maxviol, TRUE, DEFAULT_MAXVIOL, NULL, NULL) );
516 
517  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/likecoef",
518  "perform rounding like coefficient diving",
519  &heurdata->likecoefdiving, TRUE, DEFAULT_LIKECOEF, NULL, NULL) );
520 
521  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/minconflictlocks",
522  "minimal number of conflict locks per variable",
523  &heurdata->minconflictlocks, TRUE, DEFAULT_MINCONFLICTLOCKS, 0, INT_MAX, NULL, NULL) );
524 
525  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lockweight",
526  "weight used in a convex combination of conflict and variable locks",
527  &heurdata->lockweight, TRUE, DEFAULT_LOCKWEIGHT, 0.0, 1.0, NULL, NULL) );
528 
529  return SCIP_OKAY;
530 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_HEURINIT(heurInitConflictdiving)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:977
#define DEFAULT_MAXVIOL
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
public methods for SCIP parameter handling
static SCIP_RETCODE getScore(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_RANDNUMGEN *rng, SCIP_DIVETYPE divetype, SCIP_VAR *cand, SCIP_Real candsol, SCIP_Real candsfrac, SCIP_Real *score, SCIP_Bool *roundup)
#define DIVESET_ISPUBLIC
#define DEFAULT_ONLYLPBRANCHCANDS
SCIP_EXPORT int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3250
public methods for memory management
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
SCIP_RANDNUMGEN * SCIPdivesetGetRandnumgen(SCIP_DIVESET *diveset)
Definition: heur.c:700
#define DEFAULT_MAXDIVEUBQUOTNOSOL
#define HEUR_MAXDEPTH
#define DEFAULT_MAXDIVEAVGQUOT
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17197
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, SCIP_DIVECONTEXT divecontext)
Definition: heuristics.c:209
#define DEFAULT_RANDSEED
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9981
#define DEFAULT_BACKTRACK
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
methods commonly used by primal heuristics
#define DEFAULT_LIKECOEF
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
public methods for problem variables
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
unsigned int SCIP_DIVETYPE
Definition: type_heur.h:54
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
#define HEUR_TIMING
public methods for numerical tolerances
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
#define DEFAULT_LOCKWEIGHT
public methods for querying solving statistics
static SCIP_DECL_DIVESETGETSCORE(divesetGetScoreConflictdiving)
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
SCIP_HEUR * SCIPdivesetGetHeur(SCIP_DIVESET *diveset)
Definition: heur.c:396
#define SCIPerrorMessage
Definition: pub_message.h:55
#define HEUR_FREQOFS
int SCIPheurGetNDivesets(SCIP_HEUR *heur)
Definition: heur.c:1637
#define HEUR_USESSUBSCIP
#define HEUR_PRIORITY
SCIP_SOL * sol
Definition: struct_heur.h:62
#define DEFAULT_LPRESOLVEDOMCHGQUOT
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
#define NULL
Definition: lpi_spx1.cpp:155
#define MAX_RAND
#define DEFAULT_MAXRELDEPTH
static SCIP_DECL_HEUREXEC(heurExecConflictdiving)
#define SCIP_CALL(x)
Definition: def.h:364
#define SCIP_PROBINGSCORE_PENALTYRATIO
Definition: def.h:306
public methods for primal heuristic plugins and divesets
static SCIP_DECL_HEUREXIT(heurExitConflictdiving)
#define DEFAULT_MAXDIVEAVGQUOTNOSOL
public data structures and miscellaneous methods
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:9959
SCIP_DIVESET ** SCIPheurGetDivesets(SCIP_HEUR *heur)
Definition: heur.c:1627
SCIP_RETCODE SCIPincludeHeurConflictdiving(SCIP *scip)
#define SCIP_Bool
Definition: def.h:70
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
#define DEFAULT_LPSOLVEFREQ
SCIP_Longint SCIPgetNConflictConssFound(SCIP *scip)
#define HEUR_FREQ
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, 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: scip_param.c:130
SCIP_RETCODE SCIPcreateDiveset(SCIP *scip, SCIP_DIVESET **diveset, SCIP_HEUR *heur, const char *name, 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_Bool specificsos1score, SCIP_DECL_DIVESETGETSCORE((*divesetgetscore)), SCIP_DECL_DIVESETAVAILABLE((*divesetavailable)))
Definition: scip_heur.c:311
#define DEFAULT_MAXDIVEUBQUOT
SCIP_EXPORT int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3193
static SCIP_RETCODE getScoreLikeCoefdiving(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_RANDNUMGEN *rng, SCIP_DIVETYPE divetype, SCIP_VAR *cand, SCIP_Real candsol, SCIP_Real candsfrac, SCIP_Real *score, SCIP_Bool *roundup)
#define DIVESET_DIVETYPES
public methods for solutions
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
#define DEFAULT_MAXLPITEROFS
public methods for message output
#define HEUR_DESC
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, 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: scip_param.c:74
#define SCIP_Real
Definition: def.h:163
#define DEFAULT_MINRELDEPTH
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
LP diving heuristic that chooses fixings w.r.t. conflict locks.
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_DIVETYPE_SOS1VARIABLE
Definition: type_heur.h:52
#define MIN_RAND
#define HEUR_NAME
static SCIP_DECL_HEURCOPY(heurCopyConflictdiving)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
public methods for primal heuristics
#define SCIP_DIVETYPE_INTEGRALITY
Definition: type_heur.h:51
#define divesetAvailableConflictdiving
#define DEFAULT_MAXLPITERQUOT
#define SCIPABORT()
Definition: def.h:336
static SCIP_DECL_HEURFREE(heurFreeConflictdiving)
#define DEFAULT_MINCONFLICTLOCKS
#define HEUR_DISPCHAR
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)