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-2014 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch_inference.c
17  * @brief inference history branching rule
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  * @author Stefan Heinz
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include <assert.h>
26 #include <string.h>
27 
28 #include "scip/branch_inference.h"
29 
30 
31 /**@name Branching rule properties
32  *
33  * @{
34  */
35 
36 #define BRANCHRULE_NAME "inference"
37 #define BRANCHRULE_DESC "inference history branching"
38 #define BRANCHRULE_PRIORITY 1000
39 #define BRANCHRULE_MAXDEPTH -1
40 #define BRANCHRULE_MAXBOUNDDIST 1.0
41 
42 /**@} */
43 
44 /**@name Default parameter values
45  *
46  * @{
47  */
48 
49 #define DEFAULT_CONFLICTWEIGHT 1000.0 /**< weight in score calculations for conflict score */
50 #define DEFAULT_CUTOFFWEIGHT 1.0 /**< weight in score calculations for cutoff score */
51 #define DEFAULT_INFERENCEWEIGHT 1.0 /**< weight in score calculations for inference score */
52 #define DEFAULT_RELIABLESCORE 0.001 /**< score which is seen to be reliable for a branching decision */
53 #define DEFAULT_FRACTIONALS TRUE /**< should branching on LP solution be restricted to the fractional variables? */
54 #define DEFAULT_USEWEIGHTEDSUM TRUE /**< should a weighted sum of inference, conflict and cutoff weights be used? */
55 
56 /**@} */
57 
58 /** branching rule data */
59 struct SCIP_BranchruleData
60 {
61  SCIP_Real conflictweight; /**< weight in score calculations for conflict score */
62  SCIP_Real cutoffweight; /**< weight in score calculations for cutoff score */
63  SCIP_Real inferenceweight; /**< weight in score calculations for inference score */
64  SCIP_Real reliablescore; /**< score which is seen to be reliable for a branching decision */
65  SCIP_Bool fractionals; /**< should branching on LP solution be restricted to the fractional variables? */
66  SCIP_Bool useweightedsum; /**< should a weighted sum of inference, conflict and cutoff weights be used? */
67 };
68 
69 /** evaluate the given candidate with the given score against the currently best know candidate */
70 static
71 void evaluateValueCand(
72  SCIP_VAR* cand, /**< candidate to be checked */
73  SCIP_Real score, /**< score of the candidate */
74  SCIP_Real branchpoint, /**< potential branching point */
75  SCIP_BRANCHDIR branchdir, /**< potential branching direction */
76  SCIP_VAR** bestcand, /**< pointer to the currently best candidate */
77  SCIP_Real* bestscore, /**< pointer to the score of the currently best candidate */
78  SCIP_Real* bestbranchpoint, /**< pointer to store the (best) branching point */
79  SCIP_BRANCHDIR* bestbranchdir /**< pointer to store the branching direction relative to the branching point */
80  )
81 {
82  /* evaluate the candidate against the currently best candidate */
83  if( (*bestscore) < score )
84  {
85  /* the score of the candidate is better than the currently best know candidate */
86  (*bestscore) = score;
87  (*bestcand) = cand;
88  (*bestbranchpoint) = branchpoint;
89  (*bestbranchdir) = branchdir;
90  }
91  else if( (*bestscore) == score ) /*lint !e777*/
92  {
93  SCIP_Real bestobj;
94  SCIP_Real candobj;
95 
96  bestobj = REALABS(SCIPvarGetObj(*bestcand));
97  candobj = REALABS(SCIPvarGetObj(cand));
98 
99  /* the candidate has the same score as the best known candidate; therefore we use a second and third
100  * criteria to detect a unique best candidate;
101  *
102  * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
103  * since branching on that variable might trigger further propagation w.r.t. objective function
104  * - if the absolute values of the objective coefficient are equal the variable index is used to define a
105  * unique best candidate
106  *
107  * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
108  * performance to much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
109  * SCIPgetLPBranchCands()) gets dynamically changed during the solution process. In particular,
110  * starting a probing mode might already change the order of these arrays. To be independent of that
111  * the selection should be unique. Otherwise, to selection process can get influenced by starting a
112  * probing or not.
113  */
114  if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(*bestcand) < SCIPvarGetIndex(cand)) ) /*lint !e777*/
115  {
116  (*bestcand) = cand;
117  (*bestbranchpoint) = branchpoint;
118  (*bestbranchdir) = branchdir;
119  }
120  }
121 }
122 
123 /** evaluate the given candidate with the given score against the currently best know candidate */
124 static
125 void evaluateAggrCand(
126  SCIP_VAR* cand, /**< candidate to be checked */
127  SCIP_Real score, /**< score of the candidate */
128  SCIP_Real val, /**< solution value of the candidate */
129  SCIP_VAR** bestcand, /**< pointer to the currently best candidate */
130  SCIP_Real* bestscore, /**< pointer to the score of the currently best candidate */
131  SCIP_Real* bestval /**< pointer to the solution value of the currently best candidate */
132  )
133 {
134  /* evaluate the candidate against the currently best candidate */
135  if( (*bestscore) < score )
136  {
137  /* the score of the candidate is better than the currently best know candidate */
138  (*bestscore) = score;
139  (*bestcand) = cand;
140  (*bestval) = val;
141  }
142  else if( (*bestscore) == score ) /*lint !e777*/
143  {
144  SCIP_Real bestobj;
145  SCIP_Real candobj;
146 
147  bestobj = REALABS(SCIPvarGetObj(*bestcand));
148  candobj = REALABS(SCIPvarGetObj(cand));
149 
150  /* the candidate has the same score as the best known candidate; therefore we use a second and third
151  * criteria to detect a unique best candidate;
152  *
153  * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
154  * since branching on that variable might trigger further propagation w.r.t. objective function
155  * - if the absolute values of the objective coefficient are equal the variable index is used to define a
156  * unique best candidate
157  *
158  * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
159  * performance to much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
160  * SCIPgetLPBranchCands()) gets dynamically changed during the solution process. In particular,
161  * starting a probing mode might already change the order of these arrays. To be independent of that
162  * the selection should be unique. Otherwise, to selection process can get influenced by starting a
163  * probing or not.
164  */
165  if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(*bestcand) < SCIPvarGetIndex(cand)) ) /*lint !e777*/
166  {
167  (*bestcand) = cand;
168  (*bestval) = val;
169  }
170  }
171 }
172 
173 /** check if the score for the given domain value and variable domain value is better than the current best know one */
174 static
175 void checkValueScore(
176  SCIP_Real value, /**< domain value */
177  SCIP_HISTORY* history, /**< variable history for given donain value */
178  SCIP_BRANCHDIR dir, /**< branching direction */
179  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
180  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
181  SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
182  SCIP_Real* bestscore, /**< pointer to store the best score */
183  SCIP_Real* branchpoint, /**< pointer to store the (best) branching point */
184  SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
185  )
186 {
187  SCIP_Real conflictscore;
188  SCIP_Real cutoffscore;
189  SCIP_Real score;
190 
191  conflictscore = SCIPhistoryGetVSIDS(history, dir);
192  cutoffscore = SCIPhistoryGetCutoffSum(history, dir);
193 
194  /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
195  * unreliable
196  */
197  if( conflictscore < reliablescore )
198  conflictscore = 0.0;
199 
200  /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
201  if( cutoffscore < reliablescore )
202  cutoffscore = 0.0;
203 
204  /* compute weight score */
205  score = conflictweight * conflictscore + cutoffweight * cutoffscore;
206 
207  if( score > *bestscore )
208  {
209  (*bestscore) = score;
210  (*branchpoint) = value;
211  (*branchdir) = dir;
212  }
213 }
214 
215 /** return an aggregated score for the given variable using the conflict score and cutoff score */
216 static
217 SCIP_Real getAggrScore(
218  SCIP* scip, /**< SCIP data structure */
219  SCIP_VAR* var, /**< problem variable */
220  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
221  SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
222  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
223  SCIP_Real reliablescore /**< score which is seen to be reliable for a branching decision */
224  )
225 {
226  SCIP_Real conflictscore;
227  SCIP_Real cutoffscore;
228 
229  conflictscore = SCIPgetVarConflictScore(scip, var);
230  cutoffscore = SCIPgetVarAvgInferenceCutoffScore(scip, var, cutoffweight);
231 
232  /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
233  * unreliable
234  */
235  if( conflictscore < reliablescore )
236  conflictscore = 0.0;
237 
238  /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
239  if( cutoffscore < reliablescore )
240  cutoffscore = 0.0;
241 
242  /* compute weighted score for the candidate */
243  return (conflictweight * conflictscore + inferenceweight * cutoffscore);
244 }
245 
246 /** return an aggregated score for the given variable using the conflict score and cutoff score */
247 static
248 SCIP_Real getValueScore(
249  SCIP* scip, /**< SCIP data structure */
250  SCIP_VAR* var, /**< problem variable */
251  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
252  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
253  SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
254  SCIP_Real* branchpoint, /**< pointer to store the branching point */
255  SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
256  )
257 {
258  SCIP_VALUEHISTORY* valuehistory;
259  SCIP_Real bestscore;
260 
261  (*branchpoint) = SCIP_UNKNOWN;
262  (*branchdir) = SCIP_BRANCHDIR_UPWARDS;
263 
264  valuehistory = SCIPvarGetValuehistory(var);
265  bestscore = 0.0;
266 
267  if( valuehistory != NULL )
268  {
269  SCIP_HISTORY** histories;
270  SCIP_Real* values;
271  int nvalues;
272  int v;
273 
274  histories = SCIPvaluehistoryGetHistories(valuehistory);
275  values = SCIPvaluehistoryGetValues(valuehistory);
276  nvalues = SCIPvaluehistoryGetNValues(valuehistory);
277 
278  for( v = 0; v < nvalues; ++v )
279  {
280  SCIP_Real value;
281 
282  value = values[v];
283 
284  /* skip all domain values which are smaller or equal to the lower bound */
285  if( value <= SCIPvarGetLbLocal(var) )
286  continue;
287 
288  /* skip all domain values which are larger or equal to the upper bound */
289  if( value >= SCIPvarGetUbLocal(var) )
290  break;
291 
292  /* check var <= value */
293  checkValueScore(value, histories[v], SCIP_BRANCHDIR_DOWNWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir);
294 
295  /* check var >= value */
296  checkValueScore(value, histories[v], SCIP_BRANCHDIR_UPWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir);
297  }
298  }
299 
300  return bestscore;
301 }
302 
303 
304 /** selects a variable out of the given candidate array and performs the branching */
305 static
306 SCIP_RETCODE performBranching(
307  SCIP* scip, /**< SCIP data structure */
308  SCIP_VAR** cands, /**< candidate array */
309  SCIP_Real* candsols, /**< array of candidate solution values, or NULL */
310  int ncands, /**< number of candidates */
311  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
312  SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
313  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
314  SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
315  SCIP_Bool useweightedsum, /**< should a weighted sum of inference, conflict and cutoff weights be used? */
316  SCIP_RESULT* result /**< buffer to store result (branched, reduced domain, ...) */
317  )
318 {
319  SCIP_VAR* bestaggrcand;
320  SCIP_VAR* bestvaluecand;
321  SCIP_Real bestval;
322  SCIP_Real bestaggrscore;
323  SCIP_Real bestvaluescore;
324  SCIP_Real bestbranchpoint;
325  SCIP_BRANCHDIR bestbranchdir;
326  SCIP_NODE* downchild;
327  SCIP_NODE* eqchild;
328  SCIP_NODE* upchild;
329 
330  bestbranchpoint = SCIP_UNKNOWN;
331  bestbranchdir = SCIP_BRANCHDIR_DOWNWARDS;
332  bestvaluescore = 0.0;
333  bestvaluecand = NULL;
334 
335  assert(ncands > 0);
336  assert(result != NULL);
337 
338  *result = SCIP_DIDNOTFIND;
339 
340  /* check if the weighted sum between the average inferences and conflict score should be used */
341  if( useweightedsum )
342  {
343  int c;
344 
345  bestaggrcand = cands[0];
346  bestvaluecand = cands[0];
347  assert(cands[0] != NULL);
348 
349  if( candsols == NULL )
350  {
351  bestval = SCIP_UNKNOWN;
352 
353  /* get domain value score for the first candidate */
354  bestvaluescore = getValueScore(scip, cands[0], conflictweight, cutoffweight, reliablescore, &bestbranchpoint, &bestbranchdir);
355  SCIPdebugMessage("current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n",
356  SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand),
357  bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS ? "<=" : ">=", bestbranchpoint, bestvaluescore);
358  }
359  else
360  bestval = candsols[0];
361 
362  /* get aggregated score for the first candidate */
363  bestaggrscore = getAggrScore(scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore);
364 
365  for( c = 1; c < ncands; ++c )
366  {
367  SCIP_VAR* cand;
368  SCIP_Real val;
369  SCIP_Real aggrscore;
370  SCIP_Real branchpoint;
371  SCIP_BRANCHDIR branchdir;
372 
373  cand = cands[c];
374  assert(cand != NULL);
375 
376  if( candsols == NULL )
377  {
378  SCIP_Real valuescore;
379 
380  val = SCIP_UNKNOWN;
381 
382  /* get domain value score for the candidate */
383  valuescore = getValueScore(scip, cand, conflictweight, cutoffweight, reliablescore, &branchpoint, &branchdir);
384 
385  /* evaluate the candidate against the currently best candidate w.r.t. domain value score */
386  evaluateValueCand(cand, valuescore, branchpoint, branchdir, &bestvaluecand, &bestvaluescore, &bestbranchpoint, &bestbranchdir);
387 
388  SCIPdebugMessage("current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n",
389  SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand),
390  bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS ? "<=" : ">=", bestbranchpoint, bestvaluescore);
391  }
392  else
393  val = candsols[c];
394 
395  /* get aggregated score for the candidate */
396  aggrscore = getAggrScore(scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore);
397 
398  SCIPdebugMessage(" -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
399  val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore); /*lint !e777*/
400 
401  /* evaluate the candidate against the currently best candidate w.r.t. aggregated score */
402  evaluateAggrCand(cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval);
403  }
404  }
405  else
406  {
407  int c;
408 
409  bestaggrcand = cands[0];
410  assert(cands[0] != NULL);
411 
412  if( candsols != NULL )
413  bestval = candsols[0];
414  else
415  bestval = SCIP_UNKNOWN;
416 
417  bestaggrscore = SCIPgetVarAvgInferenceScore(scip, cands[0]);
418 
419  /* search for variable with best score w.r.t. average inferences per branching */
420  for( c = 1; c < ncands; ++c )
421  {
422  SCIP_VAR* cand;
423  SCIP_Real val;
424  SCIP_Real aggrscore;
425 
426  cand = cands[c];
427  assert(cand != NULL);
428 
429  if( candsols != NULL )
430  val = candsols[c];
431  else
432  val = SCIP_UNKNOWN;
433 
434  aggrscore = SCIPgetVarAvgInferenceScore(scip, cand);
435 
436  /* in case the average inferences score is below the reliable score we set it to zero since it is seen to be
437  * unreliable
438  */
439  if( aggrscore < reliablescore )
440  aggrscore = 0.0;
441 
442  SCIPdebugMessage(" -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
443  val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore); /*lint !e777*/
444 
445  /* evaluate the candidate against the currently best candidate */
446  evaluateAggrCand(cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval);
447  }
448  }
449 
450  assert(bestaggrcand != NULL);
451 
452  SCIPdebugMessage(" -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, score=%g, conflict=%g cutoff=%g, inference=%g)\n",
453  ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand),
454  bestval == SCIP_UNKNOWN ? SCIPgetVarSol(scip, bestaggrcand) : bestval, bestaggrscore, /*lint !e777*/
455  SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight),
456  SCIPgetVarAvgInferenceScore(scip, bestaggrcand));
457 
458  /* perform the branching */
459  if( candsols != NULL )
460  {
461  SCIP_CALL( SCIPbranchVarVal(scip, bestaggrcand, SCIPgetBranchingPoint(scip, bestaggrcand, bestval), &downchild, &eqchild, &upchild) );
462  }
463  else if( bestbranchpoint == SCIP_UNKNOWN ) /*lint !e777*/
464  {
465  SCIP_CALL( SCIPbranchVar(scip, bestaggrcand, &downchild, &eqchild, &upchild) );
466  }
467  else
468  {
469  SCIP_Real estimate;
470  SCIP_Real downprio;
471  SCIP_Real upprio;
472  SCIP_Real downub;
473  SCIP_Real uplb;
474 
475  assert(bestvaluecand != NULL);
476 
477  downprio = 0.0;
478  upprio = 0.0;
479 
480  if( bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS )
481  {
482  downprio = 1.0;
483  downub = bestbranchpoint;
484  uplb = bestbranchpoint + 1.0;
485  }
486  else
487  {
488  upprio = 1.0;
489  downub = bestbranchpoint - 1.0;
490  uplb = bestbranchpoint;
491  }
492 
493  /* calculate the child estimate */
494  estimate = SCIPcalcChildEstimate(scip, bestvaluecand, downub);
495 
496  /* create down child */
497  SCIP_CALL( SCIPcreateChild(scip, &downchild, downprio, estimate) );
498 
499  /* change upper bound in down child */
500  SCIP_CALL( SCIPchgVarUbNode(scip, downchild, bestvaluecand, downub) );
501 
502  /* calculate the child estimate */
503  estimate = SCIPcalcChildEstimate(scip, bestvaluecand, uplb);
504 
505  /* create up child */
506  SCIP_CALL( SCIPcreateChild(scip, &upchild, upprio, estimate) );
507 
508  /* change lower bound in up child */
509  SCIP_CALL( SCIPchgVarLbNode(scip, upchild, bestvaluecand, uplb) );
510 
511  SCIPdebugMessage("branch on variable <%s> and value <%g>\n", SCIPvarGetName(bestvaluecand), bestbranchpoint);
512 
513  eqchild = NULL;
514  }
515 
516  if( downchild != NULL || eqchild != NULL || upchild != NULL )
517  {
518  *result = SCIP_BRANCHED;
519  }
520  else
521  {
522  /* if there are no children, then variable should have been fixed by SCIPbranchVar(Val) */
523  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestaggrcand), SCIPvarGetUbLocal(bestaggrcand)));
524  *result = SCIP_REDUCEDDOM;
525  }
526 
527  return SCIP_OKAY;
528 }
529 
530 /*
531  * Callback methods
532  */
533 
534 /** copy method for branchrule plugins (called when SCIP copies plugins) */
535 static
536 SCIP_DECL_BRANCHCOPY(branchCopyInference)
537 { /*lint --e{715}*/
538  assert(scip != NULL);
539  assert(branchrule != NULL);
540  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
541 
542  /* call inclusion method of branchrule */
543  SCIP_CALL( SCIPincludeBranchruleInference(scip) );
544 
545  return SCIP_OKAY;
546 }
547 
548 /** destructor of branching rule to free user data (called when SCIP is exiting) */
549 static
550 SCIP_DECL_BRANCHFREE(branchFreeInference)
551 { /*lint --e{715}*/
552  SCIP_BRANCHRULEDATA* branchruledata;
553 
554  /* free branching rule data */
555  branchruledata = SCIPbranchruleGetData(branchrule);
556  SCIPfreeMemory(scip, &branchruledata);
557  SCIPbranchruleSetData(branchrule, NULL);
558 
559  return SCIP_OKAY;
560 }
561 
562 /** branching execution method for fractional LP solutions */
563 static
564 SCIP_DECL_BRANCHEXECLP(branchExeclpInference)
565 { /*lint --e{715}*/
566  SCIP_BRANCHRULEDATA* branchruledata;
567  SCIP_VAR** cands;
568  int ncands;
569 
570  SCIPdebugMessage("Execlp method of inference branching\n");
571 
572  /* get branching rule data */
573  branchruledata = SCIPbranchruleGetData(branchrule);
574  assert(branchruledata != NULL);
575 
576  if( branchruledata->fractionals )
577  {
578  /* get LP candidates (fractional integer variables) */
579  SCIP_CALL( SCIPgetLPBranchCands(scip, &cands, NULL, NULL, NULL, &ncands, NULL) );
580  }
581  else
582  {
583  /* get pseudo candidates (non-fixed integer variables) */
584  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, NULL, &ncands) );
585  }
586 
587  /* perform the branching */
588  SCIP_CALL( performBranching(scip, cands, NULL, ncands, branchruledata->conflictweight,
589  branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
590  branchruledata->useweightedsum, result) );
591 
592  return SCIP_OKAY;
593 }
594 
595 
596 /** branching execution method for external candidates */
597 static
598 SCIP_DECL_BRANCHEXECEXT(branchExecextInference)
599 { /*lint --e{715}*/
600  SCIP_BRANCHRULEDATA* branchruledata;
601  SCIP_VAR** cands;
602  SCIP_Real* candsols;
603  int ncands;
604 
605  SCIPdebugMessage("Execext method of inference branching\n");
606 
607  /* get branching rule data */
608  branchruledata = SCIPbranchruleGetData(branchrule);
609  assert(branchruledata != NULL);
610 
611  /* get branching candidates */
612  SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candsols, NULL, &ncands, NULL, NULL, NULL, NULL) );
613  assert(ncands > 0);
614 
615  /* perform the branching */
616  SCIP_CALL( performBranching(scip, cands, candsols, ncands, branchruledata->conflictweight,
617  branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
618  branchruledata->useweightedsum, result) );
619 
620  return SCIP_OKAY;
621 }
622 
623 /** branching execution method for not completely fixed pseudo solutions */
624 static
625 SCIP_DECL_BRANCHEXECPS(branchExecpsInference)
626 { /*lint --e{715}*/
627  SCIP_BRANCHRULEDATA* branchruledata;
628  SCIP_VAR** cands;
629  int ncands;
630 
631  SCIPdebugMessage("Execps method of inference branching\n");
632 
633  /* get branching rule data */
634  branchruledata = SCIPbranchruleGetData(branchrule);
635  assert(branchruledata != NULL);
636 
637  /* get pseudo candidates (non-fixed integer variables) */
638  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, NULL, &ncands) );
639 
640  /* perform the branching */
641  SCIP_CALL( performBranching(scip, cands, NULL, ncands, branchruledata->conflictweight,
642  branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
643  branchruledata->useweightedsum, result) );
644 
645  return SCIP_OKAY;
646 }
647 
648 
649 /*
650  * branching specific interface methods
651  */
652 
653 /** creates the inference history branching rule and includes it in SCIP */
654 SCIP_RETCODE SCIPincludeBranchruleInference(
655  SCIP* scip /**< SCIP data structure */
656  )
657 {
658  SCIP_BRANCHRULEDATA* branchruledata;
659  SCIP_BRANCHRULE* branchrule;
660 
661  /* create inference branching rule data */
662  SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
663 
664  /* include branching rule */
665  SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
666  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
667 
668  assert(branchrule != NULL);
669 
670  /* set non-fundamental callbacks via specific setter functions*/
671  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyInference) );
672  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeInference) );
673  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpInference) );
674  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextInference) );
675  SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsInference) );
676 
677  /* inference branching rule parameters */
678  SCIP_CALL( SCIPaddRealParam(scip,
679  "branching/inference/conflictweight",
680  "weight in score calculations for conflict score",
681  &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
682  SCIP_CALL( SCIPaddRealParam(scip,
683  "branching/inference/inferenceweight",
684  "weight in score calculations for inference score",
685  &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
686  SCIP_CALL( SCIPaddRealParam(scip,
687  "branching/inference/cutoffweight",
688  "weight in score calculations for cutoff score",
689  &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
690  SCIP_CALL( SCIPaddBoolParam(scip,
691  "branching/inference/fractionals",
692  "should branching on LP solution be restricted to the fractional variables?",
693  &branchruledata->fractionals, TRUE, DEFAULT_FRACTIONALS, NULL, NULL) );
694  SCIP_CALL( SCIPaddBoolParam(scip,
695  "branching/inference/useweightedsum",
696  "should a weighted sum of inference, conflict and cutoff weights be used?",
697  &branchruledata->useweightedsum, FALSE, DEFAULT_USEWEIGHTEDSUM, NULL, NULL) );
698  /* inference branching rule parameters */
699  SCIP_CALL( SCIPaddRealParam(scip,
700  "branching/inference/reliablescore",
701  "weight in score calculations for conflict score",
702  &branchruledata->reliablescore, TRUE, DEFAULT_RELIABLESCORE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
703 
704  return SCIP_OKAY;
705 }
706