Scippy

SCIP

Solving Constraint Integer Programs

branch_inference.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-2022 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 branch_inference.c
17  * @ingroup DEFPLUGINS_BRANCH
18  * @brief inference history branching rule
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Stefan Heinz
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #include "scip/branch_inference.h"
27 #include "scip/pub_branch.h"
28 #include "scip/pub_history.h"
29 #include "scip/pub_message.h"
30 #include "scip/pub_var.h"
31 #include "scip/scip_branch.h"
32 #include "scip/scip_message.h"
33 #include "scip/scip_mem.h"
34 #include "scip/scip_numerics.h"
35 #include "scip/scip_param.h"
36 #include "scip/scip_var.h"
37 #include <string.h>
38 
39 
40 /**@name Branching rule properties
41  *
42  * @{
43  */
44 
45 #define BRANCHRULE_NAME "inference"
46 #define BRANCHRULE_DESC "inference history branching"
47 #define BRANCHRULE_PRIORITY 1000
48 #define BRANCHRULE_MAXDEPTH -1
49 #define BRANCHRULE_MAXBOUNDDIST 1.0
50 
51 /**@} */
52 
53 /**@name Default parameter values
54  *
55  * @{
56  */
57 
58 #define DEFAULT_CONFLICTWEIGHT 1000.0 /**< weight in score calculations for conflict score */
59 #define DEFAULT_CUTOFFWEIGHT 1.0 /**< weight in score calculations for cutoff score */
60 #define DEFAULT_INFERENCEWEIGHT 1.0 /**< weight in score calculations for inference score */
61 #define DEFAULT_RELIABLESCORE 0.001 /**< score which is seen to be reliable for a branching decision */
62 #define DEFAULT_FRACTIONALS TRUE /**< should branching on LP solution be restricted to the fractional variables? */
63 #define DEFAULT_USEWEIGHTEDSUM TRUE /**< should a weighted sum of inference, conflict and cutoff weights be used? */
64 
65 #define DEFAULT_CONFLICTPRIO 1 /**< priority value for using conflict weights in lex. order */
66 #define DEFAULT_CUTOFFPRIO 1 /**< priority value for using cutoff weights in lex. order */
67 
68 /**@} */
69 
70 /** branching rule data */
71 struct SCIP_BranchruleData
72 {
73  SCIP_Real conflictweight; /**< weight in score calculations for conflict score */
74  SCIP_Real cutoffweight; /**< weight in score calculations for cutoff score */
75  SCIP_Real inferenceweight; /**< weight in score calculations for inference score */
76  SCIP_Real reliablescore; /**< score which is seen to be reliable for a branching decision */
77  SCIP_Bool fractionals; /**< should branching on LP solution be restricted to the fractional variables? */
78  SCIP_Bool useweightedsum; /**< should a weighted sum of inference, conflict and cutoff weights be used? */
79  int conflictprio; /**< priority value for using conflict weights in lexicographic order */
80  int cutoffprio; /**< priority value for using cutoff weights in lexicographic order */
81 };
82 
83 /** evaluate the given candidate with the given score against the currently best know candidate, tiebreaking included */
84 static
86  SCIP_VAR* cand, /**< candidate to be checked */
87  SCIP_Real score, /**< score of the candidate */
88  SCIP_Real branchpoint, /**< potential branching point */
89  SCIP_BRANCHDIR branchdir, /**< potential branching direction */
90  SCIP_VAR** bestcand, /**< pointer to the currently best candidate */
91  SCIP_Real* bestscore, /**< pointer to the score of the currently best candidate */
92  SCIP_Real* bestbranchpoint, /**< pointer to store the (best) branching point */
93  SCIP_BRANCHDIR* bestbranchdir /**< pointer to store the branching direction relative to the branching point */
94  )
95 {
96  /* evaluate the candidate against the currently best candidate */
97  if( *bestscore < score )
98  {
99  /* the score of the candidate is better than the currently best know candidate */
100  *bestscore = score;
101  *bestcand = cand;
102  *bestbranchpoint = branchpoint;
103  *bestbranchdir = branchdir;
104  }
105  else if( (*bestscore) == score ) /*lint !e777*/
106  {
107  SCIP_Real bestobj;
108  SCIP_Real candobj;
109 
110  bestobj = REALABS(SCIPvarGetObj(*bestcand));
111  candobj = REALABS(SCIPvarGetObj(cand));
112 
113  /* the candidate has the same score as the best known candidate; therefore we use a second and third
114  * criteria to detect a unique best candidate;
115  *
116  * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
117  * since branching on that variable might trigger further propagation w.r.t. objective function
118  * - if the absolute values of the objective coefficient are equal the variable index is used to define a
119  * unique best candidate
120  *
121  * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
122  * performance to much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
123  * SCIPgetLPBranchCands()) gets dynamically changed during the solution process. In particular,
124  * starting a probing mode might already change the order of these arrays. To be independent of that
125  * the selection should be unique. Otherwise, to selection process can get influenced by starting a
126  * probing or not.
127  */
128  if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(*bestcand) < SCIPvarGetIndex(cand)) ) /*lint !e777*/
129  {
130  *bestcand = cand;
131  *bestbranchpoint = branchpoint;
132  *bestbranchdir = branchdir;
133  }
134  }
135 }
136 
137 /** evaluate the given candidate with the given score against the currently best know candidate */
138 static
140  SCIP* scip, /**< SCIP data structure */
141  SCIP_VAR* cand, /**< candidate to be checked */
142  SCIP_Real score, /**< score of the candidate */
143  SCIP_Real val, /**< solution value of the candidate */
144  SCIP_VAR** bestcand, /**< pointer to the currently best candidate */
145  SCIP_Real* bestscore, /**< pointer to the score of the currently best candidate */
146  SCIP_Real* bestval, /**< pointer to the solution value of the currently best candidate */
147  SCIP_VAR** bestcands, /**< buffer array to return selected candidates */
148  int* nbestcands /**< pointer to return number of selected candidates */
149  )
150 {
151  /* evaluate the candidate against the currently best candidate */
152  /** TODO: consider a weaker comparison of some kind */
153  if( *bestscore < score )
154  {
155  /* the score of the candidate is better than the currently best know candidate, so it should be the first candidate in bestcands and nbestcands should be set to 1*/
156  *bestscore = score;
157  *bestcand = cand;
158  *bestval = val;
159  *nbestcands = 1;
160  bestcands[0] = cand;
161  }
162  /** TODO: consider a weaker comparison of some kind */
163  else if( SCIPisEQ(scip, *bestscore, score) )
164  {
165  /* the score of the candidate is comparable to the currently known best, so we add it to bestcands and increase nbestcands by 1*/
166  bestcands[*nbestcands] = cand;
167  (*nbestcands)++;
168  }
169 }
170 
171 /** choose a singular best candidate from bestcands and move it to the beginning of the candidate array */
172 static
174  SCIP_VAR** bestcands, /**< buffer array to return selected candidates */
175  int nbestcands /**< number of selected candidates */
176  )
177 {
178  int c;
179 
180  for( c = 0; c < nbestcands; ++c )
181  {
182  SCIP_Real bestobj;
183  SCIP_Real candobj;
184 
185  bestobj = REALABS(SCIPvarGetObj(bestcands[0]));
186  candobj = REALABS(SCIPvarGetObj(bestcands[c]));
187 
188  /* the candidate has the same score as the best known candidate; therefore we use a second and third
189  * criteria to detect a unique best candidate;
190  *
191  * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
192  * since branching on that variable might trigger further propagation w.r.t. objective function
193  * - if the absolute values of the objective coefficient are equal the variable index is used to define a
194  * unique best candidate
195  *
196  * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
197  * performance too much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
198  * SCIPgetLPBranchCands()) gets dynamically changed during the solution process. In particular,
199  * starting a probing mode might already change the order of these arrays. To be independent of that
200  * the selection should be unique. Otherwise, to selection process can get influenced by starting a
201  * probing or not.
202  */
203  if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(bestcands[0]) < SCIPvarGetIndex(bestcands[c])) ) /*lint !e777*/
204  {
205  bestcands[0] = bestcands[c];
206  }
207  }
208 }
209 
210 /** check if the score for the given domain value and variable domain value is better than the current best know one */
211 static
213  SCIP_Real value, /**< domain value */
214  SCIP_HISTORY* history, /**< variable history for given donain value */
215  SCIP_BRANCHDIR dir, /**< branching direction */
216  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
217  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
218  SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
219  SCIP_Real* bestscore, /**< pointer to store the best score */
220  SCIP_Real* branchpoint, /**< pointer to store the (best) branching point */
221  SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
222  )
223 {
224  SCIP_Real conflictscore;
225  SCIP_Real cutoffscore;
226  SCIP_Real score;
227 
228  conflictscore = SCIPhistoryGetVSIDS(history, dir);
229  cutoffscore = SCIPhistoryGetCutoffSum(history, dir);
230 
231  /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
232  * unreliable
233  */
234  if( conflictscore < reliablescore )
235  conflictscore = 0.0;
236 
237  /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
238  if( cutoffscore < reliablescore )
239  cutoffscore = 0.0;
240 
241  /* compute weight score */
242  score = conflictweight * conflictscore + cutoffweight * cutoffscore;
243 
244  if( score > *bestscore )
245  {
246  (*bestscore) = score;
247  (*branchpoint) = value;
248  (*branchdir) = dir;
249  }
250 }
251 
252 /** return an aggregated score for the given variable using the conflict score and cutoff score */
253 static
255  SCIP* scip, /**< SCIP data structure */
256  SCIP_VAR* var, /**< problem variable */
257  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
258  SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
259  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
260  SCIP_Real reliablescore /**< score which is seen to be reliable for a branching decision */
261  )
262 {
263  SCIP_Real conflictscore;
264  SCIP_Real cutoffscore;
265 
266  conflictscore = SCIPgetVarConflictScore(scip, var);
267  cutoffscore = SCIPgetVarAvgInferenceCutoffScore(scip, var, cutoffweight);
268 
269  /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
270  * unreliable
271  */
272  if( conflictscore < reliablescore )
273  conflictscore = 0.0;
274 
275  /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
276  if( cutoffscore < reliablescore )
277  cutoffscore = 0.0;
278 
279  /* compute weighted score for the candidate */
280  return (conflictweight * conflictscore + inferenceweight * cutoffscore);
281 }
282 
283 /** return an aggregated score for the given variable using the conflict score and cutoff score */
284 static
286  SCIP_VAR* var, /**< problem variable */
287  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
288  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
289  SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
290  SCIP_Real* branchpoint, /**< pointer to store the branching point */
291  SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
292  )
293 {
294  SCIP_VALUEHISTORY* valuehistory;
295  SCIP_Real bestscore;
296 
297  (*branchpoint) = SCIP_UNKNOWN;
298  (*branchdir) = SCIP_BRANCHDIR_UPWARDS;
299 
300  valuehistory = SCIPvarGetValuehistory(var);
301  bestscore = 0.0;
302 
303  if( valuehistory != NULL )
304  {
305  SCIP_HISTORY** histories;
306  SCIP_Real* values;
307  int nvalues;
308  int v;
309 
310  histories = SCIPvaluehistoryGetHistories(valuehistory);
311  values = SCIPvaluehistoryGetValues(valuehistory);
312  nvalues = SCIPvaluehistoryGetNValues(valuehistory);
313 
314  for( v = 0; v < nvalues; ++v )
315  {
316  SCIP_Real value;
317 
318  value = values[v];
319 
320  /* skip all domain values which are smaller or equal to the lower bound */
321  if( value <= SCIPvarGetLbLocal(var) )
322  continue;
323 
324  /* skip all domain values which are larger or equal to the upper bound */
325  if( value >= SCIPvarGetUbLocal(var) )
326  break;
327 
328  /* check var <= value */
329  checkValueScore(value, histories[v], SCIP_BRANCHDIR_DOWNWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir);
330 
331  /* check var >= value */
332  checkValueScore(value, histories[v], SCIP_BRANCHDIR_UPWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir);
333  }
334  }
335 
336  return bestscore;
337 }
338 
339 static
341  SCIP* scip, /**< SCIP data structure */
342  SCIP_VAR** cands, /**< candidate array */
343  SCIP_Real* candsols, /**< array of candidate solution values, or NULL */
344  int ncands, /**< number of candidates */
345  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
346  SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
347  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
348  SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
349  SCIP_VAR** bestcands, /**< buffer array to return selected candidates */
350  int* nbestcands /**< pointer to return number of selected candidates */
351  )
352 {
353  SCIP_VAR* bestaggrcand;
354  SCIP_Real bestval;
355  SCIP_Real bestaggrscore;
356  int c;
357 
358  bestaggrcand = cands[0];
359  assert(cands[0] != NULL);
360 
361  bestval = candsols[0];
362  bestcands[0] = cands[0];
363  *nbestcands = 1;
364 
365  /* get aggregated score for the first candidate */
366  bestaggrscore = getAggrScore(scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore);
367 
368  for( c = 1; c < ncands; ++c )
369  {
370  SCIP_VAR* cand;
371  SCIP_Real val;
372  SCIP_Real aggrscore;
373 
374  cand = cands[c];
375  assert(cand != NULL);
376 
377  val = candsols[c];
378 
379  /* get score for the candidate */
380  aggrscore = getAggrScore(scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore);
381 
382  /*lint -e777*/
383  SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
384  val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore);
385 
386  /* evaluate the candidate against the currently best candidate w.r.t. aggregated score */
387  evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, nbestcands);
388  }
389 } /*lint --e{438}*/
390 
391 
392 /** selects a variable out of the given candidate array and performs the branching */
393 static
395  SCIP* scip, /**< SCIP data structure */
396  SCIP_VAR** cands, /**< candidate array */
397  SCIP_Real* candsols, /**< array of candidate solution values, or NULL */
398  int ncands, /**< number of candidates */
399  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
400  SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
401  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
402  SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
403  SCIP_Bool useweightedsum, /**< should a weighted sum of inference, conflict and cutoff weights be used? */
404  SCIP_RESULT* result, /**< buffer to store result (branched, reduced domain, ...) */
405  int conflictprio, /**< priority value for using conflict weights in lex. order */
406  int cutoffprio /**< priority value for using conflict weights in lex. order */
407  )
408 {
409  SCIP_VAR* bestaggrcand;
410  SCIP_Real bestval;
411  SCIP_NODE* downchild;
412  SCIP_NODE* eqchild;
413  SCIP_NODE* upchild;
414  SCIP_VAR** bestcands;
415  int nbestcands;
416  int c;
417 
418  assert(ncands > 0);
419  assert(result != NULL);
420 
421  *result = SCIP_DIDNOTFIND;
422 
423  /* check if conflict score, inferences, and cutoff score should be used in combination; otherwise just use
424  * inference */
425  if( useweightedsum == FALSE )
426  {
427  conflictprio = 0;
428  cutoffprio = 0;
429  conflictweight = 0.0;
430  inferenceweight = 1.0;
431  cutoffweight = 0.0;
432  }
433 
434  /* allocate temporary memory */
435  SCIP_CALL( SCIPallocClearBufferArray(scip, &bestcands, ncands) );
436  nbestcands = 0;
437 
438  if( conflictprio > cutoffprio )
439  {
440  /* select the best candidates w.r.t. the first criterion */
441  selectBestCands(scip, cands, candsols, ncands, conflictweight, 0.0, 0.0, reliablescore,
442  bestcands, &nbestcands);
443 
444  /* select the best candidates w.r.t. the second criterion; we use bestcands and nbestcands as input and
445  * output, so the method must make sure to overwrite the last argument only at the very end */
446  if( nbestcands > 1 )
447  {
448  selectBestCands(scip, bestcands, candsols, nbestcands, 0.0, inferenceweight, cutoffweight, reliablescore,
449  bestcands, &nbestcands);
450  }
451  }
452  else if( conflictprio == cutoffprio )
453  {
454  /* select the best candidates w.r.t. weighted sum of both criteria */
455  selectBestCands(scip, cands, candsols, ncands, conflictweight, inferenceweight, cutoffweight, reliablescore,
456  bestcands, &nbestcands);
457  }
458  else
459  {
460  assert(conflictprio < cutoffprio);
461 
462  /* select the best candidates w.r.t. the first criterion */
463  selectBestCands(scip, cands, candsols, ncands, 0.0, inferenceweight, cutoffweight, reliablescore,
464  bestcands, &nbestcands);
465 
466  /* select the best candidates w.r.t. the second criterion; we use bestcands and nbestcands as input and
467  * output, so the method must make sure to overwrite the last argument only at the very end */
468  if( nbestcands > 1 )
469  {
470  /* select the best candidates w.r.t. the first criterion */
471  selectBestCands(scip, bestcands, candsols, nbestcands, conflictweight, 0.0, 0.0, reliablescore,
472  bestcands, &nbestcands);
473  }
474  }
475 
476  assert(nbestcands == 0 || bestcands[0] != NULL);
477 
478  /* final tie breaking */
479  if( nbestcands > 1 )
480  {
481  tiebreakAggrCand(bestcands, nbestcands);
482  nbestcands = 1;
483  }
484 
485  assert(nbestcands == 1);
486 
487  bestaggrcand = bestcands[0];
488  bestval = -SCIP_INVALID;
489 
490  /* loop over cands, find bestcands[0], and store corresponding candsols value in bestval */
491  for( c = 0; c < ncands; ++c )
492  {
493  if( bestaggrcand == cands[c] )
494  {
495  bestval = candsols[c];
496  break;
497  }
498  }
499 
500  assert(bestval != -SCIP_INVALID);
501 
502  /* free temporary memory */
503  SCIPfreeBufferArray(scip, &bestcands);
504 
505  assert(bestaggrcand != NULL);
506 
507  SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, conflict=%g cutoff=%g, inference=%g)\n",
508  ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand),
509  bestval == SCIP_UNKNOWN ? SCIPgetVarSol(scip, bestaggrcand) : bestval, /*lint !e777*/
510  SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight),
511  SCIPgetVarAvgInferenceScore(scip, bestaggrcand));
512 
513  assert(candsols != NULL);
514  /* perform the branching */
515  SCIP_CALL( SCIPbranchVarVal(scip, bestaggrcand, SCIPgetBranchingPoint(scip, bestaggrcand, bestval), &downchild, &eqchild, &upchild) );
516 
517  if( downchild != NULL || eqchild != NULL || upchild != NULL )
518  {
519  *result = SCIP_BRANCHED;
520  }
521  else
522  {
523  /* if there are no children, then variable should have been fixed by SCIPbranchVar(Val) */
524  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestaggrcand), SCIPvarGetUbLocal(bestaggrcand)));
525  *result = SCIP_REDUCEDDOM;
526  }
527 
528  return SCIP_OKAY;
529 }
530 
531 
532 /** selects a variable out of the given candidate array and performs the branching */
533 static
535  SCIP* scip, /**< SCIP data structure */
536  SCIP_VAR** cands, /**< candidate array */
537  int ncands, /**< number of candidates */
538  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
539  SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
540  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
541  SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
542  SCIP_Bool useweightedsum, /**< should a weighted sum of inference, conflict and cutoff weights be used? */
543  SCIP_RESULT* result /**< buffer to store result (branched, reduced domain, ...) */
544  )
545 {
546  SCIP_VAR* bestaggrcand;
547  SCIP_VAR* bestvaluecand;
548  SCIP_Real bestval;
549  SCIP_Real bestaggrscore;
550  SCIP_Real bestvaluescore;
551  SCIP_Real bestbranchpoint;
552  SCIP_BRANCHDIR bestbranchdir;
553  SCIP_NODE* downchild;
554  SCIP_NODE* eqchild;
555  SCIP_NODE* upchild;
556  SCIP_VAR** bestcands;
557  int nbestcands;
558 
559  bestbranchpoint = SCIP_UNKNOWN;
560  bestbranchdir = SCIP_BRANCHDIR_DOWNWARDS;
561  bestvaluescore = 0.0;
562  bestvaluecand = NULL;
563 
564  assert(ncands > 0);
565  assert(result != NULL);
566 
567  *result = SCIP_DIDNOTFIND;
568 
569 
570  /* allocate temporary memory */
571  SCIP_CALL( SCIPallocBufferArray(scip, &bestcands, ncands) );
572  nbestcands = 0;
573 
574  /* check if the weighted sum between the average inferences and conflict score should be used */
575  if( useweightedsum )
576  {
577  int c;
578 
579  bestaggrcand = cands[0];
580  bestvaluecand = cands[0];
581  assert(cands[0] != NULL);
582 
583  bestval = SCIP_UNKNOWN;
584 
585  /* get domain value score for the first candidate */
586  bestvaluescore = getValueScore(cands[0], conflictweight, cutoffweight, reliablescore, &bestbranchpoint, &bestbranchdir);
587  SCIPdebugMsg(scip, "current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n",
588  SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand),
589  bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS ? "<=" : ">=", bestbranchpoint, bestvaluescore);
590 
591  /* get aggregated score for the first candidate */
592  bestaggrscore = getAggrScore(scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore);
593 
594  for( c = 1; c < ncands; ++c )
595  {
596  SCIP_VAR* cand;
597  SCIP_Real val;
598  SCIP_Real aggrscore;
599  SCIP_Real branchpoint;
600  SCIP_BRANCHDIR branchdir;
601  SCIP_Real valuescore;
602 
603  cand = cands[c];
604  assert(cand != NULL);
605 
606  val = SCIP_UNKNOWN;
607 
608  /* get domain value score for the candidate */
609  valuescore = getValueScore(cand, conflictweight, cutoffweight, reliablescore, &branchpoint, &branchdir);
610 
611  /* evaluate the candidate against the currently best candidate w.r.t. domain value score */
612  evaluateValueCand(cand, valuescore, branchpoint, branchdir, &bestvaluecand, &bestvaluescore, &bestbranchpoint, &bestbranchdir);
613 
614  SCIPdebugMsg(scip, "current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n",
615  SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand),
616  bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS ? "<=" : ">=", bestbranchpoint, bestvaluescore);
617 
618  /* get aggregated score for the candidate */
619  aggrscore = getAggrScore(scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore);
620 
621  /*lint -e777*/
622  SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
623  val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore);
624 
625  /* evaluate the candidate against the currently best candidate w.r.t. aggregated score */
626  evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, &nbestcands);
627  }
628  }
629  else
630  {
631  int c;
632 
633  bestaggrcand = cands[0];
634  assert(cands[0] != NULL);
635 
636  bestval = SCIP_UNKNOWN;
637 
638  bestaggrscore = SCIPgetVarAvgInferenceScore(scip, cands[0]);
639 
640  /* search for variable with best score w.r.t. average inferences per branching */
641  for( c = 1; c < ncands; ++c )
642  {
643  SCIP_VAR* cand;
644  SCIP_Real val;
645  SCIP_Real aggrscore;
646 
647  cand = cands[c];
648  assert(cand != NULL);
649 
650  val = SCIP_UNKNOWN;
651 
652  aggrscore = SCIPgetVarAvgInferenceScore(scip, cand);
653 
654  /* in case the average inferences score is below the reliable score we set it to zero since it is seen to be
655  * unreliable
656  */
657  if( aggrscore < reliablescore )
658  aggrscore = 0.0;
659 
660  SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
661  val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore); /*lint !e777*/
662 
663  /* evaluate the candidate against the currently best candidate */
664  evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, &nbestcands);
665  }
666  }
667 
668  /* free temporary memory */
669  SCIPfreeBufferArray(scip, &bestcands);
670 
671  assert(bestaggrcand != NULL);
672 
673  SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, score=%g, conflict=%g cutoff=%g, inference=%g)\n",
674  ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand),
675  bestval == SCIP_UNKNOWN ? SCIPgetVarSol(scip, bestaggrcand) : bestval, bestaggrscore, /*lint !e777*/
676  SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight),
677  SCIPgetVarAvgInferenceScore(scip, bestaggrcand));
678 
679  if( bestbranchpoint == SCIP_UNKNOWN ) /*lint !e777*/
680  {
681  SCIP_CALL( SCIPbranchVar(scip, bestaggrcand, &downchild, &eqchild, &upchild) );
682  }
683  else
684  {
685  /* perform the branching */
686  SCIP_Real estimate;
687  SCIP_Real downprio;
688  SCIP_Real upprio;
689  SCIP_Real downub;
690  SCIP_Real uplb;
691 
692  assert(bestvaluecand != NULL);
693 
694  downprio = 0.0;
695  upprio = 0.0;
696 
697  if( bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS )
698  {
699  downprio = 1.0;
700  downub = bestbranchpoint;
701  uplb = bestbranchpoint + 1.0;
702  }
703  else
704  {
705  upprio = 1.0;
706  downub = bestbranchpoint - 1.0;
707  uplb = bestbranchpoint;
708  }
709 
710  /* calculate the child estimate */
711  estimate = SCIPcalcChildEstimate(scip, bestvaluecand, downub);
712 
713  /* create down child */
714  SCIP_CALL( SCIPcreateChild(scip, &downchild, downprio, estimate) );
715 
716  /* change upper bound in down child */
717  SCIP_CALL( SCIPchgVarUbNode(scip, downchild, bestvaluecand, downub) );
718 
719  /* calculate the child estimate */
720  estimate = SCIPcalcChildEstimate(scip, bestvaluecand, uplb);
721 
722  /* create up child */
723  SCIP_CALL( SCIPcreateChild(scip, &upchild, upprio, estimate) );
724 
725  /* change lower bound in up child */
726  SCIP_CALL( SCIPchgVarLbNode(scip, upchild, bestvaluecand, uplb) );
727 
728  SCIPdebugMsg(scip, "branch on variable <%s> and value <%g>\n", SCIPvarGetName(bestvaluecand), bestbranchpoint);
729 
730  eqchild = NULL;
731  }
732  if( downchild != NULL || eqchild != NULL || upchild != NULL )
733  {
734  *result = SCIP_BRANCHED;
735  }
736  else
737  {
738  /* if there are no children, then variable should have been fixed by SCIPbranchVar(Val) */
739  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestaggrcand), SCIPvarGetUbLocal(bestaggrcand)));
740  *result = SCIP_REDUCEDDOM;
741  }
742 
743  return SCIP_OKAY;
744 }
745 
746 /*
747  * Callback methods
748  */
749 
750 /** copy method for branchrule plugins (called when SCIP copies plugins) */
751 static
752 SCIP_DECL_BRANCHCOPY(branchCopyInference)
753 { /*lint --e{715}*/
754  assert(scip != NULL);
755  assert(branchrule != NULL);
756  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
757 
758  /* call inclusion method of branchrule */
760 
761  return SCIP_OKAY;
762 }
763 
764 /** destructor of branching rule to free user data (called when SCIP is exiting) */
765 static
766 SCIP_DECL_BRANCHFREE(branchFreeInference)
767 { /*lint --e{715}*/
768  SCIP_BRANCHRULEDATA* branchruledata;
769 
770  /* free branching rule data */
771  branchruledata = SCIPbranchruleGetData(branchrule);
772  SCIPfreeBlockMemory(scip, &branchruledata);
773  SCIPbranchruleSetData(branchrule, NULL);
774 
775  return SCIP_OKAY;
776 }
777 
778 /** branching execution method for fractional LP solutions */
779 static
780 SCIP_DECL_BRANCHEXECLP(branchExeclpInference)
781 { /*lint --e{715}*/
782  SCIP_BRANCHRULEDATA* branchruledata;
783  SCIP_VAR** cands;
784  int ncands;
785 
786  SCIPdebugMsg(scip, "Execlp method of inference branching\n");
787 
788  /* get branching rule data */
789  branchruledata = SCIPbranchruleGetData(branchrule);
790  assert(branchruledata != NULL);
791 
792  if( branchruledata->fractionals )
793  {
794  /* get LP candidates (fractional integer variables) */
795  SCIP_CALL( SCIPgetLPBranchCands(scip, &cands, NULL, NULL, NULL, &ncands, NULL) );
796  }
797  else
798  {
799  /* get pseudo candidates (non-fixed integer variables) */
800  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, NULL, &ncands) );
801  }
802 
803  /* perform the branching */
804  SCIP_CALL( performBranchingNoSol(scip, cands, ncands, branchruledata->conflictweight,
805  branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
806  branchruledata->useweightedsum, result) );
807 
808  return SCIP_OKAY;
809 }
810 
811 
812 /** branching execution method for external candidates */
813 static
814 SCIP_DECL_BRANCHEXECEXT(branchExecextInference)
815 { /*lint --e{715}*/
816  SCIP_BRANCHRULEDATA* branchruledata;
817  SCIP_VAR** cands;
818  SCIP_Real* candsols;
819  int ncands;
820 
821  SCIPdebugMsg(scip, "Execext method of inference branching\n");
822 
823  /* get branching rule data */
824  branchruledata = SCIPbranchruleGetData(branchrule);
825  assert(branchruledata != NULL);
826 
827  /* get branching candidates */
828  SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candsols, NULL, &ncands, NULL, NULL, NULL, NULL) );
829  assert(ncands > 0);
830 
831  /* perform the branching */
832  SCIP_CALL( performBranchingSol(scip, cands, candsols, ncands, branchruledata->conflictweight,
833  branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
834  branchruledata->useweightedsum, result, branchruledata->conflictprio, branchruledata->cutoffprio) );
835 
836  return SCIP_OKAY;
837 }
838 
839 /** branching execution method for not completely fixed pseudo solutions */
840 static
841 SCIP_DECL_BRANCHEXECPS(branchExecpsInference)
842 { /*lint --e{715}*/
843  SCIP_BRANCHRULEDATA* branchruledata;
844  SCIP_VAR** cands;
845  int ncands;
846 
847  SCIPdebugMsg(scip, "Execps method of inference branching\n");
848 
849  /* get branching rule data */
850  branchruledata = SCIPbranchruleGetData(branchrule);
851  assert(branchruledata != NULL);
852 
853  /* get pseudo candidates (non-fixed integer variables) */
854  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, NULL, &ncands) );
855 
856  /* perform the branching */
857  SCIP_CALL( performBranchingNoSol(scip, cands, ncands, branchruledata->conflictweight,
858  branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
859  branchruledata->useweightedsum, result) );
860 
861  return SCIP_OKAY;
862 }
863 
864 
865 /*
866  * branching specific interface methods
867  */
868 
869 /** creates the inference history branching rule and includes it in SCIP */
871  SCIP* scip /**< SCIP data structure */
872  )
873 {
874  SCIP_BRANCHRULEDATA* branchruledata;
875  SCIP_BRANCHRULE* branchrule;
876 
877  /* create inference branching rule data */
878  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
879 
880  /* include branching rule */
882  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
883 
884  assert(branchrule != NULL);
885 
886  /* set non-fundamental callbacks via specific setter functions*/
887  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyInference) );
888  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeInference) );
889  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpInference) );
890  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextInference) );
891  SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsInference) );
892 
893  /* inference branching rule parameters */
895  "branching/inference/conflictweight",
896  "weight in score calculations for conflict score",
897  &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
899  "branching/inference/inferenceweight",
900  "weight in score calculations for inference score",
901  &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
903  "branching/inference/cutoffweight",
904  "weight in score calculations for cutoff score",
905  &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
907  "branching/inference/fractionals",
908  "should branching on LP solution be restricted to the fractional variables?",
909  &branchruledata->fractionals, TRUE, DEFAULT_FRACTIONALS, NULL, NULL) );
911  "branching/inference/useweightedsum",
912  "should a weighted sum of inference, conflict and cutoff weights be used?",
913  &branchruledata->useweightedsum, FALSE, DEFAULT_USEWEIGHTEDSUM, NULL, NULL) );
914  /* inference branching rule parameters */
916  "branching/inference/reliablescore",
917  "weight in score calculations for conflict score",
918  &branchruledata->reliablescore, TRUE, DEFAULT_RELIABLESCORE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
919  /* parameters for lexicographical ordering */
921  "branching/inference/conflictprio",
922  "priority value for using conflict weights in lex. order",
923  &branchruledata->conflictprio, FALSE, DEFAULT_CONFLICTPRIO, 0, INT_MAX, NULL, NULL) );
925  "branching/inference/cutoffprio",
926  "priority value for using cutoff weights in lex. order",
927  &branchruledata->cutoffprio, FALSE, DEFAULT_CUTOFFPRIO, 0, INT_MAX, NULL, NULL) );
928 
929  return SCIP_OKAY;
930 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
static void checkValueScore(SCIP_Real value, SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *bestscore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
SCIP_RETCODE SCIPincludeBranchruleInference(SCIP *scip)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1840
static SCIP_RETCODE performBranchingSol(SCIP *scip, SCIP_VAR **cands, SCIP_Real *candsols, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Bool useweightedsum, SCIP_RESULT *result, int conflictprio, int cutoffprio)
public methods for SCIP parameter handling
public methods for branching and inference history structure
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:272
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
Definition: scip_var.c:9787
#define DEFAULT_USEWEIGHTEDSUM
public methods for memory management
#define DEFAULT_CONFLICTWEIGHT
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4843
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
SCIP_VALUEHISTORY * SCIPvarGetValuehistory(SCIP_VAR *var)
Definition: var.c:18352
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:888
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
#define FALSE
Definition: def.h:87
#define DEFAULT_CUTOFFWEIGHT
#define TRUE
Definition: def.h:86
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_DECL_BRANCHCOPY(branchCopyInference)
static void selectBestCands(SCIP *scip, SCIP_VAR **cands, SCIP_Real *candsols, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_VAR **bestcands, int *nbestcands)
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_Real SCIPhistoryGetVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:520
public methods for branching rules
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:107
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4887
static void evaluateValueCand(SCIP_VAR *cand, SCIP_Real score, SCIP_Real branchpoint, SCIP_BRANCHDIR branchdir, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestbranchpoint, SCIP_BRANCHDIR *bestbranchdir)
#define DEFAULT_CUTOFFPRIO
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: scip_branch.c:502
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
public methods for SCIP variables
static SCIP_DECL_BRANCHEXECEXT(branchExecextInference)
#define SCIPdebugMsg
Definition: scip_message.h:69
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
public methods for numerical tolerances
static SCIP_Real getAggrScore(SCIP *scip, SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
static void evaluateAggrCand(SCIP *scip, SCIP_VAR *cand, SCIP_Real score, SCIP_Real val, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestval, SCIP_VAR **bestcands, int *nbestcands)
int SCIPvaluehistoryGetNValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:351
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1041
#define DEFAULT_INFERENCEWEIGHT
static SCIP_DECL_BRANCHFREE(branchFreeInference)
#define BRANCHRULE_DESC
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:201
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1117
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:724
#define BRANCHRULE_MAXBOUNDDIST
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define SCIP_UNKNOWN
Definition: def.h:198
#define SCIP_Bool
Definition: def.h:84
int SCIPvarGetBranchPriority(SCIP_VAR *var)
Definition: var.c:18082
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1850
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:256
#define DEFAULT_FRACTIONALS
#define DEFAULT_RELIABLESCORE
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:938
#define SCIP_REAL_MAX
Definition: def.h:178
SCIP_Real SCIPhistoryGetCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:662
#define SCIP_REAL_MIN
Definition: def.h:179
public methods for branching rule plugins and branching
static SCIP_Real getValueScore(SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
SCIP_Real * SCIPvaluehistoryGetValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:371
static SCIP_DECL_BRANCHEXECLP(branchExeclpInference)
public methods for message output
SCIP_HISTORY ** SCIPvaluehistoryGetHistories(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:361
static void tiebreakAggrCand(SCIP_VAR **bestcands, int nbestcands)
#define SCIP_Real
Definition: def.h:177
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1962
#define DEFAULT_CONFLICTPRIO
inference history branching rule
public methods for message handling
static SCIP_DECL_BRANCHEXECPS(branchExecpsInference)
#define SCIP_INVALID
Definition: def.h:197
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17590
#define BRANCHRULE_NAME
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:2304
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
static SCIP_RETCODE performBranchingNoSol(SCIP *scip, SCIP_VAR **cands, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Bool useweightedsum, SCIP_RESULT *result)
SCIPallocBlockMemory(scip, subsol))
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9470
#define BRANCHRULE_PRIORITY
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
#define BRANCHRULE_MAXDEPTH
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
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9238