1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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
94   	void evaluateValueCand(
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
148  	void evaluateAggrCand(
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
182  	void tiebreakAggrCand(
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
221  	void checkValueScore(
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
263  	SCIP_Real getAggrScore(
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
294  	SCIP_Real getValueScore(
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
349  	void selectBestCands(
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
403  	SCIP_RETCODE performBranchingSol(
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
543  	SCIP_RETCODE performBranchingNoSol(
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 */
767  	   SCIP_CALL( SCIPincludeBranchruleInference(scip) );
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 */
878  	SCIP_RETCODE SCIPincludeBranchruleInference(
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 */
889  	   SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
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 */
902  	   SCIP_CALL( SCIPaddRealParam(scip,
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) );
906  	   SCIP_CALL( SCIPaddRealParam(scip,
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) );
910  	   SCIP_CALL( SCIPaddRealParam(scip,
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) );
914  	   SCIP_CALL( SCIPaddBoolParam(scip,
915  	         "branching/inference/fractionals",
916  	         "should branching on LP solution be restricted to the fractional variables?",
917  	         &branchruledata->fractionals, TRUE, DEFAULT_FRACTIONALS, NULL, NULL) );
918  	   SCIP_CALL( SCIPaddBoolParam(scip,
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 */
923  	   SCIP_CALL( SCIPaddRealParam(scip,
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 */
928  	   SCIP_CALL( SCIPaddIntParam(scip,
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) );
932  	   SCIP_CALL( SCIPaddIntParam(scip,
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  	}
939