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