Scippy

SCIP

Solving Constraint Integer Programs

branch_relpscost.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch_relpscost.c
17  * @brief reliable pseudo costs branching rule
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  * @author Gerald Gamrath
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include <assert.h>
26 #include <string.h>
27 
28 #include "scip/branch_relpscost.h"
29 #include "scip/cons_and.h"
30 #include "scip/pub_misc.h"
31 
32 #define BRANCHRULE_NAME "relpscost"
33 #define BRANCHRULE_DESC "reliability branching on pseudo cost values"
34 #define BRANCHRULE_PRIORITY 10000
35 #define BRANCHRULE_MAXDEPTH -1
36 #define BRANCHRULE_MAXBOUNDDIST 1.0
37 
38 #define DEFAULT_CONFLICTWEIGHT 0.01 /**< weight in score calculations for conflict score */
39 #define DEFAULT_CONFLENGTHWEIGHT 0.0 /**< weight in score calculations for conflict length score*/
40 #define DEFAULT_INFERENCEWEIGHT 0.0001 /**< weight in score calculations for inference score */
41 #define DEFAULT_CUTOFFWEIGHT 0.0001 /**< weight in score calculations for cutoff score */
42 #define DEFAULT_PSCOSTWEIGHT 1.0 /**< weight in score calculations for pseudo cost score */
43 #define DEFAULT_NLSCOREWEIGHT 0.1 /**< weight in score calculations for nlcount score */
44 #define DEFAULT_MINRELIABLE 1.0 /**< minimal value for minimum pseudo cost size to regard pseudo cost value as reliable */
45 #define DEFAULT_MAXRELIABLE 5.0 /**< maximal value for minimum pseudo cost size to regard pseudo cost value as reliable */
46 #define DEFAULT_SBITERQUOT 0.5 /**< maximal fraction of strong branching LP iterations compared to normal iterations */
47 #define DEFAULT_SBITEROFS 100000 /**< additional number of allowed strong branching LP iterations */
48 #define DEFAULT_MAXLOOKAHEAD 9 /**< maximal number of further variables evaluated without better score */
49 #define DEFAULT_INITCAND 100 /**< maximal number of candidates initialized with strong branching per node */
50 #define DEFAULT_INITITER 0 /**< iteration limit for strong branching initialization of pseudo cost entries (0: auto) */
51 #define DEFAULT_MAXBDCHGS 5 /**< maximal number of bound tightenings before the node is reevaluated (-1: unlimited) */
52 #define DEFAULT_MAXPROPROUNDS -2 /**< maximum number of propagation rounds to be performed during strong branching
53  * before solving the LP (-1: no limit, -2: parameter settings) */
54 #define DEFAULT_PROBINGBOUNDS TRUE /**< should valid bounds be identified in a probing-like fashion during strong
55  * branching (only with propagation)? */
56 #define DEFAULT_USERELERRORFORRELIABILITY FALSE /**< should reliability be based on relative errors? */
57 #define DEFAULT_LOWERRORTOL 0.05 /**< lowest tolerance beneath which relative errors are reliable */
58 #define DEFAULT_HIGHERRORTOL 1.0 /**< highest tolerance beneath which relative errors are reliable */
59 #define DEFAULT_USEHYPTESTFORRELIABILITY FALSE /**< should the strong branching decision be based on a hypothesis test? */
60 #define DEFAULT_USEDYNAMICCONFIDENCE FALSE /**< should the confidence level be adjusted dynamically? */
61 #define DEFAULT_STORESEMIINITCOSTS FALSE /**< should strong branching result be considered for pseudo costs if the other direction was infeasible? */
62 #define DEFAULT_USESBLOCALINFO FALSE /**< should the scoring function use only local cutoff and inference information obtained for strong branching candidates? */
63 #define DEFAULT_CONFIDENCELEVEL 2 /**< The confidence level for statistical methods, between 0 (Min) and 4 (Max). */
64 #define DEFAULT_SKIPBADINITCANDS TRUE /**< should branching rule skip candidates that have a low probability to be
65  * better than the best strong-branching or pseudo-candidate? */
66 #define DEFAULT_STARTRANDSEED 5 /**< start random seed for random number generation */
67 #define DEFAULT_RANDINITORDER FALSE /**< should slight perturbation of scores be used to break ties in the prior scores? */
68 #define DEFAULT_USESMALLWEIGHTSITLIM FALSE /**< should smaller weights be used for pseudo cost updates after hitting the LP iteration limit? */
69 #define DEFAULT_DYNAMICWEIGHTS TRUE /**< should the weights of the branching rule be adjusted dynamically during solving based
70  * infeasible and objective leaf counters? */
71 
72 /** branching rule data */
73 struct SCIP_BranchruleData
74 {
75  SCIP_Real conflictweight; /**< weight in score calculations for conflict score */
76  SCIP_Real conflengthweight; /**< weight in score calculations for conflict length score */
77  SCIP_Real inferenceweight; /**< weight in score calculations for inference score */
78  SCIP_Real cutoffweight; /**< weight in score calculations for cutoff score */
79  SCIP_Real pscostweight; /**< weight in score calculations for pseudo cost score */
80  SCIP_Real nlscoreweight; /**< weight in score calculations for nlcount score */
81  SCIP_Real minreliable; /**< minimal value for minimum pseudo cost size to regard pseudo cost value as reliable */
82  SCIP_Real maxreliable; /**< maximal value for minimum pseudo cost size to regard pseudo cost value as reliable */
83  SCIP_Real sbiterquot; /**< maximal fraction of strong branching LP iterations compared to normal iterations */
84  int sbiterofs; /**< additional number of allowed strong branching LP iterations */
85  int maxlookahead; /**< maximal number of further variables evaluated without better score */
86  int initcand; /**< maximal number of candidates initialized with strong branching per node */
87  int inititer; /**< iteration limit for strong branching initialization of pseudo cost entries (0: auto) */
88  int maxbdchgs; /**< maximal number of bound tightenings before the node is reevaluated (-1: unlimited) */
89  int maxproprounds; /**< maximum number of propagation rounds to be performed during strong branching
90  * before solving the LP (-1: no limit, -2: parameter settings) */
91  SCIP_Bool probingbounds; /**< should valid bounds be identified in a probing-like fashion during strong
92  * branching (only with propagation)? */
93  SCIP_Bool userelerrorforreliability; /**< should reliability be based on relative errors? */
94  SCIP_Real lowerrortol; /**< lowest tolerance beneath which relative errors are reliable */
95  SCIP_Real higherrortol; /**< highest tolerance beneath which relative errors are reliable */
96  SCIP_Bool usehyptestforreliability; /**< should the strong branching decision be based on a hypothesis test? */
97  SCIP_Bool usedynamicconfidence; /**< should the confidence level be adjusted dynamically? */
98  SCIP_Bool storesemiinitcosts; /**< should strong branching result be considered for pseudo costs if the other direction was infeasible? */
99  SCIP_Bool usesblocalinfo; /**< should the scoring function disregard cutoffs for variable if sb-lookahead was feasible ? */
100  SCIP_Bool skipbadinitcands; /**< should branching rule skip candidates that have a low probability to be
101  * better than the best strong-branching or pseudo-candidate? */
102  SCIP_Bool dynamicweights; /**< should the weights of the branching rule be adjusted dynamically during solving based on objective and infeasible leaf counters? */
103  int confidencelevel; /**< The confidence level for statistical methods, between 0 (Min) and 4 (Max). */
104  int* nlcount; /**< array to store nonlinear count values */
105  int nlcountsize; /**< length of nlcount array */
106  int nlcountmax; /**< maximum entry in nlcount array or 1 if NULL */
107  SCIP_Bool randinitorder; /**< should slight perturbation of scores be used to break ties in the prior scores? */
108  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
109  int startrandseed; /**< start random seed for random number generation */
110  SCIP_Bool usesmallweightsitlim; /**< should smaller weights be used for pseudo cost updates after hitting the LP iteration limit? */
111 };
112 
113 /*
114  * local methods
115  */
116 
117 /** return probindex of variable or corresponding active variable (if negated or aggregated) or -1 (if multiaggregated) */
118 static
120  SCIP* scip, /**< SCIP data structure */
121  SCIP_VAR* var, /**< binary variable */
122  int* probindex /**< buffer to store probindex */
123  )
124 {
125  assert(scip != NULL);
126  assert(var != NULL);
127  assert(SCIPvarIsBinary(var));
128  assert(probindex != NULL);
129 
130  *probindex = SCIPvarGetProbindex(var);
131 
132  /* if variable is not active, try to find active representative */
133  if( *probindex == -1 )
134  {
135  SCIP_VAR* repvar;
136  SCIP_Bool negated;
137 
138  SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
139  assert(repvar != NULL);
140  assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
141 
142  if( SCIPvarIsActive(repvar) )
143  *probindex = SCIPvarGetProbindex(repvar);
144  else if( SCIPvarIsNegated(repvar) )
145  *probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
146  }
147 
148  return SCIP_OKAY;
149 }
150 
151 /** counts number of nonlinear constraints in which each variable appears */
152 static
154  SCIP* scip, /**< SCIP data structure */
155  int* nlcount, /**< pointer to array for storing count values */
156  int nlcountsize, /**< buffer for storing length of nlcount array */
157  int* nlcountmax /**< buffer for storing maximum value in nlcount array */
158  )
159 {
160  SCIP_CONSHDLR* andconshdlr;
161  SCIP_VAR** vars;
162  int nvars;
163  int i;
164 
165  assert(scip != NULL);
166  assert(nlcount != NULL);
167  assert(nlcountmax != NULL);
168 
169  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
170  assert(nlcountsize >= nvars);
171 
172  /* get nonlinearity for constraints in NLP */
173  if( SCIPisNLPConstructed(scip) )
174  {
175  assert(SCIPgetNNLPVars(scip) == nvars);
176  SCIP_CALL( SCIPgetNLPVarsNonlinearity(scip, nlcount) );
177  }
178  else
179  {
180  BMSclearMemoryArray(nlcount, nvars);
181  }
182 
183  /* increase counters for and constraints */
184  andconshdlr = SCIPfindConshdlr(scip, "and");
185  if( andconshdlr != NULL )
186  {
187  int c;
188 
189  for( c = 0; c < SCIPconshdlrGetNActiveConss(andconshdlr); c++ )
190  {
191  SCIP_CONS* andcons;
192  SCIP_VAR** andvars;
193  SCIP_VAR* andres;
194  int probindex;
195  int nandvars;
196  int v;
197 
198  /* get constraint and variables */
199  andcons = SCIPconshdlrGetConss(andconshdlr)[c];
200  nandvars = SCIPgetNVarsAnd(scip, andcons);
201  andvars = SCIPgetVarsAnd(scip, andcons);
202  andres = SCIPgetResultantAnd(scip, andcons);
203 
204  probindex = -1;
205  for( v = 0; v < nandvars; v++ )
206  {
207  /* don't rely on the and conshdlr removing fixed variables
208  * @todo fix the and conshdlr in that respect
209  */
210  if( SCIPvarGetStatus(andvars[v]) != SCIP_VARSTATUS_FIXED )
211  {
212  SCIP_CALL( binvarGetActiveProbindex(scip, andvars[v], &probindex) );
213  if( probindex >= 0 )
214  nlcount[probindex]++;
215  }
216  }
217 
218  SCIP_CALL( binvarGetActiveProbindex(scip, andres, &probindex) );
219  if( probindex >= 0 )
220  nlcount[probindex]++;
221  }
222  }
223 
224  /* compute maximum count value */
225  *nlcountmax = 1;
226  for( i = 0; i < nvars; i++ )
227  {
228  if( *nlcountmax < nlcount[i] )
229  *nlcountmax = nlcount[i];
230  }
231 
232  return SCIP_OKAY;
233 }
234 
235 static
237  SCIP* scip, /**< SCIP data structure */
238  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
239  )
240 {
241  int nvars;
242 
243  assert(scip != NULL);
244  assert(branchruledata != NULL);
245 
246  nvars = SCIPgetNVars(scip);
247 
248  /**@todo test whether we want to apply this as if problem has only and constraints */
249  /**@todo update changes in and constraints */
250  if( branchruledata->nlscoreweight > 0.0 ) /* && SCIPisNLPConstructed(scip) */
251  {
252  if( branchruledata->nlcount == NULL )
253  {
254  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->nlcount, nvars) );
255  branchruledata->nlcountsize = nvars;
256 
257  SCIP_CALL( countNonlinearities(scip, branchruledata->nlcount, branchruledata->nlcountsize, &branchruledata->nlcountmax) );
258  }
259  else if( branchruledata->nlcountsize < nvars )
260  {
261  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->nlcount, branchruledata->nlcountsize, nvars) );
262  /**@todo should we update nlcounts for new variables? */
263  BMSclearMemoryArray(&(branchruledata->nlcount[branchruledata->nlcountsize]), nvars - branchruledata->nlcountsize); /*lint !e866*/
264  branchruledata->nlcountsize = nvars;
265  }
266  assert(branchruledata->nlcount != NULL);
267  assert(branchruledata->nlcountsize == nvars);
268  assert(branchruledata->nlcountmax >= 1);
269  }
270  else
271  {
272  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->nlcount, branchruledata->nlcountsize);
273  branchruledata->nlcountsize = 0;
274  branchruledata->nlcountmax = 1;
275  }
276 
277  return SCIP_OKAY;
278 }
279 
280 
281 /** calculates nlscore value between 0 and 1 */
282 static
284  SCIP* scip, /**< SCIP data structure */
285  int* nlcount, /**< array to store count values */
286  int nlcountmax, /**< maximum value in nlcount array */
287  int probindex /**< index of branching candidate */
288  )
289 {
290  if( nlcountmax >= 1 && nlcount != NULL )
291  {
292  SCIP_Real nlscore;
293 
294  assert(scip != NULL);
295  assert(probindex >= 0);
296  assert(probindex < SCIPgetNVars(scip));
297 
298  nlscore = nlcount[probindex] / (SCIP_Real)nlcountmax;
299 
300  assert(nlscore >= 0.0);
301  assert(nlscore <= 1.0);
302  return nlscore;
303  }
304  else
305  return 0.0;
306 }
307 
308 /** calculates an overall score value for the given individual score values */
309 static
311  SCIP* scip, /**< SCIP data structure */
312  SCIP_BRANCHRULEDATA* branchruledata, /**< branching rule data */
313  SCIP_Real conflictscore, /**< conflict score of current variable */
314  SCIP_Real avgconflictscore, /**< average conflict score */
315  SCIP_Real conflengthscore, /**< conflict length score of current variable */
316  SCIP_Real avgconflengthscore, /**< average conflict length score */
317  SCIP_Real inferencescore, /**< inference score of current variable */
318  SCIP_Real avginferencescore, /**< average inference score */
319  SCIP_Real cutoffscore, /**< cutoff score of current variable */
320  SCIP_Real avgcutoffscore, /**< average cutoff score */
321  SCIP_Real pscostscore, /**< pscost score of current variable */
322  SCIP_Real avgpscostscore, /**< average pscost score */
323  SCIP_Real nlscore, /**< nonlinear score of current variable between 0 and 1 */
324  SCIP_Real frac /**< fractional value of variable in current solution */
325  )
326 {
327  SCIP_Real score;
328  SCIP_Real dynamicfactor;
329 
330  assert(branchruledata != NULL);
331  assert(0.0 < frac && frac < 1.0);
332 
333  if( branchruledata->dynamicweights )
334  {
335  dynamicfactor = (SCIPgetNInfeasibleLeaves(scip) + 1.0) / (SCIPgetNObjlimLeaves(scip) + 1.0);
336  }
337  else
338  dynamicfactor = 1.0;
339 
340  score = dynamicfactor * (branchruledata->conflictweight * (1.0 - 1.0/(1.0+conflictscore/avgconflictscore))
341  + branchruledata->conflengthweight * (1.0 - 1.0/(1.0+conflengthscore/avgconflengthscore))
342  + branchruledata->inferenceweight * (1.0 - 1.0/(1.0+inferencescore/avginferencescore))
343  + branchruledata->cutoffweight * (1.0 - 1.0/(1.0+cutoffscore/avgcutoffscore)))
344  + branchruledata->pscostweight / dynamicfactor * (1.0 - 1.0/(1.0+pscostscore/avgpscostscore))
345  + branchruledata->nlscoreweight * nlscore;
346 
347  /* avoid close to integral variables */
348  if( MIN(frac, 1.0 - frac) < 10.0 * SCIPfeastol(scip) )
349  score *= 1e-6;
350 
351  return score;
352 }
353 
354 /** adds given index and direction to bound change arrays */
355 static
357  SCIP* scip, /**< SCIP data structure */
358  int** bdchginds, /**< pointer to bound change index array */
359  SCIP_BOUNDTYPE** bdchgtypes, /**< pointer to bound change types array */
360  SCIP_Real** bdchgbounds, /**< pointer to bound change new bounds array */
361  int* nbdchgs, /**< pointer to number of bound changes */
362  int ind, /**< index to store in bound change index array */
363  SCIP_BOUNDTYPE type, /**< type of the bound change to store in bound change type array */
364  SCIP_Real bound /**< new bound to store in bound change new bounds array */
365  )
366 {
367  assert(bdchginds != NULL);
368  assert(bdchgtypes != NULL);
369  assert(bdchgbounds != NULL);
370  assert(nbdchgs != NULL);
371 
372  SCIP_CALL( SCIPreallocBufferArray(scip, bdchginds, (*nbdchgs) + 1) );
373  SCIP_CALL( SCIPreallocBufferArray(scip, bdchgtypes, (*nbdchgs) + 1) );
374  SCIP_CALL( SCIPreallocBufferArray(scip, bdchgbounds, (*nbdchgs) + 1) );
375  assert(*bdchginds != NULL);
376  assert(*bdchgtypes != NULL);
377  assert(*bdchgbounds != NULL);
378 
379  (*bdchginds)[*nbdchgs] = ind;
380  (*bdchgtypes)[*nbdchgs] = type;
381  (*bdchgbounds)[*nbdchgs] = bound;
382  (*nbdchgs)++;
383 
384  return SCIP_OKAY;
385 }
386 
387 /** frees bound change arrays */
388 static
389 void freeBdchgs(
390  SCIP* scip, /**< SCIP data structure */
391  int** bdchginds, /**< pointer to bound change index array */
392  SCIP_BOUNDTYPE** bdchgtypes, /**< pointer to bound change types array */
393  SCIP_Real** bdchgbounds, /**< pointer to bound change new bounds array */
394  int* nbdchgs /**< pointer to number of bound changes */
395  )
396 {
397  assert(bdchginds != NULL);
398  assert(bdchgtypes != NULL);
399  assert(bdchgbounds != NULL);
400  assert(nbdchgs != NULL);
401 
402  SCIPfreeBufferArrayNull(scip, bdchgbounds);
403  SCIPfreeBufferArrayNull(scip, bdchgtypes);
404  SCIPfreeBufferArrayNull(scip, bdchginds);
405  *nbdchgs = 0;
406 }
407 
408 /** applies bound changes stored in bound change arrays */
409 static
411  SCIP* scip, /**< SCIP data structure */
412  SCIP_VAR** vars, /**< problem variables */
413  int* bdchginds, /**< bound change index array */
414  SCIP_BOUNDTYPE* bdchgtypes, /**< bound change types array */
415  SCIP_Real* bdchgbounds, /**< bound change new bound array */
416  int nbdchgs, /**< number of bound changes */
417  SCIP_RESULT* result /**< result pointer */
418  )
419 {
420 #ifndef NDEBUG
421  SCIP_BRANCHRULE* branchrule;
422  SCIP_BRANCHRULEDATA* branchruledata;
423 #endif
424  SCIP_Bool infeasible;
425  SCIP_Bool tightened;
426  int i;
427 
428  assert(vars != NULL);
429 
430 #ifndef NDEBUG
431  /* find branching rule */
432  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
433  assert(branchrule != NULL);
434 
435  /* get branching rule data */
436  branchruledata = SCIPbranchruleGetData(branchrule);
437  assert(branchruledata != NULL);
438 #endif
439 
440  SCIPdebugMsg(scip, "applying %d bound changes\n", nbdchgs);
441 
442  for( i = 0; i < nbdchgs; ++i )
443  {
444  int v;
445 
446  v = bdchginds[i];
447 
448  SCIPdebugMsg(scip, " -> <%s> [%g,%g]\n",
449  SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v]));
450 
451  if( bdchgtypes[i] == SCIP_BOUNDTYPE_LOWER )
452  {
453  /* change lower bound of variable to given bound */
454  SCIP_CALL( SCIPtightenVarLb(scip, vars[v], bdchgbounds[i], TRUE, &infeasible, &tightened) );
455  if( infeasible )
456  {
457  *result = SCIP_CUTOFF;
458  return SCIP_OKAY;
459  }
460 
461  /* if we did propagation, the bound change might already have been added */
462  assert(tightened || (branchruledata->maxproprounds != 0));
463  }
464  else
465  {
466  assert(bdchgtypes[i] == SCIP_BOUNDTYPE_UPPER);
467 
468  /* change upper bound of variable to given bound */
469  SCIP_CALL( SCIPtightenVarUb(scip, vars[v], bdchgbounds[i], TRUE, &infeasible, &tightened) );
470  if( infeasible )
471  {
472  *result = SCIP_CUTOFF;
473  return SCIP_OKAY;
474  }
475 
476  /* if we did propagation, the bound change might already have been added */
477  assert(tightened || (branchruledata->maxproprounds != 0));
478  }
479  SCIPdebugMsg(scip, " -> [%g,%g]\n", SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v]));
480  }
481 
482  return SCIP_OKAY;
483 }
484 
485 /** execute reliability pseudo cost branching */
486 static
488  SCIP* scip, /**< SCIP data structure */
489  SCIP_BRANCHRULE* branchrule, /**< branching rule */
490  SCIP_VAR** branchcands, /**< branching candidates */
491  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
492  SCIP_Real* branchcandsfrac, /**< fractional part of the branching candidates */
493  int nbranchcands, /**< number of branching candidates */
494  SCIP_Bool executebranch, /**< execute a branching step or run probing only */
495  SCIP_RESULT* result /**< pointer to the result of the execution */
496  )
497 { /*lint --e{715}*/
498  SCIP_BRANCHRULEDATA* branchruledata;
499  SCIP_Real lpobjval;
500  SCIP_Real bestsbdown;
501  SCIP_Real bestsbup;
502  SCIP_Real provedbound;
503  SCIP_Bool bestsbdownvalid;
504  SCIP_Bool bestsbupvalid;
505  SCIP_Bool bestsbdowncutoff;
506  SCIP_Bool bestsbupcutoff;
507  SCIP_Bool bestisstrongbranch;
508  SCIP_Bool allcolsinlp;
509  SCIP_Bool exactsolve;
510  int ninitcands;
511  int bestcand;
512 
513  *result = SCIP_DIDNOTRUN;
514 
515  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
516 
517  /* get branching rule data */
518  branchruledata = SCIPbranchruleGetData(branchrule);
519  assert(branchruledata != NULL);
520 
521  /* get current LP objective bound of the local sub problem and global cutoff bound */
522  lpobjval = SCIPgetLPObjval(scip);
523 
524  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
525  * for cutting off sub problems and improving lower bounds of children
526  */
527  exactsolve = SCIPisExactSolve(scip);
528 
529  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
530  allcolsinlp = SCIPallColsInLP(scip);
531 
532  bestcand = -1;
533  bestisstrongbranch = FALSE;
534  bestsbdown = SCIP_INVALID;
535  bestsbup = SCIP_INVALID;
536  bestsbdownvalid = FALSE;
537  bestsbupvalid = FALSE;
538  bestsbdowncutoff = FALSE;
539  bestsbupcutoff = FALSE;
540  provedbound = lpobjval;
541 
542  if( nbranchcands == 1 )
543  {
544  /* only one candidate: nothing has to be done */
545  bestcand = 0;
546  SCIPdebug(ninitcands = 0);
547  }
548  else
549  {
550  SCIP_VAR** vars;
551  int* initcands;
552  SCIP_Real* initcandscores;
553  SCIP_Real* newlbs = NULL;
554  SCIP_Real* newubs = NULL;
555  int* bdchginds;
556  SCIP_BOUNDTYPE* bdchgtypes;
557  SCIP_Real* bdchgbounds;
558  int maxninitcands;
559  int nuninitcands;
560  int nbdchgs;
561  int nbdconflicts;
562  SCIP_Real avgconflictscore;
563  SCIP_Real avgconflengthscore;
564  SCIP_Real avginferencescore;
565  SCIP_Real avgcutoffscore;
566  SCIP_Real avgpscostscore;
567  SCIP_Real bestpsscore;
568  SCIP_Real bestpsfracscore;
569  SCIP_Real bestpsdomainscore;
570  SCIP_Real bestsbscore;
571  SCIP_Real bestuninitsbscore;
572  SCIP_Real bestsbfracscore;
573  SCIP_Real bestsbdomainscore;
574  SCIP_Real prio;
575  SCIP_Real reliable;
576  SCIP_Real maxlookahead;
577  SCIP_Real lookahead;
578  SCIP_Real relerrorthreshold;
579  SCIP_Bool initstrongbranching;
580  SCIP_Bool propagate;
581  SCIP_Bool probingbounds;
582  SCIP_Longint nodenum;
583  SCIP_Longint nlpiterationsquot;
584  SCIP_Longint nsblpiterations;
585  SCIP_Longint maxnsblpiterations;
586  int bestsolidx;
587  int maxbdchgs;
588  int bestpscand;
589  int bestsbcand;
590  int bestuninitsbcand;
591  int inititer;
592  int nvars;
593  int i;
594  int c;
595  SCIP_CONFIDENCELEVEL clevel;
596 
597  vars = SCIPgetVars(scip);
598  nvars = SCIPgetNVars(scip);
599 
600  bestsolidx = SCIPgetBestSol(scip) == NULL ? -1 : SCIPsolGetIndex(SCIPgetBestSol(scip));
601 
602  /* get average conflict, inference, and pseudocost scores */
603  avgconflictscore = SCIPgetAvgConflictScore(scip);
604  avgconflictscore = MAX(avgconflictscore, 0.1);
605  avgconflengthscore = SCIPgetAvgConflictlengthScore(scip);
606  avgconflengthscore = MAX(avgconflengthscore, 0.1);
607  avginferencescore = SCIPgetAvgInferenceScore(scip);
608  avginferencescore = MAX(avginferencescore, 0.1);
609  avgcutoffscore = SCIPgetAvgCutoffScore(scip);
610  avgcutoffscore = MAX(avgcutoffscore, 0.1);
611  avgpscostscore = SCIPgetAvgPseudocostScore(scip);
612  avgpscostscore = MAX(avgpscostscore, 0.1);
613 
614  /* get nonlinear counts according to parameters */
615  SCIP_CALL( branchruledataEnsureNlcount(scip, branchruledata) );
616 
617  initstrongbranching = FALSE;
618 
619  /* check whether propagation should be performed */
620  propagate = (branchruledata->maxproprounds != 0);
621 
622  /* check whether valid bounds should be identified in probing-like fashion */
623  probingbounds = propagate && branchruledata->probingbounds;
624 
625  /* get maximal number of candidates to initialize with strong branching; if the current solutions is not basic,
626  * we cannot warmstart the simplex algorithm and therefore don't initialize any candidates
627  */
628  maxninitcands = MIN(nbranchcands, branchruledata->initcand);
629  if( !SCIPisLPSolBasic(scip) )
630  maxninitcands = 0;
631 
632  /* calculate maximal number of strong branching LP iterations; if we used too many, don't apply strong branching
633  * any more
634  */
635  nlpiterationsquot = (SCIP_Longint)(branchruledata->sbiterquot * SCIPgetNNodeLPIterations(scip));
636  maxnsblpiterations = nlpiterationsquot + branchruledata->sbiterofs + SCIPgetNRootStrongbranchLPIterations(scip);
637  nsblpiterations = SCIPgetNStrongbranchLPIterations(scip);
638  if( nsblpiterations > maxnsblpiterations )
639  maxninitcands = 0;
640 
641  /* get buffer for storing the unreliable candidates */
642  SCIP_CALL( SCIPallocBufferArray(scip, &initcands, maxninitcands+1) ); /* allocate one additional slot for convenience */
643  SCIP_CALL( SCIPallocBufferArray(scip, &initcandscores, maxninitcands+1) );
644  ninitcands = 0;
645 
646  /* get current node number */
647  nodenum = SCIPgetNNodes(scip);
648 
649  /* initialize bound change arrays */
650  bdchginds = NULL;
651  bdchgtypes = NULL;
652  bdchgbounds = NULL;
653  nbdchgs = 0;
654  nbdconflicts = 0;
655  maxbdchgs = branchruledata->maxbdchgs;
656  if( maxbdchgs == -1 )
657  maxbdchgs = INT_MAX;
658 
659  /* calculate value used as reliability */
660  prio = (maxnsblpiterations - nsblpiterations)/(nsblpiterations + 1.0);
661  prio = MIN(prio, 1.0);
662  prio = MAX(prio, (nlpiterationsquot - nsblpiterations)/(nsblpiterations + 1.0));
663  reliable = (1.0-prio) * branchruledata->minreliable + prio * branchruledata->maxreliable;
664 
665  /* calculate the threshold for the relative error in the same way; low tolerance is more strict than higher tolerance */
666  relerrorthreshold = (1.0 - prio) * branchruledata->higherrortol + prio * branchruledata->lowerrortol;
667 
668  clevel = (SCIP_CONFIDENCELEVEL)branchruledata->confidencelevel;
669  /* determine the confidence level for hypothesis testing based on value of prio */
670  if( branchruledata->usedynamicconfidence )
671  {
672  /* with decreasing priority, use a less strict confidence level */
673  if( prio >= 0.9 )
674  clevel = SCIP_CONFIDENCELEVEL_MAX;
675  else if( prio >= 0.7 )
676  clevel = SCIP_CONFIDENCELEVEL_HIGH;
677  else if( prio >= 0.5 )
679  else if( prio >= 0.3 )
680  clevel = SCIP_CONFIDENCELEVEL_LOW;
681  else
682  clevel = SCIP_CONFIDENCELEVEL_MIN;
683  }
684 
685  /* search for the best pseudo cost candidate, while remembering unreliable candidates in a sorted buffer */
686  nuninitcands = 0;
687  bestpscand = -1;
688  bestpsscore = -SCIPinfinity(scip);
689  bestpsfracscore = -SCIPinfinity(scip);
690  bestpsdomainscore = -SCIPinfinity(scip);
691 
692  /* search for the best candidate first */
693  if( branchruledata->usehyptestforreliability )
694  {
695  for( c = 0; c < nbranchcands; ++c )
696  {
697  SCIP_Real conflictscore;
698  SCIP_Real conflengthscore;
699  SCIP_Real inferencescore;
700  SCIP_Real cutoffscore;
701  SCIP_Real pscostscore;
702  SCIP_Real nlscore;
703  SCIP_Real score;
704 
705  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
706  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
707  inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
708  cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
709  nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
710  pscostscore = SCIPgetVarPseudocostScore(scip, branchcands[c], branchcandssol[c]);
711 
712  /* replace the pseudo cost score with the already calculated one;
713  * @todo: use old data for strong branching with propagation?
714  */
715  if( SCIPgetVarStrongbranchNode(scip, branchcands[c]) == nodenum )
716  {
717  SCIP_Real down;
718  SCIP_Real up;
719  SCIP_Real lastlpobjval;
720  SCIP_Real downgain;
721  SCIP_Real upgain;
722 
723  /* use the score of the strong branching call at the current node */
724  SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
725  downgain = MAX(down - lastlpobjval, 0.0);
726  upgain = MAX(up - lastlpobjval, 0.0);
727  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
728 
729  SCIPdebugMsg(scip, " -> strong branching on variable <%s> already performed (down=%g (%+g), up=%g (%+g), pscostscore=%g)\n",
730  SCIPvarGetName(branchcands[c]), down, downgain, up, upgain, pscostscore);
731  }
732 
733  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
734  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, nlscore, branchcandsfrac[c]);
735 
736  /* check for better score of candidate */
737  if( SCIPisSumGE(scip, score, bestpsscore) )
738  {
739  SCIP_Real fracscore;
740  SCIP_Real domainscore;
741 
742  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
743  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
744  if( SCIPisSumGT(scip, score, bestpsscore)
745  || SCIPisSumGT(scip, fracscore, bestpsfracscore)
746  || (SCIPisSumGE(scip, fracscore, bestpsfracscore) && domainscore > bestpsdomainscore) )
747  {
748  bestpscand = c;
749  bestpsscore = score;
750  bestpsfracscore = fracscore;
751  bestpsdomainscore = domainscore;
752  }
753  }
754  }
755  }
756 
757  for( c = 0; c < nbranchcands; ++c )
758  {
759  SCIP_Real conflictscore;
760  SCIP_Real conflengthscore;
761  SCIP_Real inferencescore;
762  SCIP_Real cutoffscore;
763  SCIP_Real pscostscore;
764  SCIP_Real nlscore;
765  SCIP_Real score;
766  SCIP_Bool usesb;
767 
768  assert(branchcands[c] != NULL);
769  assert(!SCIPisFeasIntegral(scip, branchcandssol[c]));
770 
771  /* get conflict, inference, cutoff, nonlinear, and pseudo cost scores for candidate */
772  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
773  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
774  inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
775  cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
776  nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
777  pscostscore = SCIPgetVarPseudocostScore(scip, branchcands[c], branchcandssol[c]);
778  usesb = FALSE;
779 
780  /* don't use strong branching on variables that have already been initialized at the current node;
781  * instead replace the pseudo cost score with the already calculated one;
782  * @todo: use old data for strong branching with propagation?
783  */
784  if( SCIPgetVarStrongbranchNode(scip, branchcands[c]) == nodenum )
785  {
786  SCIP_Real down;
787  SCIP_Real up;
788  SCIP_Real lastlpobjval;
789  SCIP_Real downgain;
790  SCIP_Real upgain;
791 
792  /* use the score of the strong branching call at the current node */
793  SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
794  downgain = MAX(down - lastlpobjval, 0.0);
795  upgain = MAX(up - lastlpobjval, 0.0);
796  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
797 
798  SCIPdebugMsg(scip, " -> strong branching on variable <%s> already performed (down=%g (%+g), up=%g (%+g), pscostscore=%g)\n",
799  SCIPvarGetName(branchcands[c]), down, downgain, up, upgain, pscostscore);
800  }
801  else if( maxninitcands > 0 )
802  {
803  SCIP_Real downsize;
804  SCIP_Real upsize;
805  SCIP_Real size;
806 
807  /* check, if the pseudo cost score of the variable is reliable */
808  downsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_DOWNWARDS);
809  upsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_UPWARDS);
810  size = MIN(downsize, upsize);
811 
812  /* determine if variable is considered reliable based on the current reliability setting */
813  /* check fixed number threshold (aka original) reliability first */
814  assert(!branchruledata->usehyptestforreliability || bestpscand >= 0);
815  usesb = FALSE;
816  if( size < reliable )
817  usesb = TRUE;
818  else if( branchruledata->userelerrorforreliability && branchruledata->usehyptestforreliability )
819  {
820  if( !SCIPisVarPscostRelerrorReliable(scip, branchcands[c], relerrorthreshold, clevel) &&
821  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
822  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE) &&
823  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1 - branchcandsfrac[bestpscand],
824  branchcands[c], 1 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
825  usesb = TRUE;
826  }
827  /* check if relative error is tolerable */
828  else if( branchruledata->userelerrorforreliability &&
829  !SCIPisVarPscostRelerrorReliable(scip, branchcands[c], relerrorthreshold, clevel))
830  usesb = TRUE;
831  /* check if best pseudo-candidate is significantly better in both directions, use strong-branching otherwise */
832  else if( branchruledata->usehyptestforreliability &&
833  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
834  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE) &&
835  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1 - branchcandsfrac[bestpscand],
836  branchcands[c], 1 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE))
837  usesb = TRUE;
838 
839  /* count the number of variables that are completely uninitialized */
840  if( size < 0.1 )
841  nuninitcands++;
842  }
843 
844  /* combine the five score values */
845  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
846  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, nlscore, branchcandsfrac[c]);
847 
848  if( usesb )
849  {
850  int j;
851 
852  /* assign a random score to this uninitialized candidate */
853  if( branchruledata->randinitorder )
854  score += SCIPrandomGetReal(branchruledata->randnumgen, 0.0, 1e-4);
855 
856  /* pseudo cost of variable is not reliable: insert candidate in initcands buffer */
857  for( j = ninitcands; j > 0 && score > initcandscores[j-1]; --j )
858  {
859  initcands[j] = initcands[j-1];
860  initcandscores[j] = initcandscores[j-1];
861  }
862  initcands[j] = c;
863  initcandscores[j] = score;
864  ninitcands++;
865  ninitcands = MIN(ninitcands, maxninitcands);
866  }
867  /* in the case of hypothesis reliability, the best pseudo candidate has been determined already */
868  else if( !branchruledata->usehyptestforreliability )
869  {
870  /* variable will keep it's pseudo cost value: check for better score of candidate */
871  if( SCIPisSumGE(scip, score, bestpsscore) )
872  {
873  SCIP_Real fracscore;
874  SCIP_Real domainscore;
875 
876  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
877  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
878  if( SCIPisSumGT(scip, score, bestpsscore)
879  || SCIPisSumGT(scip, fracscore, bestpsfracscore)
880  || (SCIPisSumGE(scip, fracscore, bestpsfracscore) && domainscore > bestpsdomainscore) )
881  {
882  bestpscand = c;
883  bestpsscore = score;
884  bestpsfracscore = fracscore;
885  bestpsdomainscore = domainscore;
886  }
887  }
888  }
889  }
890 
891  /* in the special case that only the best pseudo candidate was selected for strong branching, skip the strong branching */
892  if( branchruledata->usehyptestforreliability && ninitcands == 1 )
893  {
894  ninitcands = 0;
895  SCIPdebugMsg(scip, "Only one single candidate for initialization-->Skipping strong branching\n");
896  }
897 
898  /* initialize unreliable candidates with strong branching until maxlookahead is reached,
899  * search best strong branching candidate
900  */
901  maxlookahead = (SCIP_Real)branchruledata->maxlookahead * (1.0 + (SCIP_Real)nuninitcands/(SCIP_Real)nbranchcands);
902  inititer = branchruledata->inititer;
903  if( inititer == 0 )
904  {
905  SCIP_Longint nlpiterations;
906  SCIP_Longint nlps;
907 
908  /* iteration limit is set to twice the average number of iterations spent to resolve a dual feasible SCIP_LP;
909  * at the first few nodes, this average is not very exact, so we better increase the iteration limit on
910  * these very important nodes
911  */
912  nlpiterations = SCIPgetNDualResolveLPIterations(scip);
913  nlps = SCIPgetNDualResolveLPs(scip);
914  if( nlps == 0 )
915  {
916  nlpiterations = SCIPgetNNodeInitLPIterations(scip);
917  nlps = SCIPgetNNodeInitLPs(scip);
918  if( nlps == 0 )
919  {
920  nlpiterations = 1000;
921  nlps = 1;
922  }
923  }
924  assert(nlps >= 1);
925  inititer = (int)(2*nlpiterations / nlps);
926  inititer = (int)((SCIP_Real)inititer * (1.0 + 20.0/nodenum));
927  inititer = MAX(inititer, 10);
928  inititer = MIN(inititer, 500);
929  }
930 
931  SCIPdebugMsg(scip, "strong branching (reliable=%g, %d/%d cands, %d uninit, maxcands=%d, maxlookahead=%g, maxbdchgs=%d, inititer=%d, iterations:%" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", basic:%u)\n",
932  reliable, ninitcands, nbranchcands, nuninitcands, maxninitcands, maxlookahead, maxbdchgs, inititer,
933  SCIPgetNStrongbranchLPIterations(scip), maxnsblpiterations, SCIPisLPSolBasic(scip));
934 
935  bestsbcand = -1;
936  bestsbscore = -SCIPinfinity(scip);
937  bestsbfracscore = -SCIPinfinity(scip);
938  bestsbdomainscore = -SCIPinfinity(scip);
939  bestuninitsbscore = -SCIPinfinity(scip);
940  bestuninitsbcand = -1;
941  lookahead = 0.0;
942  for( i = 0; i < ninitcands && lookahead < maxlookahead && nbdchgs + nbdconflicts < maxbdchgs
943  && (i < (int) maxlookahead || SCIPgetNStrongbranchLPIterations(scip) < maxnsblpiterations); ++i )
944  {
945  SCIP_Real down;
946  SCIP_Real up;
947  SCIP_Real downgain;
948  SCIP_Real upgain;
949  SCIP_Bool downvalid;
950  SCIP_Bool upvalid;
951  SCIP_Longint ndomredsdown;
952  SCIP_Longint ndomredsup;
953  SCIP_Bool lperror;
954  SCIP_Bool downinf;
955  SCIP_Bool upinf;
956  SCIP_Bool downconflict;
957  SCIP_Bool upconflict;
958 
959  /* get candidate number to initialize */
960  c = initcands[i];
961  assert(!SCIPisFeasIntegral(scip, branchcandssol[c]));
962 
963  if( branchruledata->skipbadinitcands )
964  {
965  SCIP_Bool skipsb = FALSE;
966  /* if the current best candidate is a candidate found by strong branching, determine if candidate pseudo-costs are
967  * significantly smaller in at least one direction, in which case we safe the execution of strong-branching for now
968  */
969  if( bestsbscore > bestpsscore && bestsbscore > bestuninitsbscore && bestsbupvalid && bestsbdownvalid )
970  {
971  assert(bestsbcand != -1);
972  assert(bestsbup != SCIP_INVALID && bestsbdown != SCIP_INVALID); /*lint !e777 lint doesn't like comparing floats */
973 
974  /* test if the variable is unlikely to produce a better gain than the currently best one. Skip strong-branching
975  * in such a case
976  */
977  if( SCIPpscostThresholdProbabilityTest(scip, branchcands[c], branchcandsfrac[c], bestsbdown,
978  SCIP_BRANCHDIR_DOWNWARDS, clevel)
979  || SCIPpscostThresholdProbabilityTest(scip, branchcands[c], 1.0 - branchcandsfrac[c], bestsbup,
980  SCIP_BRANCHDIR_UPWARDS, clevel) )
981  skipsb = TRUE;
982  }
983  /* the currently best candidate is also a pseudo-candidate; apply significance test and skip candidate if it
984  * is significantly worse in at least one direction
985  */
986  else if( bestpscand != -1 && bestpsscore > bestuninitsbscore )
987  {
988  if( SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
989  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE)
990  || SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1.0 - branchcandsfrac[bestpscand],
991  branchcands[c], 1.0 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
992  skipsb = TRUE;
993  }
994  /* compare against the best init cand that has been skipped already */
995  else if( bestuninitsbcand != -1 )
996  {
997  if( SCIPsignificantVarPscostDifference(scip, branchcands[bestuninitsbcand], branchcandsfrac[bestuninitsbcand],
998  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE)
999  || SCIPsignificantVarPscostDifference(scip, branchcands[bestuninitsbcand], 1.0 - branchcandsfrac[bestuninitsbcand],
1000  branchcands[c], 1.0 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
1001  skipsb = TRUE;
1002  }
1003 
1004  /* skip candidate, update the best score of an unitialized candidate */
1005  if( skipsb )
1006  {
1007  if( bestuninitsbcand == -1 )
1008  {
1009  bestuninitsbcand = c;
1010  bestuninitsbscore = initcandscores[i];
1011  }
1012  continue;
1013  }
1014  }
1015  SCIPdebugMsg(scip, "init pseudo cost (%g/%g) of <%s> at %g (score:%g) with strong branching (%d iterations) -- %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT " iterations\n",
1018  SCIPvarGetName(branchcands[c]), branchcandssol[c], initcandscores[i],
1019  inititer, SCIPgetNStrongbranchLPIterations(scip), maxnsblpiterations);
1020 
1021  /* use strong branching on candidate */
1022  if( !initstrongbranching )
1023  {
1024  initstrongbranching = TRUE;
1025 
1026  SCIP_CALL( SCIPstartStrongbranch(scip, propagate) );
1027 
1028  /* create arrays for probing-like bound tightening */
1029  if( probingbounds )
1030  {
1031  SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
1032  SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
1033  }
1034  }
1035 
1036  if( propagate )
1037  {
1038  /* apply strong branching */
1039  SCIP_CALL( SCIPgetVarStrongbranchWithPropagation(scip, branchcands[c], branchcandssol[c], lpobjval, inititer,
1040  branchruledata->maxproprounds, &down, &up, &downvalid, &upvalid, &ndomredsdown, &ndomredsup, &downinf, &upinf,
1041  &downconflict, &upconflict, &lperror, newlbs, newubs) );
1042  }
1043  else
1044  {
1045  /* apply strong branching */
1046  SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, branchcands[c], inititer,
1047  &down, &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
1048 
1049  ndomredsdown = ndomredsup = 0;
1050  }
1051 
1052  /* check for an error in strong branching */
1053  if( lperror )
1054  {
1055  if( !SCIPisStopped(scip) )
1056  {
1058  "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call for variable <%s> with solution %g\n",
1059  SCIPgetNNodes(scip), SCIPvarGetName(branchcands[c]), branchcandssol[c]);
1060  }
1061  break;
1062  }
1063 
1064  /* Strong branching might have found a new primal solution which updated the cutoff bound. In this case, the
1065  * provedbound computed before can be higher than the cutoffbound and the current node can be cut off.
1066  * Additionally, also if the value for the current best candidate is valid and exceeds the new cutoff bound,
1067  * we want to change the domain of this variable rather than branching on it.
1068  */
1069  if( SCIPgetBestSol(scip) != NULL && SCIPsolGetIndex(SCIPgetBestSol(scip)) != bestsolidx )
1070  {
1071  bestsolidx = SCIPsolGetIndex(SCIPgetBestSol(scip));
1072 
1073  SCIPdebugMsg(scip, " -> strong branching on variable <%s> lead to a new incumbent\n",
1074  SCIPvarGetName(branchcands[c]));
1075 
1076  /* proved bound for current node is larger than new cutoff bound -> cut off current node */
1077  if( SCIPisGE(scip, provedbound, SCIPgetCutoffbound(scip)) )
1078  {
1079  SCIPdebugMsg(scip, " -> node can be cut off (provedbound=%g, cutoff=%g)\n", provedbound, SCIPgetCutoffbound(scip));
1080 
1081  *result = SCIP_CUTOFF;
1082  break; /* terminate initialization loop, because node is infeasible */
1083  }
1084  /* proved bound for down child of best candidate is larger than cutoff bound
1085  * -> increase lower bound of best candidate
1086  * we must only do this if the LP is complete, i.e., we are not doing column generation
1087  */
1088 
1089  else if( bestsbcand != -1 && allcolsinlp )
1090  {
1091  if( !bestsbdowncutoff && bestsbdownvalid && SCIPisGE(scip, bestsbdown, SCIPgetCutoffbound(scip)) )
1092  {
1093  bestsbdowncutoff = TRUE;
1094 
1095  SCIPdebugMsg(scip, " -> valid dual bound for down child of best candidate <%s> is higher than new cutoff bound (valid=%u, bestsbdown=%g, cutoff=%g)\n",
1096  SCIPvarGetName(branchcands[bestsbcand]), bestsbdownvalid, bestsbdown, SCIPgetCutoffbound(scip));
1097 
1098  SCIPdebugMsg(scip, " -> increase lower bound of best candidate <%s> to %g\n",
1099  SCIPvarGetName(branchcands[bestsbcand]), SCIPfeasCeil(scip, branchcandssol[bestsbcand]));
1100 
1101  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[bestsbcand]),
1102  SCIP_BOUNDTYPE_LOWER, SCIPfeasCeil(scip, branchcandssol[bestsbcand])) );
1103  }
1104  /* proved bound for up child of best candidate is larger than cutoff bound -> decrease upper bound of best candidate */
1105  else if( !bestsbupcutoff && bestsbupvalid && SCIPisGE(scip, bestsbup, SCIPgetCutoffbound(scip)) )
1106  {
1107  bestsbupcutoff = TRUE;
1108 
1109  SCIPdebugMsg(scip, " -> valid dual bound for up child of best candidate <%s> is higher than new cutoff bound (valid=%u, bestsbup=%g, cutoff=%g)\n",
1110  SCIPvarGetName(branchcands[bestsbcand]), bestsbupvalid, bestsbup, SCIPgetCutoffbound(scip));
1111 
1112  SCIPdebugMsg(scip, " -> decrease upper bound of best candidate <%s> to %g\n",
1113  SCIPvarGetName(branchcands[bestsbcand]), SCIPfeasFloor(scip, branchcandssol[bestsbcand]));
1114 
1115  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[bestsbcand]),
1116  SCIP_BOUNDTYPE_UPPER, SCIPfeasFloor(scip, branchcandssol[bestsbcand])) );
1117  }
1118  }
1119  }
1120 
1121  /* evaluate strong branching */
1122  down = MAX(down, lpobjval);
1123  up = MAX(up, lpobjval);
1124  downgain = down - lpobjval;
1125  upgain = up - lpobjval;
1126  assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
1127  assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
1128  assert(downinf || !downconflict);
1129  assert(upinf || !upconflict);
1130 
1131  /* @todo: store pseudo cost only for valid bounds?
1132  * depending on the user parameter choice of storesemiinitcosts, pseudo costs are also updated in single directions,
1133  * if the node in the other direction was infeasible or cut off
1134  */
1135  if( !downinf
1136 #ifdef WITH_LPSOLSTAT
1138 #endif
1139  && (!upinf || branchruledata->storesemiinitcosts) )
1140  {
1141  SCIP_Real weight;
1142 
1143  /* smaller weights are given if the strong branching hit the time limit in the corresponding direction */
1144  if( branchruledata->usesmallweightsitlim )
1146  else
1147  weight = 1.0;
1148 
1149  /* update pseudo cost values */
1150  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchcands[c], 0.0 - branchcandsfrac[c], downgain, weight) );
1151  }
1152  if( !upinf
1153 #ifdef WITH_LPSOLSTAT
1155 #endif
1156  && (!downinf || branchruledata->storesemiinitcosts) )
1157  {
1158  SCIP_Real weight;
1159 
1160  /* smaller weights are given if the strong branching hit the time limit in the corresponding direction */
1161  if( branchruledata->usesmallweightsitlim )
1163  else
1164  weight = 1.0;
1165 
1166  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchcands[c], 1.0 - branchcandsfrac[c], upgain, weight) );
1167  }
1168 
1169  /* the minimal lower bound of both children is a proved lower bound of the current subtree */
1170  if( allcolsinlp && !exactsolve && downvalid && upvalid )
1171  {
1172  SCIP_Real minbound;
1173 
1174  minbound = MIN(down, up);
1175  provedbound = MAX(provedbound, minbound);
1176  assert((downinf && upinf) || SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1177 
1178  /* save probing-like bounds detected during strong branching */
1179  if( probingbounds )
1180  {
1181  int v;
1182 
1183  assert(newlbs != NULL);
1184  assert(newubs != NULL);
1185 
1186  for( v = 0; v < nvars; ++v )
1187  {
1188  if( SCIPisGT(scip, newlbs[v], SCIPvarGetLbLocal(vars[v])) )
1189  {
1190  SCIPdebugMsg(scip, "better lower bound for variable <%s>: %.9g -> %.9g (by strongbranching on <%s>)\n",
1191  SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), newlbs[v], SCIPvarGetName(branchcands[c]));
1192 
1193  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, v,
1194  SCIP_BOUNDTYPE_LOWER, newlbs[v]) );
1195  }
1196  if( SCIPisLT(scip, newubs[v], SCIPvarGetUbLocal(vars[v])) )
1197  {
1198  SCIPdebugMsg(scip, "better upper bound for variable <%s>: %.9g -> %.9g (by strongbranching on <%s>)\n",
1199  SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), newubs[v], SCIPvarGetName(branchcands[c]));
1200 
1201  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, v,
1202  SCIP_BOUNDTYPE_UPPER, newubs[v]) );
1203  }
1204  }
1205  }
1206  }
1207 
1208  /* check if there are infeasible roundings */
1209  if( downinf || upinf )
1210  {
1211  assert(allcolsinlp || propagate);
1212  assert(!exactsolve);
1213 
1214  if( downinf && upinf )
1215  {
1216  /* both roundings are infeasible -> node is infeasible */
1217  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions (conflict: %u/%u)\n",
1218  SCIPvarGetName(branchcands[c]), downconflict, upconflict);
1219  *result = SCIP_CUTOFF;
1220  break; /* terminate initialization loop, because node is infeasible */
1221  }
1222  else
1223  {
1224  /* rounding is infeasible in one direction -> round variable in other direction */
1225  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in %s branch (conflict: %u/%u)\n",
1226  SCIPvarGetName(branchcands[c]), downinf ? "downward" : "upward", downconflict, upconflict);
1227  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[c]),
1229  (downinf ? SCIPfeasCeil(scip, branchcandssol[c]) : SCIPfeasFloor(scip, branchcandssol[c]))) );
1230  if( nbdchgs + nbdconflicts >= maxbdchgs )
1231  break; /* terminate initialization loop, because enough roundings are performed */
1232  }
1233  }
1234  else
1235  {
1236  SCIP_Real conflictscore;
1237  SCIP_Real conflengthscore;
1238  SCIP_Real inferencescore;
1239  SCIP_Real cutoffscore;
1240  SCIP_Real pscostscore;
1241  SCIP_Real nlscore;
1242  SCIP_Real score;
1243 
1244  /* check for a better score */
1245  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
1246  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
1247  nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
1248 
1249  /* optionally, use only local information obtained via strong branching for this candidate, i.e., local
1250  * domain reductions and no cutoff score
1251  */
1252  inferencescore = branchruledata->usesblocalinfo ? SCIPgetBranchScore(scip, branchcands[c], (SCIP_Real)ndomredsdown, (SCIP_Real)ndomredsup)
1253  : SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
1254  cutoffscore = branchruledata->usesblocalinfo ? 0.0 : SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
1255  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
1256 
1257  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1258  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, nlscore, branchcandsfrac[c]);
1259 
1260  if( SCIPisSumGE(scip, score, bestsbscore) )
1261  {
1262  SCIP_Real fracscore;
1263  SCIP_Real domainscore;
1264 
1265  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
1266  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
1267  if( SCIPisSumGT(scip, score, bestsbscore)
1268  || SCIPisSumGT(scip, fracscore, bestsbfracscore)
1269  || (SCIPisSumGE(scip, fracscore, bestsbfracscore) && domainscore > bestsbdomainscore) )
1270  {
1271  bestsbcand = c;
1272  bestsbscore = score;
1273  bestsbdown = down;
1274  bestsbup = up;
1275  bestsbdownvalid = downvalid;
1276  bestsbupvalid = upvalid;
1277  bestsbdowncutoff = FALSE;
1278  bestsbupcutoff = FALSE;
1279  bestsbfracscore = fracscore;
1280  bestsbdomainscore = domainscore;
1281  lookahead = 0.0;
1282  }
1283  else
1284  lookahead += 0.5;
1285  }
1286  else
1287  lookahead += 1.0;
1288 
1289  SCIPdebugMsg(scip, " -> variable <%s> (solval=%g, down=%g (%+g,valid=%u), up=%g (%+g,valid=%u), score=%g/ %g/%g %g/%g -> %g)\n",
1290  SCIPvarGetName(branchcands[c]), branchcandssol[c], down, downgain, downvalid, up, upgain, upvalid,
1291  pscostscore, conflictscore, conflengthscore, inferencescore, cutoffscore, score);
1292  }
1293  }
1294 #ifdef SCIP_DEBUG
1295  if( bestsbcand >= 0 )
1296  {
1297  SCIPdebugMsg(scip, " -> best: <%s> (%g / %g / %g), lookahead=%g/%g\n",
1298  SCIPvarGetName(branchcands[bestsbcand]), bestsbscore, bestsbfracscore, bestsbdomainscore,
1299  lookahead, maxlookahead);
1300  }
1301 #endif
1302 
1303  if( initstrongbranching )
1304  {
1305  if( probingbounds )
1306  {
1307  assert(newlbs != NULL);
1308  assert(newubs != NULL);
1309 
1310  SCIPfreeBufferArray(scip, &newubs);
1311  SCIPfreeBufferArray(scip, &newlbs);
1312  }
1313 
1314  SCIP_CALL( SCIPendStrongbranch(scip) );
1315 
1317  {
1318  assert(SCIPhasCurrentNodeLP(scip));
1319  *result = SCIP_CUTOFF;
1320  }
1321  }
1322 
1323  if( *result != SCIP_CUTOFF )
1324  {
1325  /* get the score of the best uninitialized strong branching candidate */
1326  if( i < ninitcands && bestuninitsbcand == -1 )
1327  bestuninitsbscore = initcandscores[i];
1328 
1329  /* if the best pseudo cost candidate is better than the best uninitialized strong branching candidate,
1330  * compare it to the best initialized strong branching candidate
1331  */
1332  if( bestpsscore > bestuninitsbscore && SCIPisSumGT(scip, bestpsscore, bestsbscore) )
1333  {
1334  bestcand = bestpscand;
1335  bestisstrongbranch = FALSE;
1336  }
1337  else if( bestsbcand >= 0 )
1338  {
1339  bestcand = bestsbcand;
1340  bestisstrongbranch = TRUE;
1341  }
1342  else
1343  {
1344  /* no candidate was initialized, and the best score is the one of the first candidate in the initialization
1345  * queue
1346  */
1347  assert(ninitcands >= 1);
1348  bestcand = initcands[0];
1349  bestisstrongbranch = FALSE;
1350  }
1351 
1352  /* update lower bound of current node */
1353  if( allcolsinlp && !exactsolve )
1354  {
1355  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1356  SCIP_CALL( SCIPupdateNodeLowerbound(scip, SCIPgetCurrentNode(scip), provedbound) );
1357  }
1358  }
1359 
1360  /* apply domain reductions */
1361  if( nbdchgs > 0 )
1362  {
1363  if( *result != SCIP_CUTOFF )
1364  {
1365  SCIP_CALL( applyBdchgs(scip, vars, bdchginds, bdchgtypes, bdchgbounds, nbdchgs, result) );
1366  if( *result != SCIP_CUTOFF )
1367  *result = SCIP_REDUCEDDOM;
1368  }
1369  freeBdchgs(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs);
1370  }
1371 
1372  /* free buffer for the unreliable candidates */
1373  SCIPfreeBufferArray(scip, &initcandscores);
1374  SCIPfreeBufferArray(scip, &initcands);
1375  }
1376 
1377  /* if no domain could be reduced, create the branching */
1378  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED && executebranch )
1379  {
1380  SCIP_NODE* downchild;
1381  SCIP_NODE* upchild;
1382  SCIP_VAR* var;
1383  SCIP_Real val;
1384 
1385  assert(*result == SCIP_DIDNOTRUN);
1386  assert(0 <= bestcand && bestcand < nbranchcands);
1387  assert(!SCIPisFeasIntegral(scip, branchcandssol[bestcand]));
1388  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1389  assert(!bestsbdowncutoff && !bestsbupcutoff);
1390 
1391  var = branchcands[bestcand];
1392  val = branchcandssol[bestcand];
1393 
1394  /* perform the branching */
1395  SCIPdebugMsg(scip, " -> %d (%d) cands, sel cand %d: var <%s> (sol=%g, down=%g (%+g), up=%g (%+g), sb=%u, psc=%g/%g [%g])\n",
1396  nbranchcands, ninitcands, bestcand, SCIPvarGetName(var), branchcandssol[bestcand],
1397  bestsbdown, bestsbdown - lpobjval, bestsbup, bestsbup - lpobjval, bestisstrongbranch,
1400  SCIPgetVarPseudocostScoreCurrentRun(scip, var, branchcandssol[bestcand]));
1401  SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, NULL, &upchild) );
1402  assert(downchild != NULL);
1403  assert(upchild != NULL);
1404 
1405  /* update the lower bounds in the children */
1406  if( bestisstrongbranch && allcolsinlp && !exactsolve )
1407  {
1408  if( bestsbdownvalid )
1409  {
1410  assert(SCIPisLT(scip, bestsbdown, SCIPgetCutoffbound(scip)));
1411  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestsbdown) );
1412  assert(SCIPisGE(scip, SCIPgetNodeLowerbound(scip, downchild), provedbound));
1413  }
1414  if( bestsbupvalid )
1415  {
1416  assert(SCIPisLT(scip, bestsbup, SCIPgetCutoffbound(scip)));
1417  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestsbup) );
1418  assert(SCIPisGE(scip, SCIPgetNodeLowerbound(scip, upchild), provedbound));
1419  }
1420  }
1421 
1422  SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
1423  SCIPdebugMsg(scip, " -> up child's lowerbound : %g\n", SCIPnodeGetLowerbound(upchild));
1424 
1426 
1427  *result = SCIP_BRANCHED;
1428  }
1429 
1430  return SCIP_OKAY;
1431 }
1432 
1433 
1434 /*
1435  * Callback methods
1436  */
1437 
1438 /** copy method for branchrule plugins (called when SCIP copies plugins) */
1439 static
1440 SCIP_DECL_BRANCHCOPY(branchCopyRelpscost)
1441 { /*lint --e{715}*/
1442  assert(scip != NULL);
1443  assert(branchrule != NULL);
1444  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1445 
1446  /* call inclusion method of branchrule */
1448 
1449  return SCIP_OKAY;
1450 }
1451 
1452 /** destructor of branching rule to free user data (called when SCIP is exiting) */
1453 static
1454 SCIP_DECL_BRANCHFREE(branchFreeRelpscost)
1455 { /*lint --e{715}*/
1456  SCIP_BRANCHRULEDATA* branchruledata;
1457 
1458  /* free branching rule data */
1459  branchruledata = SCIPbranchruleGetData(branchrule);
1460  SCIPfreeBlockMemory(scip, &branchruledata);
1461  SCIPbranchruleSetData(branchrule, NULL);
1462 
1463  return SCIP_OKAY;
1464 }
1465 
1466 
1467 /** solving process initialization method of branching rule (called when branch and bound process is about to begin) */
1468 static
1469 SCIP_DECL_BRANCHINITSOL(branchInitsolRelpscost)
1470 { /*lint --e{715}*/
1471  SCIP_BRANCHRULEDATA* branchruledata;
1472 
1473  /* initialize branching rule data */
1474  branchruledata = SCIPbranchruleGetData(branchrule);
1475  branchruledata->nlcount = NULL;
1476  branchruledata->nlcountsize = 0;
1477  branchruledata->nlcountmax = 1;
1478  assert(branchruledata->startrandseed >= 0);
1479 
1480  /* create a random number generator */
1481  SCIP_CALL( SCIPcreateRandom(scip, &branchruledata->randnumgen,
1482  (unsigned int)branchruledata->startrandseed) );
1483 
1484  return SCIP_OKAY;
1485 }
1486 
1487 
1488 /** solving process deinitialization method of branching rule (called before branch and bound process data is freed) */
1489 static
1490 SCIP_DECL_BRANCHEXITSOL(branchExitsolRelpscost)
1491 { /*lint --e{715}*/
1492  SCIP_BRANCHRULEDATA* branchruledata;
1493 
1494  /* free memory in branching rule data */
1495  branchruledata = SCIPbranchruleGetData(branchrule);
1496  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->nlcount, branchruledata->nlcountsize);
1497 
1498  /* free random number generator */
1499  SCIPfreeRandom(scip, &branchruledata->randnumgen);
1500 
1501  return SCIP_OKAY;
1502 }
1503 
1504 
1505 /** branching execution method for fractional LP solutions */
1506 static
1507 SCIP_DECL_BRANCHEXECLP(branchExeclpRelpscost)
1508 { /*lint --e{715}*/
1509  SCIP_VAR** tmplpcands;
1510  SCIP_VAR** lpcands;
1511  SCIP_Real* tmplpcandssol;
1512  SCIP_Real* lpcandssol;
1513  SCIP_Real* tmplpcandsfrac;
1514  SCIP_Real* lpcandsfrac;
1515  int nlpcands;
1516 
1517  assert(branchrule != NULL);
1518  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1519  assert(scip != NULL);
1520  assert(result != NULL);
1521 
1522  SCIPdebugMsg(scip, "Execlp method of relpscost branching in node %llu\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
1523 
1525  {
1526  *result = SCIP_DIDNOTRUN;
1527  SCIPdebugMsg(scip, "Could not apply relpscost branching, as the current LP was not solved to optimality.\n");
1528 
1529  return SCIP_OKAY;
1530  }
1531 
1532  /* get branching candidates */
1533  SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, NULL, &nlpcands, NULL) );
1534  assert(nlpcands > 0);
1535 
1536  /* copy LP banching candidates and solution values, because they will be updated w.r.t. the strong branching LP
1537  * solution
1538  */
1539  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) );
1540  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) );
1541  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) );
1542 
1543  /* execute branching rule */
1544  SCIP_CALL( execRelpscost(scip, branchrule, lpcands, lpcandssol, lpcandsfrac, nlpcands, TRUE, result) );
1545 
1546  SCIPfreeBufferArray(scip, &lpcandsfrac);
1547  SCIPfreeBufferArray(scip, &lpcandssol);
1548  SCIPfreeBufferArray(scip, &lpcands);
1549 
1550  return SCIP_OKAY;
1551 }
1552 
1553 
1554 /*
1555  * branching specific interface methods
1556  */
1557 
1558 /** creates the reliable pseudo cost branching rule and includes it in SCIP */
1560  SCIP* scip /**< SCIP data structure */
1561  )
1562 {
1563  SCIP_BRANCHRULEDATA* branchruledata;
1564  SCIP_BRANCHRULE* branchrule;
1565 
1566  /* create relpscost branching rule data */
1567  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
1568 
1569  /* include branching rule */
1571  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1572 
1573  assert(branchrule != NULL);
1574 
1575  /* set non-fundamental callbacks via specific setter functions*/
1576  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyRelpscost) );
1577  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeRelpscost) );
1578  SCIP_CALL( SCIPsetBranchruleInitsol(scip, branchrule, branchInitsolRelpscost) );
1579  SCIP_CALL( SCIPsetBranchruleExitsol(scip, branchrule, branchExitsolRelpscost) );
1580  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpRelpscost) );
1581 
1582  /* relpscost branching rule parameters */
1584  "branching/relpscost/conflictweight",
1585  "weight in score calculations for conflict score",
1586  &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1588  "branching/relpscost/conflictlengthweight",
1589  "weight in score calculations for conflict length score",
1590  &branchruledata->conflengthweight, TRUE, DEFAULT_CONFLENGTHWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1592  "branching/relpscost/inferenceweight",
1593  "weight in score calculations for inference score",
1594  &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1596  "branching/relpscost/cutoffweight",
1597  "weight in score calculations for cutoff score",
1598  &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1600  "branching/relpscost/pscostweight",
1601  "weight in score calculations for pseudo cost score",
1602  &branchruledata->pscostweight, TRUE, DEFAULT_PSCOSTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1604  "branching/relpscost/nlscoreweight",
1605  "weight in score calculations for nlcount score",
1606  &branchruledata->nlscoreweight, TRUE, DEFAULT_NLSCOREWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1608  "branching/relpscost/minreliable",
1609  "minimal value for minimum pseudo cost size to regard pseudo cost value as reliable",
1610  &branchruledata->minreliable, TRUE, DEFAULT_MINRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1612  "branching/relpscost/maxreliable",
1613  "maximal value for minimum pseudo cost size to regard pseudo cost value as reliable",
1614  &branchruledata->maxreliable, TRUE, DEFAULT_MAXRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1616  "branching/relpscost/sbiterquot",
1617  "maximal fraction of strong branching LP iterations compared to node relaxation LP iterations",
1618  &branchruledata->sbiterquot, FALSE, DEFAULT_SBITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1619  SCIP_CALL( SCIPaddIntParam(scip,
1620  "branching/relpscost/sbiterofs",
1621  "additional number of allowed strong branching LP iterations",
1622  &branchruledata->sbiterofs, FALSE, DEFAULT_SBITEROFS, 0, INT_MAX, NULL, NULL) );
1623  SCIP_CALL( SCIPaddIntParam(scip,
1624  "branching/relpscost/maxlookahead",
1625  "maximal number of further variables evaluated without better score",
1626  &branchruledata->maxlookahead, TRUE, DEFAULT_MAXLOOKAHEAD, 1, INT_MAX, NULL, NULL) );
1627  SCIP_CALL( SCIPaddIntParam(scip,
1628  "branching/relpscost/initcand",
1629  "maximal number of candidates initialized with strong branching per node",
1630  &branchruledata->initcand, FALSE, DEFAULT_INITCAND, 0, INT_MAX, NULL, NULL) );
1631  SCIP_CALL( SCIPaddIntParam(scip,
1632  "branching/relpscost/inititer",
1633  "iteration limit for strong branching initializations of pseudo cost entries (0: auto)",
1634  &branchruledata->inititer, FALSE, DEFAULT_INITITER, 0, INT_MAX, NULL, NULL) );
1635  SCIP_CALL( SCIPaddIntParam(scip,
1636  "branching/relpscost/maxbdchgs",
1637  "maximal number of bound tightenings before the node is reevaluated (-1: unlimited)",
1638  &branchruledata->maxbdchgs, TRUE, DEFAULT_MAXBDCHGS, -1, INT_MAX, NULL, NULL) );
1639  SCIP_CALL( SCIPaddIntParam(scip,
1640  "branching/relpscost/maxproprounds",
1641  "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
1642  &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
1644  "branching/relpscost/probingbounds",
1645  "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
1646  &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
1647 
1648  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/userelerrorreliability",
1649  "should reliability be based on relative errors?", &branchruledata->userelerrorforreliability, TRUE, DEFAULT_USERELERRORFORRELIABILITY,
1650  NULL, NULL) );
1651 
1652  SCIP_CALL( SCIPaddRealParam(scip, "branching/relpscost/lowerrortol", "low relative error tolerance for reliability",
1653  &branchruledata->lowerrortol, TRUE, DEFAULT_LOWERRORTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1654 
1655  SCIP_CALL( SCIPaddRealParam(scip, "branching/relpscost/higherrortol", "high relative error tolerance for reliability",
1656  &branchruledata->higherrortol, TRUE, DEFAULT_HIGHERRORTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1657 
1658  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/storesemiinitcosts",
1659  "should strong branching result be considered for pseudo costs if the other direction was infeasible?",
1660  &branchruledata->storesemiinitcosts, TRUE, DEFAULT_STORESEMIINITCOSTS,
1661  NULL, NULL) );
1662 
1663  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usesblocalinfo",
1664  "should the scoring function use only local cutoff and inference information obtained for strong branching candidates?",
1665  &branchruledata->usesblocalinfo, TRUE, DEFAULT_USESBLOCALINFO,
1666  NULL, NULL) );
1667 
1668  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usehyptestforreliability",
1669  "should the strong branching decision be based on a hypothesis test?",
1670  &branchruledata->usehyptestforreliability, TRUE, DEFAULT_USEHYPTESTFORRELIABILITY,
1671  NULL, NULL) );
1672 
1673  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usedynamicconfidence",
1674  "should the confidence level be adjusted dynamically?",
1675  &branchruledata->usedynamicconfidence, TRUE, DEFAULT_USEDYNAMICCONFIDENCE,
1676  NULL, NULL) );
1677  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/skipbadinitcands",
1678  "should branching rule skip candidates that have a low probability to "
1679  "be better than the best strong-branching or pseudo-candidate?",
1680  &branchruledata->skipbadinitcands, TRUE, DEFAULT_SKIPBADINITCANDS,
1681  NULL, NULL) );
1682  SCIP_CALL( SCIPaddIntParam(scip,
1683  "branching/relpscost/confidencelevel",
1684  "the confidence level for statistical methods, between 0 (Min) and 4 (Max).",
1685  &branchruledata->confidencelevel, TRUE, DEFAULT_CONFIDENCELEVEL, 0, 4, NULL, NULL) );
1686 
1687  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/randinitorder",
1688  "should candidates be initialized in randomized order?",
1689  &branchruledata->randinitorder, TRUE, DEFAULT_RANDINITORDER,
1690  NULL, NULL) );
1691 
1692  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usesmallweightsitlim",
1693  "should smaller weights be used for pseudo cost updates after hitting the LP iteration limit?",
1694  &branchruledata->usesmallweightsitlim, TRUE, DEFAULT_USESMALLWEIGHTSITLIM,
1695  NULL, NULL) );
1696 
1697  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/dynamicweights",
1698  "should the weights of the branching rule be adjusted dynamically during solving based on objective and infeasible leaf counters?",
1699  &branchruledata->dynamicweights, TRUE, DEFAULT_DYNAMICWEIGHTS,
1700  NULL, NULL) );
1701  SCIP_CALL( SCIPaddIntParam(scip, "branching/relpscost/startrandseed", "start seed for random number generation",
1702  &branchruledata->startrandseed, TRUE, DEFAULT_STARTRANDSEED, 0, INT_MAX, NULL, NULL) );
1703 
1704  return SCIP_OKAY;
1705 }
1706 
1707 /** execution reliability pseudo cost branching with the given branching candidates */
1709  SCIP* scip, /**< SCIP data structure */
1710  SCIP_VAR** branchcands, /**< branching candidates */
1711  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
1712  SCIP_Real* branchcandsfrac, /**< fractional part of the branching candidates */
1713  int nbranchcands, /**< number of branching candidates */
1714  SCIP_Bool executebranching, /**< perform a branching step after probing */
1715  SCIP_RESULT* result /**< pointer to the result of the execution */
1716  )
1717 {
1718  SCIP_BRANCHRULE* branchrule;
1719 
1720  assert(scip != NULL);
1721  assert(result != NULL);
1722 
1723  /* find branching rule */
1724  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
1725  assert(branchrule != NULL);
1726 
1727  /* execute branching rule */
1728  SCIP_CALL( execRelpscost(scip, branchrule, branchcands, branchcandssol, branchcandsfrac, nbranchcands, executebranching, result) );
1729 
1730  return SCIP_OKAY;
1731 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36995
static SCIP_RETCODE countNonlinearities(SCIP *scip, int *nlcount, int nlcountsize, int *nlcountmax)
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip.c:48620
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
static SCIP_Real calcNlscore(SCIP *scip, int *nlcount, int nlcountmax, int probindex)
reliable pseudo costs branching rule
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:22593
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1810
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:46437
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
#define DEFAULT_PSCOSTWEIGHT
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:31227
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22517
static void freeBdchgs(SCIP *scip, int **bdchginds, SCIP_BOUNDTYPE **bdchgtypes, SCIP_Real **bdchgbounds, int *nbdchgs)
#define BRANCHRULE_MAXDEPTH
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:41398
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip.c:19109
#define DEFAULT_MAXBDCHGS
SCIP_Bool SCIPisSumGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47243
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6604
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43447
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7360
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
Definition: scip.c:48602
#define DEFAULT_LOWERRORTOL
static long bound
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_RETCODE SCIPgetVarStrongbranchLast(SCIP *scip, SCIP_VAR *var, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Real *solval, SCIP_Real *lpobjval)
Definition: scip.c:21511
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47009
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
SCIP_Bool SCIPpscostThresholdProbabilityTest(SCIP *scip, SCIP_VAR *var, SCIP_Real frac, SCIP_Real threshold, SCIP_BRANCHDIR dir, SCIP_CONFIDENCELEVEL clevel)
Definition: scip.c:26270
static SCIP_RETCODE binvarGetActiveProbindex(SCIP *scip, SCIP_VAR *var, int *probindex)
SCIP_Real SCIPgetAvgConflictScore(SCIP *scip)
Definition: scip.c:43859
SCIP_RETCODE SCIPsetBranchruleInitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: scip.c:9187
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16842
#define BRANCHRULE_MAXBOUNDDIST
#define DEFAULT_STARTRANDSEED
SCIP_Real SCIPgetVarPseudocostCountCurrentRun(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip.c:26161
SCIP_Real SCIPgetVarPseudocostScoreCurrentRun(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition: scip.c:26352
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:9139
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11680
#define DEFAULT_SBITERQUOT
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4485
#define FALSE
Definition: def.h:64
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:9123
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Longint SCIPgetVarStrongbranchNode(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21555
#define DEFAULT_INFERENCEWEIGHT
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9269
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16969
SCIP_Longint SCIPgetNRootStrongbranchLPIterations(SCIP *scip)
Definition: scip.c:42792
SCIP_Bool SCIPisVarPscostRelerrorReliable(SCIP *scip, SCIP_VAR *var, SCIP_Real threshold, SCIP_CONFIDENCELEVEL clevel)
Definition: scip.c:26289
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22633
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
SCIP_RETCODE SCIPgetNLPVarsNonlinearity(SCIP *scip, int *nlcount)
Definition: scip.c:31338
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip.c:9086
Constraint handler for AND constraints, .
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:22628
static SCIP_DECL_BRANCHINITSOL(branchInitsolRelpscost)
static SCIP_DECL_BRANCHFREE(branchFreeRelpscost)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
#define DEFAULT_HIGHERRORTOL
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17102
#define SCIPdebugMsg
Definition: scip.h:455
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4265
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:47429
static SCIP_DECL_BRANCHEXITSOL(branchExitsolRelpscost)
#define DEFAULT_USESMALLWEIGHTSITLIM
SCIP_Real SCIPgetVarPseudocostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition: scip.c:26314
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:47417
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9221
#define DEFAULT_INITITER
SCIP_Longint SCIPgetNDualResolveLPIterations(SCIP *scip)
Definition: scip.c:42612
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip.c:25991
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip.c:37450
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7340
#define BRANCHRULE_NAME
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29731
#define BRANCHRULE_PRIORITY
int SCIPgetNNLPVars(SCIP *scip)
Definition: scip.c:31316
enum SCIP_Confidencelevel SCIP_CONFIDENCELEVEL
Definition: type_misc.h:44
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5121
static SCIP_RETCODE applyBdchgs(SCIP *scip, SCIP_VAR **vars, int *bdchginds, SCIP_BOUNDTYPE *bdchgtypes, SCIP_Real *bdchgbounds, int nbdchgs, SCIP_RESULT *result)
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5146
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46970
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:22633
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
#define DEFAULT_USEHYPTESTFORRELIABILITY
SCIP_Real SCIPgetVarConflictlengthScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26514
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Bool SCIPsignificantVarPscostDifference(SCIP *scip, SCIP_VAR *varx, SCIP_Real fracx, SCIP_VAR *vary, SCIP_Real fracy, SCIP_BRANCHDIR dir, SCIP_CONFIDENCELEVEL clevel, SCIP_Bool onesided)
Definition: scip.c:26240
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:37680
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1360
#define DEFAULT_SBITEROFS
#define DEFAULT_CUTOFFWEIGHT
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:29202
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
Definition: scip.c:42648
SCIP_Real SCIPgetVarPseudocostCurrentRun(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip.c:26107
#define DEFAULT_CONFLICTWEIGHT
static SCIP_RETCODE addBdchg(SCIP *scip, int **bdchginds, SCIP_BOUNDTYPE **bdchgtypes, SCIP_Real **bdchgbounds, int *nbdchgs, int ind, SCIP_BOUNDTYPE type, SCIP_Real bound)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip.c:20169
public data structures and miscellaneous methods
SCIP_Bool SCIPisSumGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47230
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
static SCIP_DECL_BRANCHEXECLP(branchExeclpRelpscost)
static SCIP_DECL_BRANCHCOPY(branchCopyRelpscost)
#define DEFAULT_CONFLENGTHWEIGHT
#define DEFAULT_SKIPBADINITCANDS
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip.c:13574
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1820
static SCIP_RETCODE execRelpscost(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranch, SCIP_RESULT *result)
SCIP_RETCODE SCIPgetVarStrongbranchWithPropagation(SCIP *scip, SCIP_VAR *var, SCIP_Real solval, SCIP_Real lpobjval, int itlim, int maxproprounds, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Longint *ndomredsdown, SCIP_Longint *ndomredsup, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror, SCIP_Real *newlbs, SCIP_Real *newubs)
Definition: scip.c:20856
#define DEFAULT_MINRELIABLE
#define MAX(x, y)
Definition: tclique_def.h:75
#define DEFAULT_MAXPROPROUNDS
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip.c:9203
#define DEFAULT_INITCAND
SCIP_Longint SCIPgetNDualResolveLPs(SCIP *scip)
Definition: scip.c:42592
#define DEFAULT_NLSCOREWEIGHT
#define DEFAULT_DYNAMICWEIGHTS
#define DEFAULT_MAXLOOKAHEAD
SCIP_Longint SCIPgetNObjlimLeaves(SCIP *scip)
Definition: scip.c:42253
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4549
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9388
static SCIP_Real calcScore(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_Real conflictscore, SCIP_Real avgconflictscore, SCIP_Real conflengthscore, SCIP_Real avgconflengthscore, SCIP_Real inferencescore, SCIP_Real avginferencescore, SCIP_Real cutoffscore, SCIP_Real avgcutoffscore, SCIP_Real pscostscore, SCIP_Real avgpscostscore, SCIP_Real nlscore, SCIP_Real frac)
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
#define SCIP_REAL_MAX
Definition: def.h:150
#define DEFAULT_USERELERRORFORRELIABILITY
#define SCIP_REAL_MIN
Definition: def.h:151
SCIP_Real SCIPgetAvgCutoffScore(SCIP *scip)
Definition: scip.c:44081
SCIP_LPSOLSTAT SCIPgetLastStrongbranchLPSolStat(SCIP *scip, SCIP_BRANCHDIR branchdir)
Definition: scip.c:21489
SCIP_Longint SCIPgetNNodeInitLPIterations(SCIP *scip)
Definition: scip.c:42684
SCIP_Longint SCIPgetNNodeInitLPs(SCIP *scip)
Definition: scip.c:42666
SCIP_Real SCIPgetAvgConflictlengthScore(SCIP *scip)
Definition: scip.c:43909
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29366
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:39876
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46996
#define DEFAULT_PROBINGBOUNDS
SCIP_Longint SCIPgetNStrongbranchLPIterations(SCIP *scip)
Definition: scip.c:42756
SCIP_RETCODE SCIPincludeBranchruleRelpscost(SCIP *scip)
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
Definition: scip.c:20228
#define DEFAULT_USESBLOCALINFO
SCIP_RETCODE SCIPexecRelpscostBranching(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result)
#define DEFAULT_STORESEMIINITCOSTS
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16781
#define SCIP_Real
Definition: def.h:149
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1932
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5097
#define SCIP_INVALID
Definition: def.h:169
#define SCIP_Longint
Definition: def.h:134
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:29713
#define DEFAULT_USEDYNAMICCONFIDENCE
static SCIP_RETCODE branchruledataEnsureNlcount(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_Real SCIPgetNodeLowerbound(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:13439
#define BRANCHRULE_DESC
SCIP_Real SCIPgetAvgPseudocostScore(SCIP *scip)
Definition: scip.c:43762
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:22605
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47393
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_RETCODE SCIPgetVarStrongbranchFrac(SCIP *scip, SCIP_VAR *var, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror)
Definition: scip.c:20403
#define DEFAULT_MAXRELIABLE
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:42127
SCIP_Longint SCIPgetNInfeasibleLeaves(SCIP *scip)
Definition: scip.c:42226
#define DEFAULT_CONFIDENCELEVEL
#define DEFAULT_RANDINITORDER
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26684
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip.c:1032
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2579
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4321
SCIP_Real SCIPgetAvgInferenceScore(SCIP *scip)
Definition: scip.c:43995
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4239
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26452
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16817
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:22624
SCIP_Real SCIPgetVarAvgCutoffScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26938