1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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
initOrbits(SCIP * scip,SCIP_BRANCHRULEDATA * branchruledata)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
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)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
SCIPupdateVarPseudocostSymmetric(SCIP * scip,SCIP_BRANCHRULEDATA * branchruledata,SCIP_VAR * branchvar,int * branchorbitidx,int branchvaridx,SCIP_Real solvaldelta,SCIP_Real objdelta,SCIP_Real weight)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
binvarGetActiveProbindex(SCIP * scip,SCIP_VAR * var,int * probindex)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
countNonlinearities(SCIP * scip,int * nlcount,int nlcountsize,int * nlcountmax)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
branchruledataEnsureNlcount(SCIP * scip,SCIP_BRANCHRULEDATA * branchruledata)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
calcNlscore(SCIP * scip,int * nlcount,int nlcountmax,int probindex)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
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)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
addBdchg(SCIP * scip,int ** bdchginds,SCIP_BOUNDTYPE ** bdchgtypes,SCIP_Real ** bdchgbounds,int * nbdchgs,int ind,SCIP_BOUNDTYPE type,SCIP_Real bound)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
freeBdchgs(SCIP * scip,int ** bdchginds,SCIP_BOUNDTYPE ** bdchgtypes,SCIP_Real ** bdchgbounds,int * nbdchgs)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
applyBdchgs(SCIP * scip,SCIP_VAR ** vars,int * bdchginds,SCIP_BOUNDTYPE * bdchgtypes,SCIP_Real * bdchgbounds,int nbdchgs,SCIP_RESULT * result)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
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)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, °eneracy, &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
SCIP_DECL_BRANCHCOPY(branchCopyRelpscost)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
SCIP_DECL_BRANCHFREE(branchFreeRelpscost)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
SCIP_DECL_BRANCHINITSOL(branchInitsolRelpscost)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
SCIP_DECL_BRANCHEXITSOL(branchExitsolRelpscost)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
SCIP_DECL_BRANCHEXECLP(branchExeclpRelpscost)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 */
SCIPincludeBranchruleRelpscost(SCIP * 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 */
SCIPexecRelpscostBranching(SCIP * scip,SCIP_VAR ** branchcands,SCIP_Real * branchcandssol,SCIP_Real * branchcandsfrac,int nbranchcands,SCIP_Bool executebranching,SCIP_RESULT * result)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 }
2235