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