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-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file 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 /**@} */
66 
67 /** branching rule data */
68 struct SCIP_BranchruleData
69 {
70  SCIP_Real conflictweight; /**< weight in score calculations for conflict score */
71  SCIP_Real cutoffweight; /**< weight in score calculations for cutoff score */
72  SCIP_Real inferenceweight; /**< weight in score calculations for inference score */
73  SCIP_Real reliablescore; /**< score which is seen to be reliable for a branching decision */
74  SCIP_Bool fractionals; /**< should branching on LP solution be restricted to the fractional variables? */
75  SCIP_Bool useweightedsum; /**< should a weighted sum of inference, conflict and cutoff weights be used? */
76 };
77 
78 /** evaluate the given candidate with the given score against the currently best know candidate */
79 static
81  SCIP_VAR* cand, /**< candidate to be checked */
82  SCIP_Real score, /**< score of the candidate */
83  SCIP_Real branchpoint, /**< potential branching point */
84  SCIP_BRANCHDIR branchdir, /**< potential branching direction */
85  SCIP_VAR** bestcand, /**< pointer to the currently best candidate */
86  SCIP_Real* bestscore, /**< pointer to the score of the currently best candidate */
87  SCIP_Real* bestbranchpoint, /**< pointer to store the (best) branching point */
88  SCIP_BRANCHDIR* bestbranchdir /**< pointer to store the branching direction relative to the branching point */
89  )
90 {
91  /* evaluate the candidate against the currently best candidate */
92  if( (*bestscore) < score )
93  {
94  /* the score of the candidate is better than the currently best know candidate */
95  (*bestscore) = score;
96  (*bestcand) = cand;
97  (*bestbranchpoint) = branchpoint;
98  (*bestbranchdir) = branchdir;
99  }
100  else if( (*bestscore) == score ) /*lint !e777*/
101  {
102  SCIP_Real bestobj;
103  SCIP_Real candobj;
104 
105  bestobj = REALABS(SCIPvarGetObj(*bestcand));
106  candobj = REALABS(SCIPvarGetObj(cand));
107 
108  /* the candidate has the same score as the best known candidate; therefore we use a second and third
109  * criteria to detect a unique best candidate;
110  *
111  * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
112  * since branching on that variable might trigger further propagation w.r.t. objective function
113  * - if the absolute values of the objective coefficient are equal the variable index is used to define a
114  * unique best candidate
115  *
116  * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
117  * performance to much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
118  * SCIPgetLPBranchCands()) gets dynamically changed during the solution process. In particular,
119  * starting a probing mode might already change the order of these arrays. To be independent of that
120  * the selection should be unique. Otherwise, to selection process can get influenced by starting a
121  * probing or not.
122  */
123  if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(*bestcand) < SCIPvarGetIndex(cand)) ) /*lint !e777*/
124  {
125  (*bestcand) = cand;
126  (*bestbranchpoint) = branchpoint;
127  (*bestbranchdir) = branchdir;
128  }
129  }
130 }
131 
132 /** evaluate the given candidate with the given score against the currently best know candidate */
133 static
135  SCIP_VAR* cand, /**< candidate to be checked */
136  SCIP_Real score, /**< score of the candidate */
137  SCIP_Real val, /**< solution value of the candidate */
138  SCIP_VAR** bestcand, /**< pointer to the currently best candidate */
139  SCIP_Real* bestscore, /**< pointer to the score of the currently best candidate */
140  SCIP_Real* bestval /**< pointer to the solution value of the currently best candidate */
141  )
142 {
143  /* evaluate the candidate against the currently best candidate */
144  if( (*bestscore) < score )
145  {
146  /* the score of the candidate is better than the currently best know candidate */
147  (*bestscore) = score;
148  (*bestcand) = cand;
149  (*bestval) = val;
150  }
151  else if( (*bestscore) == score ) /*lint !e777*/
152  {
153  SCIP_Real bestobj;
154  SCIP_Real candobj;
155 
156  bestobj = REALABS(SCIPvarGetObj(*bestcand));
157  candobj = REALABS(SCIPvarGetObj(cand));
158 
159  /* the candidate has the same score as the best known candidate; therefore we use a second and third
160  * criteria to detect a unique best candidate;
161  *
162  * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
163  * since branching on that variable might trigger further propagation w.r.t. objective function
164  * - if the absolute values of the objective coefficient are equal the variable index is used to define a
165  * unique best candidate
166  *
167  * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
168  * performance to much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
169  * SCIPgetLPBranchCands()) gets dynamically changed during the solution process. In particular,
170  * starting a probing mode might already change the order of these arrays. To be independent of that
171  * the selection should be unique. Otherwise, to selection process can get influenced by starting a
172  * probing or not.
173  */
174  if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(*bestcand) < SCIPvarGetIndex(cand)) ) /*lint !e777*/
175  {
176  (*bestcand) = cand;
177  (*bestval) = val;
178  }
179  }
180 }
181 
182 /** check if the score for the given domain value and variable domain value is better than the current best know one */
183 static
185  SCIP_Real value, /**< domain value */
186  SCIP_HISTORY* history, /**< variable history for given donain value */
187  SCIP_BRANCHDIR dir, /**< branching direction */
188  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
189  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
190  SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
191  SCIP_Real* bestscore, /**< pointer to store the best score */
192  SCIP_Real* branchpoint, /**< pointer to store the (best) branching point */
193  SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
194  )
195 {
196  SCIP_Real conflictscore;
197  SCIP_Real cutoffscore;
198  SCIP_Real score;
199 
200  conflictscore = SCIPhistoryGetVSIDS(history, dir);
201  cutoffscore = SCIPhistoryGetCutoffSum(history, dir);
202 
203  /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
204  * unreliable
205  */
206  if( conflictscore < reliablescore )
207  conflictscore = 0.0;
208 
209  /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
210  if( cutoffscore < reliablescore )
211  cutoffscore = 0.0;
212 
213  /* compute weight score */
214  score = conflictweight * conflictscore + cutoffweight * cutoffscore;
215 
216  if( score > *bestscore )
217  {
218  (*bestscore) = score;
219  (*branchpoint) = value;
220  (*branchdir) = dir;
221  }
222 }
223 
224 /** return an aggregated score for the given variable using the conflict score and cutoff score */
225 static
227  SCIP* scip, /**< SCIP data structure */
228  SCIP_VAR* var, /**< problem variable */
229  SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
230  SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
231  SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
232  SCIP_Real reliablescore /**< score which is seen to be reliable for a branching decision */
233  )
234 {
235  SCIP_Real conflictscore;
236  SCIP_Real cutoffscore;
237 
238  conflictscore = SCIPgetVarConflictScore(scip, var);
239  cutoffscore = SCIPgetVarAvgInferenceCutoffScore(scip, var, cutoffweight);
240 
241  /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
242  * unreliable
243  */
244  if( conflictscore < reliablescore )
245  conflictscore = 0.0;
246 
247  /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
248  if( cutoffscore < reliablescore )
249  cutoffscore = 0.0;
250 
251  /* compute weighted score for the candidate */
252  return (conflictweight * conflictscore + inferenceweight * cutoffscore);
253 }
254 
255 /** return an aggregated score for the given variable using the conflict score and cutoff score */
256 static
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(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(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  /*lint -e777*/
407  SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
408  val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore);
409 
410  /* evaluate the candidate against the currently best candidate w.r.t. aggregated score */
411  evaluateAggrCand(cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval);
412  }
413  }
414  else
415  {
416  int c;
417 
418  bestaggrcand = cands[0];
419  assert(cands[0] != NULL);
420 
421  if( candsols != NULL )
422  bestval = candsols[0];
423  else
424  bestval = SCIP_UNKNOWN;
425 
426  bestaggrscore = SCIPgetVarAvgInferenceScore(scip, cands[0]);
427 
428  /* search for variable with best score w.r.t. average inferences per branching */
429  for( c = 1; c < ncands; ++c )
430  {
431  SCIP_VAR* cand;
432  SCIP_Real val;
433  SCIP_Real aggrscore;
434 
435  cand = cands[c];
436  assert(cand != NULL);
437 
438  if( candsols != NULL )
439  val = candsols[c];
440  else
441  val = SCIP_UNKNOWN;
442 
443  aggrscore = SCIPgetVarAvgInferenceScore(scip, cand);
444 
445  /* in case the average inferences score is below the reliable score we set it to zero since it is seen to be
446  * unreliable
447  */
448  if( aggrscore < reliablescore )
449  aggrscore = 0.0;
450 
451  SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
452  val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore); /*lint !e777*/
453 
454  /* evaluate the candidate against the currently best candidate */
455  evaluateAggrCand(cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval);
456  }
457  }
458 
459  assert(bestaggrcand != NULL);
460 
461  SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, score=%g, conflict=%g cutoff=%g, inference=%g)\n",
462  ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand),
463  bestval == SCIP_UNKNOWN ? SCIPgetVarSol(scip, bestaggrcand) : bestval, bestaggrscore, /*lint !e777*/
464  SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight),
465  SCIPgetVarAvgInferenceScore(scip, bestaggrcand));
466 
467  /* perform the branching */
468  if( candsols != NULL )
469  {
470  SCIP_CALL( SCIPbranchVarVal(scip, bestaggrcand, SCIPgetBranchingPoint(scip, bestaggrcand, bestval), &downchild, &eqchild, &upchild) );
471  }
472  else if( bestbranchpoint == SCIP_UNKNOWN ) /*lint !e777*/
473  {
474  SCIP_CALL( SCIPbranchVar(scip, bestaggrcand, &downchild, &eqchild, &upchild) );
475  }
476  else
477  {
478  SCIP_Real estimate;
479  SCIP_Real downprio;
480  SCIP_Real upprio;
481  SCIP_Real downub;
482  SCIP_Real uplb;
483 
484  assert(bestvaluecand != NULL);
485 
486  downprio = 0.0;
487  upprio = 0.0;
488 
489  if( bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS )
490  {
491  downprio = 1.0;
492  downub = bestbranchpoint;
493  uplb = bestbranchpoint + 1.0;
494  }
495  else
496  {
497  upprio = 1.0;
498  downub = bestbranchpoint - 1.0;
499  uplb = bestbranchpoint;
500  }
501 
502  /* calculate the child estimate */
503  estimate = SCIPcalcChildEstimate(scip, bestvaluecand, downub);
504 
505  /* create down child */
506  SCIP_CALL( SCIPcreateChild(scip, &downchild, downprio, estimate) );
507 
508  /* change upper bound in down child */
509  SCIP_CALL( SCIPchgVarUbNode(scip, downchild, bestvaluecand, downub) );
510 
511  /* calculate the child estimate */
512  estimate = SCIPcalcChildEstimate(scip, bestvaluecand, uplb);
513 
514  /* create up child */
515  SCIP_CALL( SCIPcreateChild(scip, &upchild, upprio, estimate) );
516 
517  /* change lower bound in up child */
518  SCIP_CALL( SCIPchgVarLbNode(scip, upchild, bestvaluecand, uplb) );
519 
520  SCIPdebugMsg(scip, "branch on variable <%s> and value <%g>\n", SCIPvarGetName(bestvaluecand), bestbranchpoint);
521 
522  eqchild = NULL;
523  }
524 
525  if( downchild != NULL || eqchild != NULL || upchild != NULL )
526  {
527  *result = SCIP_BRANCHED;
528  }
529  else
530  {
531  /* if there are no children, then variable should have been fixed by SCIPbranchVar(Val) */
532  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestaggrcand), SCIPvarGetUbLocal(bestaggrcand)));
533  *result = SCIP_REDUCEDDOM;
534  }
535 
536  return SCIP_OKAY;
537 }
538 
539 /*
540  * Callback methods
541  */
542 
543 /** copy method for branchrule plugins (called when SCIP copies plugins) */
544 static
545 SCIP_DECL_BRANCHCOPY(branchCopyInference)
546 { /*lint --e{715}*/
547  assert(scip != NULL);
548  assert(branchrule != NULL);
549  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
550 
551  /* call inclusion method of branchrule */
553 
554  return SCIP_OKAY;
555 }
556 
557 /** destructor of branching rule to free user data (called when SCIP is exiting) */
558 static
559 SCIP_DECL_BRANCHFREE(branchFreeInference)
560 { /*lint --e{715}*/
561  SCIP_BRANCHRULEDATA* branchruledata;
562 
563  /* free branching rule data */
564  branchruledata = SCIPbranchruleGetData(branchrule);
565  SCIPfreeBlockMemory(scip, &branchruledata);
566  SCIPbranchruleSetData(branchrule, NULL);
567 
568  return SCIP_OKAY;
569 }
570 
571 /** branching execution method for fractional LP solutions */
572 static
573 SCIP_DECL_BRANCHEXECLP(branchExeclpInference)
574 { /*lint --e{715}*/
575  SCIP_BRANCHRULEDATA* branchruledata;
576  SCIP_VAR** cands;
577  int ncands;
578 
579  SCIPdebugMsg(scip, "Execlp method of inference branching\n");
580 
581  /* get branching rule data */
582  branchruledata = SCIPbranchruleGetData(branchrule);
583  assert(branchruledata != NULL);
584 
585  if( branchruledata->fractionals )
586  {
587  /* get LP candidates (fractional integer variables) */
588  SCIP_CALL( SCIPgetLPBranchCands(scip, &cands, NULL, NULL, NULL, &ncands, NULL) );
589  }
590  else
591  {
592  /* get pseudo candidates (non-fixed integer variables) */
593  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, NULL, &ncands) );
594  }
595 
596  /* perform the branching */
597  SCIP_CALL( performBranching(scip, cands, NULL, ncands, branchruledata->conflictweight,
598  branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
599  branchruledata->useweightedsum, result) );
600 
601  return SCIP_OKAY;
602 }
603 
604 
605 /** branching execution method for external candidates */
606 static
607 SCIP_DECL_BRANCHEXECEXT(branchExecextInference)
608 { /*lint --e{715}*/
609  SCIP_BRANCHRULEDATA* branchruledata;
610  SCIP_VAR** cands;
611  SCIP_Real* candsols;
612  int ncands;
613 
614  SCIPdebugMsg(scip, "Execext method of inference branching\n");
615 
616  /* get branching rule data */
617  branchruledata = SCIPbranchruleGetData(branchrule);
618  assert(branchruledata != NULL);
619 
620  /* get branching candidates */
621  SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candsols, NULL, &ncands, NULL, NULL, NULL, NULL) );
622  assert(ncands > 0);
623 
624  /* perform the branching */
625  SCIP_CALL( performBranching(scip, cands, candsols, ncands, branchruledata->conflictweight,
626  branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
627  branchruledata->useweightedsum, result) );
628 
629  return SCIP_OKAY;
630 }
631 
632 /** branching execution method for not completely fixed pseudo solutions */
633 static
634 SCIP_DECL_BRANCHEXECPS(branchExecpsInference)
635 { /*lint --e{715}*/
636  SCIP_BRANCHRULEDATA* branchruledata;
637  SCIP_VAR** cands;
638  int ncands;
639 
640  SCIPdebugMsg(scip, "Execps method of inference branching\n");
641 
642  /* get branching rule data */
643  branchruledata = SCIPbranchruleGetData(branchrule);
644  assert(branchruledata != NULL);
645 
646  /* get pseudo candidates (non-fixed integer variables) */
647  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, NULL, &ncands) );
648 
649  /* perform the branching */
650  SCIP_CALL( performBranching(scip, cands, NULL, ncands, branchruledata->conflictweight,
651  branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
652  branchruledata->useweightedsum, result) );
653 
654  return SCIP_OKAY;
655 }
656 
657 
658 /*
659  * branching specific interface methods
660  */
661 
662 /** creates the inference history branching rule and includes it in SCIP */
664  SCIP* scip /**< SCIP data structure */
665  )
666 {
667  SCIP_BRANCHRULEDATA* branchruledata;
668  SCIP_BRANCHRULE* branchrule;
669 
670  /* create inference branching rule data */
671  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
672 
673  /* include branching rule */
675  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
676 
677  assert(branchrule != NULL);
678 
679  /* set non-fundamental callbacks via specific setter functions*/
680  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyInference) );
681  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeInference) );
682  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpInference) );
683  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextInference) );
684  SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsInference) );
685 
686  /* inference branching rule parameters */
688  "branching/inference/conflictweight",
689  "weight in score calculations for conflict score",
690  &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
692  "branching/inference/inferenceweight",
693  "weight in score calculations for inference score",
694  &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
696  "branching/inference/cutoffweight",
697  "weight in score calculations for cutoff score",
698  &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
700  "branching/inference/fractionals",
701  "should branching on LP solution be restricted to the fractional variables?",
702  &branchruledata->fractionals, TRUE, DEFAULT_FRACTIONALS, NULL, NULL) );
704  "branching/inference/useweightedsum",
705  "should a weighted sum of inference, conflict and cutoff weights be used?",
706  &branchruledata->useweightedsum, FALSE, DEFAULT_USEWEIGHTEDSUM, NULL, NULL) );
707  /* inference branching rule parameters */
709  "branching/inference/reliablescore",
710  "weight in score calculations for conflict score",
711  &branchruledata->reliablescore, TRUE, DEFAULT_RELIABLESCORE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
712 
713  return SCIP_OKAY;
714 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
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 SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4847
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
Definition: scip_var.c:9723
public methods for SCIP parameter handling
public methods for branching and inference history structure
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
#define DEFAULT_USEWEIGHTEDSUM
public methods for memory management
#define DEFAULT_CONFLICTWEIGHT
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:888
SCIP_EXPORT SCIP_VALUEHISTORY * SCIPvarGetValuehistory(SCIP_VAR *var)
Definition: var.c:18104
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
#define FALSE
Definition: def.h:73
#define DEFAULT_CUTOFFWEIGHT
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17510
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_DECL_BRANCHCOPY(branchCopyInference)
public methods for problem variables
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
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_Real SCIPhistoryGetVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:520
public methods for branching rules
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_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
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
static SCIP_DECL_BRANCHEXECEXT(branchExecextInference)
#define SCIPdebugMsg
Definition: scip_message.h:69
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 SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:724
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9174
int SCIPvaluehistoryGetNValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:351
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17012
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:272
SCIP_EXPORT int SCIPvarGetBranchPriority(SCIP_VAR *var)
Definition: var.c:17834
#define DEFAULT_INFERENCEWEIGHT
static SCIP_DECL_BRANCHFREE(branchFreeInference)
#define BRANCHRULE_DESC
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 NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:187
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPincludeBranchruleInference(SCIP *scip)
#define BRANCHRULE_MAXBOUNDDIST
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1041
#define SCIP_UNKNOWN
Definition: def.h:184
#define SCIP_Bool
Definition: def.h:70
#define DEFAULT_FRACTIONALS
#define DEFAULT_RELIABLESCORE
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:256
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17718
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:938
#define SCIP_REAL_MAX
Definition: def.h:164
SCIP_Real SCIPhistoryGetCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:662
#define SCIP_REAL_MIN
Definition: def.h:165
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17728
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_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:361
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:2311
#define SCIP_Real
Definition: def.h:163
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
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 SCIP_DECL_BRANCHEXECPS(branchExecpsInference)
#define BRANCHRULE_NAME
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9406
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4891
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
#define BRANCHRULE_PRIORITY
#define BRANCHRULE_MAXDEPTH
SCIP_EXPORT int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17345