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 infeasible and objective leaf counters? */
70 /** branching rule data */
71 struct SCIP_BranchruleData
72 {
73  SCIP_Real conflictweight; /**< weight in score calculations for conflict score */
74  SCIP_Real conflengthweight; /**< weight in score calculations for conflict length score */
75  SCIP_Real inferenceweight; /**< weight in score calculations for inference score */
76  SCIP_Real cutoffweight; /**< weight in score calculations for cutoff score */
77  SCIP_Real pscostweight; /**< weight in score calculations for pseudo cost score */
78  SCIP_Real nlscoreweight; /**< weight in score calculations for nlcount score */
79  SCIP_Real minreliable; /**< minimal value for minimum pseudo cost size to regard pseudo cost value as reliable */
80  SCIP_Real maxreliable; /**< maximal value for minimum pseudo cost size to regard pseudo cost value as reliable */
81  SCIP_Real sbiterquot; /**< maximal fraction of strong branching LP iterations compared to normal iterations */
82  int sbiterofs; /**< additional number of allowed strong branching LP iterations */
83  int maxlookahead; /**< maximal number of further variables evaluated without better score */
84  int initcand; /**< maximal number of candidates initialized with strong branching per node */
85  int inititer; /**< iteration limit for strong branching initialization of pseudo cost entries (0: auto) */
86  int maxbdchgs; /**< maximal number of bound tightenings before the node is reevaluated (-1: unlimited) */
87  int maxproprounds; /**< maximum number of propagation rounds to be performed during strong branching
88  * before solving the LP (-1: no limit, -2: parameter settings) */
89  SCIP_Bool probingbounds; /**< should valid bounds be identified in a probing-like fashion during strong
90  * branching (only with propagation)? */
91  SCIP_Bool userelerrorforreliability; /**< should reliability be based on relative errors? */
92  SCIP_Real lowerrortol; /**< lowest tolerance beneath which relative errors are reliable */
93  SCIP_Real higherrortol; /**< highest tolerance beneath which relative errors are reliable */
94  SCIP_Bool usehyptestforreliability; /**< should the strong branching decision be based on a hypothesis test? */
95  SCIP_Bool usedynamicconfidence; /**< should the confidence level be adjusted dynamically? */
96  SCIP_Bool storesemiinitcosts; /**< should strong branching result be considered for pseudo costs if the other direction was infeasible? */
97  SCIP_Bool usesblocalinfo; /**< should the scoring function disregard cutoffs for variable if sb-lookahead was feasible ? */
98  SCIP_Bool skipbadinitcands; /**< should branching rule skip candidates that have a low probability to be
99  * better than the best strong-branching or pseudo-candidate? */
100  SCIP_Bool dynamicweights; /**< should the weights of the branching rule be adjusted dynamically during solving based on objective and infeasible leaf counters? */
101  int confidencelevel; /**< The confidence level for statistical methods, between 0 (Min) and 4 (Max). */
102  int* nlcount; /**< array to store nonlinear count values */
103  int nlcountsize; /**< length of nlcount array */
104  int nlcountmax; /**< maximum entry in nlcount array or 1 if NULL */
105  SCIP_Bool randinitorder; /**< should slight perturbation of scores be used to break ties in the prior scores? */
106  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
107  int startrandseed; /**< start random seed for random number generation */
108  SCIP_Bool usesmallweightsitlim; /**< should smaller weights be used for pseudo cost updates after hitting the LP iteration limit? */
109 };
110 
111 /*
112  * local methods
113  */
114 
115 /** return probindex of variable or corresponding active variable (if negated or aggregated) or -1 (if
116  * multiaggregated)
117  */
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_Bool allowaddcons, /**< is the branching rule allowed to add constraints to the current node
491  * in order to cut off the current solution instead of creating a branching? */
492  SCIP_VAR** branchcands, /**< branching candidates */
493  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
494  SCIP_Real* branchcandsfrac, /**< fractional part of the branching candidates */
495  int nbranchcands, /**< number of branching candidates */
496  SCIP_Bool executebranch, /**< execute a branching step or run probing only */
497  SCIP_RESULT* result /**< pointer to the result of the execution */
498  )
499 {
500  SCIP_BRANCHRULEDATA* branchruledata;
501  SCIP_Real lpobjval;
502  SCIP_Real bestsbdown;
503  SCIP_Real bestsbup;
504  SCIP_Real provedbound;
505  SCIP_Bool bestsbdownvalid;
506  SCIP_Bool bestsbupvalid;
507  SCIP_Bool bestsbdowncutoff;
508  SCIP_Bool bestsbupcutoff;
509  SCIP_Bool bestisstrongbranch;
510  SCIP_Bool allcolsinlp;
511  SCIP_Bool exactsolve;
512  int ninitcands;
513  int bestcand;
514 
515  *result = SCIP_DIDNOTRUN;
516 
517  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
518 
519  /* get branching rule data */
520  branchruledata = SCIPbranchruleGetData(branchrule);
521  assert(branchruledata != NULL);
522 
523  /* get current LP objective bound of the local sub problem and global cutoff bound */
524  lpobjval = SCIPgetLPObjval(scip);
525 
526  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
527  * for cutting off sub problems and improving lower bounds of children
528  */
529  exactsolve = SCIPisExactSolve(scip);
530 
531  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
532  allcolsinlp = SCIPallColsInLP(scip);
533 
534  bestcand = -1;
535  bestisstrongbranch = FALSE;
536  bestsbdown = SCIP_INVALID;
537  bestsbup = SCIP_INVALID;
538  bestsbdownvalid = FALSE;
539  bestsbupvalid = FALSE;
540  bestsbdowncutoff = FALSE;
541  bestsbupcutoff = FALSE;
542  provedbound = lpobjval;
543 
544  if( nbranchcands == 1 )
545  {
546  /* only one candidate: nothing has to be done */
547  bestcand = 0;
548  SCIPdebug(ninitcands = 0);
549  }
550  else
551  {
552  SCIP_VAR** vars;
553  int* initcands;
554  SCIP_Real* initcandscores;
555  SCIP_Real* newlbs = NULL;
556  SCIP_Real* newubs = NULL;
557  int* bdchginds;
558  SCIP_BOUNDTYPE* bdchgtypes;
559  SCIP_Real* bdchgbounds;
560  int maxninitcands;
561  int nuninitcands;
562  int nbdchgs;
563  int nbdconflicts;
564  SCIP_Real avgconflictscore;
565  SCIP_Real avgconflengthscore;
566  SCIP_Real avginferencescore;
567  SCIP_Real avgcutoffscore;
568  SCIP_Real avgpscostscore;
569  SCIP_Real bestpsscore;
570  SCIP_Real bestpsfracscore;
571  SCIP_Real bestpsdomainscore;
572  SCIP_Real bestsbscore;
573  SCIP_Real bestuninitsbscore;
574  SCIP_Real bestsbfracscore;
575  SCIP_Real bestsbdomainscore;
576  SCIP_Real prio;
577  SCIP_Real reliable;
578  SCIP_Real maxlookahead;
579  SCIP_Real lookahead;
580  SCIP_Real relerrorthreshold;
581  SCIP_Bool initstrongbranching;
582  SCIP_Bool propagate;
583  SCIP_Bool probingbounds;
584  SCIP_Longint nodenum;
585  SCIP_Longint nlpiterationsquot;
586  SCIP_Longint nsblpiterations;
587  SCIP_Longint maxnsblpiterations;
588  int bestsolidx;
589  int maxbdchgs;
590  int bestpscand;
591  int bestsbcand;
592  int bestuninitsbcand;
593  int inititer;
594  int nvars;
595  int i;
596  int c;
597  SCIP_CONFIDENCELEVEL clevel;
598 
599  vars = SCIPgetVars(scip);
600  nvars = SCIPgetNVars(scip);
601 
602  bestsolidx = SCIPgetBestSol(scip) == NULL ? -1 : SCIPsolGetIndex(SCIPgetBestSol(scip));
603 
604  /* get average conflict, inference, and pseudocost scores */
605  avgconflictscore = SCIPgetAvgConflictScore(scip);
606  avgconflictscore = MAX(avgconflictscore, 0.1);
607  avgconflengthscore = SCIPgetAvgConflictlengthScore(scip);
608  avgconflengthscore = MAX(avgconflengthscore, 0.1);
609  avginferencescore = SCIPgetAvgInferenceScore(scip);
610  avginferencescore = MAX(avginferencescore, 0.1);
611  avgcutoffscore = SCIPgetAvgCutoffScore(scip);
612  avgcutoffscore = MAX(avgcutoffscore, 0.1);
613  avgpscostscore = SCIPgetAvgPseudocostScore(scip);
614  avgpscostscore = MAX(avgpscostscore, 0.1);
615 
616  /* get nonlinear counts according to parameters */
617  SCIP_CALL( branchruledataEnsureNlcount(scip, branchruledata) );
618 
619  initstrongbranching = FALSE;
620 
621  /* check whether propagation should be performed */
622  propagate = (branchruledata->maxproprounds != 0);
623 
624  /* check whether valid bounds should be identified in probing-like fashion */
625  probingbounds = propagate && branchruledata->probingbounds;
626 
627  /* get maximal number of candidates to initialize with strong branching; if the current solutions is not basic,
628  * we cannot warmstart the simplex algorithm and therefore don't initialize any candidates
629  */
630  maxninitcands = MIN(nbranchcands, branchruledata->initcand);
631  if( !SCIPisLPSolBasic(scip) )
632  maxninitcands = 0;
633 
634  /* calculate maximal number of strong branching LP iterations; if we used too many, don't apply strong branching
635  * any more
636  */
637  nlpiterationsquot = (SCIP_Longint)(branchruledata->sbiterquot * SCIPgetNNodeLPIterations(scip));
638  maxnsblpiterations = nlpiterationsquot + branchruledata->sbiterofs + SCIPgetNRootStrongbranchLPIterations(scip);
639  nsblpiterations = SCIPgetNStrongbranchLPIterations(scip);
640  if( nsblpiterations > maxnsblpiterations )
641  maxninitcands = 0;
642 
643  /* get buffer for storing the unreliable candidates */
644  SCIP_CALL( SCIPallocBufferArray(scip, &initcands, maxninitcands+1) ); /* allocate one additional slot for convenience */
645  SCIP_CALL( SCIPallocBufferArray(scip, &initcandscores, maxninitcands+1) );
646  ninitcands = 0;
647 
648  /* get current node number */
649  nodenum = SCIPgetNNodes(scip);
650 
651  /* initialize bound change arrays */
652  bdchginds = NULL;
653  bdchgtypes = NULL;
654  bdchgbounds = NULL;
655  nbdchgs = 0;
656  nbdconflicts = 0;
657  maxbdchgs = branchruledata->maxbdchgs;
658  if( maxbdchgs == -1 )
659  maxbdchgs = INT_MAX;
660 
661  /* calculate value used as reliability */
662  prio = (maxnsblpiterations - nsblpiterations)/(nsblpiterations + 1.0);
663  prio = MIN(prio, 1.0);
664  prio = MAX(prio, (nlpiterationsquot - nsblpiterations)/(nsblpiterations + 1.0));
665  reliable = (1.0-prio) * branchruledata->minreliable + prio * branchruledata->maxreliable;
666 
667  /* calculate the threshold for the relative error in the same way; low tolerance is more strict than higher tolerance */
668  relerrorthreshold = (1.0 - prio) * branchruledata->higherrortol + prio * branchruledata->lowerrortol;
669 
670  clevel = (SCIP_CONFIDENCELEVEL)branchruledata->confidencelevel;
671  /* determine the confidence level for hypothesis testing based on value of prio */
672  if( branchruledata->usedynamicconfidence )
673  {
674  /* with decreasing priority, use a less strict confidence level */
675  if( prio >= 0.9 )
676  clevel = SCIP_CONFIDENCELEVEL_MAX;
677  else if( prio >= 0.7 )
678  clevel = SCIP_CONFIDENCELEVEL_HIGH;
679  else if( prio >= 0.5 )
681  else if( prio >= 0.3 )
682  clevel = SCIP_CONFIDENCELEVEL_LOW;
683  else
684  clevel = SCIP_CONFIDENCELEVEL_MIN;
685  }
686 
687  /* search for the best pseudo cost candidate, while remembering unreliable candidates in a sorted buffer */
688  nuninitcands = 0;
689  bestpscand = -1;
690  bestpsscore = -SCIPinfinity(scip);
691  bestpsfracscore = -SCIPinfinity(scip);
692  bestpsdomainscore = -SCIPinfinity(scip);
693 
694  /* search for the best candidate first */
695  if( branchruledata->usehyptestforreliability )
696  {
697  for( c = 0; c < nbranchcands; ++c )
698  {
699  SCIP_Real conflictscore;
700  SCIP_Real conflengthscore;
701  SCIP_Real inferencescore;
702  SCIP_Real cutoffscore;
703  SCIP_Real pscostscore;
704  SCIP_Real nlscore;
705  SCIP_Real score;
706 
707  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
708  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
709  inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
710  cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
711  nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
712  pscostscore = SCIPgetVarPseudocostScore(scip, branchcands[c], branchcandssol[c]);
713 
714  /* replace the pseudo cost score with the already calculated one;
715  * @todo: use old data for strong branching with propagation?
716  */
717  if( SCIPgetVarStrongbranchNode(scip, branchcands[c]) == nodenum )
718  {
719  SCIP_Real down;
720  SCIP_Real up;
721  SCIP_Real lastlpobjval;
722  SCIP_Real downgain;
723  SCIP_Real upgain;
724 
725  /* use the score of the strong branching call at the current node */
726  SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
727  downgain = MAX(down - lastlpobjval, 0.0);
728  upgain = MAX(up - lastlpobjval, 0.0);
729  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
730 
731  SCIPdebugMsg(scip, " -> strong branching on variable <%s> already performed (down=%g (%+g), up=%g (%+g), pscostscore=%g)\n",
732  SCIPvarGetName(branchcands[c]), down, downgain, up, upgain, pscostscore);
733  }
734 
735  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
736  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, nlscore, branchcandsfrac[c]);
737 
738  /* check for better score of candidate */
739  if( SCIPisSumGE(scip, score, bestpsscore) )
740  {
741  SCIP_Real fracscore;
742  SCIP_Real domainscore;
743 
744  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
745  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
746  if( SCIPisSumGT(scip, score, bestpsscore)
747  || SCIPisSumGT(scip, fracscore, bestpsfracscore)
748  || (SCIPisSumGE(scip, fracscore, bestpsfracscore) && domainscore > bestpsdomainscore) )
749  {
750  bestpscand = c;
751  bestpsscore = score;
752  bestpsfracscore = fracscore;
753  bestpsdomainscore = domainscore;
754  }
755  }
756  }
757  }
758 
759  for( c = 0; c < nbranchcands; ++c )
760  {
761  SCIP_Real conflictscore;
762  SCIP_Real conflengthscore;
763  SCIP_Real inferencescore;
764  SCIP_Real cutoffscore;
765  SCIP_Real pscostscore;
766  SCIP_Real nlscore;
767  SCIP_Real score;
768  SCIP_Bool usesb;
769 
770  assert(branchcands[c] != NULL);
771  assert(!SCIPisFeasIntegral(scip, branchcandssol[c]));
772 
773  /* get conflict, inference, cutoff, nonlinear, and pseudo cost scores for candidate */
774  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
775  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
776  inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
777  cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
778  nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
779  pscostscore = SCIPgetVarPseudocostScore(scip, branchcands[c], branchcandssol[c]);
780  usesb = FALSE;
781 
782  /* don't use strong branching on variables that have already been initialized at the current node;
783  * instead replace the pseudo cost score with the already calculated one;
784  * @todo: use old data for strong branching with propagation?
785  */
786  if( SCIPgetVarStrongbranchNode(scip, branchcands[c]) == nodenum )
787  {
788  SCIP_Real down;
789  SCIP_Real up;
790  SCIP_Real lastlpobjval;
791  SCIP_Real downgain;
792  SCIP_Real upgain;
793 
794  /* use the score of the strong branching call at the current node */
795  SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
796  downgain = MAX(down - lastlpobjval, 0.0);
797  upgain = MAX(up - lastlpobjval, 0.0);
798  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
799 
800  SCIPdebugMsg(scip, " -> strong branching on variable <%s> already performed (down=%g (%+g), up=%g (%+g), pscostscore=%g)\n",
801  SCIPvarGetName(branchcands[c]), down, downgain, up, upgain, pscostscore);
802  }
803  else if( maxninitcands > 0 )
804  {
805  SCIP_Real downsize;
806  SCIP_Real upsize;
807  SCIP_Real size;
808 
809  /* check, if the pseudo cost score of the variable is reliable */
810  downsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_DOWNWARDS);
811  upsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_UPWARDS);
812  size = MIN(downsize, upsize);
813 
814  /* determine if variable is considered reliable based on the current reliability setting */
815  /* check fixed number threshold (aka original) reliability first */
816  assert(!branchruledata->usehyptestforreliability || bestpscand >= 0);
817  usesb = FALSE;
818  if( size < reliable )
819  usesb = TRUE;
820  else if( branchruledata->userelerrorforreliability && branchruledata->usehyptestforreliability )
821  {
822  if( !SCIPisVarPscostRelerrorReliable(scip, branchcands[c], relerrorthreshold, clevel) &&
823  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
824  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE) &&
825  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1 - branchcandsfrac[bestpscand],
826  branchcands[c], 1 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
827  usesb = TRUE;
828  }
829  /* check if relative error is tolerable */
830  else if( branchruledata->userelerrorforreliability &&
831  !SCIPisVarPscostRelerrorReliable(scip, branchcands[c], relerrorthreshold, clevel))
832  usesb = TRUE;
833  /* check if best pseudo-candidate is significantly better in both directions, use strong-branching otherwise */
834  else if( branchruledata->usehyptestforreliability &&
835  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
836  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE) &&
837  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1 - branchcandsfrac[bestpscand],
838  branchcands[c], 1 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE))
839  usesb = TRUE;
840 
841  /* count the number of variables that are completely uninitialized */
842  if( size < 0.1 )
843  nuninitcands++;
844  }
845 
846  /* combine the five score values */
847  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
848  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, nlscore, branchcandsfrac[c]);
849 
850  if( usesb )
851  {
852  int j;
853 
854  /* assign a random score to this uninitialized candidate */
855  if( branchruledata->randinitorder )
856  score += SCIPrandomGetReal(branchruledata->randnumgen, 0.0, 1e-4);
857 
858  /* pseudo cost of variable is not reliable: insert candidate in initcands buffer */
859  for( j = ninitcands; j > 0 && score > initcandscores[j-1]; --j )
860  {
861  initcands[j] = initcands[j-1];
862  initcandscores[j] = initcandscores[j-1];
863  }
864  initcands[j] = c;
865  initcandscores[j] = score;
866  ninitcands++;
867  ninitcands = MIN(ninitcands, maxninitcands);
868  }
869  /* in the case of hypothesis reliability, the best pseudo candidate has been determined already */
870  else if( !branchruledata->usehyptestforreliability )
871  {
872  /* variable will keep it's pseudo cost value: check for better score of candidate */
873  if( SCIPisSumGE(scip, score, bestpsscore) )
874  {
875  SCIP_Real fracscore;
876  SCIP_Real domainscore;
877 
878  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
879  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
880  if( SCIPisSumGT(scip, score, bestpsscore)
881  || SCIPisSumGT(scip, fracscore, bestpsfracscore)
882  || (SCIPisSumGE(scip, fracscore, bestpsfracscore) && domainscore > bestpsdomainscore) )
883  {
884  bestpscand = c;
885  bestpsscore = score;
886  bestpsfracscore = fracscore;
887  bestpsdomainscore = domainscore;
888  }
889  }
890  }
891  }
892 
893  /* in the special case that only the best pseudo candidate was selected for strong branching, skip the strong branching */
894  if( branchruledata->usehyptestforreliability && ninitcands == 1 )
895  {
896  ninitcands = 0;
897  SCIPdebugMsg(scip, "Only one single candidate for initialization-->Skipping strong branching\n");
898  }
899 
900  /* initialize unreliable candidates with strong branching until maxlookahead is reached,
901  * search best strong branching candidate
902  */
903  maxlookahead = (SCIP_Real)branchruledata->maxlookahead * (1.0 + (SCIP_Real)nuninitcands/(SCIP_Real)nbranchcands);
904  inititer = branchruledata->inititer;
905  if( inititer == 0 )
906  {
907  SCIP_Longint nlpiterations;
908  SCIP_Longint nlps;
909 
910  /* iteration limit is set to twice the average number of iterations spent to resolve a dual feasible SCIP_LP;
911  * at the first few nodes, this average is not very exact, so we better increase the iteration limit on
912  * these very important nodes
913  */
914  nlpiterations = SCIPgetNDualResolveLPIterations(scip);
915  nlps = SCIPgetNDualResolveLPs(scip);
916  if( nlps == 0 )
917  {
918  nlpiterations = SCIPgetNNodeInitLPIterations(scip);
919  nlps = SCIPgetNNodeInitLPs(scip);
920  if( nlps == 0 )
921  {
922  nlpiterations = 1000;
923  nlps = 1;
924  }
925  }
926  assert(nlps >= 1);
927  inititer = (int)(2*nlpiterations / nlps);
928  inititer = (int)((SCIP_Real)inititer * (1.0 + 20.0/nodenum));
929  inititer = MAX(inititer, 10);
930  inititer = MIN(inititer, 500);
931  }
932 
933  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",
934  reliable, ninitcands, nbranchcands, nuninitcands, maxninitcands, maxlookahead, maxbdchgs, inititer,
935  SCIPgetNStrongbranchLPIterations(scip), maxnsblpiterations, SCIPisLPSolBasic(scip));
936 
937  bestsbcand = -1;
938  bestsbscore = -SCIPinfinity(scip);
939  bestsbfracscore = -SCIPinfinity(scip);
940  bestsbdomainscore = -SCIPinfinity(scip);
941  bestuninitsbscore = -SCIPinfinity(scip);
942  bestuninitsbcand = -1;
943  lookahead = 0.0;
944  for( i = 0; i < ninitcands && lookahead < maxlookahead && nbdchgs + nbdconflicts < maxbdchgs
945  && (i < (int) maxlookahead || SCIPgetNStrongbranchLPIterations(scip) < maxnsblpiterations); ++i )
946  {
947  SCIP_Real down;
948  SCIP_Real up;
949  SCIP_Real downgain;
950  SCIP_Real upgain;
951  SCIP_Bool downvalid;
952  SCIP_Bool upvalid;
953  SCIP_Longint ndomredsdown;
954  SCIP_Longint ndomredsup;
955  SCIP_Bool lperror;
956  SCIP_Bool downinf;
957  SCIP_Bool upinf;
958  SCIP_Bool downconflict;
959  SCIP_Bool upconflict;
960 
961  /* get candidate number to initialize */
962  c = initcands[i];
963  assert(!SCIPisFeasIntegral(scip, branchcandssol[c]));
964 
965  if( branchruledata->skipbadinitcands )
966  {
967  SCIP_Bool skipsb = FALSE;
968  /* if the current best candidate is a candidate found by strong branching, determine if candidate pseudo-costs are
969  * significantly smaller in at least one direction, in which case we safe the execution of strong-branching for now
970  */
971  if( bestsbscore > bestpsscore && bestsbscore > bestuninitsbscore && bestsbupvalid && bestsbdownvalid )
972  {
973  assert(bestsbcand != -1);
974  assert(bestsbup != SCIP_INVALID && bestsbdown != SCIP_INVALID); /*lint !e777 lint doesn't like comparing floats */
975 
976  /* test if the variable is unlikely to produce a better gain than the currently best one. Skip strong-branching
977  * in such a case
978  */
979  if( SCIPpscostThresholdProbabilityTest(scip, branchcands[c], branchcandsfrac[c], bestsbdown,
980  SCIP_BRANCHDIR_DOWNWARDS, clevel)
981  || SCIPpscostThresholdProbabilityTest(scip, branchcands[c], 1.0 - branchcandsfrac[c], bestsbup,
982  SCIP_BRANCHDIR_UPWARDS, clevel) )
983  skipsb = TRUE;
984  }
985  /* the currently best candidate is also a pseudo-candidate; apply significance test and skip candidate if it
986  * is significantly worse in at least one direction
987  */
988  else if( bestpscand != -1 && bestpsscore > bestuninitsbscore )
989  {
990  if( SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
991  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE)
992  || SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1.0 - branchcandsfrac[bestpscand],
993  branchcands[c], 1.0 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
994  skipsb = TRUE;
995  }
996  /* compare against the best init cand that has been skipped already */
997  else if( bestuninitsbcand != -1 )
998  {
999  if( SCIPsignificantVarPscostDifference(scip, branchcands[bestuninitsbcand], branchcandsfrac[bestuninitsbcand],
1000  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE)
1001  || SCIPsignificantVarPscostDifference(scip, branchcands[bestuninitsbcand], 1.0 - branchcandsfrac[bestuninitsbcand],
1002  branchcands[c], 1.0 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
1003  skipsb = TRUE;
1004  }
1005 
1006  /* skip candidate, update the best score of an unitialized candidate */
1007  if( skipsb )
1008  {
1009  if( bestuninitsbcand == -1 )
1010  {
1011  bestuninitsbcand = c;
1012  bestuninitsbscore = initcandscores[i];
1013  }
1014  continue;
1015  }
1016  }
1017  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",
1020  SCIPvarGetName(branchcands[c]), branchcandssol[c], initcandscores[i],
1021  inititer, SCIPgetNStrongbranchLPIterations(scip), maxnsblpiterations);
1022 
1023  /* use strong branching on candidate */
1024  if( !initstrongbranching )
1025  {
1026  initstrongbranching = TRUE;
1027 
1028  SCIP_CALL( SCIPstartStrongbranch(scip, propagate) );
1029 
1030  /* create arrays for probing-like bound tightening */
1031  if( probingbounds )
1032  {
1033  SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
1034  SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
1035  }
1036  }
1037 
1038  if( propagate )
1039  {
1040  /* apply strong branching */
1041  SCIP_CALL( SCIPgetVarStrongbranchWithPropagation(scip, branchcands[c], branchcandssol[c], lpobjval, inititer,
1042  branchruledata->maxproprounds, &down, &up, &downvalid, &upvalid, &ndomredsdown, &ndomredsup, &downinf, &upinf,
1043  &downconflict, &upconflict, &lperror, newlbs, newubs) );
1044  }
1045  else
1046  {
1047  /* apply strong branching */
1048  SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, branchcands[c], inititer,
1049  &down, &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
1050 
1051  ndomredsdown = ndomredsup = 0;
1052  }
1053 
1054  /* check for an error in strong branching */
1055  if( lperror )
1056  {
1057  if( !SCIPisStopped(scip) )
1058  {
1060  "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call for variable <%s> with solution %g\n",
1061  SCIPgetNNodes(scip), SCIPvarGetName(branchcands[c]), branchcandssol[c]);
1062  }
1063  break;
1064  }
1065 
1066  /* Strong branching might have found a new primal solution which updated the cutoff bound. In this case, the
1067  * provedbound computed before can be higher than the cutoffbound and the current node can be cut off.
1068  * Additionally, also if the value for the current best candidate is valid and exceeds the new cutoff bound,
1069  * we want to change the domain of this variable rather than branching on it.
1070  */
1071  if( SCIPgetBestSol(scip) != NULL && SCIPsolGetIndex(SCIPgetBestSol(scip)) != bestsolidx )
1072  {
1073  bestsolidx = SCIPsolGetIndex(SCIPgetBestSol(scip));
1074 
1075  SCIPdebugMsg(scip, " -> strong branching on variable <%s> lead to a new incumbent\n",
1076  SCIPvarGetName(branchcands[c]));
1077 
1078  /* proved bound for current node is larger than new cutoff bound -> cut off current node */
1079  if( SCIPisGE(scip, provedbound, SCIPgetCutoffbound(scip)) )
1080  {
1081  SCIPdebugMsg(scip, " -> node can be cut off (provedbound=%g, cutoff=%g)\n", provedbound, SCIPgetCutoffbound(scip));
1082 
1083  *result = SCIP_CUTOFF;
1084  break; /* terminate initialization loop, because node is infeasible */
1085  }
1086  /* proved bound for down child of best candidate is larger than cutoff bound
1087  * -> increase lower bound of best candidate
1088  * we must only do this if the LP is complete, i.e., we are not doing column generation
1089  */
1090 
1091  else if( bestsbcand != -1 && allcolsinlp )
1092  {
1093  if( !bestsbdowncutoff && bestsbdownvalid && SCIPisGE(scip, bestsbdown, SCIPgetCutoffbound(scip)) )
1094  {
1095  bestsbdowncutoff = TRUE;
1096 
1097  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",
1098  SCIPvarGetName(branchcands[bestsbcand]), bestsbdownvalid, bestsbdown, SCIPgetCutoffbound(scip));
1099 
1100  SCIPdebugMsg(scip, " -> increase lower bound of best candidate <%s> to %g\n",
1101  SCIPvarGetName(branchcands[bestsbcand]), SCIPfeasCeil(scip, branchcandssol[bestsbcand]));
1102 
1103  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[bestsbcand]),
1104  SCIP_BOUNDTYPE_LOWER, SCIPfeasCeil(scip, branchcandssol[bestsbcand])) );
1105  }
1106  /* proved bound for up child of best candidate is larger than cutoff bound -> decrease upper bound of best candidate */
1107  else if( !bestsbupcutoff && bestsbupvalid && SCIPisGE(scip, bestsbup, SCIPgetCutoffbound(scip)) )
1108  {
1109  bestsbupcutoff = TRUE;
1110 
1111  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",
1112  SCIPvarGetName(branchcands[bestsbcand]), bestsbupvalid, bestsbup, SCIPgetCutoffbound(scip));
1113 
1114  SCIPdebugMsg(scip, " -> decrease upper bound of best candidate <%s> to %g\n",
1115  SCIPvarGetName(branchcands[bestsbcand]), SCIPfeasFloor(scip, branchcandssol[bestsbcand]));
1116 
1117  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[bestsbcand]),
1118  SCIP_BOUNDTYPE_UPPER, SCIPfeasFloor(scip, branchcandssol[bestsbcand])) );
1119  }
1120  }
1121  }
1122 
1123  /* evaluate strong branching */
1124  down = MAX(down, lpobjval);
1125  up = MAX(up, lpobjval);
1126  downgain = down - lpobjval;
1127  upgain = up - lpobjval;
1128  assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
1129  assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
1130  assert(downinf || !downconflict);
1131  assert(upinf || !upconflict);
1132 
1133  /* @todo: store pseudo cost only for valid bounds?
1134  * depending on the user parameter choice of storesemiinitcosts, pseudo costs are also updated in single directions,
1135  * if the node in the other direction was infeasible or cut off
1136  */
1137  if( !downinf
1138 #ifdef WITH_LPSOLSTAT
1140 #endif
1141  && (!upinf || branchruledata->storesemiinitcosts) )
1142  {
1143  SCIP_Real weight;
1144 
1145  /* smaller weights are given if the strong branching hit the time limit in the corresponding direction */
1146  if( branchruledata->usesmallweightsitlim )
1148  else
1149  weight = 1.0;
1150 
1151  /* update pseudo cost values */
1152  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchcands[c], 0.0 - branchcandsfrac[c], downgain, weight) );
1153  }
1154  if( !upinf
1155 #ifdef WITH_LPSOLSTAT
1157 #endif
1158  && (!downinf || branchruledata->storesemiinitcosts) )
1159  {
1160  SCIP_Real weight;
1161 
1162  /* smaller weights are given if the strong branching hit the time limit in the corresponding direction */
1163  if( branchruledata->usesmallweightsitlim )
1165  else
1166  weight = 1.0;
1167 
1168  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchcands[c], 1.0 - branchcandsfrac[c], upgain, weight) );
1169  }
1170 
1171  /* the minimal lower bound of both children is a proved lower bound of the current subtree */
1172  if( allcolsinlp && !exactsolve && downvalid && upvalid )
1173  {
1174  SCIP_Real minbound;
1175 
1176  minbound = MIN(down, up);
1177  provedbound = MAX(provedbound, minbound);
1178  assert((downinf && upinf) || SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1179 
1180  /* save probing-like bounds detected during strong branching */
1181  if( probingbounds )
1182  {
1183  int v;
1184 
1185  assert(newlbs != NULL);
1186  assert(newubs != NULL);
1187 
1188  for( v = 0; v < nvars; ++v )
1189  {
1190  if( SCIPisGT(scip, newlbs[v], SCIPvarGetLbLocal(vars[v])) )
1191  {
1192  SCIPdebugMsg(scip, "better lower bound for variable <%s>: %.9g -> %.9g (by strongbranching on <%s>)\n",
1193  SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), newlbs[v], SCIPvarGetName(branchcands[c]));
1194 
1195  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, v,
1196  SCIP_BOUNDTYPE_LOWER, newlbs[v]) );
1197  }
1198  if( SCIPisLT(scip, newubs[v], SCIPvarGetUbLocal(vars[v])) )
1199  {
1200  SCIPdebugMsg(scip, "better upper bound for variable <%s>: %.9g -> %.9g (by strongbranching on <%s>)\n",
1201  SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), newubs[v], SCIPvarGetName(branchcands[c]));
1202 
1203  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, v,
1204  SCIP_BOUNDTYPE_UPPER, newubs[v]) );
1205  }
1206  }
1207  }
1208  }
1209 
1210  /* check if there are infeasible roundings */
1211  if( downinf || upinf )
1212  {
1213  assert(allcolsinlp || propagate);
1214  assert(!exactsolve);
1215 
1216  /* if for both infeasibilities, a conflict constraint was created, we don't need to fix the variable by hand,
1217  * but better wait for the next propagation round to fix them as an inference, and potentially produce a
1218  * cutoff that can be analyzed
1219  */
1220  if( allowaddcons && downinf == downconflict && upinf == upconflict )
1221  {
1222  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in %s: conflict constraint added\n",
1223  SCIPvarGetName(branchcands[c]),
1224  downinf && upinf ? "both directions" : (downinf ? "downward branch" : "upward branch"));
1225  *result = SCIP_CONSADDED;
1226  nbdconflicts++;
1227  if( (downinf && upinf) || (nbdchgs + nbdconflicts >= maxbdchgs) )
1228  break; /* terminate initialization loop, because enough roundings are performed or a cutoff was found */
1229  }
1230  else if( downinf && upinf )
1231  {
1232  /* both roundings are infeasible -> node is infeasible */
1233  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions (conflict: %u/%u)\n",
1234  SCIPvarGetName(branchcands[c]), downconflict, upconflict);
1235  *result = SCIP_CUTOFF;
1236  break; /* terminate initialization loop, because node is infeasible */
1237  }
1238  else
1239  {
1240  /* rounding is infeasible in one direction -> round variable in other direction */
1241  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in %s branch (conflict: %u/%u)\n",
1242  SCIPvarGetName(branchcands[c]), downinf ? "downward" : "upward", downconflict, upconflict);
1243  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[c]),
1245  (downinf ? SCIPfeasCeil(scip, branchcandssol[c]) : SCIPfeasFloor(scip, branchcandssol[c]))) );
1246  if( nbdchgs + nbdconflicts >= maxbdchgs )
1247  break; /* terminate initialization loop, because enough roundings are performed */
1248  }
1249  }
1250  else
1251  {
1252  SCIP_Real conflictscore;
1253  SCIP_Real conflengthscore;
1254  SCIP_Real inferencescore;
1255  SCIP_Real cutoffscore;
1256  SCIP_Real pscostscore;
1257  SCIP_Real nlscore;
1258  SCIP_Real score;
1259 
1260  /* check for a better score */
1261  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
1262  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
1263  nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
1264 
1265  /* optionally, use only local information obtained via strong branching for this candidate, i.e., local
1266  * domain reductions and no cutoff score
1267  */
1268  inferencescore = branchruledata->usesblocalinfo ? SCIPgetBranchScore(scip, branchcands[c], (SCIP_Real)ndomredsdown, (SCIP_Real)ndomredsup)
1269  : SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
1270  cutoffscore = branchruledata->usesblocalinfo ? 0.0 : SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
1271  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
1272 
1273  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1274  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, nlscore, branchcandsfrac[c]);
1275 
1276  if( SCIPisSumGE(scip, score, bestsbscore) )
1277  {
1278  SCIP_Real fracscore;
1279  SCIP_Real domainscore;
1280 
1281  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
1282  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
1283  if( SCIPisSumGT(scip, score, bestsbscore)
1284  || SCIPisSumGT(scip, fracscore, bestsbfracscore)
1285  || (SCIPisSumGE(scip, fracscore, bestsbfracscore) && domainscore > bestsbdomainscore) )
1286  {
1287  bestsbcand = c;
1288  bestsbscore = score;
1289  bestsbdown = down;
1290  bestsbup = up;
1291  bestsbdownvalid = downvalid;
1292  bestsbupvalid = upvalid;
1293  bestsbdowncutoff = FALSE;
1294  bestsbupcutoff = FALSE;
1295  bestsbfracscore = fracscore;
1296  bestsbdomainscore = domainscore;
1297  lookahead = 0.0;
1298  }
1299  else
1300  lookahead += 0.5;
1301  }
1302  else
1303  lookahead += 1.0;
1304 
1305  SCIPdebugMsg(scip, " -> variable <%s> (solval=%g, down=%g (%+g,valid=%u), up=%g (%+g,valid=%u), score=%g/ %g/%g %g/%g -> %g)\n",
1306  SCIPvarGetName(branchcands[c]), branchcandssol[c], down, downgain, downvalid, up, upgain, upvalid,
1307  pscostscore, conflictscore, conflengthscore, inferencescore, cutoffscore, score);
1308  }
1309  }
1310 #ifdef SCIP_DEBUG
1311  if( bestsbcand >= 0 )
1312  {
1313  SCIPdebugMsg(scip, " -> best: <%s> (%g / %g / %g), lookahead=%g/%g\n",
1314  SCIPvarGetName(branchcands[bestsbcand]), bestsbscore, bestsbfracscore, bestsbdomainscore,
1315  lookahead, maxlookahead);
1316  }
1317 #endif
1318 
1319  if( initstrongbranching )
1320  {
1321  if( probingbounds )
1322  {
1323  assert(newlbs != NULL);
1324  assert(newubs != NULL);
1325 
1326  SCIPfreeBufferArray(scip, &newubs);
1327  SCIPfreeBufferArray(scip, &newlbs);
1328  }
1329 
1330  SCIP_CALL( SCIPendStrongbranch(scip) );
1331 
1333  {
1334  assert(SCIPhasCurrentNodeLP(scip));
1335  *result = SCIP_CUTOFF;
1336  }
1337  }
1338 
1339  if( *result != SCIP_CUTOFF )
1340  {
1341  /* get the score of the best uninitialized strong branching candidate */
1342  if( i < ninitcands && bestuninitsbcand == -1 )
1343  bestuninitsbscore = initcandscores[i];
1344 
1345  /* if the best pseudo cost candidate is better than the best uninitialized strong branching candidate,
1346  * compare it to the best initialized strong branching candidate
1347  */
1348  if( bestpsscore > bestuninitsbscore && SCIPisSumGT(scip, bestpsscore, bestsbscore) )
1349  {
1350  bestcand = bestpscand;
1351  bestisstrongbranch = FALSE;
1352  }
1353  else if( bestsbcand >= 0 )
1354  {
1355  bestcand = bestsbcand;
1356  bestisstrongbranch = TRUE;
1357  }
1358  else
1359  {
1360  /* no candidate was initialized, and the best score is the one of the first candidate in the initialization
1361  * queue
1362  */
1363  assert(ninitcands >= 1);
1364  bestcand = initcands[0];
1365  bestisstrongbranch = FALSE;
1366  }
1367 
1368  /* update lower bound of current node */
1369  if( allcolsinlp && !exactsolve )
1370  {
1371  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1372  SCIP_CALL( SCIPupdateNodeLowerbound(scip, SCIPgetCurrentNode(scip), provedbound) );
1373  }
1374  }
1375 
1376  /* apply domain reductions */
1377  if( nbdchgs > 0 )
1378  {
1379  if( *result != SCIP_CUTOFF )
1380  {
1381  SCIP_CALL( applyBdchgs(scip, vars, bdchginds, bdchgtypes, bdchgbounds, nbdchgs, result) );
1382  if( *result != SCIP_CUTOFF )
1383  *result = SCIP_REDUCEDDOM;
1384  }
1385  freeBdchgs(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs);
1386  }
1387 
1388  /* free buffer for the unreliable candidates */
1389  SCIPfreeBufferArray(scip, &initcandscores);
1390  SCIPfreeBufferArray(scip, &initcands);
1391  }
1392 
1393  /* if no domain could be reduced, create the branching */
1394  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED && executebranch )
1395  {
1396  SCIP_NODE* downchild;
1397  SCIP_NODE* upchild;
1398  SCIP_VAR* var;
1399  SCIP_Real val;
1400 
1401  assert(*result == SCIP_DIDNOTRUN);
1402  assert(0 <= bestcand && bestcand < nbranchcands);
1403  assert(!SCIPisFeasIntegral(scip, branchcandssol[bestcand]));
1404  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1405  assert(!bestsbdowncutoff && !bestsbupcutoff);
1406 
1407  var = branchcands[bestcand];
1408  val = branchcandssol[bestcand];
1409 
1410  /* perform the branching */
1411  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",
1412  nbranchcands, ninitcands, bestcand, SCIPvarGetName(var), branchcandssol[bestcand],
1413  bestsbdown, bestsbdown - lpobjval, bestsbup, bestsbup - lpobjval, bestisstrongbranch,
1416  SCIPgetVarPseudocostScoreCurrentRun(scip, var, branchcandssol[bestcand]));
1417  SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, NULL, &upchild) );
1418  assert(downchild != NULL);
1419  assert(upchild != NULL);
1420 
1421  /* update the lower bounds in the children */
1422  if( bestisstrongbranch && allcolsinlp && !exactsolve )
1423  {
1424  if( bestsbdownvalid )
1425  {
1426  assert(SCIPisLT(scip, bestsbdown, SCIPgetCutoffbound(scip)));
1427  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestsbdown) );
1428  assert(SCIPisGE(scip, SCIPgetNodeLowerbound(scip, downchild), provedbound));
1429  }
1430  if( bestsbupvalid )
1431  {
1432  assert(SCIPisLT(scip, bestsbup, SCIPgetCutoffbound(scip)));
1433  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestsbup) );
1434  assert(SCIPisGE(scip, SCIPgetNodeLowerbound(scip, upchild), provedbound));
1435  }
1436  }
1437 
1438  SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
1439  SCIPdebugMsg(scip, " -> up child's lowerbound : %g\n", SCIPnodeGetLowerbound(upchild));
1440 
1442 
1443  *result = SCIP_BRANCHED;
1444  }
1445 
1446  return SCIP_OKAY;
1447 }
1448 
1449 
1450 /*
1451  * Callback methods
1452  */
1453 
1454 /** copy method for branchrule plugins (called when SCIP copies plugins) */
1455 static
1456 SCIP_DECL_BRANCHCOPY(branchCopyRelpscost)
1457 { /*lint --e{715}*/
1458  assert(scip != NULL);
1459  assert(branchrule != NULL);
1460  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1461 
1462  /* call inclusion method of branchrule */
1464 
1465  return SCIP_OKAY;
1466 }
1467 
1468 /** destructor of branching rule to free user data (called when SCIP is exiting) */
1469 static
1470 SCIP_DECL_BRANCHFREE(branchFreeRelpscost)
1471 { /*lint --e{715}*/
1472  SCIP_BRANCHRULEDATA* branchruledata;
1474  /* free branching rule data */
1475  branchruledata = SCIPbranchruleGetData(branchrule);
1476  SCIPfreeBlockMemory(scip, &branchruledata);
1477  SCIPbranchruleSetData(branchrule, NULL);
1478 
1479  return SCIP_OKAY;
1480 }
1481 
1482 
1483 /** solving process initialization method of branching rule (called when branch and bound process is about to begin) */
1484 static
1485 SCIP_DECL_BRANCHINITSOL(branchInitsolRelpscost)
1486 { /*lint --e{715}*/
1487  SCIP_BRANCHRULEDATA* branchruledata;
1489  /* initialize branching rule data */
1490  branchruledata = SCIPbranchruleGetData(branchrule);
1491  branchruledata->nlcount = NULL;
1492  branchruledata->nlcountsize = 0;
1493  branchruledata->nlcountmax = 1;
1494  assert(branchruledata->startrandseed >= 0);
1495 
1496  /* create a random number generator */
1497  SCIP_CALL( SCIPrandomCreate(&branchruledata->randnumgen, SCIPblkmem(scip),
1498  SCIPinitializeRandomSeed(scip, branchruledata->startrandseed)) );
1499 
1500  return SCIP_OKAY;
1501 }
1502 
1503 
1504 /** solving process deinitialization method of branching rule (called before branch and bound process data is freed) */
1505 static
1506 SCIP_DECL_BRANCHEXITSOL(branchExitsolRelpscost)
1507 { /*lint --e{715}*/
1508  SCIP_BRANCHRULEDATA* branchruledata;
1510  /* free memory in branching rule data */
1511  branchruledata = SCIPbranchruleGetData(branchrule);
1512  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->nlcount, branchruledata->nlcountsize);
1513 
1514  /* free random number generator */
1515  SCIPrandomFree(&branchruledata->randnumgen);
1516 
1517  return SCIP_OKAY;
1518 }
1519 
1520 
1521 /** branching execution method for fractional LP solutions */
1522 static
1523 SCIP_DECL_BRANCHEXECLP(branchExeclpRelpscost)
1524 { /*lint --e{715}*/
1525  SCIP_VAR** tmplpcands;
1526  SCIP_VAR** lpcands;
1527  SCIP_Real* tmplpcandssol;
1528  SCIP_Real* lpcandssol;
1529  SCIP_Real* tmplpcandsfrac;
1530  SCIP_Real* lpcandsfrac;
1531  int nlpcands;
1532 
1533  assert(branchrule != NULL);
1534  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1535  assert(scip != NULL);
1536  assert(result != NULL);
1537 
1538  SCIPdebugMsg(scip, "Execlp method of relpscost branching in node %llu\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
1539 
1540  /* get branching candidates */
1541  SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, NULL, &nlpcands, NULL) );
1542  assert(nlpcands > 0);
1543 
1544  /* copy LP banching candidates and solution values, because they will be updated w.r.t. the strong branching LP
1545  * solution
1546  */
1547  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) );
1548  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) );
1549  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) );
1550 
1551  /* execute branching rule */
1552  SCIP_CALL( execRelpscost(scip, branchrule, allowaddcons, lpcands, lpcandssol, lpcandsfrac, nlpcands, TRUE, result) );
1553 
1554  SCIPfreeBufferArray(scip, &lpcandsfrac);
1555  SCIPfreeBufferArray(scip, &lpcandssol);
1556  SCIPfreeBufferArray(scip, &lpcands);
1557 
1558  return SCIP_OKAY;
1559 }
1560 
1561 
1562 /*
1563  * branching specific interface methods
1564  */
1565 
1566 /** creates the reliable pseudo cost branching rule and includes it in SCIP */
1568  SCIP* scip /**< SCIP data structure */
1569  )
1571  SCIP_BRANCHRULEDATA* branchruledata;
1572  SCIP_BRANCHRULE* branchrule;
1573 
1574  /* create relpscost branching rule data */
1575  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
1576 
1577  /* include branching rule */
1579  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1580 
1581  assert(branchrule != NULL);
1582 
1583  /* set non-fundamental callbacks via specific setter functions*/
1584  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyRelpscost) );
1585  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeRelpscost) );
1586  SCIP_CALL( SCIPsetBranchruleInitsol(scip, branchrule, branchInitsolRelpscost) );
1587  SCIP_CALL( SCIPsetBranchruleExitsol(scip, branchrule, branchExitsolRelpscost) );
1588  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpRelpscost) );
1589 
1590  /* relpscost branching rule parameters */
1592  "branching/relpscost/conflictweight",
1593  "weight in score calculations for conflict score",
1594  &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1596  "branching/relpscost/conflictlengthweight",
1597  "weight in score calculations for conflict length score",
1598  &branchruledata->conflengthweight, TRUE, DEFAULT_CONFLENGTHWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1600  "branching/relpscost/inferenceweight",
1601  "weight in score calculations for inference score",
1602  &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1604  "branching/relpscost/cutoffweight",
1605  "weight in score calculations for cutoff score",
1606  &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1608  "branching/relpscost/pscostweight",
1609  "weight in score calculations for pseudo cost score",
1610  &branchruledata->pscostweight, TRUE, DEFAULT_PSCOSTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1612  "branching/relpscost/nlscoreweight",
1613  "weight in score calculations for nlcount score",
1614  &branchruledata->nlscoreweight, TRUE, DEFAULT_NLSCOREWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1616  "branching/relpscost/minreliable",
1617  "minimal value for minimum pseudo cost size to regard pseudo cost value as reliable",
1618  &branchruledata->minreliable, TRUE, DEFAULT_MINRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1620  "branching/relpscost/maxreliable",
1621  "maximal value for minimum pseudo cost size to regard pseudo cost value as reliable",
1622  &branchruledata->maxreliable, TRUE, DEFAULT_MAXRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1624  "branching/relpscost/sbiterquot",
1625  "maximal fraction of strong branching LP iterations compared to node relaxation LP iterations",
1626  &branchruledata->sbiterquot, FALSE, DEFAULT_SBITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1627  SCIP_CALL( SCIPaddIntParam(scip,
1628  "branching/relpscost/sbiterofs",
1629  "additional number of allowed strong branching LP iterations",
1630  &branchruledata->sbiterofs, FALSE, DEFAULT_SBITEROFS, 0, INT_MAX, NULL, NULL) );
1631  SCIP_CALL( SCIPaddIntParam(scip,
1632  "branching/relpscost/maxlookahead",
1633  "maximal number of further variables evaluated without better score",
1634  &branchruledata->maxlookahead, TRUE, DEFAULT_MAXLOOKAHEAD, 1, INT_MAX, NULL, NULL) );
1635  SCIP_CALL( SCIPaddIntParam(scip,
1636  "branching/relpscost/initcand",
1637  "maximal number of candidates initialized with strong branching per node",
1638  &branchruledata->initcand, FALSE, DEFAULT_INITCAND, 0, INT_MAX, NULL, NULL) );
1639  SCIP_CALL( SCIPaddIntParam(scip,
1640  "branching/relpscost/inititer",
1641  "iteration limit for strong branching initializations of pseudo cost entries (0: auto)",
1642  &branchruledata->inititer, FALSE, DEFAULT_INITITER, 0, INT_MAX, NULL, NULL) );
1643  SCIP_CALL( SCIPaddIntParam(scip,
1644  "branching/relpscost/maxbdchgs",
1645  "maximal number of bound tightenings before the node is reevaluated (-1: unlimited)",
1646  &branchruledata->maxbdchgs, TRUE, DEFAULT_MAXBDCHGS, -1, INT_MAX, NULL, NULL) );
1647  SCIP_CALL( SCIPaddIntParam(scip,
1648  "branching/relpscost/maxproprounds",
1649  "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
1650  &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
1652  "branching/relpscost/probingbounds",
1653  "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
1654  &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
1655 
1656  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/userelerrorreliability",
1657  "should reliability be based on relative errors?", &branchruledata->userelerrorforreliability, TRUE, DEFAULT_USERELERRORFORRELIABILITY,
1658  NULL, NULL) );
1659 
1660  SCIP_CALL( SCIPaddRealParam(scip, "branching/relpscost/lowerrortol", "low relative error tolerance for reliability",
1661  &branchruledata->lowerrortol, TRUE, DEFAULT_LOWERRORTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1662 
1663  SCIP_CALL( SCIPaddRealParam(scip, "branching/relpscost/higherrortol", "high relative error tolerance for reliability",
1664  &branchruledata->higherrortol, TRUE, DEFAULT_HIGHERRORTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1665 
1666  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/storesemiinitcosts",
1667  "should strong branching result be considered for pseudo costs if the other direction was infeasible?",
1668  &branchruledata->storesemiinitcosts, TRUE, DEFAULT_STORESEMIINITCOSTS,
1669  NULL, NULL) );
1670 
1671  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usesblocalinfo",
1672  "should the scoring function use only local cutoff and inference information obtained for strong branching candidates?",
1673  &branchruledata->usesblocalinfo, TRUE, DEFAULT_USESBLOCALINFO,
1674  NULL, NULL) );
1675 
1676  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usehyptestforreliability",
1677  "should the strong branching decision be based on a hypothesis test?",
1678  &branchruledata->usehyptestforreliability, TRUE, DEFAULT_USEHYPTESTFORRELIABILITY,
1679  NULL, NULL) );
1680 
1681  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usedynamicconfidence",
1682  "should the confidence level be adjusted dynamically?",
1683  &branchruledata->usedynamicconfidence, TRUE, DEFAULT_USEDYNAMICCONFIDENCE,
1684  NULL, NULL) );
1685  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/skipbadinitcands",
1686  "should branching rule skip candidates that have a low probability to "
1687  "be better than the best strong-branching or pseudo-candidate?",
1688  &branchruledata->skipbadinitcands, TRUE, DEFAULT_SKIPBADINITCANDS,
1689  NULL, NULL) );
1690  SCIP_CALL( SCIPaddIntParam(scip,
1691  "branching/relpscost/confidencelevel",
1692  "the confidence level for statistical methods, between 0 (Min) and 4 (Max).",
1693  &branchruledata->confidencelevel, TRUE, DEFAULT_CONFIDENCELEVEL, 0, 4, NULL, NULL) );
1694 
1695  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/randinitorder",
1696  "should candidates be initialized in randomized order?",
1697  &branchruledata->randinitorder, TRUE, DEFAULT_RANDINITORDER,
1698  NULL, NULL) );
1699 
1700  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usesmallweightsitlim",
1701  "should smaller weights be used for pseudo cost updates after hitting the LP iteration limit?",
1702  &branchruledata->usesmallweightsitlim, TRUE, DEFAULT_USESMALLWEIGHTSITLIM,
1703  NULL, NULL) );
1704 
1705  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/dynamicweights",
1706  "should the weights of the branching rule be adjusted dynamically during solving based on objective and infeasible leaf counters?",
1707  &branchruledata->dynamicweights, TRUE, DEFAULT_DYNAMICWEIGHTS,
1708  NULL, NULL) );
1709  SCIP_CALL( SCIPaddIntParam(scip, "branching/relpscost/startrandseed", "start seed for random number generation",
1710  &branchruledata->startrandseed, TRUE, DEFAULT_STARTRANDSEED, 0, INT_MAX, NULL, NULL) );
1711 
1712  return SCIP_OKAY;
1713 }
1714 
1715 /** execution reliability pseudo cost branching with the given branching candidates */
1717  SCIP* scip, /**< SCIP data structure */
1718  SCIP_Bool allowaddcons, /**< is the branching rule allowed to add constraints to the current node
1719  * in order to cut off the current solution instead of creating a branching? */
1720  SCIP_VAR** branchcands, /**< branching candidates */
1721  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
1722  SCIP_Real* branchcandsfrac, /**< fractional part of the branching candidates */
1723  int nbranchcands, /**< number of branching candidates */
1724  SCIP_Bool executebranching, /**< perform a branching step after probing */
1725  SCIP_RESULT* result /**< pointer to the result of the execution */
1726  )
1727 {
1728  SCIP_BRANCHRULE* branchrule;
1729 
1730  assert(scip != NULL);
1731  assert(result != NULL);
1732 
1733  /* find branching rule */
1734  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
1735  assert(branchrule != NULL);
1736 
1737  /* execute branching rule */
1738  SCIP_CALL( execRelpscost(scip, branchrule, allowaddcons, branchcands, branchcandssol, branchcandsfrac, nbranchcands, executebranching, result) );
1739 
1740  return SCIP_OKAY;
1741 }
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:36128
static SCIP_RETCODE countNonlinearities(SCIP *scip, int *nlcount, int nlcountsize, int *nlcountmax)
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:21898
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1774
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip.c:45274
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21892
#define DEFAULT_PSCOSTWEIGHT
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip.c:30835
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22118
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:40453
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip.c:18733
#define DEFAULT_MAXBDCHGS
SCIP_Bool SCIPisSumGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46037
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42499
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7163
#define DEFAULT_LOWERRORTOL
static long bound
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
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:21112
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45803
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
static SCIP_RETCODE execRelpscost(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Bool allowaddcons, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranch, SCIP_RESULT *result)
SCIP_Bool SCIPpscostThresholdProbabilityTest(SCIP *scip, SCIP_VAR *var, SCIP_Real frac, SCIP_Real threshold, SCIP_BRANCHDIR dir, SCIP_CONFIDENCELEVEL clevel)
Definition: scip.c:25838
static SCIP_RETCODE binvarGetActiveProbindex(SCIP *scip, SCIP_VAR *var, int *probindex)
SCIP_Real SCIPgetAvgConflictScore(SCIP *scip)
Definition: scip.c:42912
SCIP_RETCODE SCIPsetBranchruleInitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: scip.c:9102
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16732
#define BRANCHRULE_MAXBOUNDDIST
#define DEFAULT_STARTRANDSEED
SCIP_Real SCIPgetVarPseudocostCountCurrentRun(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip.c:25729
SCIP_Real SCIPgetVarPseudocostScoreCurrentRun(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition: scip.c:25920
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:9054
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip.c:11505
#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:45816
#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:9038
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Longint SCIPgetVarStrongbranchNode(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21156
#define DEFAULT_INFERENCEWEIGHT
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9184
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:16859
SCIP_Longint SCIPgetNRootStrongbranchLPIterations(SCIP *scip)
Definition: scip.c:41847
SCIP_Bool SCIPisVarPscostRelerrorReliable(SCIP *scip, SCIP_VAR *var, SCIP_Real threshold, SCIP_CONFIDENCELEVEL clevel)
Definition: scip.c:25857
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22234
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
SCIP_RETCODE SCIPgetNLPVarsNonlinearity(SCIP *scip, int *nlcount)
Definition: scip.c:30946
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:9001
Constraint handler for AND constraints, .
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21933
static SCIP_DECL_BRANCHINITSOL(branchInitsolRelpscost)
static SCIP_DECL_BRANCHFREE(branchFreeRelpscost)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
#define DEFAULT_HIGHERRORTOL
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:16992
#define SCIPdebugMsg
Definition: scip.h:451
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:4202
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46223
static SCIP_DECL_BRANCHEXITSOL(branchExitsolRelpscost)
#define DEFAULT_USESMALLWEIGHTSITLIM
SCIP_Real SCIPgetVarPseudocostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition: scip.c:25882
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46211
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9136
#define DEFAULT_INITITER
SCIP_Longint SCIPgetNDualResolveLPIterations(SCIP *scip)
Definition: scip.c:41667
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip.c:25559
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip.c:36583
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7143
#define BRANCHRULE_NAME
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip.c:29262
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
#define BRANCHRULE_PRIORITY
int SCIPgetNNLPVars(SCIP *scip)
Definition: scip.c:30924
enum SCIP_Confidencelevel SCIP_CONFIDENCELEVEL
Definition: type_misc.h:44
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5101
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:5126
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip.h:21938
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
#define DEFAULT_USEHYPTESTFORRELIABILITY
#define NULL
Definition: lpi_spx1.cpp:137
SCIP_Real SCIPgetVarConflictlengthScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26082
#define SCIP_CALL(x)
Definition: def.h:306
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:25808
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:36813
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1353
#define DEFAULT_SBITEROFS
#define DEFAULT_CUTOFFWEIGHT
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:28769
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
Definition: scip.c:41703
SCIP_Real SCIPgetVarPseudocostCurrentRun(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip.c:25675
#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:21925
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip.c:19781
public data structures and miscellaneous methods
SCIP_Bool SCIPisSumGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46024
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
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:13394
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1784
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:20465
#define DEFAULT_MINRELIABLE
#define MAX(x, y)
Definition: tclique_def.h:75
#define DEFAULT_MAXPROPROUNDS
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25467
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip.c:9118
#define DEFAULT_INITCAND
SCIP_Longint SCIPgetNDualResolveLPs(SCIP *scip)
Definition: scip.c:41647
#define DEFAULT_NLSCOREWEIGHT
#define DEFAULT_DYNAMICWEIGHTS
#define DEFAULT_MAXLOOKAHEAD
SCIP_Longint SCIPgetNObjlimLeaves(SCIP *scip)
Definition: scip.c:41308
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4549
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:8745
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:11631
#define SCIP_REAL_MAX
Definition: def.h:136
#define DEFAULT_USERELERRORFORRELIABILITY
#define SCIP_REAL_MIN
Definition: def.h:137
SCIP_Real SCIPgetAvgCutoffScore(SCIP *scip)
Definition: scip.c:43134
SCIP_LPSOLSTAT SCIPgetLastStrongbranchLPSolStat(SCIP *scip, SCIP_BRANCHDIR branchdir)
Definition: scip.c:21090
SCIP_Longint SCIPgetNNodeInitLPIterations(SCIP *scip)
Definition: scip.c:41739
SCIP_Longint SCIPgetNNodeInitLPs(SCIP *scip)
Definition: scip.c:41721
SCIP_Real SCIPgetAvgConflictlengthScore(SCIP *scip)
Definition: scip.c:42962
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:28897
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:38931
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
#define DEFAULT_PROBINGBOUNDS
SCIP_Longint SCIPgetNStrongbranchLPIterations(SCIP *scip)
Definition: scip.c:41811
SCIP_RETCODE SCIPincludeBranchruleRelpscost(SCIP *scip)
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
Definition: scip.c:19840
#define DEFAULT_USESBLOCALINFO
#define DEFAULT_STORESEMIINITCOSTS
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11586
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16671
#define SCIP_Real
Definition: def.h:135
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1896
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5077
#define SCIP_INVALID
Definition: def.h:155
#define SCIP_Longint
Definition: def.h:120
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:29244
#define DEFAULT_USEDYNAMICCONFIDENCE
static SCIP_RETCODE branchruledataEnsureNlcount(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_RETCODE SCIPexecRelpscostBranching(SCIP *scip, SCIP_Bool allowaddcons, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result)
SCIP_Real SCIPgetNodeLowerbound(SCIP *scip, SCIP_NODE *node)
Definition: scip.c:13259
#define BRANCHRULE_DESC
SCIP_Real SCIPgetAvgPseudocostScore(SCIP *scip)
Definition: scip.c:42815
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:21910
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46187
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
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:20012
#define DEFAULT_MAXRELIABLE
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182
SCIP_Longint SCIPgetNInfeasibleLeaves(SCIP *scip)
Definition: scip.c:41281
#define DEFAULT_CONFIDENCELEVEL
#define DEFAULT_RANDINITORDER
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26252
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip.c:1025
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2413
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:4258
SCIP_Real SCIPgetAvgInferenceScore(SCIP *scip)
Definition: scip.c:43048
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:4176
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26020
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16839
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16707
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip.h:21929
SCIP_Real SCIPgetVarAvgCutoffScore(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:26506