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_allfullstrong.c
26   	 * @ingroup DEFPLUGINS_BRANCH
27   	 * @brief  all variables full strong LP branching rule
28   	 * @author Tobias Achterberg
29   	 *
30   	 * The all variables full strong branching rule applies strong branching to every non-fixed variable
31   	 * at the current node of the branch-and-bound search. The rule selects the candidate
32   	 * which will cause the highest gain of the dual bound in the created sub-tree among all branching variables.
33   	 *
34   	 * For calculating the gain, a look-ahead is performed by solving the child node LPs which will result
35   	 * from branching on a variable.
36   	 *
37   	 * For a more mathematical description and a comparison between the strong branching rule and other branching rules
38   	 * in SCIP, we refer to
39   	 *
40   	 * @par
41   	 * Tobias Achterberg@n
42   	 * Constraint Integer Programming@n
43   	 * PhD Thesis, Technische Universität Berlin, 2007@n
44   	 *
45   	 */
46   	
47   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
48   	
49   	#include "blockmemshell/memory.h"
50   	#include "scip/branch_allfullstrong.h"
51   	#include "scip/pub_branch.h"
52   	#include "scip/pub_message.h"
53   	#include "scip/pub_tree.h"
54   	#include "scip/pub_var.h"
55   	#include "scip/scip_branch.h"
56   	#include "scip/scip_general.h"
57   	#include "scip/scip_lp.h"
58   	#include "scip/scip_mem.h"
59   	#include "scip/scip_message.h"
60   	#include "scip/scip_numerics.h"
61   	#include "scip/scip_prob.h"
62   	#include "scip/scip_solvingstats.h"
63   	#include "scip/scip_tree.h"
64   	#include "scip/scip_var.h"
65   	#include <string.h>
66   	
67   	
68   	#define BRANCHRULE_NAME          "allfullstrong"
69   	#define BRANCHRULE_DESC          "all variables full strong branching"
70   	#define BRANCHRULE_PRIORITY      -1000
71   	#define BRANCHRULE_MAXDEPTH      -1
72   	#define BRANCHRULE_MAXBOUNDDIST  1.0
73   	
74   	
75   	/** branching rule data */
76   	struct SCIP_BranchruleData
77   	{
78   	   int                   lastcand;           /**< last evaluated candidate of last branching rule execution */
79   	   int                   skipsize;           /**< size of skipdown and skipup array */
80   	   SCIP_Bool*            skipdown;           /**< should down branch be skiped? */
81   	   SCIP_Bool*            skipup;             /**< should up branch be skiped? */
82   	};
83   	
84   	
85   	/** performs the all fullstrong branching */
86   	static
87   	SCIP_RETCODE branch(
88   	   SCIP*                 scip,               /**< SCIP data structure */
89   	   SCIP_BRANCHRULE*      branchrule,         /**< branching rule */
90   	   SCIP_RESULT*          result              /**< pointer to store the result of the callback method */
91   	   )
92   	{
93   	   SCIP_BRANCHRULEDATA* branchruledata;
94   	   SCIP_VAR** pseudocands;
95   	   SCIP_VAR** pseudocandscopy;
96   	   SCIP_Real bestdown;
97   	   SCIP_Real bestup;
98   	   SCIP_Real bestscore;
99   	   SCIP_Real provedbound;
100  	   SCIP_Bool exactsolve;
101  	   SCIP_Bool allcolsinlp;
102  	   SCIP_Bool bestdownvalid;
103  	   SCIP_Bool bestupvalid;
104  	   int npseudocands;
105  	   int npriopseudocands;
106  	   int bestpseudocand;
107  	#ifndef NDEBUG
108  	   SCIP_Real cutoffbound;
109  	   cutoffbound = SCIPgetCutoffbound(scip);
110  	#endif
111  	
112  	   assert(branchrule != NULL);
113  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
114  	   assert(scip != NULL);
115  	   assert(result != NULL);
116  	
117  	   /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
118  	   allcolsinlp = SCIPallColsInLP(scip);
119  	
120  	   /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
121  	    * for cutting off sub problems and improving lower bounds of children
122  	    */
123  	   exactsolve = SCIPisExactSolve(scip);
124  	
125  	   /* get branching rule data */
126  	   branchruledata = SCIPbranchruleGetData(branchrule);
127  	   assert(branchruledata != NULL);
128  	
129  	   if( branchruledata->skipdown == NULL )
130  	   {
131  	      assert(branchruledata->skipup == NULL);
132  	
133  	      branchruledata->skipsize = SCIPgetNVars(scip);
134  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
135  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
136  	      BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
137  	      BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
138  	   }
139  	
140  	   /* get all non-fixed variables (not only the fractional ones) */
141  	   SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &npseudocands, &npriopseudocands) );
142  	   assert(npseudocands > 0);
143  	   assert(npriopseudocands > 0);
144  	
145  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &pseudocandscopy, pseudocands, npseudocands) );
146  	
147  	   SCIP_CALL( SCIPselectVarPseudoStrongBranching(scip, pseudocandscopy, branchruledata->skipdown, branchruledata->skipup, npseudocands,
148  	         npriopseudocands, &bestpseudocand, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
149  	
150  	   if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
151  	   {
152  	      SCIP_NODE* downchild;
153  	      SCIP_NODE* eqchild;
154  	      SCIP_NODE* upchild;
155  	      SCIP_VAR* var;
156  	
157  	      assert(*result == SCIP_DIDNOTRUN);
158  	      assert(0 <= bestpseudocand && bestpseudocand < npseudocands);
159  	      assert(SCIPisLT(scip, provedbound, cutoffbound));
160  	
161  	      var = pseudocandscopy[bestpseudocand];
162  	
163  	      /* perform the branching */
164  	      SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s>[%g,%g] (solval=%g, down=%g, up=%g, score=%g)\n",
165  	         npseudocands, bestpseudocand, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLPSol(var),
166  	         bestdown, bestup, bestscore);
167  	      SCIP_CALL( SCIPbranchVarVal(scip, var, SCIPvarGetLPSol(var), &downchild, &eqchild, &upchild) );
168  	
169  	      /* update the lower bounds in the children */
170  	      if( allcolsinlp && !exactsolve )
171  	      {
172  	         if( downchild != NULL )
173  	         {
174  	            SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
175  	            SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
176  	         }
177  	         if( eqchild != NULL )
178  	         {
179  	            SCIP_CALL( SCIPupdateNodeLowerbound(scip, eqchild, provedbound) );
180  	            SCIPdebugMsg(scip, " -> eq child's lowerbound:   %g\n", SCIPnodeGetLowerbound(eqchild));
181  	         }
182  	         if( upchild != NULL )
183  	         {
184  	            SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
185  	            SCIPdebugMsg(scip, " -> up child's lowerbound:   %g\n", SCIPnodeGetLowerbound(upchild));
186  	         }
187  	      }
188  	
189  	      *result = SCIP_BRANCHED;
190  	   }
191  	
192  	   SCIPfreeBufferArray(scip, &pseudocandscopy);
193  	
194  	   return SCIP_OKAY;
195  	}
196  	
197  	
198  	/*
199  	 * Callback methods
200  	 */
201  	
202  	/** copy method for branchrule plugins (called when SCIP copies plugins) */
203  	static
204  	SCIP_DECL_BRANCHCOPY(branchCopyAllfullstrong)
205  	{  /*lint --e{715}*/
206  	   assert(scip != NULL);
207  	   assert(branchrule != NULL);
208  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
209  	
210  	   /* call inclusion method of branchrule */
211  	   SCIP_CALL( SCIPincludeBranchruleAllfullstrong(scip) );
212  	
213  	   return SCIP_OKAY;
214  	}
215  	
216  	/** destructor of branching rule to free user data (called when SCIP is exiting) */
217  	static
218  	SCIP_DECL_BRANCHFREE(branchFreeAllfullstrong)
219  	{  /*lint --e{715}*/
220  	   SCIP_BRANCHRULEDATA* branchruledata;
221  	
222  	   /* free branching rule data */
223  	   branchruledata = SCIPbranchruleGetData(branchrule);
224  	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize);
225  	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize);
226  	
227  	   SCIPfreeBlockMemory(scip, &branchruledata);
228  	   SCIPbranchruleSetData(branchrule, NULL);
229  	
230  	   return SCIP_OKAY;
231  	}
232  	
233  	
234  	/** initialization method of branching rule (called after problem was transformed) */
235  	static
236  	SCIP_DECL_BRANCHINIT(branchInitAllfullstrong)
237  	{  /*lint --e{715}*/
238  	   SCIP_BRANCHRULEDATA* branchruledata;
239  	
240  	   /* initialize branching rule data */
241  	   branchruledata = SCIPbranchruleGetData(branchrule);
242  	   branchruledata->lastcand = 0;
243  	
244  	   return SCIP_OKAY;
245  	}
246  	
247  	
248  	/** branching execution method for fractional LP solutions */
249  	static
250  	SCIP_DECL_BRANCHEXECLP(branchExeclpAllfullstrong)
251  	{  /*lint --e{715}*/
252  	   assert(result != NULL);
253  	
254  	   SCIPdebugMsg(scip, "Execlp method of allfullstrong branching\n");
255  	
256  	   *result = SCIP_DIDNOTRUN;
257  	
258  	   SCIP_CALL( branch(scip, branchrule, result) );
259  	
260  	   return SCIP_OKAY;
261  	}
262  	
263  	
264  	/** branching execution method for not completely fixed pseudo solutions */
265  	static
266  	SCIP_DECL_BRANCHEXECPS(branchExecpsAllfullstrong)
267  	{  /*lint --e{715}*/
268  	   assert(result != NULL);
269  	
270  	   SCIPdebugMsg(scip, "Execps method of allfullstrong branching\n");
271  	
272  	   *result = SCIP_DIDNOTRUN;
273  	
274  	   if( SCIPhasCurrentNodeLP(scip) )
275  	   {
276  	      SCIP_CALL( branch(scip, branchrule, result) );
277  	   }
278  	
279  	   return SCIP_OKAY;
280  	}
281  	
282  	
283  	/*
284  	 * branching specific interface methods
285  	 */
286  	/**
287  	 * Selects a variable from a set of candidates by strong branching
288  	 *
289  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
290  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
291  	 *
292  	 * @note The variables in the lpcands array must have a fractional value in the current LP solution
293  	 */
294  	SCIP_RETCODE SCIPselectVarPseudoStrongBranching(
295  	   SCIP*                 scip,               /**< original SCIP data structure                        */
296  	   SCIP_VAR**            pseudocands,        /**< branching candidates                                */
297  	   SCIP_Bool*            skipdown,           /**< should down branchings be skipped? */
298  	   SCIP_Bool*            skipup,             /**< should up branchings be skipped? */
299  	   int                   npseudocands,       /**< number of branching candidates                      */
300  	   int                   npriopseudocands,   /**< number of priority branching candidates             */
301  	   int*                  bestpseudocand,     /**< best candidate for branching                        */
302  	   SCIP_Real*            bestdown,           /**< objective value of the down branch for bestcand     */
303  	   SCIP_Real*            bestup,             /**< objective value of the up branch for bestcand       */
304  	   SCIP_Real*            bestscore,          /**< score for bestcand                                  */
305  	   SCIP_Bool*            bestdownvalid,      /**< is bestdown a valid dual bound for the down branch? */
306  	   SCIP_Bool*            bestupvalid,        /**< is bestup a valid dual bound for the up branch?     */
307  	   SCIP_Real*            provedbound,        /**< proved dual bound for current subtree               */
308  	   SCIP_RESULT*          result              /**< result pointer                                      */
309  	   )
310  	{  /*lint --e{715}*/
311  	   SCIP_Real lpobjval;
312  	   SCIP_Bool allcolsinlp;
313  	   SCIP_Bool exactsolve;
314  	#ifndef NDEBUG
315  	   SCIP_Real cutoffbound;
316  	   cutoffbound = SCIPgetCutoffbound(scip);
317  	#endif
318  	
319  	   assert(scip != NULL);
320  	   assert(pseudocands != NULL);
321  	   assert(bestpseudocand != NULL);
322  	   assert(skipdown != NULL);
323  	   assert(skipup != NULL);
324  	   assert(bestdown != NULL);
325  	   assert(bestup != NULL);
326  	   assert(bestscore != NULL);
327  	   assert(bestdownvalid != NULL);
328  	   assert(bestupvalid != NULL);
329  	   assert(provedbound != NULL);
330  	   assert(result != NULL);
331  	   assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
332  	
333  	   /* get current LP objective bound of the local sub problem and global cutoff bound */
334  	   lpobjval = SCIPgetLPObjval(scip);
335  	
336  	   /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
337  	    * for cutting off sub problems and improving lower bounds of children
338  	    */
339  	   exactsolve = SCIPisExactSolve(scip);
340  	
341  	   /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
342  	   allcolsinlp = SCIPallColsInLP(scip);
343  	
344  	   /* if only one candidate exists, choose this one without applying strong branching */
345  	   *bestpseudocand = 0;
346  	   *bestdown = lpobjval;
347  	   *bestup = lpobjval;
348  	   *bestdownvalid = TRUE;
349  	   *bestupvalid = TRUE;
350  	   *bestscore = -SCIPinfinity(scip);
351  	   *provedbound = lpobjval;
352  	   if( npseudocands > 1 )
353  	   {
354  	      SCIP_BRANCHRULE* branchrule;
355  	      SCIP_BRANCHRULEDATA* branchruledata;
356  	
357  	      SCIP_Real solval;
358  	      SCIP_Real down;
359  	      SCIP_Real up;
360  	      SCIP_Real downgain;
361  	      SCIP_Real upgain;
362  	      SCIP_Real score;
363  	      SCIP_Bool integral;
364  	      SCIP_Bool lperror;
365  	      SCIP_Bool downvalid;
366  	      SCIP_Bool upvalid;
367  	      SCIP_Bool downinf;
368  	      SCIP_Bool upinf;
369  	      SCIP_Bool downconflict;
370  	      SCIP_Bool upconflict;
371  	      int nsbcalls;
372  	      int i;
373  	      int c;
374  	
375  	      branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
376  	      assert(branchrule != NULL);
377  	
378  	      /* get branching rule data */
379  	      branchruledata = SCIPbranchruleGetData(branchrule);
380  	      assert(branchruledata != NULL);
381  	
382  	      /* initialize strong branching */
383  	      SCIP_CALL( SCIPstartStrongbranch(scip, FALSE) );
384  	
385  	      /* search the full strong candidate:
386  	       * cycle through the candidates, starting with the position evaluated in the last run
387  	       */
388  	      nsbcalls = 0;
389  	      for( i = 0, c = branchruledata->lastcand; i < npseudocands; ++i, ++c )
390  	      {
391  	         c = c % npseudocands;
392  	         assert(pseudocands[c] != NULL);
393  	
394  	         /* we can only apply strong branching on COLUMN variables that are in the current LP */
395  	         if( !SCIPvarIsInLP(pseudocands[c]) )
396  	            continue;
397  	
398  	         solval = SCIPvarGetLPSol(pseudocands[c]);
399  	         integral = SCIPisFeasIntegral(scip, solval);
400  	
401  	         SCIPdebugMsg(scip, "applying strong branching on %s variable <%s>[%g,%g] with solution %g\n",
402  	            integral ? "integral" : "fractional", SCIPvarGetName(pseudocands[c]), SCIPvarGetLbLocal(pseudocands[c]),
403  	            SCIPvarGetUbLocal(pseudocands[c]), solval);
404  	
405  	         up = -SCIPinfinity(scip);
406  	         down = -SCIPinfinity(scip);
407  	
408  	         if( integral )
409  	         {
410  	            SCIP_CALL( SCIPgetVarStrongbranchInt(scip, pseudocands[c], INT_MAX, FALSE,
411  	                  skipdown[c] ? NULL : &down, skipup[c] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
412  	         }
413  	         else
414  	         {
415  	            SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, pseudocands[c], INT_MAX, FALSE,
416  	                  skipdown[c] ? NULL : &down, skipup[c] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
417  	         }
418  	         nsbcalls++;
419  	
420  	         /* display node information line in root node */
421  	         if( SCIPgetDepth(scip) == 0 && nsbcalls % 100 == 0 )
422  	         {
423  	            SCIP_CALL( SCIPprintDisplayLine(scip, NULL, SCIP_VERBLEVEL_HIGH, TRUE) );
424  	         }
425  	
426  	         /* check for an error in strong branching */
427  	         if( lperror )
428  	         {
429  	            SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
430  	               "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call for variable <%s> with solution %g\n",
431  	               SCIPgetNNodes(scip), SCIPvarGetName(pseudocands[c]), solval);
432  	            break;
433  	         }
434  	
435  	         /* evaluate strong branching */
436  	         down = MAX(down, lpobjval);
437  	         up = MAX(up, lpobjval);
438  	         downgain = down - lpobjval;
439  	         upgain = up - lpobjval;
440  	         assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, cutoffbound));
441  	         assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, cutoffbound));
442  	         assert(downinf || !downconflict);
443  	         assert(upinf || !upconflict);
444  	
445  	         /* check if there are infeasible roundings */
446  	         if( downinf || upinf )
447  	         {
448  	            assert(allcolsinlp);
449  	            assert(!exactsolve);
450  	
451  	            if( downinf && upinf )
452  	            {
453  	               if( integral )
454  	               {
455  	                  SCIP_Bool infeasible;
456  	                  SCIP_Bool fixed;
457  	
458  	                  /* both bound changes are infeasible: variable can be fixed to its current value */
459  	                  SCIP_CALL( SCIPfixVar(scip, pseudocands[c], solval, &infeasible, &fixed) );
460  	                  assert(!infeasible);
461  	                  assert(fixed);
462  	                  *result = SCIP_REDUCEDDOM;
463  	                  SCIPdebugMsg(scip, " -> integral variable <%s> is infeasible in both directions\n",
464  	                     SCIPvarGetName(pseudocands[c]));
465  	                  break; /* terminate initialization loop, because LP was changed */
466  	               }
467  	               else
468  	               {
469  	                  /* both roundings are infeasible: the node is infeasible */
470  	                  *result = SCIP_CUTOFF;
471  	                  SCIPdebugMsg(scip, " -> fractional variable <%s> is infeasible in both directions\n",
472  	                     SCIPvarGetName(pseudocands[c]));
473  	                  break; /* terminate initialization loop, because node is infeasible */
474  	               }
475  	            }
476  	            else if( downinf )
477  	            {
478  	               SCIP_Real newlb;
479  	
480  	               /* downwards rounding is infeasible -> change lower bound of variable to upward rounding */
481  	               newlb = SCIPfeasCeil(scip, solval);
482  	               if( SCIPvarGetLbLocal(pseudocands[c]) < newlb - 0.5 )
483  	               {
484  	                  SCIP_CALL( SCIPchgVarLb(scip, pseudocands[c], newlb) );
485  	                  *result = SCIP_REDUCEDDOM;
486  	                  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in downward branch\n", SCIPvarGetName(pseudocands[c]));
487  	                  break; /* terminate initialization loop, because LP was changed */
488  	               }
489  	            }
490  	            else
491  	            {
492  	               SCIP_Real newub;
493  	
494  	               /* upwards rounding is infeasible -> change upper bound of variable to downward rounding */
495  	               assert(upinf);
496  	               newub = SCIPfeasFloor(scip, solval);
497  	               if( SCIPvarGetUbLocal(pseudocands[c]) > newub + 0.5 )
498  	               {
499  	                  SCIP_CALL( SCIPchgVarUb(scip, pseudocands[c], newub) );
500  	                  *result = SCIP_REDUCEDDOM;
501  	                  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in upward branch\n", SCIPvarGetName(pseudocands[c]));
502  	                  break; /* terminate initialization loop, because LP was changed */
503  	               }
504  	            }
505  	         }
506  	         else if( allcolsinlp && !exactsolve && downvalid && upvalid )
507  	         {
508  	            SCIP_Real minbound;
509  	
510  	            /* the minimal lower bound of both children is a proved lower bound of the current subtree */
511  	            minbound = MIN(down, up);
512  	            *provedbound = MAX(*provedbound, minbound);
513  	         }
514  	
515  	         /* check for a better score, if we are within the maximum priority candidates */
516  	         if( c < npriopseudocands )
517  	         {
518  	            if( integral )
519  	            {
520  	               if( skipdown[c] )
521  	               {
522  	                  downgain = 0.0;
523  	                  score = SCIPgetBranchScore(scip, pseudocands[c], downgain, upgain);
524  	               }
525  	               else if( skipup[c] )
526  	               {
527  	                  upgain = 0.0;
528  	                  score = SCIPgetBranchScore(scip, pseudocands[c], downgain, upgain);
529  	               }
530  	               else
531  	               {
532  	                  SCIP_Real gains[3];
533  	
534  	                  gains[0] = downgain;
535  	                  gains[1] = 0.0;
536  	                  gains[2] = upgain;
537  	                  score = SCIPgetBranchScoreMultiple(scip, pseudocands[c], 3, gains);
538  	               }
539  	            }
540  	            else
541  	               score = SCIPgetBranchScore(scip, pseudocands[c], downgain, upgain);
542  	
543  	            if( score > *bestscore )
544  	            {
545  	               *bestpseudocand = c;
546  	               *bestdown = down;
547  	               *bestup = up;
548  	               *bestdownvalid = downvalid;
549  	               *bestupvalid = upvalid;
550  	               *bestscore = score;
551  	            }
552  	         }
553  	         else
554  	         {
555  	            SCIPdebug( score = 0.0; )
556  	         }
557  	
558  	         /* update pseudo cost values */
559  	         if( !downinf )
560  	         {
561  	            SCIP_CALL( SCIPupdateVarPseudocost(scip, pseudocands[c],
562  	                  solval-SCIPfeasCeil(scip, solval-1.0), downgain, 1.0) );
563  	         }
564  	         if( !upinf )
565  	         {
566  	            SCIP_CALL( SCIPupdateVarPseudocost(scip, pseudocands[c],
567  	                  solval-SCIPfeasFloor(scip, solval+1.0), upgain, 1.0) );
568  	         }
569  	
570  	         SCIPdebugMsg(scip, " -> var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
571  	            SCIPvarGetName(pseudocands[c]), solval, downgain, upgain, score,
572  	            SCIPvarGetName(pseudocands[*bestpseudocand]), *bestscore);
573  	      }
574  	
575  	      /* remember last evaluated candidate */
576  	      branchruledata->lastcand = c;
577  	
578  	      /* end strong branching */
579  	      SCIP_CALL( SCIPendStrongbranch(scip) );
580  	   }
581  	
582  	   return SCIP_OKAY;
583  	}
584  	
585  	/** creates the all variables full strong LP branching rule and includes it in SCIP */
586  	SCIP_RETCODE SCIPincludeBranchruleAllfullstrong(
587  	   SCIP*                 scip                /**< SCIP data structure */
588  	   )
589  	{
590  	   SCIP_BRANCHRULEDATA* branchruledata;
591  	   SCIP_BRANCHRULE* branchrule;
592  	
593  	   /* create allfullstrong branching rule data */
594  	   SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
595  	   branchruledata->lastcand = 0;
596  	   branchruledata->skipsize = 0;
597  	   branchruledata->skipup = NULL;
598  	   branchruledata->skipdown = NULL;
599  	
600  	   /* include allfullstrong branching rule */
601  	   SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
602  	         BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
603  	
604  	   assert(branchrule != NULL);
605  	
606  	   /* set non-fundamental callbacks via specific setter functions*/
607  	   SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyAllfullstrong) );
608  	   SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeAllfullstrong) );
609  	   SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitAllfullstrong) );
610  	   SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpAllfullstrong) );
611  	   SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsAllfullstrong) );
612  	
613  	   return SCIP_OKAY;
614  	}
615