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-2020 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 scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch_relpscost.c
17  * @ingroup DEFPLUGINS_BRANCH
18  * @brief reliable pseudo costs branching rule
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Gerald Gamrath
22  * @author Marc Pfetsch
23  */
24 
25 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
26 
27 #include "blockmemshell/memory.h"
28 #include "scip/branch_relpscost.h"
29 #include "scip/treemodel.h"
30 #include "scip/cons_and.h"
31 #include "scip/pub_branch.h"
32 #include "scip/pub_cons.h"
33 #include "scip/pub_message.h"
34 #include "scip/pub_misc.h"
35 #include "scip/pub_sol.h"
36 #include "scip/pub_tree.h"
37 #include "scip/pub_var.h"
38 #include "scip/scip_branch.h"
39 #include "scip/scip_cons.h"
40 #include "scip/scip_general.h"
41 #include "scip/scip_lp.h"
42 #include "scip/scip_mem.h"
43 #include "scip/scip_message.h"
44 #include "scip/scip_nlp.h"
45 #include "scip/scip_numerics.h"
46 #include "scip/scip_param.h"
47 #include "scip/scip_prob.h"
48 #include "scip/scip_randnumgen.h"
49 #include "scip/scip_sol.h"
50 #include "scip/scip_solvingstats.h"
51 #include "scip/scip_tree.h"
52 #include "scip/scip_var.h"
53 #include "scip/prop_symmetry.h"
54 #include "scip/symmetry.h"
55 #include <string.h>
56 
57 #define BRANCHRULE_NAME "relpscost"
58 #define BRANCHRULE_DESC "reliability branching on pseudo cost values"
59 #define BRANCHRULE_PRIORITY 10000
60 #define BRANCHRULE_MAXDEPTH -1
61 #define BRANCHRULE_MAXBOUNDDIST 1.0
62 
63 #define DEFAULT_CONFLICTWEIGHT 0.01 /**< weight in score calculations for conflict score */
64 #define DEFAULT_CONFLENGTHWEIGHT 0.0 /**< weight in score calculations for conflict length score*/
65 #define DEFAULT_INFERENCEWEIGHT 0.0001 /**< weight in score calculations for inference score */
66 #define DEFAULT_CUTOFFWEIGHT 0.0001 /**< weight in score calculations for cutoff score */
67 #define DEFAULT_PSCOSTWEIGHT 1.0 /**< weight in score calculations for pseudo cost score */
68 #define DEFAULT_NLSCOREWEIGHT 0.1 /**< weight in score calculations for nlcount score */
69 #define DEFAULT_MINRELIABLE 1.0 /**< minimal value for minimum pseudo cost size to regard pseudo cost value as reliable */
70 #define DEFAULT_MAXRELIABLE 5.0 /**< maximal value for minimum pseudo cost size to regard pseudo cost value as reliable */
71 #define DEFAULT_SBITERQUOT 0.5 /**< maximal fraction of strong branching LP iterations compared to normal iterations */
72 #define DEFAULT_SBITEROFS 100000 /**< additional number of allowed strong branching LP iterations */
73 #define DEFAULT_MAXLOOKAHEAD 9 /**< maximal number of further variables evaluated without better score */
74 #define DEFAULT_INITCAND 100 /**< maximal number of candidates initialized with strong branching per node */
75 #define DEFAULT_INITITER 0 /**< iteration limit for strong branching initialization of pseudo cost entries (0: auto) */
76 #define DEFAULT_MAXBDCHGS 5 /**< maximal number of bound tightenings before the node is reevaluated (-1: unlimited) */
77 #define DEFAULT_MAXPROPROUNDS -2 /**< maximum number of propagation rounds to be performed during strong branching
78  * before solving the LP (-1: no limit, -2: parameter settings) */
79 #define DEFAULT_PROBINGBOUNDS TRUE /**< should valid bounds be identified in a probing-like fashion during strong
80  * branching (only with propagation)? */
81 #define DEFAULT_USERELERRORFORRELIABILITY FALSE /**< should reliability be based on relative errors? */
82 #define DEFAULT_LOWERRORTOL 0.05 /**< lowest tolerance beneath which relative errors are reliable */
83 #define DEFAULT_HIGHERRORTOL 1.0 /**< highest tolerance beneath which relative errors are reliable */
84 #define DEFAULT_USEHYPTESTFORRELIABILITY FALSE /**< should the strong branching decision be based on a hypothesis test? */
85 #define DEFAULT_USEDYNAMICCONFIDENCE FALSE /**< should the confidence level be adjusted dynamically? */
86 #define DEFAULT_STORESEMIINITCOSTS FALSE /**< should strong branching result be considered for pseudo costs if the other direction was infeasible? */
87 #define DEFAULT_USESBLOCALINFO FALSE /**< should the scoring function use only local cutoff and inference information obtained for strong branching candidates? */
88 #define DEFAULT_CONFIDENCELEVEL 2 /**< The confidence level for statistical methods, between 0 (Min) and 4 (Max). */
89 #define DEFAULT_SKIPBADINITCANDS TRUE /**< should branching rule skip candidates that have a low probability to be
90  * better than the best strong-branching or pseudo-candidate? */
91 #define DEFAULT_STARTRANDSEED 5 /**< start random seed for random number generation */
92 #define DEFAULT_RANDINITORDER FALSE /**< should slight perturbation of scores be used to break ties in the prior scores? */
93 #define DEFAULT_USESMALLWEIGHTSITLIM FALSE /**< should smaller weights be used for pseudo cost updates after hitting the LP iteration limit? */
94 #define DEFAULT_DYNAMICWEIGHTS TRUE /**< should the weights of the branching rule be adjusted dynamically during solving based
95  * infeasible and objective leaf counters? */
96 #define DEFAULT_DEGENERACYAWARE 1 /**< should degeneracy be taken into account to update weights and skip strong branching? (0: off, 1: after root, 2: always)*/
97 
98 /* symmetry handling */
99 #define DEFAULT_FILTERCANDSSYM FALSE /**< Use symmetry to filter branching candidates? */
100 #define DEFAULT_TRANSSYMPSCOST FALSE /**< Transfer pscost information to symmetric variables if filtering is performed? */
101 
102 /** branching rule data */
103 struct SCIP_BranchruleData
104 {
105  SCIP_Real conflictweight; /**< weight in score calculations for conflict score */
106  SCIP_Real conflengthweight; /**< weight in score calculations for conflict length score */
107  SCIP_Real inferenceweight; /**< weight in score calculations for inference score */
108  SCIP_Real cutoffweight; /**< weight in score calculations for cutoff score */
109  SCIP_Real pscostweight; /**< weight in score calculations for pseudo cost score */
110  SCIP_Real nlscoreweight; /**< weight in score calculations for nlcount score */
111  SCIP_Real minreliable; /**< minimal value for minimum pseudo cost size to regard pseudo cost value as reliable */
112  SCIP_Real maxreliable; /**< maximal value for minimum pseudo cost size to regard pseudo cost value as reliable */
113  SCIP_Real sbiterquot; /**< maximal fraction of strong branching LP iterations compared to normal iterations */
114  int sbiterofs; /**< additional number of allowed strong branching LP iterations */
115  int maxlookahead; /**< maximal number of further variables evaluated without better score */
116  int initcand; /**< maximal number of candidates initialized with strong branching per node */
117  int inititer; /**< iteration limit for strong branching initialization of pseudo cost entries (0: auto) */
118  int maxbdchgs; /**< maximal number of bound tightenings before the node is reevaluated (-1: unlimited) */
119  int maxproprounds; /**< maximum number of propagation rounds to be performed during strong branching
120  * before solving the LP (-1: no limit, -2: parameter settings) */
121  SCIP_Bool probingbounds; /**< should valid bounds be identified in a probing-like fashion during strong
122  * branching (only with propagation)? */
123  SCIP_Bool userelerrorforreliability; /**< should reliability be based on relative errors? */
124  SCIP_Real lowerrortol; /**< lowest tolerance beneath which relative errors are reliable */
125  SCIP_Real higherrortol; /**< highest tolerance beneath which relative errors are reliable */
126  SCIP_Bool usehyptestforreliability; /**< should the strong branching decision be based on a hypothesis test? */
127  SCIP_Bool usedynamicconfidence; /**< should the confidence level be adjusted dynamically? */
128  SCIP_Bool storesemiinitcosts; /**< should strong branching result be considered for pseudo costs if the
129  * other direction was infeasible? */
130  SCIP_Bool usesblocalinfo; /**< should the scoring function disregard cutoffs for variable if sb-lookahead was feasible ? */
131  SCIP_Bool skipbadinitcands; /**< should branching rule skip candidates that have a low probability to be
132  * better than the best strong-branching or pseudo-candidate? */
133  SCIP_Bool dynamicweights; /**< should the weights of the branching rule be adjusted dynamically during
134  * solving based on objective and infeasible leaf counters? */
135  int degeneracyaware; /**< should degeneracy be taken into account to update weights and skip strong branching? (0: off, 1: after root, 2: always) */
136  int confidencelevel; /**< The confidence level for statistical methods, between 0 (Min) and 4 (Max). */
137  int* nlcount; /**< array to store nonlinear count values */
138  int nlcountsize; /**< length of nlcount array */
139  int nlcountmax; /**< maximum entry in nlcount array or 1 if NULL */
140  SCIP_Bool randinitorder; /**< should slight perturbation of scores be used to break ties in the prior scores? */
141  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
142  int startrandseed; /**< start random seed for random number generation */
143  SCIP_Bool usesmallweightsitlim; /**< should smaller weights be used for pseudo cost updates after hitting the LP iteration limit? */
144  SCIP_TREEMODEL* treemodel; /**< Parameters for the Treemodel branching rules */
145 
146  /* for symmetry */
147  SCIP_Bool filtercandssym; /**< Use symmetry to filter branching candidates? */
148  SCIP_Bool transsympscost; /**< Transfer pscost information to symmetric variables? */
149 
150  SCIP_Bool nosymmetry; /**< No symmetry present? */
151  int* orbits; /**< array of non-trivial orbits */
152  int* orbitbegins; /**< array containing begin positions of new orbits in orbits array */
153  int norbits; /**< pointer to number of orbits currently stored in orbits */
154  int* varorbitmap; /**< array for storing indices of the containing orbit for each variable */
155  int* orbitrep; /**< representative variable of each orbit */
156  SCIP_VAR** permvars; /**< variables on which permutations act */
157  int npermvars; /**< number of variables for permutations */
158  SCIP_HASHMAP* permvarmap; /**< map of variables to indices in permvars array */
159 };
160 
161 /*
162  * local methods
163  */
164 
165 /** initialize orbits */
166 static
167 SCIP_RETCODE initOrbits(
168  SCIP* scip, /**< SCIP data structure */
169  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
170  )
171 {
172  int** permstrans = NULL;
173  int* components = NULL;
174  int* componentbegins = NULL;
175  int* vartocomponent = NULL;
176  int ncomponents = 0;
177  int nperms = -1;
178 
179  assert( scip != NULL );
180  assert( branchruledata != NULL );
181  assert( branchruledata->filtercandssym );
182 
183  /* exit if no symmetry or orbits already available */
184  if( branchruledata->nosymmetry || branchruledata->orbits != NULL )
185  return SCIP_OKAY;
186 
187  assert( branchruledata->orbitbegins == NULL );
188  assert( branchruledata->varorbitmap == NULL );
189  assert( branchruledata->orbitrep == NULL );
190 
191  /* obtain symmetry including permutations */
192  SCIP_CALL( SCIPgetSymmetry(scip, &branchruledata->npermvars, &branchruledata->permvars, &branchruledata->permvarmap,
193  &nperms, NULL, &permstrans, NULL, NULL, &components, &componentbegins, &vartocomponent, &ncomponents) );
194 
195  /* turn off symmetry handling if there is no symmetry or the number of variables is not equal */
196  if( nperms <= 0 || branchruledata->npermvars != SCIPgetNVars(scip) )
197  {
198  branchruledata->nosymmetry = TRUE;
199  return SCIP_OKAY;
200  }
201  assert( branchruledata->permvars != NULL );
202  assert( branchruledata->permvarmap != NULL );
203  assert( branchruledata->npermvars > 0 );
204  assert( permstrans != NULL );
205  assert( components != NULL );
206  assert( componentbegins != NULL );
207  assert( vartocomponent != NULL );
208  assert( ncomponents > 0 );
209 
210  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->orbits, branchruledata->npermvars) );
211  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->orbitbegins, branchruledata->npermvars) );
212  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->varorbitmap, branchruledata->npermvars) );
213  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->orbitrep, branchruledata->npermvars) );
214 
215  /* Compute orbits on all variables, since this might help for branching and this computation is only done once. */
216  SCIP_CALL( SCIPcomputeOrbitsComponentsSym(scip, branchruledata->npermvars, permstrans, nperms,
217  components, componentbegins, vartocomponent, ncomponents,
218  branchruledata->orbits, branchruledata->orbitbegins, &branchruledata->norbits, branchruledata->varorbitmap) );
219  assert( branchruledata->norbits < branchruledata->npermvars );
220 
221  return SCIP_OKAY;
222 }
223 
224 /** filter out symmetric variables from branching variables */
225 static
226 SCIP_RETCODE filterSymmetricVariables(
227  SCIP* scip, /**< SCIP data structure */
228  SCIP_BRANCHRULEDATA* branchruledata, /**< branching rule data */
229  SCIP_VAR** origbranchcands, /**< original branching candidates */
230  SCIP_Real* origbranchcandssol, /**< original solution value for the branching candidates */
231  SCIP_Real* origbranchcandsfrac,/**< original fractional part of the branching candidates */
232  int norigbranchcands, /**< original number of branching candidates */
233  SCIP_VAR** branchcands, /**< branching candidates */
234  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
235  SCIP_Real* branchcandsfrac, /**< fractional part of the branching candidates */
236  int* branchorbitidx, /**< array of indices of orbit of branching candidates */
237  int* nbranchcands /**< pointer to store number of branching candidates */
238  )
239 {
240  int i;
241 
242  assert( scip != NULL );
243  assert( branchruledata != NULL );
244  assert( origbranchcands != NULL );
245  assert( origbranchcandssol != NULL );
246  assert( origbranchcandsfrac != NULL );
247  assert( branchcands != NULL );
248  assert( branchcandssol != NULL );
249  assert( branchcandsfrac != NULL );
250  assert( nbranchcands != NULL );
251 
252  assert( ! branchruledata->nosymmetry );
253  assert( branchruledata->orbitbegins != NULL );
254  assert( branchruledata->orbits != NULL );
255  assert( branchruledata->permvarmap != NULL );
256  assert( branchruledata->varorbitmap != NULL );
257  assert( branchruledata->orbitrep != NULL );
258  assert( branchruledata->norbits < branchruledata->npermvars );
259 
260  /* init representatives (used to see whether variable is the first in an orbit) */
261  for( i = 0; i < branchruledata->norbits; ++i )
262  branchruledata->orbitrep[i] = -1;
263 
264  /* loop through branching variables, determine orbit and whether they are the first ones */
265  *nbranchcands = 0;
266  for( i = 0; i < norigbranchcands; ++i )
267  {
268  int orbitidx = -1;
269  int varidx;
270 
271  varidx = SCIPhashmapGetImageInt(branchruledata->permvarmap, (void*) origbranchcands[i]);
272  if( varidx != INT_MAX )
273  {
274  assert( 0 <= varidx && varidx < branchruledata->npermvars );
275  orbitidx = branchruledata->varorbitmap[varidx];
276  }
277  assert( -1 <= orbitidx && orbitidx < branchruledata->norbits );
278 
279  /* Check whether the variable is not present (can happen if variable was added after computing symmetries or is in
280  * a singleton orbit). */
281  if( orbitidx == -1 )
282  {
283  branchcands[*nbranchcands] = origbranchcands[i];
284  branchcandssol[*nbranchcands] = origbranchcandssol[i];
285  branchcandsfrac[*nbranchcands] = origbranchcandsfrac[i];
286  branchorbitidx[*nbranchcands] = -1;
287  ++(*nbranchcands);
288  }
289  else if( branchruledata->orbitrep[orbitidx] == -1 )
290  {
291  /* if variable is the first in a nontrivial orbit */
292  assert( 0 <= varidx && varidx < branchruledata->npermvars );
293  branchruledata->orbitrep[orbitidx] = varidx;
294  branchcands[*nbranchcands] = origbranchcands[i];
295  branchcandssol[*nbranchcands] = origbranchcandssol[i];
296  branchcandsfrac[*nbranchcands] = origbranchcandsfrac[i];
297  branchorbitidx[*nbranchcands] = orbitidx;
298  ++(*nbranchcands);
299  }
300  }
301 
302  SCIPdebugMsg(scip, "Filtered out %d variables by symmetry.\n", norigbranchcands - *nbranchcands);
303 
304  return SCIP_OKAY;
305 }
306 
307 /** updates the pseudo costs of the given variable and all its symmetric variables */
308 static
309 SCIP_RETCODE SCIPupdateVarPseudocostSymmetric(
310  SCIP* scip, /**< SCIP data structure */
311  SCIP_BRANCHRULEDATA* branchruledata, /**< branching rule data */
312  SCIP_VAR* branchvar, /**< branching variable candidate */
313  int* branchorbitidx, /**< array of orbit indices */
314  int branchvaridx, /**< index of variable in branchorbitidx */
315  SCIP_Real solvaldelta, /**< difference of variable's new LP value - old LP value */
316  SCIP_Real objdelta, /**< difference of new LP's objective value - old LP's objective value */
317  SCIP_Real weight /**< weight in (0,1] of this update in pseudo cost sum */
318  )
319 {
320  int orbitidx;
321  int j;
322 
323  assert( scip != NULL );
324  assert( branchruledata != NULL );
325 
326  if( branchruledata->nosymmetry || ! branchruledata->transsympscost || branchorbitidx == NULL )
327  {
328  /* use original update function */
329  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchvar, solvaldelta, objdelta, weight) );
330  return SCIP_OKAY;
331  }
332 
333  assert( branchruledata->orbitbegins != NULL );
334  assert( branchruledata->orbits != NULL );
335  assert( 0 <= branchvaridx && branchvaridx < branchruledata->npermvars );
336 
337  orbitidx = branchorbitidx[branchvaridx];
338  if( orbitidx < 0 )
339  {
340  /* only update given variable */
341  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchvar, solvaldelta, objdelta, weight) );
342  return SCIP_OKAY;
343  }
344  assert( 0 <= orbitidx && orbitidx < branchruledata->norbits );
345 
346  /* loop through orbit containing variable and update pseudo costs for all variables */
347  for( j = branchruledata->orbitbegins[orbitidx]; j < branchruledata->orbitbegins[orbitidx+1]; ++j )
348  {
349  SCIP_VAR* var;
350  int idx;
351 
352  idx = branchruledata->orbits[j];
353  assert( 0 <= idx && idx < branchruledata->npermvars );
354 
355  var = branchruledata->permvars[idx];
356  assert( var != NULL );
357 
358  if( SCIPvarIsActive(var) )
359  {
360  SCIP_CALL( SCIPupdateVarPseudocost(scip, var, solvaldelta, objdelta, weight) );
361  }
362  }
363 
364  return SCIP_OKAY;
365 }
366 
367 /**! [SnippetCodeStyleStaticAsserts] */
368 
369 /** return probindex of variable or corresponding active variable (if negated or aggregated) or -1 (if multiaggregated) */
370 static
371 SCIP_RETCODE binvarGetActiveProbindex(
372  SCIP* scip, /**< SCIP data structure */
373  SCIP_VAR* var, /**< binary variable */
374  int* probindex /**< buffer to store probindex */
375  )
376 {
377  assert(scip != NULL);
378  assert(var != NULL);
379  assert(SCIPvarIsBinary(var));
380  assert(probindex != NULL);
381 
382 /**! [SnippetCodeStyleStaticAsserts] */
383 
384  *probindex = SCIPvarGetProbindex(var);
385 
386  /* if variable is not active, try to find active representative */
387  if( *probindex == -1 )
388  {
389  SCIP_VAR* repvar;
390  SCIP_Bool negated;
391 
392  SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
393  assert(repvar != NULL);
394  assert(SCIPvarGetStatus(repvar) != SCIP_VARSTATUS_FIXED);
395 
396  if( SCIPvarIsActive(repvar) )
397  *probindex = SCIPvarGetProbindex(repvar);
398  else if( SCIPvarIsNegated(repvar) )
399  *probindex = SCIPvarGetProbindex(SCIPvarGetNegationVar(repvar));
400  }
401 
402  return SCIP_OKAY;
403 }
404 
405 /**! [SnippetCodeStyleDeclaration] */
406 
407 /** counts number of nonlinear constraints in which each variable appears */
408 static
409 SCIP_RETCODE countNonlinearities(
410  SCIP* scip, /**< SCIP data structure */
411  int* nlcount, /**< pointer to array for storing count values */
412  int nlcountsize, /**< buffer for storing length of nlcount array */
413  int* nlcountmax /**< buffer for storing maximum value in nlcount array */
414  )
415 {
416  SCIP_CONSHDLR* andconshdlr;
417  SCIP_VAR** vars;
418  int nvars;
419  int i;
420 
421 /**! [SnippetCodeStyleDeclaration] */
422 
423  assert(scip != NULL);
424  assert(nlcount != NULL);
425  assert(nlcountmax != NULL);
426 
427  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
428  assert(nlcountsize >= nvars);
429 
430  /* get nonlinearity for constraints in NLP */
431  if( SCIPisNLPConstructed(scip) )
432  {
433  assert(SCIPgetNNLPVars(scip) == nvars);
434  SCIP_CALL( SCIPgetNLPVarsNonlinearity(scip, nlcount) );
435  }
436  else
437  {
438  BMSclearMemoryArray(nlcount, nvars);
439  }
440 
441  /* increase counters for and constraints */
442  andconshdlr = SCIPfindConshdlr(scip, "and");
443  if( andconshdlr != NULL )
444  {
445  int c;
446 
447  for( c = 0; c < SCIPconshdlrGetNActiveConss(andconshdlr); c++ )
448  {
449  SCIP_CONS* andcons;
450  SCIP_VAR** andvars;
451  SCIP_VAR* andres;
452  int probindex;
453  int nandvars;
454  int v;
455 
456  /* get constraint and variables */
457  andcons = SCIPconshdlrGetConss(andconshdlr)[c];
458  nandvars = SCIPgetNVarsAnd(scip, andcons);
459  andvars = SCIPgetVarsAnd(scip, andcons);
460  andres = SCIPgetResultantAnd(scip, andcons);
461 
462  probindex = -1;
463 
464  /**! [SnippetCodeStyleIfFor] */
465 
466  for( v = 0; v < nandvars; v++ )
467  {
468  /* don't rely on the and conshdlr removing fixed variables
469  * @todo fix the and conshdlr in that respect
470  */
471  if( SCIPvarGetStatus(andvars[v]) != SCIP_VARSTATUS_FIXED )
472  {
473  SCIP_CALL( binvarGetActiveProbindex(scip, andvars[v], &probindex) );
474  if( probindex >= 0 )
475  nlcount[probindex]++;
476  }
477  }
478 
479  /**! [SnippetCodeStyleIfFor] */
480 
481  SCIP_CALL( binvarGetActiveProbindex(scip, andres, &probindex) );
482  if( probindex >= 0 )
483  nlcount[probindex]++;
484  }
485  }
486 
487  /* compute maximum count value */
488  *nlcountmax = 1;
489  for( i = 0; i < nvars; i++ )
490  {
491  if( *nlcountmax < nlcount[i] )
492  *nlcountmax = nlcount[i];
493  }
494 
495  return SCIP_OKAY;
496 }
497 
498 static
499 SCIP_RETCODE branchruledataEnsureNlcount(
500  SCIP* scip, /**< SCIP data structure */
501  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
502  )
503 {
504  int nvars;
505 
506  assert(scip != NULL);
507  assert(branchruledata != NULL);
508 
509  nvars = SCIPgetNVars(scip);
510 
511  /**@todo test whether we want to apply this as if problem has only and constraints */
512  /**@todo update changes in and constraints */
513  if( branchruledata->nlscoreweight > 0.0 ) /* && SCIPisNLPConstructed(scip) */
514  {
515  if( branchruledata->nlcount == NULL )
516  {
517  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->nlcount, nvars) );
518  branchruledata->nlcountsize = nvars;
519 
520  SCIP_CALL( countNonlinearities(scip, branchruledata->nlcount, branchruledata->nlcountsize, &branchruledata->nlcountmax) );
521  }
522  else if( branchruledata->nlcountsize < nvars )
523  {
524  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &branchruledata->nlcount, branchruledata->nlcountsize, nvars) );
525  /**@todo should we update nlcounts for new variables? */
526  BMSclearMemoryArray(&(branchruledata->nlcount[branchruledata->nlcountsize]), nvars - branchruledata->nlcountsize); /*lint !e866*/
527  branchruledata->nlcountsize = nvars;
528  }
529  assert(branchruledata->nlcount != NULL);
530  assert(branchruledata->nlcountsize == nvars);
531  assert(branchruledata->nlcountmax >= 1);
532  }
533  else
534  {
535  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->nlcount, branchruledata->nlcountsize);
536  branchruledata->nlcountsize = 0;
537  branchruledata->nlcountmax = 1;
538  }
539 
540  return SCIP_OKAY;
541 }
542 
543 
544 /** calculates nlscore value between 0 and 1 */
545 static
546 SCIP_Real calcNlscore(
547  SCIP* scip, /**< SCIP data structure */
548  int* nlcount, /**< array to store count values */
549  int nlcountmax, /**< maximum value in nlcount array */
550  int probindex /**< index of branching candidate */
551  )
552 {
553  if( nlcountmax >= 1 && nlcount != NULL )
554  {
555  SCIP_Real nlscore;
556 
557  assert(scip != NULL);
558  assert(probindex >= 0);
559  assert(probindex < SCIPgetNVars(scip));
560 
561  nlscore = nlcount[probindex] / (SCIP_Real)nlcountmax;
562 
563  assert(nlscore >= 0.0);
564  assert(nlscore <= 1.0);
565  return nlscore;
566  }
567  else
568  return 0.0;
569 }
570 
571 /** calculates an overall score value for the given individual score values */
572 static
573 SCIP_Real calcScore(
574  SCIP* scip, /**< SCIP data structure */
575  SCIP_BRANCHRULEDATA* branchruledata, /**< branching rule data */
576  SCIP_Real conflictscore, /**< conflict score of current variable */
577  SCIP_Real avgconflictscore, /**< average conflict score */
578  SCIP_Real conflengthscore, /**< conflict length score of current variable */
579  SCIP_Real avgconflengthscore, /**< average conflict length score */
580  SCIP_Real inferencescore, /**< inference score of current variable */
581  SCIP_Real avginferencescore, /**< average inference score */
582  SCIP_Real cutoffscore, /**< cutoff score of current variable */
583  SCIP_Real avgcutoffscore, /**< average cutoff score */
584  SCIP_Real pscostscore, /**< pscost score of current variable */
585  SCIP_Real avgpscostscore, /**< average pscost score */
586  SCIP_Real nlscore, /**< nonlinear score of current variable between 0 and 1 */
587  SCIP_Real frac, /**< fractional value of variable in current solution */
588  SCIP_Real degeneracyfactor /**< factor to apply because of degeneracy */
589  )
590 {
591  SCIP_Real score;
592  SCIP_Real dynamicfactor;
593 
594  assert(branchruledata != NULL);
595  assert(0.0 < frac && frac < 1.0);
596 
597  if( branchruledata->dynamicweights )
598  {
599  dynamicfactor = (SCIPgetNInfeasibleLeaves(scip) + 1.0) / (SCIPgetNObjlimLeaves(scip) + 1.0);
600  }
601  else
602  dynamicfactor = 1.0;
603 
604  dynamicfactor *= degeneracyfactor;
605 
606  score = dynamicfactor * (branchruledata->conflictweight * (1.0 - 1.0/(1.0+conflictscore/avgconflictscore))
607  + branchruledata->conflengthweight * (1.0 - 1.0/(1.0+conflengthscore/avgconflengthscore))
608  + branchruledata->inferenceweight * (1.0 - 1.0/(1.0+inferencescore/avginferencescore))
609  + branchruledata->cutoffweight * (1.0 - 1.0/(1.0+cutoffscore/avgcutoffscore)))
610  + branchruledata->pscostweight / dynamicfactor * (1.0 - 1.0/(1.0+pscostscore/avgpscostscore))
611  + branchruledata->nlscoreweight * nlscore;
612 
613  /* avoid close to integral variables */
614  if( MIN(frac, 1.0 - frac) < 10.0 * SCIPfeastol(scip) )
615  score *= 1e-6;
616 
617  return score;
618 }
619 
620 /** adds given index and direction to bound change arrays */
621 static
622 SCIP_RETCODE addBdchg(
623  SCIP* scip, /**< SCIP data structure */
624  int** bdchginds, /**< pointer to bound change index array */
625  SCIP_BOUNDTYPE** bdchgtypes, /**< pointer to bound change types array */
626  SCIP_Real** bdchgbounds, /**< pointer to bound change new bounds array */
627  int* nbdchgs, /**< pointer to number of bound changes */
628  int ind, /**< index to store in bound change index array */
629  SCIP_BOUNDTYPE type, /**< type of the bound change to store in bound change type array */
630  SCIP_Real bound /**< new bound to store in bound change new bounds array */
631  )
632 {
633  assert(bdchginds != NULL);
634  assert(bdchgtypes != NULL);
635  assert(bdchgbounds != NULL);
636  assert(nbdchgs != NULL);
637 
638  SCIP_CALL( SCIPreallocBufferArray(scip, bdchginds, (*nbdchgs) + 1) );
639  SCIP_CALL( SCIPreallocBufferArray(scip, bdchgtypes, (*nbdchgs) + 1) );
640  SCIP_CALL( SCIPreallocBufferArray(scip, bdchgbounds, (*nbdchgs) + 1) );
641  assert(*bdchginds != NULL);
642  assert(*bdchgtypes != NULL);
643  assert(*bdchgbounds != NULL);
644 
645  (*bdchginds)[*nbdchgs] = ind;
646  (*bdchgtypes)[*nbdchgs] = type;
647  (*bdchgbounds)[*nbdchgs] = bound;
648  (*nbdchgs)++;
649 
650  return SCIP_OKAY;
651 }
652 
653 /** frees bound change arrays */
654 static
655 void freeBdchgs(
656  SCIP* scip, /**< SCIP data structure */
657  int** bdchginds, /**< pointer to bound change index array */
658  SCIP_BOUNDTYPE** bdchgtypes, /**< pointer to bound change types array */
659  SCIP_Real** bdchgbounds, /**< pointer to bound change new bounds array */
660  int* nbdchgs /**< pointer to number of bound changes */
661  )
662 {
663  assert(bdchginds != NULL);
664  assert(bdchgtypes != NULL);
665  assert(bdchgbounds != NULL);
666  assert(nbdchgs != NULL);
667 
668  SCIPfreeBufferArrayNull(scip, bdchgbounds);
669  SCIPfreeBufferArrayNull(scip, bdchgtypes);
670  SCIPfreeBufferArrayNull(scip, bdchginds);
671  *nbdchgs = 0;
672 }
673 
674 /** applies bound changes stored in bound change arrays */
675 static
676 SCIP_RETCODE applyBdchgs(
677  SCIP* scip, /**< SCIP data structure */
678  SCIP_VAR** vars, /**< problem variables */
679  int* bdchginds, /**< bound change index array */
680  SCIP_BOUNDTYPE* bdchgtypes, /**< bound change types array */
681  SCIP_Real* bdchgbounds, /**< bound change new bound array */
682  int nbdchgs, /**< number of bound changes */
683  SCIP_RESULT* result /**< result pointer */
684  )
685 {
686 #ifndef NDEBUG
687  SCIP_BRANCHRULE* branchrule;
688  SCIP_BRANCHRULEDATA* branchruledata;
689 #endif
690  SCIP_Bool infeasible;
691  SCIP_Bool tightened;
692  int i;
693 
694  assert(vars != NULL);
695 
696 #ifndef NDEBUG
697  /* find branching rule */
698  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
699  assert(branchrule != NULL);
700 
701  /* get branching rule data */
702  branchruledata = SCIPbranchruleGetData(branchrule);
703  assert(branchruledata != NULL);
704 #endif
705 
706  SCIPdebugMsg(scip, "applying %d bound changes\n", nbdchgs);
707 
708  for( i = 0; i < nbdchgs; ++i )
709  {
710  int v;
711 
712  v = bdchginds[i];
713 
714  SCIPdebugMsg(scip, " -> <%s> [%g,%g]\n",
715  SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v]));
716 
717  if( bdchgtypes[i] == SCIP_BOUNDTYPE_LOWER )
718  {
719  /* change lower bound of variable to given bound */
720  SCIP_CALL( SCIPtightenVarLb(scip, vars[v], bdchgbounds[i], TRUE, &infeasible, &tightened) );
721  if( infeasible )
722  {
723  *result = SCIP_CUTOFF;
724  return SCIP_OKAY;
725  }
726 
727  /* if we did propagation, the bound change might already have been added */
728  assert(tightened || (branchruledata->maxproprounds != 0));
729  }
730  else
731  {
732  assert(bdchgtypes[i] == SCIP_BOUNDTYPE_UPPER);
733 
734  /* change upper bound of variable to given bound */
735  SCIP_CALL( SCIPtightenVarUb(scip, vars[v], bdchgbounds[i], TRUE, &infeasible, &tightened) );
736  if( infeasible )
737  {
738  *result = SCIP_CUTOFF;
739  return SCIP_OKAY;
740  }
741 
742  /* if we did propagation, the bound change might already have been added */
743  assert(tightened || (branchruledata->maxproprounds != 0));
744  }
745  SCIPdebugMsg(scip, " -> [%g,%g]\n", SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v]));
746  }
747 
748  return SCIP_OKAY;
749 }
750 
751 /** execute reliability pseudo cost branching */
752 static
753 SCIP_RETCODE execRelpscost(
754  SCIP* scip, /**< SCIP data structure */
755  SCIP_BRANCHRULE* branchrule, /**< branching rule */
756  SCIP_VAR** branchcands, /**< branching candidates */
757  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
758  SCIP_Real* branchcandsfrac, /**< fractional part of the branching candidates */
759  int* branchorbitidx, /**< indices of orbit (or NULL) */
760  int nbranchcands, /**< number of branching candidates */
761  SCIP_Bool executebranch, /**< execute a branching step or run probing only */
762  SCIP_RESULT* result /**< pointer to the result of the execution */
763  )
764 { /*lint --e{715}*/
765  SCIP_BRANCHRULEDATA* branchruledata;
766  SCIP_Real lpobjval;
767  SCIP_Real bestsbdown;
768  SCIP_Real bestsbup;
769  SCIP_Real provedbound;
770  SCIP_Bool bestsbdownvalid;
771  SCIP_Bool bestsbupvalid;
772  SCIP_Bool bestsbdowncutoff;
773  SCIP_Bool bestsbupcutoff;
774  SCIP_Bool bestisstrongbranch;
775  SCIP_Bool allcolsinlp;
776  SCIP_Bool exactsolve;
777  int ninitcands;
778  int bestcand;
779 
780  /* remember which variables strong branching is performed on, and the
781  * recorded lp bound changes that are observed */
782  SCIP_Bool* sbvars = NULL;
783  SCIP_Real* sbdown = NULL;
784  SCIP_Real* sbup = NULL;
785  SCIP_Bool* sbdownvalid = NULL;
786  SCIP_Bool* sbupvalid = NULL;
787 
788  *result = SCIP_DIDNOTRUN;
789 
790  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
791 
792  /* get branching rule data */
793  branchruledata = SCIPbranchruleGetData(branchrule);
794  assert(branchruledata != NULL);
795 
796  /* get current LP objective bound of the local sub problem and global cutoff bound */
797  lpobjval = SCIPgetLPObjval(scip);
798 
799  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
800  * for cutting off sub problems and improving lower bounds of children
801  */
802  exactsolve = SCIPisExactSolve(scip);
803 
804  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
805  allcolsinlp = SCIPallColsInLP(scip);
806 
807  bestcand = -1;
808  bestisstrongbranch = FALSE;
809  bestsbdown = SCIP_INVALID;
810  bestsbup = SCIP_INVALID;
811  bestsbdownvalid = FALSE;
812  bestsbupvalid = FALSE;
813  bestsbdowncutoff = FALSE;
814  bestsbupcutoff = FALSE;
815  provedbound = lpobjval;
816 
817  /* Allocate memory to store the lp bounds of the up and down children
818  * for those of the variables that we performed sb on
819  */
820  SCIP_CALL( SCIPallocBufferArray(scip, &sbdown, nbranchcands) );
821  SCIP_CALL( SCIPallocBufferArray(scip, &sbup, nbranchcands) );
822  SCIP_CALL( SCIPallocBufferArray(scip, &sbdownvalid, nbranchcands) );
823  SCIP_CALL( SCIPallocBufferArray(scip, &sbupvalid, nbranchcands) );
824  SCIP_CALL( SCIPallocBufferArray(scip, &sbvars, nbranchcands) );
825 
826  if( nbranchcands == 1 )
827  {
828  /* only one candidate: nothing has to be done */
829  bestcand = 0;
830  SCIPdebug(ninitcands = 0);
831  sbvars[0] = FALSE;
832  }
833  else
834  {
835  SCIP_VAR** vars;
836  int* initcands;
837  SCIP_Real* initcandscores;
838  SCIP_Real* newlbs = NULL;
839  SCIP_Real* newubs = NULL;
840  SCIP_Real* mingains = NULL;
841  SCIP_Real* maxgains = NULL;
842  /* scores computed from pseudocost branching */
843  SCIP_Real* scores = NULL;
844  SCIP_Real* scoresfrompc = NULL;
845  SCIP_Real* scoresfromothers = NULL;
846  int* bdchginds;
847  SCIP_BOUNDTYPE* bdchgtypes;
848  SCIP_Real* bdchgbounds;
849  int maxninitcands;
850  int nuninitcands;
851  int nbdchgs;
852  int nbdconflicts;
853  SCIP_Real avgconflictscore;
854  SCIP_Real avgconflengthscore;
855  SCIP_Real avginferencescore;
856  SCIP_Real avgcutoffscore;
857  SCIP_Real avgpscostscore;
858  SCIP_Real bestpsscore;
859  SCIP_Real bestpsfracscore;
860  SCIP_Real bestpsdomainscore;
861  SCIP_Real bestsbscore;
862  SCIP_Real bestuninitsbscore;
863  SCIP_Real bestsbfracscore;
864  SCIP_Real bestsbdomainscore;
865  SCIP_Real prio;
866  SCIP_Real reliable;
867  SCIP_Real maxlookahead;
868  SCIP_Real lookahead;
869  SCIP_Real relerrorthreshold;
870  SCIP_Bool initstrongbranching;
871  SCIP_Bool propagate;
872  SCIP_Bool probingbounds;
873  SCIP_Longint nodenum;
874  SCIP_Longint nlpiterationsquot;
875  SCIP_Longint nsblpiterations;
876  SCIP_Longint maxnsblpiterations;
877  int bestsolidx;
878  int maxbdchgs;
879  int bestpscand;
880  int bestsbcand;
881  int bestuninitsbcand;
882  int inititer;
883  int nvars;
884  int i;
885  int c;
886  SCIP_CONFIDENCELEVEL clevel;
887  SCIP_Real degeneracyfactor = 1.0;
888 
889  /* get LP degeneracy information and compute a factor to change weighting of pseudo cost score vs. other scores */
890  if( branchruledata->degeneracyaware > 0 && (SCIPgetDepth(scip) > 0 || branchruledata->degeneracyaware > 1) )
891  {
892  SCIP_Real degeneracy;
893  SCIP_Real varconsratio;
894 
895  /* get LP degeneracy information */
896  SCIP_CALL( SCIPgetLPDegeneracy(scip, &degeneracy, &varconsratio) );
897 
898  assert(degeneracy >= 0.0);
899  assert(degeneracy <= 1.0);
900  assert(varconsratio >= 1.0);
901 
902  /* increase factor for a degeneracy >= 80% */
903  if( degeneracy >= 0.8 )
904  {
905  degeneracy = 10.0 * (degeneracy - 0.7);
906  degeneracyfactor = degeneracyfactor * pow(10.0,degeneracy);
907  }
908  /* increase factor for a variable-constraint ratio >= 2.0 */
909  if( varconsratio >= 2.0 )
910  {
911  degeneracyfactor *= 10.0 * varconsratio;
912  }
913  }
914 
915  vars = SCIPgetVars(scip);
916  nvars = SCIPgetNVars(scip);
917 
918  bestsolidx = SCIPgetBestSol(scip) == NULL ? -1 : SCIPsolGetIndex(SCIPgetBestSol(scip));
919 
920  /* get average conflict, inference, and pseudocost scores */
921  avgconflictscore = SCIPgetAvgConflictScore(scip);
922  avgconflictscore = MAX(avgconflictscore, 0.1);
923  avgconflengthscore = SCIPgetAvgConflictlengthScore(scip);
924  avgconflengthscore = MAX(avgconflengthscore, 0.1);
925  avginferencescore = SCIPgetAvgInferenceScore(scip);
926  avginferencescore = MAX(avginferencescore, 0.1);
927  avgcutoffscore = SCIPgetAvgCutoffScore(scip);
928  avgcutoffscore = MAX(avgcutoffscore, 0.1);
929  avgpscostscore = SCIPgetAvgPseudocostScore(scip);
930  avgpscostscore = MAX(avgpscostscore, 0.1);
931 
932  /* get nonlinear counts according to parameters */
933  SCIP_CALL( branchruledataEnsureNlcount(scip, branchruledata) );
934 
935  initstrongbranching = FALSE;
936 
937  /* check whether propagation should be performed */
938  propagate = (branchruledata->maxproprounds != 0);
939 
940  /* check whether valid bounds should be identified in probing-like fashion */
941  probingbounds = propagate && branchruledata->probingbounds;
942 
943  /* get maximal number of candidates to initialize with strong branching; if the current solutions is not basic,
944  * we cannot warmstart the simplex algorithm and therefore don't initialize any candidates
945  */
946  maxninitcands = MIN(nbranchcands, branchruledata->initcand);
947  if( !SCIPisLPSolBasic(scip) )
948  maxninitcands = 0;
949 
950  /* calculate maximal number of strong branching LP iterations; if we used too many, don't apply strong branching
951  * any more; also, if degeneracy is too high, don't run strong branching at this node
952  */
953  nlpiterationsquot = (SCIP_Longint)(branchruledata->sbiterquot * SCIPgetNNodeLPIterations(scip));
954  maxnsblpiterations = nlpiterationsquot + branchruledata->sbiterofs + SCIPgetNRootStrongbranchLPIterations(scip);
955  nsblpiterations = SCIPgetNStrongbranchLPIterations(scip);
956  if( nsblpiterations > maxnsblpiterations || degeneracyfactor >= 10.0 )
957  maxninitcands = 0;
958 
959  /* get buffer for storing the unreliable candidates */
960  SCIP_CALL( SCIPallocBufferArray(scip, &initcands, maxninitcands+1) ); /* allocate one additional slot for convenience */
961  SCIP_CALL( SCIPallocBufferArray(scip, &initcandscores, maxninitcands+1) );
962  ninitcands = 0;
963 
964  /* Allocate memory for the down and up gains, and the computed pseudocost scores */
965  SCIP_CALL( SCIPallocBufferArray(scip, &mingains, nbranchcands) );
966  SCIP_CALL( SCIPallocBufferArray(scip, &maxgains, nbranchcands) );
967  SCIP_CALL( SCIPallocBufferArray(scip, &scores, nbranchcands) );
968  SCIP_CALL( SCIPallocBufferArray(scip, &scoresfrompc, nbranchcands) );
969  SCIP_CALL( SCIPallocBufferArray(scip, &scoresfromothers, nbranchcands) );
970 
971  /* get current node number */
972  nodenum = SCIPgetNNodes(scip);
973 
974  /* initialize bound change arrays */
975  bdchginds = NULL;
976  bdchgtypes = NULL;
977  bdchgbounds = NULL;
978  nbdchgs = 0;
979  nbdconflicts = 0;
980  maxbdchgs = branchruledata->maxbdchgs;
981  if( maxbdchgs == -1 )
982  maxbdchgs = INT_MAX;
983 
984  /* calculate value used as reliability */
985  prio = (maxnsblpiterations - nsblpiterations)/(nsblpiterations + 1.0);
986  prio = MIN(prio, 1.0);
987  prio = MAX(prio, (nlpiterationsquot - nsblpiterations)/(nsblpiterations + 1.0));
988  reliable = (1.0-prio) * branchruledata->minreliable + prio * branchruledata->maxreliable;
989 
990  /* calculate the threshold for the relative error in the same way; low tolerance is more strict than higher tolerance */
991  relerrorthreshold = (1.0 - prio) * branchruledata->higherrortol + prio * branchruledata->lowerrortol;
992 
993  clevel = (SCIP_CONFIDENCELEVEL)branchruledata->confidencelevel;
994  /* determine the confidence level for hypothesis testing based on value of prio */
995  if( branchruledata->usedynamicconfidence )
996  {
997  /* with decreasing priority, use a less strict confidence level */
998  if( prio >= 0.9 )
999  clevel = SCIP_CONFIDENCELEVEL_MAX;
1000  else if( prio >= 0.7 )
1001  clevel = SCIP_CONFIDENCELEVEL_HIGH;
1002  else if( prio >= 0.5 )
1003  clevel = SCIP_CONFIDENCELEVEL_MEDIUM;
1004  else if( prio >= 0.3 )
1005  clevel = SCIP_CONFIDENCELEVEL_LOW;
1006  else
1007  clevel = SCIP_CONFIDENCELEVEL_MIN;
1008  }
1009 
1010  /* search for the best pseudo cost candidate, while remembering unreliable candidates in a sorted buffer */
1011  nuninitcands = 0;
1012  bestpscand = -1;
1013  bestpsscore = -SCIPinfinity(scip);
1014  bestpsfracscore = -SCIPinfinity(scip);
1015  bestpsdomainscore = -SCIPinfinity(scip);
1016 
1017  /* search for the best candidate first */
1018  if( branchruledata->usehyptestforreliability )
1019  {
1020  for( c = 0; c < nbranchcands; ++c )
1021  {
1022  SCIP_Real conflictscore;
1023  SCIP_Real conflengthscore;
1024  SCIP_Real inferencescore;
1025  SCIP_Real cutoffscore;
1026  SCIP_Real pscostscore;
1027  SCIP_Real nlscore;
1028  SCIP_Real score;
1029 
1030  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
1031  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
1032  inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
1033  cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
1034  nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
1035  pscostscore = SCIPgetVarPseudocostScore(scip, branchcands[c], branchcandssol[c]);
1036 
1037  /* replace the pseudo cost score with the already calculated one;
1038  * @todo: use old data for strong branching with propagation?
1039  */
1040  if( SCIPgetVarStrongbranchNode(scip, branchcands[c]) == nodenum )
1041  {
1042  SCIP_Real down;
1043  SCIP_Real up;
1044  SCIP_Real lastlpobjval;
1045  SCIP_Real downgain;
1046  SCIP_Real upgain;
1047 
1048  /* use the score of the strong branching call at the current node */
1049  SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
1050  downgain = MAX(down - lastlpobjval, 0.0);
1051  upgain = MAX(up - lastlpobjval, 0.0);
1052  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
1053 
1054  SCIPdebugMsg(scip, " -> strong branching on variable <%s> already performed (down=%g (%+g), up=%g (%+g), pscostscore=%g)\n",
1055  SCIPvarGetName(branchcands[c]), down, downgain, up, upgain, pscostscore);
1056  }
1057 
1058  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1059  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, nlscore, branchcandsfrac[c],
1060  degeneracyfactor);
1061 
1062  /* check for better score of candidate */
1063  if( SCIPisSumGE(scip, score, bestpsscore) )
1064  {
1065  SCIP_Real fracscore;
1066  SCIP_Real domainscore;
1067 
1068  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
1069  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
1070  if( SCIPisSumGT(scip, score, bestpsscore)
1071  || SCIPisSumGT(scip, fracscore, bestpsfracscore)
1072  || (SCIPisSumGE(scip, fracscore, bestpsfracscore) && domainscore > bestpsdomainscore) )
1073  {
1074  bestpscand = c;
1075  bestpsscore = score;
1076  bestpsfracscore = fracscore;
1077  bestpsdomainscore = domainscore;
1078  }
1079  }
1080  }
1081  }
1082 
1083  for( c = 0; c < nbranchcands; ++c )
1084  {
1085  SCIP_Real conflictscore;
1086  SCIP_Real conflengthscore;
1087  SCIP_Real inferencescore;
1088  SCIP_Real cutoffscore;
1089  SCIP_Real pscostscore;
1090  SCIP_Real nlscore;
1091  SCIP_Real score;
1092  SCIP_Bool usesb;
1093  SCIP_Real downgain;
1094  SCIP_Real upgain;
1095  SCIP_Real fracpart;
1096 
1097  assert(branchcands[c] != NULL);
1098  assert(!SCIPisFeasIntegral(scip, branchcandssol[c]));
1099  assert(!SCIPisFeasIntegral(scip, SCIPvarGetLPSol(branchcands[c])));
1100 
1101  /* Record the variables current pseudocosts. These may be overwritten if
1102  * strong branching is performed.
1103  */
1104  sbvars[c] = FALSE;
1105  fracpart = SCIPfeasFrac(scip, SCIPvarGetLPSol(branchcands[c]));
1106  downgain = SCIPgetVarPseudocostVal(scip, branchcands[c], 0.0 - fracpart);
1107  upgain = SCIPgetVarPseudocostVal(scip, branchcands[c], 1.0 - fracpart);
1108  mingains[c] = MIN(downgain, upgain);
1109  maxgains[c] = MAX(downgain, upgain);
1110 
1111  /* get conflict, inference, cutoff, nonlinear, and pseudo cost scores for candidate */
1112  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
1113  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
1114  inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
1115  cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
1116  nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
1117  pscostscore = SCIPgetVarPseudocostScore(scip, branchcands[c], branchcandssol[c]);
1118  usesb = FALSE;
1119 
1120  /* don't use strong branching on variables that have already been initialized at the current node;
1121  * instead replace the pseudo cost score with the already calculated one;
1122  * @todo: use old data for strong branching with propagation?
1123  */
1124  if( SCIPgetVarStrongbranchNode(scip, branchcands[c]) == nodenum )
1125  {
1126  SCIP_Real down;
1127  SCIP_Real up;
1128  SCIP_Real lastlpobjval;
1129 
1130  /* use the score of the strong branching call at the current node */
1131  SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
1132  downgain = MAX(down - lastlpobjval, 0.0);
1133  upgain = MAX(up - lastlpobjval, 0.0);
1134  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
1135 
1136  mingains[c] = MIN(downgain, upgain);
1137  maxgains[c] = MAX(downgain, upgain);
1138 
1139  SCIPdebugMsg(scip, " -> strong branching on variable <%s> already performed (down=%g (%+g), up=%g (%+g), pscostscore=%g)\n",
1140  SCIPvarGetName(branchcands[c]), down, downgain, up, upgain, pscostscore);
1141  }
1142  else if( maxninitcands > 0 )
1143  {
1144  SCIP_Real downsize;
1145  SCIP_Real upsize;
1146  SCIP_Real size;
1147 
1148  /* check, if the pseudo cost score of the variable is reliable */
1149  downsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_DOWNWARDS);
1150  upsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_UPWARDS);
1151  size = MIN(downsize, upsize);
1152 
1153  /* determine if variable is considered reliable based on the current reliability setting */
1154  /* check fixed number threshold (aka original) reliability first */
1155  assert(!branchruledata->usehyptestforreliability || bestpscand >= 0);
1156  usesb = FALSE;
1157  if( size < reliable )
1158  usesb = TRUE;
1159  else if( branchruledata->userelerrorforreliability && branchruledata->usehyptestforreliability )
1160  {
1161  if( !SCIPisVarPscostRelerrorReliable(scip, branchcands[c], relerrorthreshold, clevel) &&
1162  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
1163  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE) &&
1164  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1 - branchcandsfrac[bestpscand],
1165  branchcands[c], 1 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
1166  usesb = TRUE;
1167  }
1168  /* check if relative error is tolerable */
1169  else if( branchruledata->userelerrorforreliability &&
1170  !SCIPisVarPscostRelerrorReliable(scip, branchcands[c], relerrorthreshold, clevel))
1171  usesb = TRUE;
1172  /* check if best pseudo-candidate is significantly better in both directions, use strong-branching otherwise */
1173  else if( branchruledata->usehyptestforreliability &&
1174  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
1175  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE) &&
1176  !SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1 - branchcandsfrac[bestpscand],
1177  branchcands[c], 1 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE))
1178  usesb = TRUE;
1179 
1180  /* count the number of variables that are completely uninitialized */
1181  if( size < 0.1 )
1182  nuninitcands++;
1183  }
1184 
1185  /* combine the five score values */
1186  scoresfrompc[c] = calcScore(scip, branchruledata, 0.0, avgconflictscore, 0.0, avgconflengthscore,
1187  0.0, avginferencescore, 0.0, avgcutoffscore, pscostscore, avgpscostscore, 0.0, branchcandsfrac[c], degeneracyfactor);
1188  scoresfromothers[c] = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1189  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, 0.0, avgpscostscore, nlscore, branchcandsfrac[c], degeneracyfactor);
1190  score = scoresfrompc[c] + scoresfromothers[c];
1191  scores[c] = score;
1192  /*score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1193  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, nlscore, branchcandsfrac[c],
1194  degeneracyfactor);*/
1195  if( usesb )
1196  {
1197  int j;
1198 
1199  mingains[c] = 0;
1200  maxgains[c] = 0;
1201  scoresfrompc[c] = 0;
1202  scoresfromothers[c] = 0;
1203 
1204  /* assign a random score to this uninitialized candidate */
1205  if( branchruledata->randinitorder )
1206  score += SCIPrandomGetReal(branchruledata->randnumgen, 0.0, 1e-4);
1207 
1208  /* pseudo cost of variable is not reliable: insert candidate in initcands buffer */
1209  for( j = ninitcands; j > 0 && score > initcandscores[j-1]; --j )
1210  {
1211  initcands[j] = initcands[j-1];
1212  initcandscores[j] = initcandscores[j-1];
1213  }
1214  initcands[j] = c;
1215  initcandscores[j] = score;
1216  ninitcands++;
1217  ninitcands = MIN(ninitcands, maxninitcands);
1218  }
1219  /* in the case of hypothesis reliability, the best pseudo candidate has been determined already */
1220  else if( !branchruledata->usehyptestforreliability )
1221  {
1222  /* variable will keep its pseudo cost value: check for better score of candidate */
1223  if( SCIPisSumGE(scip, score, bestpsscore) )
1224  {
1225  SCIP_Real fracscore;
1226  SCIP_Real domainscore;
1227 
1228  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
1229  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
1230  if( SCIPisSumGT(scip, score, bestpsscore)
1231  || SCIPisSumGT(scip, fracscore, bestpsfracscore)
1232  || (SCIPisSumGE(scip, fracscore, bestpsfracscore) && domainscore > bestpsdomainscore) )
1233  {
1234  bestpscand = c;
1235  bestpsscore = score;
1236  bestpsfracscore = fracscore;
1237  bestpsdomainscore = domainscore;
1238  }
1239  }
1240  }
1241  }
1242 
1243  /* in the special case that only the best pseudo candidate was selected for strong branching, skip the strong branching */
1244  if( branchruledata->usehyptestforreliability && ninitcands == 1 )
1245  {
1246  ninitcands = 0;
1247  SCIPdebugMsg(scip, "Only one single candidate for initialization-->Skipping strong branching\n");
1248  }
1249 
1250  /* initialize unreliable candidates with strong branching until maxlookahead is reached,
1251  * search best strong branching candidate
1252  */
1253  maxlookahead = (SCIP_Real)branchruledata->maxlookahead * (1.0 + (SCIP_Real)nuninitcands/(SCIP_Real)nbranchcands);
1254  inititer = branchruledata->inititer;
1255  if( inititer == 0 )
1256  {
1257  SCIP_Longint nlpiterations;
1258  SCIP_Longint nlps;
1259 
1260  /* iteration limit is set to twice the average number of iterations spent to resolve a dual feasible SCIP_LP;
1261  * at the first few nodes, this average is not very exact, so we better increase the iteration limit on
1262  * these very important nodes
1263  */
1264  nlpiterations = SCIPgetNDualResolveLPIterations(scip);
1265  nlps = SCIPgetNDualResolveLPs(scip);
1266  if( nlps == 0 )
1267  {
1268  nlpiterations = SCIPgetNNodeInitLPIterations(scip);
1269  nlps = SCIPgetNNodeInitLPs(scip);
1270  if( nlps == 0 )
1271  {
1272  nlpiterations = 1000;
1273  nlps = 1;
1274  }
1275  }
1276  assert(nlps >= 1);
1277  inititer = (int)(2*nlpiterations / nlps);
1278  inititer = (int)((SCIP_Real)inititer * (1.0 + 20.0/nodenum));
1279  inititer = MAX(inititer, 10);
1280  inititer = MIN(inititer, 500);
1281  }
1282 
1283  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",
1284  reliable, ninitcands, nbranchcands, nuninitcands, maxninitcands, maxlookahead, maxbdchgs, inititer,
1285  SCIPgetNStrongbranchLPIterations(scip), maxnsblpiterations, SCIPisLPSolBasic(scip));
1286 
1287  bestsbcand = -1;
1288  bestsbscore = -SCIPinfinity(scip);
1289  bestsbfracscore = -SCIPinfinity(scip);
1290  bestsbdomainscore = -SCIPinfinity(scip);
1291  bestuninitsbscore = -SCIPinfinity(scip);
1292  bestuninitsbcand = -1;
1293  lookahead = 0.0;
1294  for( i = 0; i < ninitcands && lookahead < maxlookahead && nbdchgs + nbdconflicts < maxbdchgs
1295  && (i < (int) maxlookahead || SCIPgetNStrongbranchLPIterations(scip) < maxnsblpiterations); ++i )
1296  {
1297  SCIP_Real down;
1298  SCIP_Real up;
1299  SCIP_Real downgain;
1300  SCIP_Real upgain;
1301  SCIP_Bool downvalid;
1302  SCIP_Bool upvalid;
1303  SCIP_Longint ndomredsdown;
1304  SCIP_Longint ndomredsup;
1305  SCIP_Bool lperror;
1306  SCIP_Bool downinf;
1307  SCIP_Bool upinf;
1308  SCIP_Bool downconflict;
1309  SCIP_Bool upconflict;
1310 
1311  /* get candidate number to initialize */
1312  c = initcands[i];
1313  assert(!SCIPisFeasIntegral(scip, branchcandssol[c]));
1314 
1315  if( branchruledata->skipbadinitcands )
1316  {
1317  SCIP_Bool skipsb = FALSE;
1318  /* if the current best candidate is a candidate found by strong branching, determine if candidate pseudo-costs are
1319  * significantly smaller in at least one direction, in which case we safe the execution of strong-branching for now
1320  */
1321  if( bestsbscore > bestpsscore && bestsbscore > bestuninitsbscore && bestsbupvalid && bestsbdownvalid )
1322  {
1323  assert(bestsbcand != -1);
1324  assert(bestsbup != SCIP_INVALID && bestsbdown != SCIP_INVALID); /*lint !e777 lint doesn't like comparing floats */
1325 
1326  /* test if the variable is unlikely to produce a better gain than the currently best one. Skip strong-branching
1327  * in such a case
1328  */
1329  if( SCIPpscostThresholdProbabilityTest(scip, branchcands[c], branchcandsfrac[c], bestsbdown,
1330  SCIP_BRANCHDIR_DOWNWARDS, clevel)
1331  || SCIPpscostThresholdProbabilityTest(scip, branchcands[c], 1.0 - branchcandsfrac[c], bestsbup,
1332  SCIP_BRANCHDIR_UPWARDS, clevel) )
1333  skipsb = TRUE;
1334  }
1335  /* the currently best candidate is also a pseudo-candidate; apply significance test and skip candidate if it
1336  * is significantly worse in at least one direction
1337  */
1338  else if( bestpscand != -1 && bestpsscore > bestuninitsbscore )
1339  {
1340  if( SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], branchcandsfrac[bestpscand],
1341  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE)
1342  || SCIPsignificantVarPscostDifference(scip, branchcands[bestpscand], 1.0 - branchcandsfrac[bestpscand],
1343  branchcands[c], 1.0 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
1344  skipsb = TRUE;
1345  }
1346  /* compare against the best init cand that has been skipped already */
1347  else if( bestuninitsbcand != -1 )
1348  {
1349  if( SCIPsignificantVarPscostDifference(scip, branchcands[bestuninitsbcand], branchcandsfrac[bestuninitsbcand],
1350  branchcands[c], branchcandsfrac[c], SCIP_BRANCHDIR_DOWNWARDS, clevel, TRUE)
1351  || SCIPsignificantVarPscostDifference(scip, branchcands[bestuninitsbcand], 1.0 - branchcandsfrac[bestuninitsbcand],
1352  branchcands[c], 1.0 - branchcandsfrac[c], SCIP_BRANCHDIR_UPWARDS, clevel, TRUE) )
1353  skipsb = TRUE;
1354  }
1355 
1356  /* skip candidate, update the best score of an unitialized candidate */
1357  if( skipsb )
1358  {
1359  if( bestuninitsbcand == -1 )
1360  {
1361  bestuninitsbcand = c;
1362  bestuninitsbscore = initcandscores[i];
1363  }
1364  continue;
1365  }
1366  }
1367  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",
1368  SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_DOWNWARDS),
1369  SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_UPWARDS),
1370  SCIPvarGetName(branchcands[c]), branchcandssol[c], initcandscores[i],
1371  inititer, SCIPgetNStrongbranchLPIterations(scip), maxnsblpiterations);
1372 
1373  /* use strong branching on candidate */
1374  if( !initstrongbranching )
1375  {
1376  initstrongbranching = TRUE;
1377 
1378  SCIP_CALL( SCIPstartStrongbranch(scip, propagate) );
1379 
1380  /* create arrays for probing-like bound tightening */
1381  if( probingbounds )
1382  {
1383  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newlbs, nvars) );
1384  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &newubs, nvars) );
1385  }
1386  }
1387 
1388  if( propagate )
1389  {
1390  /* apply strong branching */
1391  SCIP_CALL( SCIPgetVarStrongbranchWithPropagation(scip, branchcands[c], branchcandssol[c], lpobjval, inititer,
1392  branchruledata->maxproprounds, &down, &up, &downvalid, &upvalid, &ndomredsdown, &ndomredsup, &downinf, &upinf,
1393  &downconflict, &upconflict, &lperror, newlbs, newubs) );
1394  }
1395  else
1396  {
1397  /* apply strong branching */
1398  SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, branchcands[c], inititer, FALSE,
1399  &down, &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
1400 
1401  ndomredsdown = ndomredsup = 0;
1402  }
1403 
1404  /* check for an error in strong branching */
1405  if( lperror )
1406  {
1407  if( !SCIPisStopped(scip) )
1408  {
1409  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1410  "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call for variable <%s> with solution %g\n",
1411  SCIPgetNNodes(scip), SCIPvarGetName(branchcands[c]), branchcandssol[c]);
1412  }
1413  break;
1414  }
1415 
1416  /* Strong branching might have found a new primal solution which updated the cutoff bound. In this case, the
1417  * provedbound computed before can be higher than the cutoffbound and the current node can be cut off.
1418  * Additionally, also if the value for the current best candidate is valid and exceeds the new cutoff bound,
1419  * we want to change the domain of this variable rather than branching on it.
1420  */
1421  if( SCIPgetBestSol(scip) != NULL && SCIPsolGetIndex(SCIPgetBestSol(scip)) != bestsolidx )
1422  {
1423  bestsolidx = SCIPsolGetIndex(SCIPgetBestSol(scip));
1424 
1425  SCIPdebugMsg(scip, " -> strong branching on variable <%s> lead to a new incumbent\n",
1426  SCIPvarGetName(branchcands[c]));
1427 
1428  /* proved bound for current node is larger than new cutoff bound -> cut off current node */
1429  if( SCIPisGE(scip, provedbound, SCIPgetCutoffbound(scip)) )
1430  {
1431  SCIPdebugMsg(scip, " -> node can be cut off (provedbound=%g, cutoff=%g)\n", provedbound, SCIPgetCutoffbound(scip));
1432 
1433  *result = SCIP_CUTOFF;
1434  break; /* terminate initialization loop, because node is infeasible */
1435  }
1436  /* proved bound for down child of best candidate is larger than cutoff bound
1437  * -> increase lower bound of best candidate
1438  * we must only do this if the LP is complete, i.e., we are not doing column generation
1439  */
1440 
1441  else if( bestsbcand != -1 && allcolsinlp )
1442  {
1443  if( !bestsbdowncutoff && bestsbdownvalid && SCIPisGE(scip, bestsbdown, SCIPgetCutoffbound(scip)) )
1444  {
1445  bestsbdowncutoff = TRUE;
1446 
1447  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",
1448  SCIPvarGetName(branchcands[bestsbcand]), bestsbdownvalid, bestsbdown, SCIPgetCutoffbound(scip));
1449 
1450  SCIPdebugMsg(scip, " -> increase lower bound of best candidate <%s> to %g\n",
1451  SCIPvarGetName(branchcands[bestsbcand]), SCIPfeasCeil(scip, branchcandssol[bestsbcand]));
1452 
1453  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[bestsbcand]),
1454  SCIP_BOUNDTYPE_LOWER, SCIPfeasCeil(scip, branchcandssol[bestsbcand])) );
1455  }
1456  /* proved bound for up child of best candidate is larger than cutoff bound -> decrease upper bound of best candidate */
1457  else if( !bestsbupcutoff && bestsbupvalid && SCIPisGE(scip, bestsbup, SCIPgetCutoffbound(scip)) )
1458  {
1459  bestsbupcutoff = TRUE;
1460 
1461  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",
1462  SCIPvarGetName(branchcands[bestsbcand]), bestsbupvalid, bestsbup, SCIPgetCutoffbound(scip));
1463 
1464  SCIPdebugMsg(scip, " -> decrease upper bound of best candidate <%s> to %g\n",
1465  SCIPvarGetName(branchcands[bestsbcand]), SCIPfeasFloor(scip, branchcandssol[bestsbcand]));
1466 
1467  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[bestsbcand]),
1468  SCIP_BOUNDTYPE_UPPER, SCIPfeasFloor(scip, branchcandssol[bestsbcand])) );
1469  }
1470  }
1471  }
1472 
1473  /* evaluate strong branching */
1474  down = MAX(down, lpobjval);
1475  up = MAX(up, lpobjval);
1476  downgain = down - lpobjval;
1477  upgain = up - lpobjval;
1478  assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
1479  assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
1480  assert(downinf || !downconflict);
1481  assert(upinf || !upconflict);
1482 
1483  /* @todo: store pseudo cost only for valid bounds?
1484  * depending on the user parameter choice of storesemiinitcosts, pseudo costs are also updated in single directions,
1485  * if the node in the other direction was infeasible or cut off
1486  */
1487  if( !downinf
1488 #ifdef WITH_LPSOLSTAT
1489  && SCIPgetLastStrongbranchLPSolStat(scip, SCIP_BRANCHDIR_DOWNWARDS) != SCIP_LPSOLSTAT_ITERLIMIT
1490 #endif
1491  && (!upinf || branchruledata->storesemiinitcosts) )
1492  {
1493  SCIP_Real weight;
1494 
1495  /* smaller weights are given if the strong branching hit the time limit in the corresponding direction */
1496  if( branchruledata->usesmallweightsitlim )
1497  weight = SCIPgetLastStrongbranchLPSolStat(scip, SCIP_BRANCHDIR_DOWNWARDS) != SCIP_LPSOLSTAT_ITERLIMIT ? 1.0 : 0.5;
1498  else
1499  weight = 1.0;
1500 
1501  /* update pseudo cost values */
1502  SCIP_CALL( SCIPupdateVarPseudocostSymmetric(scip, branchruledata, branchcands[c], branchorbitidx, c, 0.0 - branchcandsfrac[c], downgain, weight) );
1503  }
1504  if( !upinf
1505 #ifdef WITH_LPSOLSTAT
1506  && SCIPgetLastStrongbranchLPSolStat(scip, SCIP_BRANCHDIR_UPWARDS) != SCIP_LPSOLSTAT_ITERLIMIT
1507 #endif
1508  && (!downinf || branchruledata->storesemiinitcosts) )
1509  {
1510  SCIP_Real weight;
1511 
1512  /* smaller weights are given if the strong branching hit the time limit in the corresponding direction */
1513  if( branchruledata->usesmallweightsitlim )
1514  weight = SCIPgetLastStrongbranchLPSolStat(scip, SCIP_BRANCHDIR_UPWARDS) != SCIP_LPSOLSTAT_ITERLIMIT ? 1.0 : 0.5;
1515  else
1516  weight = 1.0;
1517 
1518  /* update pseudo cost values */
1519  SCIP_CALL( SCIPupdateVarPseudocostSymmetric(scip, branchruledata, branchcands[c], branchorbitidx, c, 1.0 - branchcandsfrac[c], upgain, weight) );
1520  }
1521 
1522  /* the minimal lower bound of both children is a proved lower bound of the current subtree */
1523  if( allcolsinlp && !exactsolve && downvalid && upvalid )
1524  {
1525  SCIP_Real minbound;
1526 
1527  minbound = MIN(down, up);
1528  provedbound = MAX(provedbound, minbound);
1529  assert((downinf && upinf) || SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1530 
1531  /* save probing-like bounds detected during strong branching */
1532  if( probingbounds )
1533  {
1534  int v;
1535 
1536  assert(newlbs != NULL);
1537  assert(newubs != NULL);
1538 
1539  for( v = 0; v < nvars; ++v )
1540  {
1541  if( SCIPisGT(scip, newlbs[v], SCIPvarGetLbLocal(vars[v])) )
1542  {
1543  SCIPdebugMsg(scip, "better lower bound for variable <%s>: %.9g -> %.9g (by strongbranching on <%s>)\n",
1544  SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), newlbs[v], SCIPvarGetName(branchcands[c]));
1545 
1546  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, v,
1547  SCIP_BOUNDTYPE_LOWER, newlbs[v]) );
1548  }
1549  if( SCIPisLT(scip, newubs[v], SCIPvarGetUbLocal(vars[v])) )
1550  {
1551  SCIPdebugMsg(scip, "better upper bound for variable <%s>: %.9g -> %.9g (by strongbranching on <%s>)\n",
1552  SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), newubs[v], SCIPvarGetName(branchcands[c]));
1553 
1554  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, v,
1555  SCIP_BOUNDTYPE_UPPER, newubs[v]) );
1556  }
1557  }
1558  }
1559  }
1560 
1561  /* check if there are infeasible roundings */
1562  if( downinf || upinf )
1563  {
1564  assert(allcolsinlp || propagate);
1565  assert(!exactsolve);
1566 
1567  if( downinf && upinf )
1568  {
1569  /* both roundings are infeasible -> node is infeasible */
1570  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions (conflict: %u/%u)\n",
1571  SCIPvarGetName(branchcands[c]), downconflict, upconflict);
1572  *result = SCIP_CUTOFF;
1573  break; /* terminate initialization loop, because node is infeasible */
1574  }
1575  else
1576  {
1577  /* rounding is infeasible in one direction -> round variable in other direction */
1578  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in %s branch (conflict: %u/%u)\n",
1579  SCIPvarGetName(branchcands[c]), downinf ? "downward" : "upward", downconflict, upconflict);
1580  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[c]),
1581  (downinf ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER),
1582  (downinf ? SCIPfeasCeil(scip, branchcandssol[c]) : SCIPfeasFloor(scip, branchcandssol[c]))) );
1583  if( nbdchgs + nbdconflicts >= maxbdchgs )
1584  break; /* terminate initialization loop, because enough roundings are performed */
1585  }
1586  }
1587  else
1588  {
1589  SCIP_Real conflictscore;
1590  SCIP_Real conflengthscore;
1591  SCIP_Real inferencescore;
1592  SCIP_Real cutoffscore;
1593  SCIP_Real pscostscore;
1594  SCIP_Real nlscore;
1595  SCIP_Real score;
1596 
1597  mingains[c] = MIN(downgain, upgain);
1598  maxgains[c] = MAX(downgain, upgain);
1599 
1600  sbdown[c] = down;
1601  sbup[c] = up;
1602  sbdownvalid[c] = downvalid;
1603  sbupvalid[c] = upvalid;
1604  sbvars[c] = TRUE;
1605 
1606  /* check for a better score */
1607  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
1608  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
1609  nlscore = calcNlscore(scip, branchruledata->nlcount, branchruledata->nlcountmax, SCIPvarGetProbindex(branchcands[c]));
1610 
1611  /* optionally, use only local information obtained via strong branching for this candidate, i.e., local
1612  * domain reductions and no cutoff score
1613  */
1614  inferencescore = branchruledata->usesblocalinfo ? SCIPgetBranchScore(scip, branchcands[c], (SCIP_Real)ndomredsdown, (SCIP_Real)ndomredsup)
1615  : SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
1616  cutoffscore = branchruledata->usesblocalinfo ? 0.0 : SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
1617  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
1618 
1619  scoresfrompc[c] = calcScore(scip, branchruledata, 0.0, avgconflictscore, 0.0, avgconflengthscore,
1620  0.0, avginferencescore, 0.0, avgcutoffscore, pscostscore, avgpscostscore, 0.0, branchcandsfrac[c], degeneracyfactor);
1621  scoresfromothers[c] = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1622  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, 0.0, avgpscostscore, nlscore, branchcandsfrac[c], degeneracyfactor);
1623  score = scoresfrompc[c] + scoresfromothers[c];
1624  scores[c] = score;
1625  /*score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
1626  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, nlscore, branchcandsfrac[c],
1627  degeneracyfactor);*/
1628 
1629  if( SCIPisSumGE(scip, score, bestsbscore) )
1630  {
1631  SCIP_Real fracscore;
1632  SCIP_Real domainscore;
1633 
1634  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
1635  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
1636  if( SCIPisSumGT(scip, score, bestsbscore)
1637  || SCIPisSumGT(scip, fracscore, bestsbfracscore)
1638  || (SCIPisSumGE(scip, fracscore, bestsbfracscore) && domainscore > bestsbdomainscore) )
1639  {
1640  bestsbcand = c;
1641  bestsbscore = score;
1642  bestsbdown = down;
1643  bestsbup = up;
1644  bestsbdownvalid = downvalid;
1645  bestsbupvalid = upvalid;
1646  bestsbdowncutoff = FALSE;
1647  bestsbupcutoff = FALSE;
1648  bestsbfracscore = fracscore;
1649  bestsbdomainscore = domainscore;
1650  lookahead = 0.0;
1651  }
1652  else
1653  lookahead += 0.5;
1654  }
1655  else
1656  lookahead += 1.0;
1657 
1658  SCIPdebugMsg(scip, " -> variable <%s> (solval=%g, down=%g (%+g,valid=%u), up=%g (%+g,valid=%u), score=%g/ %g/%g %g/%g -> %g)\n",
1659  SCIPvarGetName(branchcands[c]), branchcandssol[c], down, downgain, downvalid, up, upgain, upvalid,
1660  pscostscore, conflictscore, conflengthscore, inferencescore, cutoffscore, score);
1661  }
1662  }
1663 #ifdef SCIP_DEBUG
1664  if( bestsbcand >= 0 )
1665  {
1666  SCIPdebugMsg(scip, " -> best: <%s> (%g / %g / %g), lookahead=%g/%g\n",
1667  SCIPvarGetName(branchcands[bestsbcand]), bestsbscore, bestsbfracscore, bestsbdomainscore,
1668  lookahead, maxlookahead);
1669  }
1670 #endif
1671 
1672  if( initstrongbranching )
1673  {
1674  if( probingbounds )
1675  {
1676  assert(newlbs != NULL);
1677  assert(newubs != NULL);
1678 
1679  SCIPfreeBlockMemoryArray(scip, &newubs, nvars);
1680  SCIPfreeBlockMemoryArray(scip, &newlbs, nvars);
1681  }
1682 
1683  SCIP_CALL( SCIPendStrongbranch(scip) );
1684 
1685  if( SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OBJLIMIT || SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_INFEASIBLE )
1686  {
1687  assert(SCIPhasCurrentNodeLP(scip));
1688  *result = SCIP_CUTOFF;
1689  }
1690  }
1691 
1692  if( *result != SCIP_CUTOFF )
1693  {
1694  /* get the score of the best uninitialized strong branching candidate */
1695  if( i < ninitcands && bestuninitsbcand == -1 )
1696  bestuninitsbscore = initcandscores[i];
1697 
1698  /* if the best pseudo cost candidate is better than the best uninitialized strong branching candidate,
1699  * compare it to the best initialized strong branching candidate
1700  */
1701  if( bestpsscore > bestuninitsbscore && SCIPisSumGT(scip, bestpsscore, bestsbscore) )
1702  {
1703  bestcand = bestpscand;
1704  bestisstrongbranch = FALSE;
1705  }
1706  else if( bestsbcand >= 0 )
1707  {
1708  bestcand = bestsbcand;
1709  bestisstrongbranch = TRUE;
1710  }
1711  else
1712  {
1713  /* no candidate was initialized, and the best score is the one of the first candidate in the initialization
1714  * queue
1715  */
1716  assert(ninitcands >= 1);
1717  bestcand = initcands[0];
1718  bestisstrongbranch = FALSE;
1719  }
1720 
1721  /* update lower bound of current node */
1722  if( allcolsinlp && !exactsolve )
1723  {
1724  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1725  SCIP_CALL( SCIPupdateNodeLowerbound(scip, SCIPgetCurrentNode(scip), provedbound) );
1726  }
1727  }
1728 
1729  /* apply domain reductions */
1730  if( nbdchgs > 0 )
1731  {
1732  if( *result != SCIP_CUTOFF )
1733  {
1734  SCIP_CALL( applyBdchgs(scip, vars, bdchginds, bdchgtypes, bdchgbounds, nbdchgs, result) );
1735  if( *result != SCIP_CUTOFF )
1736  *result = SCIP_REDUCEDDOM;
1737  }
1738  freeBdchgs(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs);
1739  }
1740 
1741  /* Apply the Treemodel branching rule to potentially select a better branching candidate than the current one. */
1742  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED && SCIPtreemodelIsEnabled(scip, branchruledata->treemodel) )
1743  {
1744  SCIP_Real smallpscost;
1745  SCIP_Bool usetreemodel;
1746 
1747  usetreemodel = TRUE;
1748 
1749  /* If the pseudocosts are zero, use SCIPs best variable since the Treemodel is not applicable */
1750  if( SCIPisZero(scip, maxgains[bestcand]))
1751  {
1752  usetreemodel = FALSE;
1753  }
1754 
1755  /* If SCIPs best candidate was selected due to hybrid branching scores
1756  * rather than because of pseudocosts, then we keep it.
1757  */
1758  SCIP_CALL( SCIPgetRealParam(scip, "branching/treemodel/smallpscost", &smallpscost) );
1759  if( usetreemodel == TRUE && avgpscostscore <= smallpscost )
1760  {
1761  int cand;
1762  for( cand = 0; cand < nbranchcands; ++cand )
1763  {
1764  if( scoresfrompc[cand] > scoresfrompc[bestcand] )
1765  {
1766  usetreemodel = FALSE;
1767  break;
1768  }
1769  }
1770  }
1771 
1772  if( usetreemodel == TRUE )
1773  {
1774  SCIP_CALL( SCIPtreemodelSelectCandidate(
1775  scip, /* SCIP data structure */
1776  branchruledata->treemodel, /* branching rule */
1777  branchcands, /* branching candidate storage */
1778  mingains, /* minimum gain of rounding downwards or upwards */
1779  maxgains, /* maximum gain of rounding downwards or upwards */
1780  scoresfromothers, /* scores from other branching methods */
1781  nbranchcands, /* the number of branching candidates */
1782  &bestcand /* the best branching candidate found by SCIP */
1783  ) );
1784  }
1785  }
1786 
1787  /* free buffer for the lp gains and pseudocost scores */
1788  SCIPfreeBufferArray(scip, &scoresfromothers);
1789  SCIPfreeBufferArray(scip, &scoresfrompc);
1790  SCIPfreeBufferArray(scip, &scores);
1791  SCIPfreeBufferArray(scip, &maxgains);
1792  SCIPfreeBufferArray(scip, &mingains);
1793 
1794  /* free buffer for the unreliable candidates */
1795  SCIPfreeBufferArray(scip, &initcandscores);
1796  SCIPfreeBufferArray(scip, &initcands);
1797  }
1798 
1799  /* if no domain could be reduced, create the branching */
1800  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED && executebranch )
1801  {
1802  SCIP_NODE* downchild;
1803  SCIP_NODE* upchild;
1804  SCIP_VAR* var;
1805  SCIP_Real val;
1806 
1807  assert(*result == SCIP_DIDNOTRUN);
1808  assert(0 <= bestcand && bestcand < nbranchcands);
1809  assert(!SCIPisFeasIntegral(scip, branchcandssol[bestcand]));
1810  assert(!allcolsinlp || SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
1811  assert(!bestsbdowncutoff && !bestsbupcutoff);
1812 
1813  var = branchcands[bestcand];
1814  val = branchcandssol[bestcand];
1815 
1816  /* perform the branching */
1817  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",
1818  nbranchcands, ninitcands, bestcand, SCIPvarGetName(var), branchcandssol[bestcand],
1819  bestsbdown, bestsbdown - lpobjval, bestsbup, bestsbup - lpobjval, bestisstrongbranch,
1820  SCIPgetVarPseudocostCurrentRun(scip, var, SCIP_BRANCHDIR_DOWNWARDS),
1821  SCIPgetVarPseudocostCurrentRun(scip, var, SCIP_BRANCHDIR_UPWARDS),
1822  SCIPgetVarPseudocostScoreCurrentRun(scip, var, branchcandssol[bestcand]));
1823  SCIP_UNUSED(bestisstrongbranch);
1824  SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, NULL, &upchild) );
1825  assert(downchild != NULL);
1826  assert(upchild != NULL);
1827 
1828  /* update the lower bounds in the children */
1829  if( sbvars[bestcand] && allcolsinlp && !exactsolve )
1830  {
1831  if( sbdownvalid[bestcand] )
1832  {
1833  assert(SCIPisLT(scip, sbdown[bestcand], SCIPgetCutoffbound(scip)));
1834  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, sbdown[bestcand]) );
1835  assert(SCIPisGE(scip, SCIPgetNodeLowerbound(scip, downchild), provedbound));
1836  }
1837  if( sbupvalid[bestcand] )
1838  {
1839  assert(SCIPisLT(scip, sbup[bestcand], SCIPgetCutoffbound(scip)));
1840  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, sbup[bestcand]) );
1841  assert(SCIPisGE(scip, SCIPgetNodeLowerbound(scip, upchild), provedbound));
1842  }
1843  }
1844 
1845  SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
1846  SCIPdebugMsg(scip, " -> up child's lowerbound : %g\n", SCIPnodeGetLowerbound(upchild));
1847 
1848  assert(SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_INFEASIBLE && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OBJLIMIT);
1849 
1850  *result = SCIP_BRANCHED;
1851  }
1852 
1853  /* free buffer for the strong branching lp gains */
1854  SCIPfreeBufferArray(scip, &sbvars);
1855  SCIPfreeBufferArray(scip, &sbupvalid);
1856  SCIPfreeBufferArray(scip, &sbdownvalid);
1857  SCIPfreeBufferArray(scip, &sbup);
1858  SCIPfreeBufferArray(scip, &sbdown);
1859 
1860  return SCIP_OKAY;
1861 }
1862 
1863 
1864 /*
1865  * Callback methods
1866  */
1867 
1868 /** copy method for branchrule plugins (called when SCIP copies plugins) */
1869 static
1870 SCIP_DECL_BRANCHCOPY(branchCopyRelpscost)
1871 { /*lint --e{715}*/
1872  assert(scip != NULL);
1873  assert(branchrule != NULL);
1874  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1875 
1876  /* call inclusion method of branchrule */
1877  SCIP_CALL( SCIPincludeBranchruleRelpscost(scip) );
1878 
1879  return SCIP_OKAY;
1880 }
1881 
1882 /** destructor of branching rule to free user data (called when SCIP is exiting) */
1883 static
1884 SCIP_DECL_BRANCHFREE(branchFreeRelpscost)
1885 { /*lint --e{715}*/
1886  SCIP_BRANCHRULEDATA* branchruledata;
1887  branchruledata = SCIPbranchruleGetData(branchrule);
1888 
1889  /* free Treemodel parameter data structure */
1890  SCIP_CALL( SCIPtreemodelFree(scip, &branchruledata->treemodel) );
1891 
1892  /* free branching rule data */
1893  SCIPfreeBlockMemory(scip, &branchruledata);
1894  SCIPbranchruleSetData(branchrule, NULL);
1895 
1896  return SCIP_OKAY;
1897 }
1898 
1899 
1900 /** solving process initialization method of branching rule (called when branch and bound process is about to begin) */
1901 static
1902 SCIP_DECL_BRANCHINITSOL(branchInitsolRelpscost)
1903 { /*lint --e{715}*/
1904  SCIP_BRANCHRULEDATA* branchruledata;
1905 
1906  /* initialize branching rule data */
1907  branchruledata = SCIPbranchruleGetData(branchrule);
1908  branchruledata->nlcount = NULL;
1909  branchruledata->nlcountsize = 0;
1910  branchruledata->nlcountmax = 1;
1911  assert(branchruledata->startrandseed >= 0);
1912 
1913  /* create a random number generator */
1914  SCIP_CALL( SCIPcreateRandom(scip, &branchruledata->randnumgen,
1915  (unsigned int)branchruledata->startrandseed, TRUE) );
1916 
1917  return SCIP_OKAY;
1918 }
1919 
1920 
1921 /** solving process deinitialization method of branching rule (called before branch and bound process data is freed) */
1922 static
1923 SCIP_DECL_BRANCHEXITSOL(branchExitsolRelpscost)
1924 { /*lint --e{715}*/
1925  SCIP_BRANCHRULEDATA* branchruledata;
1926 
1927  /* free memory in branching rule data */
1928  branchruledata = SCIPbranchruleGetData(branchrule);
1929  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->nlcount, branchruledata->nlcountsize);
1930 
1931  /* free random number generator */
1932  SCIPfreeRandom(scip, &branchruledata->randnumgen);
1933 
1934  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->orbitrep, branchruledata->npermvars);
1935  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->varorbitmap, branchruledata->npermvars);
1936  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->orbitbegins, branchruledata->npermvars);
1937  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->orbits, branchruledata->npermvars);
1938  branchruledata->nosymmetry = FALSE;
1939  branchruledata->norbits = 0;
1940  branchruledata->permvars = NULL;
1941  branchruledata->permvarmap = NULL;
1942  branchruledata->npermvars = 0;
1943 
1944  return SCIP_OKAY;
1945 }
1946 
1947 
1948 /** branching execution method for fractional LP solutions */
1949 static
1950 SCIP_DECL_BRANCHEXECLP(branchExeclpRelpscost)
1951 { /*lint --e{715}*/
1952  SCIP_BRANCHRULEDATA* branchruledata;
1953  SCIP_VAR** lpcands;
1954  SCIP_Real* lpcandssol;
1955  SCIP_Real* lpcandsfrac;
1956  SCIP_VAR** filteredlpcands;
1957  SCIP_Real* filteredlpcandssol;
1958  SCIP_Real* filteredlpcandsfrac;
1959  SCIP_Bool runfiltering;
1960  int* filteredlpcandsorbitidx = NULL;
1961  int nfilteredlpcands;
1962  int nlpcands;
1963 
1964  assert(branchrule != NULL);
1965  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1966  assert(scip != NULL);
1967  assert(result != NULL);
1968 
1969  SCIPdebugMsg(scip, "Execlp method of relpscost branching in node %llu\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
1970 
1971  if( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
1972  {
1973  *result = SCIP_DIDNOTRUN;
1974  SCIPdebugMsg(scip, "Could not apply relpscost branching, as the current LP was not solved to optimality.\n");
1975 
1976  return SCIP_OKAY;
1977  }
1978 
1979  /* get branching candidates */
1980  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, NULL, &nlpcands, NULL) );
1981  assert(nlpcands > 0);
1982 
1983  branchruledata = SCIPbranchruleGetData(branchrule);
1984  assert(branchruledata != NULL);
1985 
1986  /* determine whether we should run filtering */
1987  runfiltering = ! branchruledata->nosymmetry && branchruledata->filtercandssym && SCIPgetSubscipDepth(scip) == 0 && ! SCIPinDive(scip) && ! SCIPinProbing(scip);
1988 
1989  /* init orbits if necessary */
1990  if( runfiltering )
1991  {
1992  SCIP_CALL( initOrbits(scip, branchruledata) );
1993  }
1994 
1995  /* determine fractional variables (possibly filter by using symmetries) */
1996  if( runfiltering && branchruledata->norbits != 0 )
1997  {
1998  SCIP_CALL( SCIPallocBufferArray(scip, &filteredlpcands, nlpcands) );
1999  SCIP_CALL( SCIPallocBufferArray(scip, &filteredlpcandssol, nlpcands) );
2000  SCIP_CALL( SCIPallocBufferArray(scip, &filteredlpcandsfrac, nlpcands) );
2001  SCIP_CALL( SCIPallocBufferArray(scip, &filteredlpcandsorbitidx, nlpcands) );
2002 
2003  /* determine filtered fractional variables */
2004  SCIP_CALL( filterSymmetricVariables(scip, branchruledata, lpcands, lpcandssol, lpcandsfrac, nlpcands,
2005  filteredlpcands, filteredlpcandssol, filteredlpcandsfrac, filteredlpcandsorbitidx, &nfilteredlpcands) );
2006  }
2007  else
2008  {
2009  /* No orbits available. Copy all (unfiltered) branching candidates, because they will be updated w.r.t. the strong branching LP solution */
2010  SCIP_CALL( SCIPduplicateBufferArray(scip, &filteredlpcands, lpcands, nlpcands) );
2011  SCIP_CALL( SCIPduplicateBufferArray(scip, &filteredlpcandssol, lpcandssol, nlpcands) );
2012  SCIP_CALL( SCIPduplicateBufferArray(scip, &filteredlpcandsfrac, lpcandsfrac, nlpcands) );
2013  nfilteredlpcands = nlpcands;
2014  }
2015 
2016  /* execute branching rule */
2017  SCIP_CALL( execRelpscost(scip, branchrule, filteredlpcands, filteredlpcandssol, filteredlpcandsfrac, filteredlpcandsorbitidx, nfilteredlpcands, TRUE, result) );
2018 
2019  SCIPfreeBufferArrayNull(scip, &filteredlpcandsorbitidx);
2020  SCIPfreeBufferArray(scip, &filteredlpcandsfrac);
2021  SCIPfreeBufferArray(scip, &filteredlpcandssol);
2022  SCIPfreeBufferArray(scip, &filteredlpcands);
2023 
2024  return SCIP_OKAY;
2025 }
2026 
2027 
2028 /*
2029  * branching specific interface methods
2030  */
2031 
2032 /** creates the reliable pseudo cost branching rule and includes it in SCIP */
2033 SCIP_RETCODE SCIPincludeBranchruleRelpscost(
2034  SCIP* scip /**< SCIP data structure */
2035  )
2036 {
2037  SCIP_BRANCHRULEDATA* branchruledata;
2038  SCIP_BRANCHRULE* branchrule;
2039 
2040  /* create relpscost branching rule data */
2041  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
2042 
2043  branchruledata->nosymmetry = FALSE;
2044  branchruledata->orbits = NULL;
2045  branchruledata->orbitbegins = NULL;
2046  branchruledata->orbitrep = NULL;
2047  branchruledata->varorbitmap = NULL;
2048  branchruledata->norbits = 0;
2049  branchruledata->permvars = NULL;
2050  branchruledata->npermvars = 0;
2051  branchruledata->permvarmap = NULL;
2052 
2053  /* include branching rule */
2054  SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
2055  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
2056 
2057  assert(branchrule != NULL);
2058 
2059  /* set non-fundamental callbacks via specific setter functions*/
2060  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyRelpscost) );
2061  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeRelpscost) );
2062  SCIP_CALL( SCIPsetBranchruleInitsol(scip, branchrule, branchInitsolRelpscost) );
2063  SCIP_CALL( SCIPsetBranchruleExitsol(scip, branchrule, branchExitsolRelpscost) );
2064  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpRelpscost) );
2065 
2066  /* relpscost branching rule parameters */
2067  SCIP_CALL( SCIPaddRealParam(scip,
2068  "branching/relpscost/conflictweight",
2069  "weight in score calculations for conflict score",
2070  &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2071  SCIP_CALL( SCIPaddRealParam(scip,
2072  "branching/relpscost/conflictlengthweight",
2073  "weight in score calculations for conflict length score",
2074  &branchruledata->conflengthweight, TRUE, DEFAULT_CONFLENGTHWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2075  SCIP_CALL( SCIPaddRealParam(scip,
2076  "branching/relpscost/inferenceweight",
2077  "weight in score calculations for inference score",
2078  &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2079  SCIP_CALL( SCIPaddRealParam(scip,
2080  "branching/relpscost/cutoffweight",
2081  "weight in score calculations for cutoff score",
2082  &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2083  SCIP_CALL( SCIPaddRealParam(scip,
2084  "branching/relpscost/pscostweight",
2085  "weight in score calculations for pseudo cost score",
2086  &branchruledata->pscostweight, TRUE, DEFAULT_PSCOSTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2087  SCIP_CALL( SCIPaddRealParam(scip,
2088  "branching/relpscost/nlscoreweight",
2089  "weight in score calculations for nlcount score",
2090  &branchruledata->nlscoreweight, TRUE, DEFAULT_NLSCOREWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
2091  SCIP_CALL( SCIPaddRealParam(scip,
2092  "branching/relpscost/minreliable",
2093  "minimal value for minimum pseudo cost size to regard pseudo cost value as reliable",
2094  &branchruledata->minreliable, TRUE, DEFAULT_MINRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2095  SCIP_CALL( SCIPaddRealParam(scip,
2096  "branching/relpscost/maxreliable",
2097  "maximal value for minimum pseudo cost size to regard pseudo cost value as reliable",
2098  &branchruledata->maxreliable, TRUE, DEFAULT_MAXRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2099  SCIP_CALL( SCIPaddRealParam(scip,
2100  "branching/relpscost/sbiterquot",
2101  "maximal fraction of strong branching LP iterations compared to node relaxation LP iterations",
2102  &branchruledata->sbiterquot, FALSE, DEFAULT_SBITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2103  SCIP_CALL( SCIPaddIntParam(scip,
2104  "branching/relpscost/sbiterofs",
2105  "additional number of allowed strong branching LP iterations",
2106  &branchruledata->sbiterofs, FALSE, DEFAULT_SBITEROFS, 0, INT_MAX, NULL, NULL) );
2107  SCIP_CALL( SCIPaddIntParam(scip,
2108  "branching/relpscost/maxlookahead",
2109  "maximal number of further variables evaluated without better score",
2110  &branchruledata->maxlookahead, TRUE, DEFAULT_MAXLOOKAHEAD, 1, INT_MAX, NULL, NULL) );
2111  SCIP_CALL( SCIPaddIntParam(scip,
2112  "branching/relpscost/initcand",
2113  "maximal number of candidates initialized with strong branching per node",
2114  &branchruledata->initcand, FALSE, DEFAULT_INITCAND, 0, INT_MAX, NULL, NULL) );
2115  SCIP_CALL( SCIPaddIntParam(scip,
2116  "branching/relpscost/inititer",
2117  "iteration limit for strong branching initializations of pseudo cost entries (0: auto)",
2118  &branchruledata->inititer, FALSE, DEFAULT_INITITER, 0, INT_MAX, NULL, NULL) );
2119  SCIP_CALL( SCIPaddIntParam(scip,
2120  "branching/relpscost/maxbdchgs",
2121  "maximal number of bound tightenings before the node is reevaluated (-1: unlimited)",
2122  &branchruledata->maxbdchgs, TRUE, DEFAULT_MAXBDCHGS, -1, INT_MAX, NULL, NULL) );
2123  SCIP_CALL( SCIPaddIntParam(scip,
2124  "branching/relpscost/maxproprounds",
2125  "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
2126  &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
2127  SCIP_CALL( SCIPaddBoolParam(scip,
2128  "branching/relpscost/probingbounds",
2129  "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
2130  &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
2131 
2132  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/userelerrorreliability",
2133  "should reliability be based on relative errors?", &branchruledata->userelerrorforreliability, TRUE, DEFAULT_USERELERRORFORRELIABILITY,
2134  NULL, NULL) );
2135 
2136  SCIP_CALL( SCIPaddRealParam(scip, "branching/relpscost/lowerrortol", "low relative error tolerance for reliability",
2137  &branchruledata->lowerrortol, TRUE, DEFAULT_LOWERRORTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2138 
2139  SCIP_CALL( SCIPaddRealParam(scip, "branching/relpscost/higherrortol", "high relative error tolerance for reliability",
2140  &branchruledata->higherrortol, TRUE, DEFAULT_HIGHERRORTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2141 
2142 /**! [SnippetCodeStyleParenIndent] */
2143 
2144  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/storesemiinitcosts",
2145  "should strong branching result be considered for pseudo costs if the other direction was infeasible?",
2146  &branchruledata->storesemiinitcosts, TRUE, DEFAULT_STORESEMIINITCOSTS,
2147  NULL, NULL) );
2148 
2149 /**! [SnippetCodeStyleParenIndent] */
2150 
2151  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usesblocalinfo",
2152  "should the scoring function use only local cutoff and inference information obtained for strong branching candidates?",
2153  &branchruledata->usesblocalinfo, TRUE, DEFAULT_USESBLOCALINFO,
2154  NULL, NULL) );
2155 
2156  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usehyptestforreliability",
2157  "should the strong branching decision be based on a hypothesis test?",
2158  &branchruledata->usehyptestforreliability, TRUE, DEFAULT_USEHYPTESTFORRELIABILITY,
2159  NULL, NULL) );
2160 
2161  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usedynamicconfidence",
2162  "should the confidence level be adjusted dynamically?",
2163  &branchruledata->usedynamicconfidence, TRUE, DEFAULT_USEDYNAMICCONFIDENCE,
2164  NULL, NULL) );
2165  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/skipbadinitcands",
2166  "should branching rule skip candidates that have a low probability to "
2167  "be better than the best strong-branching or pseudo-candidate?",
2168  &branchruledata->skipbadinitcands, TRUE, DEFAULT_SKIPBADINITCANDS,
2169  NULL, NULL) );
2170  SCIP_CALL( SCIPaddIntParam(scip,
2171  "branching/relpscost/confidencelevel",
2172  "the confidence level for statistical methods, between 0 (Min) and 4 (Max).",
2173  &branchruledata->confidencelevel, TRUE, DEFAULT_CONFIDENCELEVEL, 0, 4, NULL, NULL) );
2174 
2175  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/randinitorder",
2176  "should candidates be initialized in randomized order?",
2177  &branchruledata->randinitorder, TRUE, DEFAULT_RANDINITORDER,
2178  NULL, NULL) );
2179 
2180  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/usesmallweightsitlim",
2181  "should smaller weights be used for pseudo cost updates after hitting the LP iteration limit?",
2182  &branchruledata->usesmallweightsitlim, TRUE, DEFAULT_USESMALLWEIGHTSITLIM,
2183  NULL, NULL) );
2184 
2185  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/dynamicweights",
2186  "should the weights of the branching rule be adjusted dynamically during solving based on objective and infeasible leaf counters?",
2187  &branchruledata->dynamicweights, TRUE, DEFAULT_DYNAMICWEIGHTS,
2188  NULL, NULL) );
2189  SCIP_CALL( SCIPaddIntParam(scip, "branching/relpscost/degeneracyaware",
2190  "should degeneracy be taken into account to update weights and skip strong branching? (0: off, 1: after root, 2: always)",
2191  &branchruledata->degeneracyaware, TRUE, DEFAULT_DEGENERACYAWARE, 0, 2,
2192  NULL, NULL) );
2193  SCIP_CALL( SCIPaddIntParam(scip, "branching/relpscost/startrandseed", "start seed for random number generation",
2194  &branchruledata->startrandseed, TRUE, DEFAULT_STARTRANDSEED, 0, INT_MAX, NULL, NULL) );
2195 
2196  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/filtercandssym",
2197  "Use symmetry to filter branching candidates?",
2198  &branchruledata->filtercandssym, TRUE, DEFAULT_FILTERCANDSSYM, NULL, NULL) );
2199 
2200  SCIP_CALL( SCIPaddBoolParam(scip, "branching/relpscost/transsympscost",
2201  "Transfer pscost information to symmetric variables?",
2202  &branchruledata->transsympscost, TRUE, DEFAULT_TRANSSYMPSCOST, NULL, NULL) );
2203 
2204  /* initialise the Treemodel parameters */
2205  SCIP_CALL( SCIPtreemodelInit(scip, &branchruledata->treemodel) );
2206 
2207  return SCIP_OKAY;
2208 }
2209 
2210 /** execution reliability pseudo cost branching with the given branching candidates */
2211 SCIP_RETCODE SCIPexecRelpscostBranching(
2212  SCIP* scip, /**< SCIP data structure */
2213  SCIP_VAR** branchcands, /**< branching candidates */
2214  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
2215  SCIP_Real* branchcandsfrac, /**< fractional part of the branching candidates */
2216  int nbranchcands, /**< number of branching candidates */
2217  SCIP_Bool executebranching, /**< perform a branching step after probing */
2218  SCIP_RESULT* result /**< pointer to the result of the execution */
2219  )
2220 {
2221  SCIP_BRANCHRULE* branchrule;
2222 
2223  assert(scip != NULL);
2224  assert(result != NULL);
2225 
2226  /* find branching rule */
2227  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
2228  assert(branchrule != NULL);
2229 
2230  /* execute branching rule */
2231  SCIP_CALL( execRelpscost(scip, branchrule, branchcands, branchcandssol, branchcandsfrac, NULL, nbranchcands, executebranching, result) );
2232 
2233  return SCIP_OKAY;
2234 }
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
countNonlinearities
static SCIP_RETCODE countNonlinearities(SCIP *scip, int *nlcount, int nlcountsize, int *nlcountmax)
Definition: branch_relpscost.c:413
SCIPsetBranchruleExecLp
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
DEFAULT_FILTERCANDSSYM
#define DEFAULT_FILTERCANDSSYM
Definition: branch_relpscost.c:103
SCIP_BOUNDTYPE
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:50
calcNlscore
static SCIP_Real calcNlscore(SCIP *scip, int *nlcount, int nlcountmax, int probindex)
Definition: branch_relpscost.c:550
SCIPgetVarPseudocostCurrentRun
SCIP_Real SCIPgetVarPseudocostCurrentRun(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip_var.c:8831
SCIPfeastol
SCIP_Real SCIPfeastol(SCIP *scip)
Definition: scip_numerics.c:158
branch_relpscost.h
reliable pseudo costs branching rule
SCIPreallocBlockMemoryArray
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
SCIP_DIDNOTRUN
Definition: type_result.h:33
SCIPgetVarAvgCutoffScore
SCIP_Real SCIPgetVarAvgCutoffScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9662
SCIPisStopped
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:687
SCIPallocBlockMemoryArray
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIPvarIsNegated
SCIP_EXPORT SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17172
DEFAULT_PSCOSTWEIGHT
#define DEFAULT_PSCOSTWEIGHT
Definition: branch_relpscost.c:67
SCIPupdateVarPseudocostSymmetric
static SCIP_RETCODE SCIPupdateVarPseudocostSymmetric(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *branchvar, int *branchorbitidx, int branchvaridx, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: branch_relpscost.c:313
SCIPfindConshdlr
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
freeBdchgs
static void freeBdchgs(SCIP *scip, int **bdchginds, SCIP_BOUNDTYPE **bdchgtypes, SCIP_Real **bdchgbounds, int *nbdchgs)
Definition: branch_relpscost.c:659
BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXDEPTH
Definition: branch_relpscost.c:60
scip_param.h
public methods for SCIP parameter handling
SCIPsetBranchruleFree
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
pub_tree.h
public methods for branch and bound tree
SCIPfreeRandom
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip_randnumgen.c:70
DEFAULT_MAXBDCHGS
#define DEFAULT_MAXBDCHGS
Definition: branch_relpscost.c:76
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
SCIPtightenVarLb
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5184
scip_mem.h
public methods for memory management
SCIPgetVarsAnd
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5160
SCIPgetNDualResolveLPIterations
SCIP_Longint SCIPgetNDualResolveLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:720
SCIPbranchruleGetName
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIPgetSymmetry
SCIP_RETCODE SCIPgetSymmetry(SCIP *scip, int *npermvars, SCIP_VAR ***permvars, SCIP_HASHMAP **permvarmap, int *nperms, int ***perms, int ***permstrans, SCIP_Real *log10groupsize, SCIP_Bool *binvaraffected, int **components, int **componentbegins, int **vartocomponent, int *ncomponents)
Definition: prop_symmetry.c:3993
DEFAULT_LOWERRORTOL
#define DEFAULT_LOWERRORTOL
Definition: branch_relpscost.c:84
pow
SCIPInterval pow(const SCIPInterval &x, const SCIPInterval &y)
Definition: intervalarithext.h:291
bound
static long bound
Definition: GomoryHuTree.cpp:38
SCIPgetBinvarRepresentative
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip_var.c:1601
SCIPbranchruleGetData
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
SCIPvarGetLPSol
SCIP_EXPORT SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18041
SCIPtightenVarUb
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5301
SCIPgetNodeLowerbound
SCIP_Real SCIPgetNodeLowerbound(SCIP *scip, SCIP_NODE *node)
Definition: scip_prob.c:3616
SCIPnodeGetNumber
SCIP_EXPORT SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7429
SCIP_BRANCHRULEDATA
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
SCIPgetVarStrongbranchFrac
SCIP_RETCODE SCIPgetVarStrongbranchFrac(SCIP *scip, SCIP_VAR *var, int itlim, SCIP_Bool idempotent, 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:2923
DEFAULT_DEGENERACYAWARE
#define DEFAULT_DEGENERACYAWARE
Definition: branch_relpscost.c:100
SCIPgetNNodeInitLPIterations
SCIP_Longint SCIPgetNNodeInitLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:810
binvarGetActiveProbindex
static SCIP_RETCODE binvarGetActiveProbindex(SCIP *scip, SCIP_VAR *var, int *probindex)
Definition: branch_relpscost.c:375
SCIP_Var
Definition: struct_var.h:198
BRANCHRULE_MAXBOUNDDIST
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_relpscost.c:61
DEFAULT_STARTRANDSEED
#define DEFAULT_STARTRANDSEED
Definition: branch_relpscost.c:94
SCIPgetCurrentNode
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:81
SCIPvarIsBinary
SCIP_EXPORT SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17197
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
DEFAULT_SBITERQUOT
#define DEFAULT_SBITERQUOT
Definition: branch_relpscost.c:71
SCIP_VERBLEVEL_HIGH
Definition: type_message.h:45
SCIPverbMessage
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
FALSE
#define FALSE
Definition: def.h:73
SCIPrandomGetReal
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9981
SCIPsetBranchruleCopy
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
TRUE
#define TRUE
Definition: def.h:72
SCIPdebug
#define SCIPdebug(x)
Definition: pub_message.h:84
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIPgetNLPVarsNonlinearity
SCIP_RETCODE SCIPgetNLPVarsNonlinearity(SCIP *scip, int *nlcount)
Definition: scip_nlp.c:321
treemodel.h
Branching rules based on the Single-Variable-Branching (SVB) model.
DEFAULT_INFERENCEWEIGHT
#define DEFAULT_INFERENCEWEIGHT
Definition: branch_relpscost.c:65
SCIP_RandNumGen
Definition: struct_misc.h:259
SCIP_UNUSED
#define SCIP_UNUSED(x)
Definition: def.h:418
SCIPpscostThresholdProbabilityTest
SCIP_Bool SCIPpscostThresholdProbabilityTest(SCIP *scip, SCIP_VAR *var, SCIP_Real frac, SCIP_Real threshold, SCIP_BRANCHDIR dir, SCIP_CONFIDENCELEVEL clevel)
Definition: scip_var.c:8994
SCIPvarIsActive
SCIP_EXPORT SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17340
pub_var.h
public methods for problem variables
SCIPaddBoolParam
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:48
SCIPincludeBranchruleRelpscost
SCIP_RETCODE SCIPincludeBranchruleRelpscost(SCIP *scip)
Definition: branch_relpscost.c:2037
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIPbranchVarVal
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1117
pub_branch.h
public methods for branching rules
SCIPvarGetStatus
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17136
cons_and.h
Constraint handler for AND constraints, .
SCIPgetVarConflictlengthScore
SCIP_Real SCIPgetVarConflictlengthScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9238
SCIPgetVarPseudocostCountCurrentRun
SCIP_Real SCIPgetVarPseudocostCountCurrentRun(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: scip_var.c:8885
SCIPduplicateBufferArray
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:119
SCIPgetVarPseudocostScore
SCIP_Real SCIPgetVarPseudocostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition: scip_var.c:9038
SCIPincludeBranchruleBasic
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:107
SCIPgetNStrongbranchLPIterations
SCIP_Longint SCIPgetNStrongbranchLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:882
SCIPgetNNodeLPIterations
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:774
SCIP_DECL_BRANCHINITSOL
static SCIP_DECL_BRANCHINITSOL(branchInitsolRelpscost)
Definition: branch_relpscost.c:1906
SCIPnodeGetLowerbound
SCIP_EXPORT SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7449
SCIP_DECL_BRANCHFREE
static SCIP_DECL_BRANCHFREE(branchFreeRelpscost)
Definition: branch_relpscost.c:1888
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
DEFAULT_HIGHERRORTOL
#define DEFAULT_HIGHERRORTOL
Definition: branch_relpscost.c:85
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_LPSOLSTAT_OBJLIMIT
Definition: type_lp.h:37
scip_var.h
public methods for SCIP variables
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIPgetCutoffbound
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip_solvingstats.c:1565
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:874
SCIPgetLPSolstat
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
initOrbits
static SCIP_RETCODE initOrbits(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch_relpscost.c:171
SCIP_Node
Definition: struct_tree.h:132
SCIP_Treemodel
Definition: treemodel.c:92
SCIPhasCurrentNodeLP
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip_lp.c:74
SCIPgetResultantAnd
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5185
SCIP_DECL_BRANCHEXITSOL
static SCIP_DECL_BRANCHEXITSOL(branchExitsolRelpscost)
Definition: branch_relpscost.c:1927
DEFAULT_USESMALLWEIGHTSITLIM
#define DEFAULT_USESMALLWEIGHTSITLIM
Definition: branch_relpscost.c:96
scip_numerics.h
public methods for numerical tolerances
SCIPtreemodelSelectCandidate
SCIP_RETCODE SCIPtreemodelSelectCandidate(SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Real *tiebreakerscore, int nbranchcands, int *bestcand)
Definition: treemodel.c:911
SCIPcreateRandom
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
Definition: scip_randnumgen.c:47
SCIPgetVarPseudocostScoreCurrentRun
SCIP_Real SCIPgetVarPseudocostScoreCurrentRun(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition: scip_var.c:9076
scip_solvingstats.h
public methods for querying solving statistics
DEFAULT_INITITER
#define DEFAULT_INITITER
Definition: branch_relpscost.c:75
SCIPhashmapGetImageInt
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
scip_tree.h
public methods for the branch-and-bound tree
BRANCHRULE_NAME
#define BRANCHRULE_NAME
Definition: branch_relpscost.c:57
SCIPgetNNodes
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip_solvingstats.c:200
SCIP_HashMap
Definition: struct_misc.h:128
pub_cons.h
public methods for managing constraints
SCIPgetVarConflictScore
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9176
BRANCHRULE_PRIORITY
#define BRANCHRULE_PRIORITY
Definition: branch_relpscost.c:59
SCIPisSumGE
SCIP_Bool SCIPisSumGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:724
SCIP_CONFIDENCELEVEL
enum SCIP_Confidencelevel SCIP_CONFIDENCELEVEL
Definition: type_misc.h:44
SCIPvarGetName
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
SCIPgetAvgPseudocostScore
SCIP_Real SCIPgetAvgPseudocostScore(SCIP *scip)
Definition: scip_solvingstats.c:1869
SCIPgetVarStrongbranchLast
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:4014
SCIPallColsInLP
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:619
applyBdchgs
static SCIP_RETCODE applyBdchgs(SCIP *scip, SCIP_VAR **vars, int *bdchginds, SCIP_BOUNDTYPE *bdchgtypes, SCIP_Real *bdchgbounds, int nbdchgs, SCIP_RESULT *result)
Definition: branch_relpscost.c:680
SCIP_Cons
Definition: struct_cons.h:37
SCIPfindBranchrule
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
SCIP_Conshdlr
Definition: struct_cons.h:117
SCIPgetVars
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1941
SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:47
SCIPfreeBufferArrayNull
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:124
SCIPfeasFrac
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:934
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:551
SCIPupdateNodeLowerbound
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip_prob.c:3751
SCIPinProbing
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:88
DEFAULT_USEHYPTESTFORRELIABILITY
#define DEFAULT_USEHYPTESTFORRELIABILITY
Definition: branch_relpscost.c:86
SCIPgetAvgInferenceScore
SCIP_Real SCIPgetAvgInferenceScore(SCIP *scip)
Definition: scip_solvingstats.c:2102
NULL
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_OKAY
Definition: type_retcode.h:33
pub_sol.h
public methods for primal CIP solutions
SCIPgetNObjlimLeaves
SCIP_Longint SCIPgetNObjlimLeaves(SCIP *scip)
Definition: scip_solvingstats.c:308
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:364
filterSymmetricVariables
static SCIP_RETCODE filterSymmetricVariables(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR **origbranchcands, SCIP_Real *origbranchcandssol, SCIP_Real *origbranchcandsfrac, int norigbranchcands, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int *branchorbitidx, int *nbranchcands)
Definition: branch_relpscost.c:230
prop_symmetry.h
propagator for symmetry handling
SCIP_REDUCEDDOM
Definition: type_result.h:42
SCIPisLPSolBasic
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition: scip_lp.c:637
DEFAULT_SBITEROFS
#define DEFAULT_SBITEROFS
Definition: branch_relpscost.c:72
SCIPfeasFloor
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:898
DEFAULT_CUTOFFWEIGHT
#define DEFAULT_CUTOFFWEIGHT
Definition: branch_relpscost.c:66
SCIP_Branchrule
Definition: struct_branch.h:69
SCIPgetLPObjval
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:238
SCIPtreemodelIsEnabled
SCIP_Bool SCIPtreemodelIsEnabled(SCIP *scip, SCIP_TREEMODEL *treemodel)
Definition: treemodel.c:899
SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:34
scip_cons.h
public methods for constraint handler plugins and constraints
DEFAULT_CONFLICTWEIGHT
#define DEFAULT_CONFLICTWEIGHT
Definition: branch_relpscost.c:63
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
addBdchg
static SCIP_RETCODE addBdchg(SCIP *scip, int **bdchginds, SCIP_BOUNDTYPE **bdchgtypes, SCIP_Real **bdchgbounds, int *nbdchgs, int ind, SCIP_BOUNDTYPE type, SCIP_Real bound)
Definition: branch_relpscost.c:626
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:503
pub_misc.h
public data structures and miscellaneous methods
SCIPvarGetNegationVar
SCIP_EXPORT SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17493
SCIPgetDepth
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:638
SCIP_Bool
#define SCIP_Bool
Definition: def.h:70
SCIPisSumGT
SCIP_Bool SCIPisSumGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:711
SCIP_DECL_BRANCHEXECLP
static SCIP_DECL_BRANCHEXECLP(branchExeclpRelpscost)
Definition: branch_relpscost.c:1954
SCIPgetNDualResolveLPs
SCIP_Longint SCIPgetNDualResolveLPs(SCIP *scip)
Definition: scip_solvingstats.c:700
SCIP_DECL_BRANCHCOPY
static SCIP_DECL_BRANCHCOPY(branchCopyRelpscost)
Definition: branch_relpscost.c:1874
SCIPisNLPConstructed
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:210
DEFAULT_CONFLENGTHWEIGHT
#define DEFAULT_CONFLENGTHWEIGHT
Definition: branch_relpscost.c:64
DEFAULT_SKIPBADINITCANDS
#define DEFAULT_SKIPBADINITCANDS
Definition: branch_relpscost.c:91
SCIPtreemodelFree
SCIP_RETCODE SCIPtreemodelFree(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition: treemodel.c:883
SCIP_CONFIDENCELEVEL_HIGH
Definition: type_misc.h:41
DEFAULT_MINRELIABLE
#define DEFAULT_MINRELIABLE
Definition: branch_relpscost.c:69
MAX
#define MAX(x, y)
Definition: tclique_def.h:83
DEFAULT_MAXPROPROUNDS
#define DEFAULT_MAXPROPROUNDS
Definition: branch_relpscost.c:77
SCIPisVarPscostRelerrorReliable
SCIP_Bool SCIPisVarPscostRelerrorReliable(SCIP *scip, SCIP_VAR *var, SCIP_Real threshold, SCIP_CONFIDENCELEVEL clevel)
Definition: scip_var.c:9013
SCIPendStrongbranch
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
Definition: scip_var.c:2748
SCIPsolGetIndex
SCIP_EXPORT int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2635
SCIPexecRelpscostBranching
SCIP_RETCODE SCIPexecRelpscostBranching(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result)
Definition: branch_relpscost.c:2215
SCIPgetNVarsAnd
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5136
SCIPconshdlrGetNActiveConss
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4616
DEFAULT_INITCAND
#define DEFAULT_INITCAND
Definition: branch_relpscost.c:74
DEFAULT_NLSCOREWEIGHT
#define DEFAULT_NLSCOREWEIGHT
Definition: branch_relpscost.c:68
DEFAULT_DYNAMICWEIGHTS
#define DEFAULT_DYNAMICWEIGHTS
Definition: branch_relpscost.c:97
SCIPcomputeOrbitsComponentsSym
SCIP_RETCODE SCIPcomputeOrbitsComponentsSym(SCIP *scip, int npermvars, int **permstrans, int nperms, int *components, int *componentbegins, int *vartocomponent, int ncomponents, int *orbits, int *orbitbegins, int *norbits, int *varorbitmap)
Definition: symmetry.c:304
SCIPsetBranchruleInitsol
SCIP_RETCODE SCIPsetBranchruleInitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: scip_branch.c:208
DEFAULT_MAXLOOKAHEAD
#define DEFAULT_MAXLOOKAHEAD
Definition: branch_relpscost.c:73
SCIPgetVarStrongbranchNode
SCIP_Longint SCIPgetVarStrongbranchNode(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:4164
SCIP_CONFIDENCELEVEL_LOW
Definition: type_misc.h:39
SCIPvarGetLbLocal
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
SCIPaddRealParam
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:130
SCIPisExactSolve
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip_general.c:574
SCIP_CONFIDENCELEVEL_MIN
Definition: type_misc.h:38
scip_lp.h
public methods for the LP relaxation, rows and columns
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition: def.h:164
DEFAULT_USERELERRORFORRELIABILITY
#define DEFAULT_USERELERRORFORRELIABILITY
Definition: branch_relpscost.c:83
scip_nlp.h
public methods for nonlinear relaxations
execRelpscost
static SCIP_RETCODE execRelpscost(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int *branchorbitidx, int nbranchcands, SCIP_Bool executebranch, SCIP_RESULT *result)
Definition: branch_relpscost.c:757
SCIPinDive
SCIP_Bool SCIPinDive(SCIP *scip)
Definition: scip_lp.c:2715
SCIP_REAL_MIN
#define SCIP_REAL_MIN
Definition: def.h:165
SCIP_CONFIDENCELEVEL_MAX
Definition: type_misc.h:42
SCIPvarGetUbLocal
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
SCIP_BRANCHDIR_DOWNWARDS
Definition: type_history.h:34
scip_branch.h
public methods for branching rule plugins and branching
scip_general.h
general public methods
SCIPstartStrongbranch
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip_var.c:2690
DEFAULT_PROBINGBOUNDS
#define DEFAULT_PROBINGBOUNDS
Definition: branch_relpscost.c:80
SCIP_BRANCHDIR_UPWARDS
Definition: type_history.h:35
scip_sol.h
public methods for solutions
SCIPgetLPDegeneracy
SCIP_RETCODE SCIPgetLPDegeneracy(SCIP *scip, SCIP_Real *degeneracy, SCIP_Real *varconsratio)
Definition: scip_lp.c:2731
scip_randnumgen.h
public methods for random numbers
SCIPgetNRootStrongbranchLPIterations
SCIP_Longint SCIPgetNRootStrongbranchLPIterations(SCIP *scip)
Definition: scip_solvingstats.c:918
symmetry.h
methods for handling symmetries
SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:48
SCIPconshdlrGetConss
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4539
DEFAULT_USESBLOCALINFO
#define DEFAULT_USESBLOCALINFO
Definition: branch_relpscost.c:89
pub_message.h
public methods for message output
SCIPgetVarsData
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1860
SCIP_CONSADDED
Definition: type_result.h:43
DEFAULT_STORESEMIINITCOSTS
#define DEFAULT_STORESEMIINITCOSTS
Definition: branch_relpscost.c:88
SCIPaddIntParam
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:74
SCIPgetVarPseudocostVal
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip_var.c:8749
SCIPgetVarStrongbranchWithPropagation
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:3356
SCIP_Real
#define SCIP_Real
Definition: def.h:163
SCIPsetBranchruleExitsol
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip_branch.c:224
calcScore
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, SCIP_Real degeneracyfactor)
Definition: branch_relpscost.c:577
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
scip_message.h
public methods for message handling
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIPgetLPBranchCands
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
SCIP_INVALID
#define SCIP_INVALID
Definition: def.h:183
SCIPgetNNodeInitLPs
SCIP_Longint SCIPgetNNodeInitLPs(SCIP *scip)
Definition: scip_solvingstats.c:792
SCIP_Longint
#define SCIP_Longint
Definition: def.h:148
DEFAULT_USEDYNAMICCONFIDENCE
#define DEFAULT_USEDYNAMICCONFIDENCE
Definition: branch_relpscost.c:87
branchruledataEnsureNlcount
static SCIP_RETCODE branchruledataEnsureNlcount(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch_relpscost.c:503
SCIP_LPSOLSTAT_INFEASIBLE
Definition: type_lp.h:35
DEFAULT_TRANSSYMPSCOST
#define DEFAULT_TRANSSYMPSCOST
Definition: branch_relpscost.c:104
SCIP_BRANCHED
Definition: type_result.h:45
BRANCHRULE_DESC
#define BRANCHRULE_DESC
Definition: branch_relpscost.c:58
SCIPvarGetProbindex
SCIP_EXPORT int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17360
SCIPfreeBlockMemoryArrayNull
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:98
SCIPsignificantVarPscostDifference
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:8964
SCIP_LPSOLSTAT_ITERLIMIT
Definition: type_lp.h:38
SCIPgetAvgCutoffScore
SCIP_Real SCIPgetAvgCutoffScore(SCIP *scip)
Definition: scip_solvingstats.c:2188
SCIPfeasCeil
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:910
SCIPgetVarAvgInferenceScore
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9408
SCIPgetBranchScore
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:840
BMSclearMemoryArray
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:122
SCIPtreemodelInit
SCIP_RETCODE SCIPtreemodelInit(SCIP *scip, SCIP_TREEMODEL **treemodel)
Definition: treemodel.c:825
DEFAULT_MAXRELIABLE
#define DEFAULT_MAXRELIABLE
Definition: branch_relpscost.c:70
SCIPbranchruleSetData
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
scip_prob.h
public methods for global and local (sub)problems
DEFAULT_CONFIDENCELEVEL
#define DEFAULT_CONFIDENCELEVEL
Definition: branch_relpscost.c:90
SCIP_VARSTATUS_FIXED
Definition: type_var.h:43
SCIP_CONFIDENCELEVEL_MEDIUM
Definition: type_misc.h:40
DEFAULT_RANDINITORDER
#define DEFAULT_RANDINITORDER
Definition: branch_relpscost.c:95
SCIPupdateVarPseudocost
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip_var.c:8715
SCIPgetBestSol
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2305
SCIPgetSubscipDepth
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2548
SCIPgetAvgConflictlengthScore
SCIP_Real SCIPgetAvgConflictlengthScore(SCIP *scip)
Definition: scip_solvingstats.c:2016
SCIPgetLastStrongbranchLPSolStat
SCIP_LPSOLSTAT SCIPgetLastStrongbranchLPSolStat(SCIP *scip, SCIP_BRANCHDIR branchdir)
Definition: scip_var.c:3992
SCIPgetAvgConflictScore
SCIP_Real SCIPgetAvgConflictScore(SCIP *scip)
Definition: scip_solvingstats.c:1966
SCIP_CUTOFF
Definition: type_result.h:39
SCIPgetNNLPVars
int SCIPgetNNLPVars(SCIP *scip)
Definition: scip_nlp.c:299
SCIPreallocBufferArray
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIPgetNInfeasibleLeaves
SCIP_Longint SCIPgetNInfeasibleLeaves(SCIP *scip)
Definition: scip_solvingstats.c:281
memory.h
memory allocation routines