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_fullstrong.c
26   	 * @ingroup DEFPLUGINS_BRANCH
27   	 * @brief  full strong LP branching rule
28   	 * @author Tobias Achterberg
29   	 * @author Gerald Gamrath
30   	 */
31   	
32   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33   	
34   	#include "blockmemshell/memory.h"
35   	#include "scip/branch_fullstrong.h"
36   	#include "scip/pub_branch.h"
37   	#include "scip/pub_message.h"
38   	#include "scip/pub_tree.h"
39   	#include "scip/pub_var.h"
40   	#include "scip/scip_branch.h"
41   	#include "scip/scip_general.h"
42   	#include "scip/scip_lp.h"
43   	#include "scip/scip_mem.h"
44   	#include "scip/scip_message.h"
45   	#include "scip/scip_numerics.h"
46   	#include "scip/scip_param.h"
47   	#include "scip/scip_prob.h"
48   	#include "scip/scip_solvingstats.h"
49   	#include "scip/scip_tree.h"
50   	#include "scip/scip_var.h"
51   	#include <string.h>
52   	
53   	
54   	#define BRANCHRULE_NAME          "fullstrong"
55   	#define BRANCHRULE_DESC          "full strong branching"
56   	#define BRANCHRULE_PRIORITY      0
57   	#define BRANCHRULE_MAXDEPTH      -1
58   	#define BRANCHRULE_MAXBOUNDDIST  1.0
59   	
60   	#define DEFAULT_REEVALAGE        10LL        /**< number of intermediate LPs solved to trigger reevaluation of strong branching
61   	                                              *   value for a variable that was already evaluated at the current node */
62   	#define DEFAULT_MAXPROPROUNDS      -2        /**< maximum number of propagation rounds to be performed during strong branching
63   	                                              *   before solving the LP (-1: no limit, -2: parameter settings) */
64   	#define DEFAULT_PROBINGBOUNDS    TRUE        /**< should valid bounds be identified in a probing-like fashion during strong
65   	                                              *   branching (only with propagation)? */
66   	#define DEFAULT_FORCESTRONGBRANCH FALSE      /**< should strong branching be applied even if there is just a single candidate? */
67   	
68   	
69   	/** branching rule data */
70   	struct SCIP_BranchruleData
71   	{
72   	   SCIP_Longint          reevalage;          /**< number of intermediate LPs solved to trigger reevaluation of strong branching
73   	                                              *   value for a variable that was already evaluated at the current node */
74   	   int                   maxproprounds;      /**< maximum number of propagation rounds to be performed during strong branching
75   	                                              *   before solving the LP (-1: no limit, -2: parameter settings) */
76   	   SCIP_Bool             probingbounds;      /**< should valid bounds be identified in a probing-like fashion during strong
77   	                                              *   branching (only with propagation)? */
78   	   SCIP_Bool             forcestrongbranch;  /**< should strong branching be applied even if there is just a single candidate? */
79   	   int                   lastcand;           /**< last evaluated candidate of last branching rule execution */
80   	   int                   skipsize;           /**< size of skipdown and skipup array */
81   	   SCIP_Bool*            skipdown;           /**< should be branching on down child be skipped? */
82   	   SCIP_Bool*            skipup;             /**< should be branching on up child be skipped? */
83   	};
84   	
85   	
86   	/*
87   	 * Callback methods
88   	 */
89   	
90   	/** copy method for branchrule plugins (called when SCIP copies plugins) */
91   	static
92   	SCIP_DECL_BRANCHCOPY(branchCopyFullstrong)
93   	{  /*lint --e{715}*/
94   	   assert(scip != NULL);
95   	   assert(branchrule != NULL);
96   	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
97   	
98   	   /* call inclusion method of branchrule */
99   	   SCIP_CALL( SCIPincludeBranchruleFullstrong(scip) );
100  	
101  	   return SCIP_OKAY;
102  	}
103  	
104  	/** destructor of branching rule to free user data (called when SCIP is exiting) */
105  	static
106  	SCIP_DECL_BRANCHFREE(branchFreeFullstrong)
107  	{  /*lint --e{715}*/
108  	   SCIP_BRANCHRULEDATA* branchruledata;
109  	
110  	   /* free branching rule data */
111  	   branchruledata = SCIPbranchruleGetData(branchrule);
112  	   assert(branchruledata != NULL);
113  	
114  	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize);
115  	   SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize);
116  	
117  	   SCIPfreeBlockMemory(scip, &branchruledata);
118  	   SCIPbranchruleSetData(branchrule, NULL);
119  	
120  	   return SCIP_OKAY;
121  	}
122  	
123  	
124  	/** initialization method of branching rule (called after problem was transformed) */
125  	static
126  	SCIP_DECL_BRANCHINIT(branchInitFullstrong)
127  	{  /*lint --e{715}*/
128  	   SCIP_BRANCHRULEDATA* branchruledata;
129  	
130  	   /* initialize branching rule data */
131  	   branchruledata = SCIPbranchruleGetData(branchrule);
132  	   assert(branchruledata != NULL);
133  	
134  	   branchruledata->lastcand = 0;
135  	
136  	   return SCIP_OKAY;
137  	}
138  	
139  	/** deinitialization method of branching rule (called before transformed problem is freed) */
140  	static
141  	SCIP_DECL_BRANCHEXIT(branchExitFullstrong)
142  	{  /*lint --e{715}*/
143  	   SCIP_BRANCHRULEDATA* branchruledata;
144  	
145  	   /* initialize branching rule data */
146  	   branchruledata = SCIPbranchruleGetData(branchrule);
147  	   assert(branchruledata != NULL);
148  	   assert((branchruledata->skipdown != NULL) == (branchruledata->skipup != NULL));
149  	
150  	   if( branchruledata->skipdown != NULL )
151  	   {
152  	      SCIPfreeBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize);
153  	      SCIPfreeBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize);
154  	      branchruledata->skipdown = NULL;
155  	      branchruledata->skipup = NULL;
156  	      branchruledata->skipsize = 0;
157  	   }
158  	
159  	   return SCIP_OKAY;
160  	}
161  	
162  	/**
163  	 * Selects a variable from a set of candidates by strong branching
164  	 *
165  	 *  @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
166  	 *          SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
167  	 *
168  	 * @note The variables in the lpcands array must have a fractional value in the current LP solution
169  	 */
170  	SCIP_RETCODE SCIPselectVarStrongBranching(
171  	   SCIP*                 scip,               /**< original SCIP data structure                        */
172  	   SCIP_VAR**            lpcands,            /**< branching candidates                                */
173  	   SCIP_Real*            lpcandssol,         /**< solution values of the branching candidates         */
174  	   SCIP_Real*            lpcandsfrac,        /**< fractional values of the branching candidates       */
175  	   SCIP_Bool*            skipdown,           /**< should down branchings be skipped? */
176  	   SCIP_Bool*            skipup,             /**< should up branchings be skipped? */
177  	   int                   nlpcands,           /**< number of branching candidates                      */
178  	   int                   npriolpcands,       /**< number of priority branching candidates             */
179  	   int                   ncomplete,          /**< number of branching candidates without skip         */
180  	   int*                  start,              /**< starting index in lpcands                           */
181  	   int                   maxproprounds,      /**< maximum number of propagation rounds to be performed during strong
182  	                                              *   branching before solving the LP (-1: no limit, -2: parameter settings) */
183  	   SCIP_Bool             probingbounds,      /**< should valid bounds be identified in a probing-like fashion during
184  	                                              *   strong branching (only with propagation)? */
185  	   SCIP_Bool             forcestrongbranch,  /**< should strong branching be applied even if there is just a single candidate? */
186  	   int*                  bestcand,           /**< best candidate for branching                        */
187  	   SCIP_Real*            bestdown,           /**< objective value of the down branch for bestcand     */
188  	   SCIP_Real*            bestup,             /**< objective value of the up branch for bestcand       */
189  	   SCIP_Real*            bestscore,          /**< score for bestcand                                  */
190  	   SCIP_Bool*            bestdownvalid,      /**< is bestdown a valid dual bound for the down branch? */
191  	   SCIP_Bool*            bestupvalid,        /**< is bestup a valid dual bound for the up branch?     */
192  	   SCIP_Real*            provedbound,        /**< proved dual bound for current subtree               */
193  	   SCIP_RESULT*          result              /**< result pointer                                      */
194  	   )
195  	{  /*lint --e{715}*/
196  	   SCIP_VAR** vars = NULL;
197  	   SCIP_Real* newlbs = NULL;
198  	   SCIP_Real* newubs = NULL;
199  	   SCIP_BRANCHRULE* branchrule;
200  	   SCIP_BRANCHRULEDATA* branchruledata;
201  	   SCIP_Longint reevalage;
202  	   SCIP_Longint nodenum;
203  	   SCIP_Real down;
204  	   SCIP_Real up;
205  	   SCIP_Real downgain;
206  	   SCIP_Real upgain;
207  	   SCIP_Real score;
208  	   SCIP_Real lpobjval;
209  	   SCIP_Bool exactsolve;
210  	   SCIP_Bool lperror;
211  	   SCIP_Bool allcolsinlp;
212  	   SCIP_Bool downvalid;
213  	   SCIP_Bool upvalid;
214  	   SCIP_Bool downinf;
215  	   SCIP_Bool upinf;
216  	   SCIP_Bool downconflict;
217  	   SCIP_Bool upconflict;
218  	   SCIP_Bool bothgains;
219  	   SCIP_Bool propagate;
220  	   int nvars = 0;
221  	   int nsbcalls;
222  	   int i;
223  	   int c;
224  	
225  	   assert(scip != NULL);
226  	   assert(lpcands != NULL);
227  	   assert(lpcandssol != NULL);
228  	   assert(lpcandsfrac != NULL);
229  	   assert(bestcand != NULL);
230  	   assert(skipdown != NULL);
231  	   assert(skipup != NULL);
232  	   assert(bestdown != NULL);
233  	   assert(bestup != NULL);
234  	   assert(bestscore != NULL);
235  	   assert(bestdownvalid != NULL);
236  	   assert(bestupvalid != NULL);
237  	   assert(provedbound != NULL);
238  	   assert(result != NULL);
239  	   assert(nlpcands > 0);
240  	
241  	   /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
242  	    * for cutting off sub problems and improving lower bounds of children
243  	    */
244  	   exactsolve = SCIPisExactSolve(scip);
245  	
246  	   /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
247  	   allcolsinlp = SCIPallColsInLP(scip);
248  	
249  	   /* get current node number */
250  	   nodenum = SCIPgetNNodes(scip);
251  	
252  	   /* get current LP objective bound of the local sub problem and global cutoff bound */
253  	   lpobjval = SCIPgetLPObjval(scip);
254  	   *provedbound = lpobjval;
255  	
256  	   *bestcand = 0;
257  	   *bestdown = lpobjval;
258  	   *bestup = lpobjval;
259  	   *bestdownvalid = TRUE;
260  	   *bestupvalid = TRUE;
261  	   *bestscore = -SCIPinfinity(scip);
262  	
263  	   /* if only one candidate exists, choose this one without applying strong branching; also, when SCIP is about to be
264  	    * stopped, all strongbranching evaluations will be aborted anyway, thus we can return immediately
265  	    */
266  	   if( (!forcestrongbranch && nlpcands == 1) || SCIPisStopped(scip) )
267  	      return SCIP_OKAY;
268  	
269  	   /* this assert may not hold if SCIP is stopped, thus we only check it here */
270  	   assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
271  	
272  	   /* get branching rule */
273  	   branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
274  	   assert(branchrule != NULL);
275  	
276  	   /* get branching rule data */
277  	   branchruledata = SCIPbranchruleGetData(branchrule);
278  	   assert(branchruledata != NULL);
279  	
280  	   /* auto-setting for reevalage */
281  	   reevalage = branchruledata->reevalage;
282  	
283  	   /* check whether propagation should be performed */
284  	   propagate = (maxproprounds != 0);
285  	
286  	   /* if we don't do propagation, we cannot identify valid bounds in a probing-like fashion */
287  	   if( !propagate && maxproprounds > -3 )
288  	      probingbounds = FALSE;
289  	
290  	   /* create arrays for probing-like bound tightening */
291  	   if( probingbounds )
292  	   {
293  	      vars = SCIPgetVars(scip);
294  	      nvars = SCIPgetNVars(scip);
295  	
296  	      SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
297  	      SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
298  	   }
299  	
300  	    /* initialize strong branching */
301  	   SCIP_CALL( SCIPstartStrongbranch(scip, propagate) );
302  	
303  	   /* search the full strong candidate
304  	    * cycle through the candidates, starting with the position evaluated in the last run
305  	    */
306  	   nsbcalls = 0;
307  	   bothgains = TRUE;
308  	   for( i = 0, c = *start; i < nlpcands && (!bothgains || i < ncomplete); ++i, ++c )
309  	   {
310  	      c = c % nlpcands;
311  	      assert(lpcands[c] != NULL);
312  	
313  	      /* don't use strong branching on variables that have already been initialized at the current node,
314  	       * and that were evaluated not too long ago
315  	       */
316  	      if( SCIPgetVarStrongbranchNode(scip, lpcands[c]) == nodenum
317  	         && SCIPgetVarStrongbranchLPAge(scip, lpcands[c]) < reevalage )
318  	      {
319  	         SCIP_Real lastlpobjval;
320  	
321  	         /* use the score of the strong branching call at the current node */
322  	         SCIP_CALL( SCIPgetVarStrongbranchLast(scip, lpcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
323  	         downgain = MAX(down - lastlpobjval, 0.0);
324  	         upgain = MAX(up - lastlpobjval, 0.0);
325  	         downvalid = FALSE;
326  	         upvalid = FALSE;
327  	         downinf = FALSE;
328  	         upinf = FALSE;
329  	         downconflict = FALSE;
330  	         upconflict = FALSE;
331  	         lperror = FALSE;
332  	         SCIPdebugMsg(scip, "strong branching on variable <%s> already performed (lpage=%" SCIP_LONGINT_FORMAT ", down=%g (%+g), up=%g (%+g))\n",
333  	            SCIPvarGetName(lpcands[c]), SCIPgetVarStrongbranchLPAge(scip, lpcands[c]), down, downgain, up, upgain);
334  	      }
335  	      else
336  	      {
337  	         SCIPdebugMsg(scip, "applying strong branching%s on variable <%s> with solution %g\n",
338  	            propagate ? "with propagation" : "", SCIPvarGetName(lpcands[c]), lpcandssol[c]);
339  	         assert(i >= ncomplete || (!skipdown[i] && !skipup[i]));
340  	
341  	         /* apply strong branching */
342  	         up = -SCIPinfinity(scip);
343  	         down = -SCIPinfinity(scip);
344  	
345  	         if( propagate )
346  	         {
347  	            SCIP_CALL( SCIPgetVarStrongbranchWithPropagation(scip, lpcands[c], lpcandssol[c], lpobjval, INT_MAX,
348  	                  maxproprounds, skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid,
349  	                  &upvalid, NULL, NULL, &downinf, &upinf, &downconflict, &upconflict, &lperror, newlbs, newubs) );
350  	
351  	            SCIPdebugMsg(scip, "-> down=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u), up=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u)\n",
352  	               down, down - lpobjval, downvalid, downinf, downconflict, up, up - lpobjval, upvalid, upinf, upconflict);
353  	         }
354  	         else
355  	         {
356  	            SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, lpcands[c], INT_MAX, FALSE,
357  	                  skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf,
358  	                  &downconflict, &upconflict, &lperror) );
359  	         }
360  	         nsbcalls++;
361  	
362  	         /* display node information line */
363  	         if( SCIPgetDepth(scip) == 0 && nsbcalls % 100 == 0 )
364  	         {
365  	            SCIP_CALL( SCIPprintDisplayLine(scip, NULL, SCIP_VERBLEVEL_HIGH, TRUE) );
366  	         }
367  	
368  	         /* check for an error in strong branching */
369  	         if( lperror )
370  	         {
371  	            SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
372  	               "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call%s for variable <%s> with solution %g\n",
373  	               SCIPgetNNodes(scip), propagate ? " with propagation" : "", SCIPvarGetName(lpcands[c]), lpcandssol[c]);
374  	            break;
375  	         }
376  	
377  	         /* evaluate strong branching */
378  	         down = MAX(down, lpobjval);
379  	         up = MAX(up, lpobjval);
380  	         downgain = down - lpobjval;
381  	         upgain = up - lpobjval;
382  	         if( !SCIPisFeasZero(scip,downgain) && !SCIPisFeasZero(scip,upgain) )
383  	            bothgains = TRUE;
384  	
385  	         assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
386  	         assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
387  	         assert(downinf || !downconflict);
388  	         assert(upinf || !upconflict);
389  	
390  	         /* update pseudo cost values */
391  	         if( !downinf && downvalid )
392  	         {
393  	            SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[c], 0.0-lpcandsfrac[c], downgain, 1.0) );
394  	         }
395  	         if( !upinf && upvalid )
396  	         {
397  	            SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[c], 1.0-lpcandsfrac[c], upgain, 1.0) );
398  	         }
399  	
400  	         /* check if there are infeasible roundings */
401  	         if( downinf || upinf )
402  	         {
403  	            /* if we didn't do propagation, we can only detect infeasibility if the LP is a valid relaxation */
404  	            assert(allcolsinlp || propagate);
405  	            assert(!exactsolve);
406  	
407  	            if( downinf && upinf )
408  	            {
409  	               /* both roundings are infeasible -> node is infeasible */
410  	               *result = SCIP_CUTOFF;
411  	               SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions\n", SCIPvarGetName(lpcands[c]));
412  	               break; /* terminate initialization loop, because node is infeasible */
413  	            }
414  	            else if( downinf )
415  	            {
416  	               SCIP_Bool infeasible;
417  	               SCIP_Bool tightened;
418  	
419  	               /* downwards rounding is infeasible -> change lower bound of variable to upward rounding */
420  	               SCIP_CALL( SCIPtightenVarLb(scip, lpcands[c], SCIPfeasCeil(scip, lpcandssol[c]), TRUE, &infeasible, &tightened) );
421  	               assert(!infeasible);
422  	
423  	               /* if we did propagation, the bound change might already have been added */
424  	               assert(tightened || propagate);
425  	
426  	               *result = SCIP_REDUCEDDOM;
427  	               SCIPdebugMsg(scip, " -> variable <%s> is infeasible in downward branch\n", SCIPvarGetName(lpcands[c]));
428  	               break; /* terminate initialization loop, because LP was changed */
429  	            }
430  	            else
431  	            {
432  	               SCIP_Bool infeasible;
433  	               SCIP_Bool tightened;
434  	
435  	               /* upwards rounding is infeasible -> change upper bound of variable to downward rounding */
436  	               assert(upinf);
437  	               SCIP_CALL( SCIPtightenVarUb(scip, lpcands[c], SCIPfeasFloor(scip, lpcandssol[c]), TRUE, &infeasible, &tightened) );
438  	               assert(!infeasible);
439  	
440  	               /* if we did propagation, the bound change might already have been added */
441  	               assert(tightened || propagate);
442  	
443  	               *result = SCIP_REDUCEDDOM;
444  	               SCIPdebugMsg(scip, " -> variable <%s> is infeasible in upward branch\n", SCIPvarGetName(lpcands[c]));
445  	               break; /* terminate initialization loop, because LP was changed */
446  	            }
447  	         }
448  	         else if( allcolsinlp && !exactsolve && downvalid && upvalid )
449  	         {
450  	            SCIP_Real minbound;
451  	
452  	            /* the minimal lower bound of both children is a proved lower bound of the current subtree */
453  	            minbound = MIN(down, up);
454  	            *provedbound = MAX(*provedbound, minbound);
455  	
456  	            /* apply probing-like bounds detected during strong branching */
457  	            if( probingbounds )
458  	            {
459  	               int nboundchgs;
460  	               int v;
461  	
462  	               assert(vars != NULL);
463  	               assert(nvars > 0);
464  	               assert(newlbs != NULL);
465  	               assert(newubs != NULL);
466  	
467  	               nboundchgs = 0;
468  	
469  	               for( v = 0; v < nvars; ++v )
470  	               {
471  	                  if( SCIPisGT(scip, newlbs[v], SCIPvarGetLbLocal(vars[v])) )
472  	                  {
473  	                     SCIPdebugMsg(scip, "better lower bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
474  	                        SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), newlbs[v], SCIPvarGetName(lpcands[c]));
475  	
476  	                     SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlbs[v]) );
477  	                     ++nboundchgs;
478  	                  }
479  	                  if( SCIPisLT(scip, newubs[v], SCIPvarGetUbLocal(vars[v])) )
480  	                  {
481  	                     SCIPdebugMsg(scip, "better upper bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
482  	                        SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), newubs[v], SCIPvarGetName(lpcands[c]));
483  	
484  	                     SCIP_CALL( SCIPchgVarUb(scip, vars[v], newubs[v]) );
485  	                     ++nboundchgs;
486  	                  }
487  	               }
488  	
489  	               if( nboundchgs > 0 )
490  	               {
491  	                  *result = SCIP_REDUCEDDOM;
492  	                  SCIPdebugMsg(scip, " -> strong branching with propagation on variable <%s> led to %d bound changes\n",
493  	                     SCIPvarGetName(lpcands[c]), nboundchgs);
494  	                  break; /* terminate initialization loop, because LP was changed */
495  	               }
496  	            }
497  	         }
498  	      }
499  	
500  	      /* check for a better score, if we are within the maximum priority candidates */
501  	      if( c < npriolpcands )
502  	      {
503  	         score = SCIPgetBranchScore(scip, lpcands[c], downgain, upgain);
504  	         if( score > *bestscore )
505  	         {
506  	            *bestcand = c;
507  	            *bestdown = down;
508  	            *bestup = up;
509  	            *bestdownvalid = downvalid;
510  	            *bestupvalid = upvalid;
511  	            *bestscore = score;
512  	         }
513  	      }
514  	      else
515  	      {
516  	         SCIPdebug(score = 0.0;)
517  	      }
518  	
519  	      SCIPdebugMsg(scip, " -> cand %d/%d (prio:%d) var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
520  	         c, nlpcands, npriolpcands, SCIPvarGetName(lpcands[c]), lpcandssol[c], downgain, upgain, score,
521  	         SCIPvarGetName(lpcands[*bestcand]), *bestscore);
522  	   }
523  	
524  	   /* end strong branching */
525  	   SCIP_CALL( SCIPendStrongbranch(scip) );
526  	
527  	   *start = c;
528  	
529  	   if( probingbounds )
530  	   {
531  	      assert(newlbs != NULL);
532  	      assert(newubs != NULL);
533  	
534  	      SCIPfreeBufferArray(scip, &newlbs);
535  	      SCIPfreeBufferArray(scip, &newubs);
536  	   }
537  	
538  	   return SCIP_OKAY;
539  	}
540  	
541  	/** branching execution method for fractional LP solutions */
542  	static
543  	SCIP_DECL_BRANCHEXECLP(branchExeclpFullstrong)
544  	{  /*lint --e{715}*/
545  	   SCIP_BRANCHRULEDATA* branchruledata;
546  	   SCIP_VAR** tmplpcands;
547  	   SCIP_VAR** lpcands;
548  	   SCIP_Real* tmplpcandssol;
549  	   SCIP_Real* lpcandssol;
550  	   SCIP_Real* tmplpcandsfrac;
551  	   SCIP_Real* lpcandsfrac;
552  	   SCIP_Real bestdown;
553  	   SCIP_Real bestup;
554  	   SCIP_Real bestscore;
555  	   SCIP_Real provedbound;
556  	   SCIP_Bool bestdownvalid;
557  	   SCIP_Bool bestupvalid;
558  	   int nlpcands;
559  	   int npriolpcands;
560  	   int bestcand;
561  	
562  	   assert(branchrule != NULL);
563  	   assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
564  	   assert(scip != NULL);
565  	   assert(result != NULL);
566  	
567  	   SCIPdebugMsg(scip, "Execlp method of fullstrong branching\n");
568  	
569  	   *result = SCIP_DIDNOTRUN;
570  	
571  	   /* get branching rule data */
572  	   branchruledata = SCIPbranchruleGetData(branchrule);
573  	   assert(branchruledata != NULL);
574  	
575  	   /* get branching candidates */
576  	   SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, &nlpcands, &npriolpcands, NULL) );
577  	   assert(nlpcands > 0);
578  	   assert(npriolpcands > 0);
579  	
580  	   /* copy LP banching candidates and solution values, because they will be updated w.r.t. the strong branching LP
581  	    * solution
582  	    */
583  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) );
584  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) );
585  	   SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) );
586  	
587  	   if( branchruledata->skipdown == NULL )
588  	   {
589  	      assert(branchruledata->skipup == NULL);
590  	
591  	      branchruledata->skipsize = SCIPgetNVars(scip);
592  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
593  	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
594  	      BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
595  	      BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
596  	   }
597  	
598  	   SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcands, lpcandssol, lpcandsfrac, branchruledata->skipdown,
599  	         branchruledata->skipup, nlpcands, npriolpcands, nlpcands, &branchruledata->lastcand,
600  	         branchruledata->maxproprounds, branchruledata->probingbounds, branchruledata->forcestrongbranch, &bestcand,
601  	         &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
602  	
603  	   if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
604  	   {
605  	      SCIP_NODE* downchild;
606  	      SCIP_NODE* upchild;
607  	      SCIP_VAR* var;
608  	      SCIP_Real val;
609  	      SCIP_Bool allcolsinlp;
610  	      SCIP_Bool exactsolve;
611  	
612  	      assert(*result == SCIP_DIDNOTRUN);
613  	      assert(0 <= bestcand && bestcand < nlpcands);
614  	      assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
615  	
616  	      var = lpcands[bestcand];
617  	      val = lpcandssol[bestcand];
618  	
619  	      /* perform the branching */
620  	      SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
621  	         nlpcands, bestcand, SCIPvarGetName(var), lpcandssol[bestcand], bestdown, bestup, bestscore);
622  	      SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, NULL, &upchild) );
623  	      assert(downchild != NULL);
624  	      assert(upchild != NULL);
625  	
626  	      /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
627  	       * for cutting off sub problems and improving lower bounds of children
628  	       */
629  	      exactsolve = SCIPisExactSolve(scip);
630  	
631  	      /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
632  	      allcolsinlp = SCIPallColsInLP(scip);
633  	
634  	      /* update the lower bounds in the children */
635  	      if( allcolsinlp && !exactsolve )
636  	      {
637  	         SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
638  	         SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
639  	      }
640  	      SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
641  	      SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
642  	
643  	      *result = SCIP_BRANCHED;
644  	   }
645  	
646  	   SCIPfreeBufferArray(scip, &lpcandsfrac);
647  	   SCIPfreeBufferArray(scip, &lpcandssol);
648  	   SCIPfreeBufferArray(scip, &lpcands);
649  	
650  	   return SCIP_OKAY;
651  	}
652  	
653  	
654  	/*
655  	 * branching specific interface methods
656  	 */
657  	
658  	/** creates the full strong LP branching rule and includes it in SCIP */
659  	SCIP_RETCODE SCIPincludeBranchruleFullstrong(
660  	   SCIP*                 scip                /**< SCIP data structure */
661  	   )
662  	{
663  	   SCIP_BRANCHRULEDATA* branchruledata;
664  	   SCIP_BRANCHRULE* branchrule;
665  	
666  	   /* create fullstrong branching rule data */
667  	   SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
668  	   branchruledata->lastcand = 0;
669  	   branchruledata->skipsize = 0;
670  	   branchruledata->skipup = NULL;
671  	   branchruledata->skipdown = NULL;
672  	
673  	   /* include branching rule */
674  	   SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
675  	         BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
676  	
677  	   assert(branchrule != NULL);
678  	
679  	   /* set non-fundamental callbacks via specific setter functions*/
680  	   SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyFullstrong) );
681  	   SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeFullstrong) );
682  	   SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitFullstrong) );
683  	   SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitFullstrong) );
684  	   SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpFullstrong) );
685  	
686  	   /* fullstrong branching rule parameters */
687  	   SCIP_CALL( SCIPaddLongintParam(scip,
688  	         "branching/fullstrong/reevalage",
689  	         "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node",
690  	         &branchruledata->reevalage, TRUE, DEFAULT_REEVALAGE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
691  	   SCIP_CALL( SCIPaddIntParam(scip,
692  	         "branching/fullstrong/maxproprounds",
693  	         "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
694  	         &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -3, INT_MAX, NULL, NULL) );
695  	   SCIP_CALL( SCIPaddBoolParam(scip,
696  	         "branching/fullstrong/probingbounds",
697  	         "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
698  	         &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
699  	   SCIP_CALL( SCIPaddBoolParam(scip,
700  	         "branching/fullstrong/forcestrongbranch",
701  	         "should strong branching be applied even if there is just a single candidate?",
702  	         &branchruledata->forcestrongbranch, TRUE, DEFAULT_FORCESTRONGBRANCH, NULL, NULL) );
703  	
704  	   return SCIP_OKAY;
705  	}
706