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