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