Scippy

SCIP

Solving Constraint Integer Programs

branch_lookahead.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-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_lookahead.c
17  * @ingroup DEFPLUGINS_BRANCH
18  * @ingroup BRANCHINGRULES
19  * @brief lookahead LP branching rule
20  * @author Christoph Schubert
21  * @author Gerald Gamrath
22  *
23  * The (multi-level) lookahead branching rule applies strong branching to every fractional value of the LP solution
24  * at the current node of the branch-and-bound tree, as well as recursivly to every temporary child problem created by this
25  * strong branching. The rule selects the candidate with the best proven dual bound.
26  *
27  * The branching rule was motivated by the following technical report:
28  *
29  * @par
30  * Wasu Glankwamdee and Jeff Linderoth@n
31  * Lookahead Branching for Mixed Integer Programming@n
32  * Technical Report 06T-004, Department of Industrial and Systems Engineering, Lehigh University.
33  *
34  * For a more mathematical description and a comparison between lookahead branching and other branching rules
35  * in SCIP, we refer to
36  *
37  * @par
38  * Christoph Schubert@n
39  * Multi-Level Lookahead Branching@n
40  * Master Thesis, Technische Universit├Ąt Berlin, 2017@n
41  */
42 
43 /* Supported defines:
44  * PRINTNODECONS: prints the binary constraints added
45  * SCIP_DEBUG: prints detailed execution information
46  * SCIP_STATISTIC: prints some statistics after the branching rule is freed */
47 
48 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49 
50 #include "blockmemshell/memory.h"
51 #include "lpi/lpi.h"
52 #include "scip/branch_lookahead.h"
53 #include "scip/cons_logicor.h"
54 #include "scip/pub_branch.h"
55 #include "scip/pub_message.h"
56 #include "scip/pub_misc.h"
57 #include "scip/pub_tree.h"
58 #include "scip/pub_var.h"
59 #include "scip/scip_branch.h"
60 #include "scip/scip_cons.h"
61 #include "scip/scip_general.h"
62 #include "scip/scip_lp.h"
63 #include "scip/scip_mem.h"
64 #include "scip/scip_message.h"
65 #include "scip/scip_numerics.h"
66 #include "scip/scip_param.h"
67 #include "scip/scip_prob.h"
68 #include "scip/scip_probing.h"
69 #include "scip/scip_sol.h"
70 #include "scip/scip_solvingstats.h"
71 #include "scip/scip_tree.h"
72 #include "scip/scip_var.h"
73 #include <string.h>
74 
75 #define BRANCHRULE_NAME "lookahead"
76 #define BRANCHRULE_DESC "full strong branching over multiple levels"
77 #define BRANCHRULE_PRIORITY 0
78 #define BRANCHRULE_MAXDEPTH -1
79 #define BRANCHRULE_MAXBOUNDDIST 1.0
80 
81 #define DEFAULT_USEBINARYCONSTRAINTS FALSE /**< should binary constraints be collected and applied? */
82 #define DEFAULT_ADDCLIQUE FALSE /**< add binary constraints with two variables found at the root node also as a clique? */
83 #define DEFAULT_ADDBINCONSROW 0 /**< should binary constraints be added as rows to the base LP?
84  * (0: no, 1: separate, 2: as initial rows) */
85 #define DEFAULT_USEDOMAINREDUCTION TRUE /**< Should domain reductions be collected and applied? */
86 #define DEFAULT_MERGEDOMAINREDUCTIONS FALSE /**< should domain reductions of feasible siblings should be merged? */
87 #define DEFAULT_PREFERSIMPLEBOUNDS FALSE /**< should domain reductions only be applied if there are simple bound changes? */
88 #define DEFAULT_ONLYVIOLDOMREDS FALSE /**< Should only domain reductions that violate the LP solution be applied? */
89 #define DEFAULT_MAXNVIOLATEDCONS 1 /**< How many constraints that are violated by the base lp solution
90  * should be gathered until the rule is stopped and they are added? */
91 #define DEFAULT_MAXNVIOLATEDBINCONS 0 /**< How many binary constraints that are violated by the base lp
92  * solution should be gathered until the rule is stopped and they are
93  * added? */
94 #define DEFAULT_MAXNVIOLATEDDOMREDS 1 /**< How many domain reductions that are violated by the base lp solution
95  * should be gathered until the rule is stopped and they are added? */
96 #define DEFAULT_STOREUNVIOLATEDSOL TRUE /**< If only non violating constraints are added, should the branching
97  * decision be stored till the next call? */
98 #define DEFAULT_REEVALAGE 10LL /**< Max number of LPs solved after which a previous prob branching
99  * result is recalculated. */
100 #define DEFAULT_REEVALAGEFSB 10LL /**< Max number of LPs solved after which a previous FSB scoring
101  * result is recalculated. */
102 #define DEFAULT_RECURSIONDEPTH 2 /**< The max depth of LAB. */
103 #define DEFAULT_ADDNONVIOCONS FALSE /**< Should binary constraints, that are not violated by the base LP, be
104  * collected and added? */
105 #define DEFAULT_PROPAGATE TRUE /**< Should domain propagation be executed before each temporary node is
106  * solved? */
107 #define DEFAULT_USELEVEL2DATA TRUE /**< should branching data generated at depth level 2 be stored for re-using it? */
108 #define DEFAULT_APPLYCHILDBOUNDS FALSE /**< should bounds known for child nodes be applied? */
109 #define DEFAULT_ENFORCEMAXDOMREDS FALSE /**< should the maximum number of domain reductions maxnviolateddomreds be enforced? */
110 #define DEFAULT_UPDATEBRANCHINGRESULTS FALSE /**< should branching results (and scores) be updated w.r.t. proven dual bounds? */
111 #define DEFAULT_MAXPROPROUNDS 0 /**< maximum number of propagation rounds to perform at temporary
112  * nodes (-1: unlimited, 0: SCIP default) */
113 #define DEFAULT_ABBREVIATED TRUE /**< Toggles the abbreviated LAB. */
114 #define DEFAULT_MAXNCANDS 4 /**< If abbreviated: The max number of candidates to consider at the base node */
115 #define DEFAULT_MAXNDEEPERCANDS 2 /**< If abbreviated: The max number of candidates to consider per deeper node
116  * (0: same as base node) */
117 #define DEFAULT_REUSEBASIS TRUE /**< If abbreviated: Should the information gathered to obtain the best
118  * candidates be reused? */
119 #define DEFAULT_ABBREVPSEUDO FALSE /**< If abbreviated: Use pseudo costs to estimate the score of a
120  * candidate. */
121 #define DEFAULT_LEVEL2AVGSCORE FALSE /**< should the average score be used for uninitialized scores in level 2? */
122 #define DEFAULT_LEVEL2ZEROSCORE FALSE /**< should uninitialized scores be set to 0? */
123 #define DEFAULT_SCORINGFUNCTION 'a' /**< scoring function to be used at the base level */
124 #define DEFAULT_DEEPERSCORINGFUNCTION 'x' /**< scoring function to be used at deeper levels */
125 #define DEFAULT_SCORINGSCORINGFUNCTION 'd' /**< scoring function to be used for FSB scoring */
126 #define DEFAULT_MINWEIGHT 0.8 /**< default value for the weight of the minimum in the convex combination of two
127  * child gains (taken from the paper) */
128 #define DEFAULT_WORSEFACTOR -1.0 /**< if the FSB score is of a candidate is worse than the best by this factor, skip this candidate (-1: disable) */
129 #define DEFAULT_FILTERBYMAXGAIN FALSE /**< should lookahead branching only be applied if the max gain in level 1 is not uniquely that of the best candidate? */
130 
131 #ifdef SCIP_DEBUG
132 /* Adjusted debug message that also prints the current probing depth. */
133 #define LABdebugMessage(scip,lvl,...) do \
134  { \
135  SCIP_STAGE stage; \
136  SCIPverbMessage(scip, lvl, NULL, "[%s:%-4d] ", __FILE__, __LINE__); \
137  stage = SCIPgetStage(scip); \
138  if( stage == SCIP_STAGE_INIT ) \
139  { \
140  SCIPverbMessage(scip, lvl, NULL, "Init : "); \
141  } \
142  else if( stage == SCIP_STAGE_FREE ) \
143  { \
144  SCIPverbMessage(scip, lvl, NULL, "Free : "); \
145  } \
146  else if( SCIPinProbing(scip) ) \
147  { \
148  SCIPverbMessage(scip, lvl, NULL, "%*sDepth %i: ", \
149  2 * SCIPgetProbingDepth(scip), "", SCIPgetProbingDepth(scip)); \
150  } \
151  else \
152  { \
153  SCIPverbMessage(scip, lvl, NULL, "Base : "); \
154  } \
155  SCIPverbMessage(scip, lvl, NULL, __VA_ARGS__); \
156  } \
157  while( FALSE )
158 
159 /* Writes a debug message without the leading information. Can be used to append something to an output of LABdebugMessage*/
160 #define LABdebugMessagePrint(scip,lvl,...) do \
161  { \
162  SCIPverbMessage(scip, lvl, NULL, __VA_ARGS__); \
163  } \
164  while( FALSE )
165 #else
166 #define LABdebugMessage(scip,lvl,...) /**/
167 /*#define LABdebugMessagePrint(scip,lvl,...) only used with SCIP_DEBUG defined */
168 #endif
169 
170 /*
171  * Data structures
172  */
173 
174 /** A struct holding information to speed up the solving time for solving a problem again. This is filled by the FSB
175  * scoring routine that is run to get the best candidates. It is then read by the actual ALAB routine. */
176 typedef struct
177 {
178  SCIP_LPISTATE* lpistate; /**< the basis information that may be set before another solve lp call */
179  SCIP_LPINORMS* lpinorms; /**< the norms that may be set before another solve lp call */
180  SCIP_Bool primalfeas; /**< indicates whether the solution was primal feasible */
181  SCIP_Bool dualfeas; /**< indicates whether the solution was dual feasible */
182 } WARMSTARTINFO;
183 
184 /** Allocates the warm start information on the buffer and initializes it with default values. */
185 static
187  SCIP* scip, /**< SCIP data structure */
188  WARMSTARTINFO** warmstartinfo /**< the warmstartinfo to allocate and initialize */
189  )
190 {
191  assert(scip != NULL);
192  assert(warmstartinfo != NULL);
194  SCIP_CALL( SCIPallocBlockMemory(scip, warmstartinfo) );
196  (*warmstartinfo)->lpistate = NULL;
197  (*warmstartinfo)->lpinorms = NULL;
198  (*warmstartinfo)->primalfeas = FALSE;
199  (*warmstartinfo)->dualfeas = FALSE;
200 
201  return SCIP_OKAY;
202 }
203 
204 /** checks that the warm start info can be read into the lp solver. */
205 static
207  WARMSTARTINFO* warmstartinfo /**< the warm start info to check (may be NULL) */
208  )
209 {
210  return warmstartinfo != NULL && warmstartinfo->lpistate != NULL;
211 }
212 
213 /** Frees the allocated buffer memory of the warm start info. */
214 static
216  SCIP* scip, /**< SCIP data structure */
217  WARMSTARTINFO** warmstartinfo /**< the warm start info to free */
218  )
219 {
220  SCIP_LPI* lpi;
221  BMS_BLKMEM* blkmem;
222 
223  assert(scip != NULL);
224  assert(warmstartinfo != NULL);
225 
226  SCIP_CALL( SCIPgetLPI(scip, &lpi) );
227  blkmem = SCIPblkmem(scip);
228 
229  if( (*warmstartinfo)->lpistate != NULL )
230  {
231  SCIP_CALL( SCIPlpiFreeState(lpi, blkmem, &(*warmstartinfo)->lpistate) );
232  }
233 
234  if( (*warmstartinfo)->lpinorms != NULL )
235  {
236  SCIP_CALL( SCIPlpiFreeNorms(lpi, blkmem, &(*warmstartinfo)->lpinorms) );
237  }
238 
239  SCIPfreeBlockMemory(scip, warmstartinfo);
240 
241  return SCIP_OKAY;
242 }
243 
244 /** A struct containing all information needed to branch on a variable. */
245 typedef struct
246 {
247  SCIP_VAR* branchvar; /**< the variable to branch on */
248  SCIP_Real branchval; /**< the fractional value to branch on */
249  SCIP_Real fracval; /**< the fractional part of the value to branch on (val - floor(val)) */
250  WARMSTARTINFO* downwarmstartinfo; /**< the warm start info containing the lp data from a previous down branch */
251  WARMSTARTINFO* upwarmstartinfo; /**< the warm start info containing the lp data from a previous up branch */
252 } CANDIDATE;
253 
254 /** Allocates the candidate on the buffer and initializes it with default values. */
255 static
257  SCIP* scip, /**< SCIP data structure */
258  CANDIDATE** candidate /**< the candidate to allocate and initialize */
259  )
260 {
261  assert(scip != NULL);
262  assert(candidate != NULL);
264  SCIP_CALL( SCIPallocBlockMemory(scip, candidate) );
266  (*candidate)->downwarmstartinfo = NULL;
267  (*candidate)->upwarmstartinfo = NULL;
268  (*candidate)->branchvar = NULL;
269 
270  return SCIP_OKAY;
271 }
272 
273 /** free the warm starting information for the given candidate */
274 static
276  SCIP* scip, /**< SCIP data structure */
277  CANDIDATE* candidate /**< the candidate to free the warm starting information for */
278  )
279 {
280  assert(scip != NULL);
281  assert(candidate != NULL);
282 
283  LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "freeing warmstart info of candidate <%s>(%u/%u)...\n",
284  SCIPvarGetName(candidate->branchvar),
285  candidate->upwarmstartinfo != NULL, candidate->downwarmstartinfo != NULL);
286 
287  if( candidate->upwarmstartinfo != NULL )
288  {
289  SCIP_CALL( warmStartInfoFree(scip, &candidate->upwarmstartinfo) );
290  }
291  if( candidate->downwarmstartinfo != NULL )
292  {
293  SCIP_CALL( warmStartInfoFree(scip, &candidate->downwarmstartinfo) );
294  }
295 
296  return SCIP_OKAY;
297 }
298 
299 
300 /** Frees the allocated buffer memory of the candidate and clears the contained lpi memories. */
301 static
303  SCIP* scip, /**< SCIP data structure */
304  CANDIDATE** candidate /**< the candidate to free */
305  )
306 {
307  assert(scip != NULL);
308  assert(candidate != NULL);
309 
310  LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "freeing candidate <%s>(%u/%u)...\n",
311  (*candidate) != NULL ? SCIPvarGetName((*candidate)->branchvar) : "none",
312  (*candidate)->upwarmstartinfo != NULL, (*candidate)->downwarmstartinfo != NULL);
313 
314  /* if a candidate is freed, we no longer need the content of the warm start info */
315  SCIP_CALL( candidateFreeWarmStartInfo(scip, *candidate) );
316 
317  SCIPfreeBlockMemory(scip, candidate);
318  return SCIP_OKAY;
319 }
320 
321 /** Store the current lp solution in the warm start info for further usage. */
322 static
324  SCIP* scip, /**< SCIP data structure */
325  CANDIDATE* candidate, /**< the branching candidate */
326  SCIP_Bool down /**< is the info for down branching? */
327  )
328 {
329  SCIP_LPI* lpi;
330  BMS_BLKMEM* blkmem;
331  WARMSTARTINFO* warmstartinfo;
332 
333  assert(scip != NULL);
334  assert(candidate != NULL);
335 
336  SCIP_CALL( SCIPgetLPI(scip, &lpi) );
337  blkmem = SCIPblkmem(scip);
339  if( down )
340  {
341  if( candidate->downwarmstartinfo == NULL )
342  {
343  SCIP_CALL( warmStartInfoCreate(scip, &candidate->downwarmstartinfo) );
344  }
345  warmstartinfo = candidate->downwarmstartinfo;
346  }
347  else
348  {
349  if( candidate->upwarmstartinfo == NULL )
350  {
351  SCIP_CALL( warmStartInfoCreate(scip, &candidate->upwarmstartinfo) );
352  }
353  warmstartinfo = candidate->upwarmstartinfo;
354  }
355 
356  SCIP_CALL( SCIPlpiGetState(lpi, blkmem, &warmstartinfo->lpistate) );
357 
358  SCIP_CALL( SCIPlpiGetNorms(lpi, blkmem, &warmstartinfo->lpinorms) );
359 
360  warmstartinfo->primalfeas = SCIPlpiIsPrimalFeasible(lpi);
361  warmstartinfo->dualfeas = SCIPlpiIsDualFeasible(lpi);
362 
363  assert(warmstartinfo->lpistate != NULL);
364  /* warmstartinfo->lpinorms may be NULL */
365 
366  return SCIP_OKAY;
367 }
368 
369 /** returns whether the candidate has stored warm starting information for the given direction */
370 static
372  CANDIDATE* candidate, /**< the branching candidate */
373  SCIP_Bool down /**< is the info for down branching? */
374  )
375 {
376  assert(candidate != NULL);
377 
378  return warmStartInfoIsAvailable(down ? candidate->downwarmstartinfo : candidate->upwarmstartinfo);
379 }
380 
381 
382 /** loads the warm starting information of the candidate for the given direction */
383 static
385  SCIP* scip, /**< SCIP data structure */
386  CANDIDATE* candidate, /**< the branching candidate */
387  SCIP_Bool down /**< is the info for down branching? */
388  )
389 {
390  WARMSTARTINFO* warmstartinfo;
391 
392  assert(scip != NULL);
393  assert(candidate != NULL);
394 
395  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "loading basis...\n");
396 
397  if( down )
398  warmstartinfo = candidate->downwarmstartinfo;
399  else
400  warmstartinfo = candidate->upwarmstartinfo;
401 
402  /* As we solved the very same LP some time earlier and stored the state (the basis) and the norms, we can now set those in
403  * the LP solver, such that the solution does not (in best case) need any further calculation.
404  * Some iterations may occur, as the conflict analysis may have added some constraints in the meantime. */
405  SCIP_CALL( SCIPsetProbingLPState(scip, &(warmstartinfo->lpistate), &(warmstartinfo->lpinorms), warmstartinfo->primalfeas,
406  warmstartinfo->dualfeas) );
407 
408  /* The state and norms will be freed later by the SCIP framework. Therefore they are set to NULL to enforce that we won't
409  * free them on our own. */
410  assert(warmstartinfo->lpistate == NULL);
411  assert(warmstartinfo->lpinorms == NULL);
412 
413  return SCIP_OKAY;
414 }
415 
416 
417 /** Holds the information needed for branching on a variable. */
418 typedef struct
419 {
420  SCIP_VAR* branchvar; /**< the variable to branch on, may be NULL */
421  SCIP_Real branchval; /**< the fractional value to branch on */
422  SCIP_Real* downlowerbounds; /**< variable lower bounds for down child */
423  SCIP_Real* downupperbounds; /**< variable upper bounds for down child */
424  SCIP_Real* uplowerbounds; /**< variable lower bounds for up child */
425  SCIP_Real* upupperbounds; /**< variable upper bounds for up child */
426  SCIP_Real downdb; /**< dual bound for down branch */
427  SCIP_Real updb; /**< dual bound for the up branch */
428  SCIP_Real proveddb; /**< proven dual bound for the current node */
429  SCIP_Real score; /**< score of the branching decision */
430  SCIP_Bool downdbvalid; /**< Indicator for the validity of the downdb value. Is FALSE, if no actual
431  * branching occurred or the value was determined by an LP not solved to
432  * optimality. */
433  SCIP_Bool updbvalid; /**< Indicator for the validity of the updb value. Is FALSE, if no actual
434  * branching occurred or the value was determined by an LP not solved to
435  * optimality. */
436  SCIP_Bool boundsvalid; /**< are variable bounds for down and up child valid? */
437  int boundssize; /**< size of bounds arrays */
440 /** initialize a branching decsion with default values */
441 static
443  SCIP* scip, /**< SCIP data structure */
444  BRANCHINGDECISION* decision /**< the decision to initialize */
445  )
446 {
447  assert(scip != NULL);
448  assert(decision != NULL);
449 
450  decision->branchvar = NULL;
451  decision->branchval = SCIP_INVALID;
452  decision->downlowerbounds = NULL;
453  decision->downupperbounds = NULL;
454  decision->uplowerbounds = NULL;
455  decision->upupperbounds = NULL;
456  decision->downdb = -SCIPinfinity(scip);
457  decision->downdbvalid = FALSE;
458  decision->updb = -SCIPinfinity(scip);
459  decision->updbvalid = FALSE;
460  decision->boundsvalid = FALSE;
461  decision->proveddb = -SCIPinfinity(scip);
462  decision->score = -SCIPinfinity(scip);
463  decision->boundssize = 0;
464 }
465 
466 
467 /** allocates a branching decision in the buffer and initializes it with default values. */
468 static
470  SCIP* scip, /**< SCIP data structure */
471  BRANCHINGDECISION** decision /**< pointer to the decision to allocate and initialize */
472  )
473 {
474  assert(scip != NULL);
475  assert(decision != NULL);
476 
477  SCIP_CALL( SCIPallocBuffer(scip, decision) );
478 
479  branchingDecisionInit(scip, *decision);
480 
481  return SCIP_OKAY;
482 }
483 
484 /** copies the data from the source branching decision storage to the target storage;
485  * this is used to store the most important information (i.e., the dual bounds obtained) so that it can be used in a
486  * subsequent call in case the LP solution did not change because we only added bound changes that did not forbid the
487  * current LP solution;
488  * however, we do not want to store all the domain changes for the two potential child nodes for this rare case, they
489  * will be identified when processing the child nodes anyway
490  */
491 static
493  BRANCHINGDECISION* sourcedecision, /**< the source branching decision */
494  BRANCHINGDECISION* targetdecision /**< the target branching decision */
495  )
496 {
497  assert(sourcedecision != NULL);
498  assert(targetdecision != NULL);
499 
500  targetdecision->branchvar = sourcedecision->branchvar;
501  targetdecision->branchval = sourcedecision->branchval;
502  targetdecision->downdb = sourcedecision->downdb;
503  targetdecision->downdbvalid = sourcedecision->downdbvalid;
504  targetdecision->updb = sourcedecision->updb;
505  targetdecision->updbvalid = sourcedecision->updbvalid;
506  targetdecision->proveddb = sourcedecision->proveddb;
507  targetdecision->score = sourcedecision->score;
508 
509  assert(targetdecision->downlowerbounds == NULL);
510  assert(targetdecision->downupperbounds == NULL);
511  assert(targetdecision->uplowerbounds == NULL);
512  assert(targetdecision->upupperbounds == NULL);
513  assert(targetdecision->boundsvalid == FALSE);
514  assert(targetdecision->boundssize == 0);
515 }
516 
517 /** Checks whether the given branching decision can be used to branch on. */
518 static
520  BRANCHINGDECISION* decision /**< the branching decision to check */
521  )
522 {
523  assert(decision != NULL);
524 
525  /* a branching decision is deemed valid, if the var pointer is not on the default NULL value (see the allocate method) */
526  return decision->branchvar != NULL;
527 }
528 
529 /* ensure that the array that stores the bounds for both child nodes is large enough */
530 static
532  SCIP* scip, /**< SCIP data structure */
533  BRANCHINGDECISION* decision, /**< branching decision */
534  int nvars /**< number of problem variables */
535  )
536 {
537  assert(decision != NULL);
538 
539  if( decision->boundssize == 0 )
540  {
541  decision->boundssize = nvars;
542  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decision->downlowerbounds, decision->boundssize) );
543  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decision->downupperbounds, decision->boundssize) );
544  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decision->uplowerbounds, decision->boundssize) );
545  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &decision->upupperbounds, decision->boundssize) );
546  }
547  assert(decision->boundssize == nvars);
548 
549  return SCIP_OKAY;
550 }
551 
552 /** Frees the allocated memory of the branching decision. */
553 static
555  SCIP* scip, /**< SCIP data structure */
556  BRANCHINGDECISION** decision /**< pointer to the decision to be freed */
557  )
558 {
559  assert(scip != NULL);
560  assert(decision != NULL);
561 
562  if( (*decision)->boundssize != 0 )
563  {
564  assert((*decision)->downlowerbounds != NULL);
565  assert((*decision)->downupperbounds != NULL);
566  assert((*decision)->uplowerbounds != NULL);
567  assert((*decision)->upupperbounds != NULL);
568 
569  SCIPfreeBlockMemoryArray(scip, &(*decision)->downlowerbounds, (*decision)->boundssize);
570  SCIPfreeBlockMemoryArray(scip, &(*decision)->downupperbounds, (*decision)->boundssize);
571  SCIPfreeBlockMemoryArray(scip, &(*decision)->uplowerbounds, (*decision)->boundssize);
572  SCIPfreeBlockMemoryArray(scip, &(*decision)->upupperbounds, (*decision)->boundssize);
573  }
574 
575  SCIPfreeBuffer(scip, decision);
576 }
577 
578 /** A container to hold the result of a branching. */
579 typedef struct
580 {
581  SCIP_Real objval; /**< The objective value of the solved lp. Only contains meaningful data, if
582  * cutoff == FALSE. */
583  SCIP_Real dualbound; /**< The best dual bound for this branching, may be changed by deeper level
584  * branchings. */
585  SCIP_Longint niterations; /**< The number of probing iterations needed in sub branch. */
586  SCIP_Bool cutoff; /**< Indicates whether the node was infeasible and was cutoff. */
587  SCIP_Bool dualboundvalid; /**< Is the value of the dual bound valid? That means, was the according LP
588  * or the sub problems solved to optimality? */
589  int ndeepestcutoffs; /**< number of cutoffs on the lowest level below this child */
590  SCIP_Real deeperscore; /**< best score computed for the deeper lookahead level */
591  SCIP_Real bestgain; /**< best gain (w.r.t. to the base lp) on the lowest level below this child */
592  SCIP_Real totalgains; /**< sum over all gains that are valid in both children */
593  int ntotalgains; /**< number of gains summed in totalgains */
594  int ndeepestnodes; /**< number of nodes processed in the deepest level */
597 /** Allocates a branching result in the buffer. */
598 static
600  SCIP* scip, /**< SCIP data structure */
601  BRANCHINGRESULTDATA** resultdata /**< pointer to the result to be allocated */
602  )
603 {
604  assert(scip != NULL);
605  assert(resultdata != NULL);
607  SCIP_CALL( SCIPallocBuffer(scip, resultdata) );
609  return SCIP_OKAY;
610 }
611 
612 /** Initiates the branching result with default values. */
613 static
615  SCIP* scip, /**< SCIP data structure */
616  BRANCHINGRESULTDATA* resultdata /**< pointer to the result to be initialized */
617  )
618 {
619  assert(scip != NULL);
620  assert(resultdata != NULL);
621 
622  resultdata->objval = -SCIPinfinity(scip);
623  resultdata->dualbound = -SCIPinfinity(scip);
624  resultdata->cutoff = FALSE;
625  resultdata->dualboundvalid = FALSE;
626  resultdata->niterations = 0;
627  resultdata->ndeepestcutoffs = 0;
628  resultdata->deeperscore = -SCIPinfinity(scip);
629  resultdata->bestgain = 0.;
630  resultdata->totalgains = 0.;
631  resultdata->ntotalgains = 0;
632  resultdata->ndeepestnodes = 0;
633 }
634 
635 /** Copies the data from the source to the target. */
636 static
638  BRANCHINGRESULTDATA* sourcedata, /**< the source branching result */
639  BRANCHINGRESULTDATA* targetdata /**< the target branching result */
640  )
641 {
642  assert(sourcedata != NULL);
643  assert(targetdata != NULL);
644 
645  targetdata->cutoff = sourcedata->cutoff;
646  targetdata->objval = sourcedata->objval;
647  targetdata->dualbound = sourcedata->dualbound;
648  targetdata->dualboundvalid = sourcedata->dualboundvalid;
649  targetdata->niterations = sourcedata->niterations;
650  targetdata->ndeepestcutoffs = sourcedata->ndeepestcutoffs;
651  targetdata->deeperscore = sourcedata->deeperscore;
652  targetdata->bestgain = sourcedata->bestgain;
653  targetdata->totalgains = sourcedata->totalgains;
654  targetdata->ntotalgains = sourcedata->ntotalgains;
655  targetdata->ndeepestnodes = sourcedata->ndeepestnodes;
656 }
657 
658 /** Frees the allocated buffer memory of the branching result. */
659 static
661  SCIP* scip, /**< SCIP data structure */
662  BRANCHINGRESULTDATA** resultdata /**< pointer to the result to be freed */
663  )
664 {
665  assert(scip != NULL);
666  assert(resultdata != NULL);
667 
668  SCIPfreeBuffer(scip, resultdata);
669 }
670 
671 /** a container to hold the result of a second-level LP */
672 typedef struct
673 {
674  SCIP_Real lpobjval; /**< the objective value of the solved lp; only contains meaningful data, if
675  * cutoff == FALSE. */
676  SCIP_Real branchval1; /**< new bound for first branching variable */
677  SCIP_Real branchval2; /**< new bound for second branching variable */
678  unsigned int branchvar1:30; /**< problem index of first branching variable */
679  unsigned int branchvar2:30; /**< problem index of second branching variable */
680  unsigned int branchdir1:1; /**< branching direction for first branching variable (0:down, 1:up) */
681  unsigned int branchdir2:1; /**< branching direction for second branching variable (0:down, 1:up) */
682  unsigned int cutoff:1; /**< indicates whether the node was infeasible and was cut off. */
683  unsigned int valid:1; /**< is the lpobjval a valid dual bound? */
684 } LEVEL2RESULT;
685 
686 /** a container to hold the results of all second-level LPs */
687 typedef struct
688 {
689  LEVEL2RESULT** level2results; /**< array with all level2 results */
690  SCIP_Real branchval1; /**< new bound for first branching variable */
691  SCIP_Real branchval2; /**< new bound for second branching variable */
692  int nlevel2results; /**< number of level2 results stored */
693  int level2resultssize; /**< size of level2results array */
694  unsigned int branchvar1:30; /**< problem index of first branching variable */
695  unsigned int branchvar2:30; /**< problem index of second branching variable */
696  unsigned int branchdir1:1; /**< branching direction for first branching variable (0:down, 1:up) */
697  unsigned int branchdir2:1; /**< branching direction for second branching variable (0:down, 1:up) */
699 
700 /** allocates a double branching result in the memory and fills it with the information stored in the level 2 data */
701 static
703  SCIP* scip, /**< SCIP data structure */
704  LEVEL2DATA* data, /**< level2 data */
705  LEVEL2RESULT** result /**< pointer to the result to be allocated */
706  )
707 {
708  assert(scip != NULL);
709  assert(data != NULL);
710  assert(result != NULL);
712  SCIP_CALL( SCIPallocBlockMemory(scip, result) );
713 
714  if( data->branchvar1 < data->branchvar2 )
715  {
716  (*result)->branchval1 = data->branchval1;
717  (*result)->branchval2 = data->branchval2;
718  (*result)->branchvar1 = data->branchvar1; /*lint !e732*/
719  (*result)->branchvar2 = data->branchvar2; /*lint !e732*/
720  (*result)->branchdir1 = data->branchdir1;
721  (*result)->branchdir2 = data->branchdir2;
722  }
723  else
724  {
725  (*result)->branchval1 = data->branchval2;
726  (*result)->branchval2 = data->branchval1;
727  (*result)->branchvar1 = data->branchvar2; /*lint !e732*/
728  (*result)->branchvar2 = data->branchvar1; /*lint !e732*/
729  (*result)->branchdir1 = data->branchdir2;
730  (*result)->branchdir2 = data->branchdir1;
731  }
732 
733  return SCIP_OKAY;
734 }
735 
736 
737 #ifdef SCIP_DEBUG
738 /** prints the double branching result */
739 static
740 void level2resultPrint(
741  SCIP* scip, /**< SCIP data structure */
742  LEVEL2RESULT* result /**< pointer to the result to be initialized */
743  )
744 {
745  SCIP_VAR** vars;
746 
747  assert(result != NULL);
748 
749  vars = SCIPgetVars(scip);
750 
752  "level 2 result: <%s> %s %g + <%s> %s %g: lpval: %.9g, inf: %d, valid: %d\n",
753  SCIPvarGetName(vars[result->branchvar1]), result->branchdir1 ? ">=" : "<=", result->branchval1,
754  SCIPvarGetName(vars[result->branchvar2]), result->branchdir2 ? ">=" : "<=", result->branchval2,
755  result->lpobjval, result->cutoff, result->valid);
756 }
757 #else
758 #define level2resultPrint(scip,result) /**/
759 #endif
760 
761 /** frees the allocated memory of the double branching result */
762 static
763 void level2resultFree(
764  SCIP* scip, /**< SCIP data structure */
765  LEVEL2RESULT** result /**< pointer to the result to be freed */
766  )
767 {
768  assert(scip != NULL);
769  assert(result != NULL);
770 
771  SCIPfreeBlockMemory(scip, result);
772 }
774 /** returns TRUE iff both level 2 results are equal; two branchings are equal if they branched on the same variables
775  * with the same values
776  */
777 static
779  LEVEL2RESULT* result1, /**< first level 2 result */
780  LEVEL2RESULT* result2 /**< second level 2 result */
781  )
782 {
783  assert(result1->branchvar1 < result1->branchvar2);
784  assert(result2->branchvar1 < result2->branchvar2);
785 
786  /* check all cases */
787  if( result1->branchvar1 != result2->branchvar1
788  || result1->branchvar2 != result2->branchvar2
789  || result1->branchdir1 != result2->branchdir1
790  || result1->branchdir2 != result2->branchdir2
791  || result1->branchval1 > result2->branchval1 + 0.5
792  || result1->branchval1 < result2->branchval1 - 0.5
793  || result1->branchval2 > result2->branchval2 + 0.5
794  || result1->branchval2 < result2->branchval2 - 0.5)
795  return FALSE;
796 
797  return TRUE;
798 }
799 
800 /** allocates the level2 data */
801 static
803  SCIP* scip, /**< SCIP data structure */
804  LEVEL2DATA** data /**< pointer to the data to be allocated */
805  )
806 {
807  assert(scip != NULL);
808  assert(data != NULL);
809 
810  SCIP_CALL( SCIPallocBlockMemory(scip, data) );
811 
812  (*data)->level2results = NULL;
813  (*data)->branchval1 = -SCIPinfinity(scip);
814  (*data)->branchval2 = -SCIPinfinity(scip);
815  (*data)->nlevel2results = 0;
816  (*data)->level2resultssize = 0;
817  (*data)->branchvar1 = 0;
818  (*data)->branchvar2 = 0;
819  (*data)->branchdir1 = 0;
820  (*data)->branchdir2 = 0;
821 
822  return SCIP_OKAY;
823 }
824 
825 /** frees the allocated memory of the level2 data */
826 static
827 void level2dataFree(
828  SCIP* scip, /**< SCIP data structure */
829  LEVEL2DATA** data /**< pointer to the data to be freed */
830  )
831 {
832  assert(scip != NULL);
833  assert(data != NULL);
834 
835  while( (*data)->nlevel2results > 0 )
836  {
837  --(*data)->nlevel2results;
838  level2resultFree(scip, &((*data)->level2results[(*data)->nlevel2results]));
839  }
840  assert((*data)->nlevel2results == 0);
841 
842  if( (*data)->level2results != NULL )
843  {
844  SCIPfreeBlockMemoryArray(scip, &(*data)->level2results, (*data)->level2resultssize);
845  }
846 
847  SCIPfreeBlockMemory(scip, data);
848 }
849 
850 /** ensures that level2results can store at least one more element */
851 static
853  SCIP* scip, /**< SCIP data structure */
854  LEVEL2DATA* data /**< level2 data */
855  )
856 {
857  assert(scip != NULL);
858  assert(data != NULL);
859 
860  if( data->nlevel2results >= data->level2resultssize )
861  {
862  int newsize = SCIPcalcMemGrowSize(scip, data->level2resultssize + 1);
863 
864  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &data->level2results, data->level2resultssize, newsize) );
865  data->level2resultssize = newsize;
866  }
868  return SCIP_OKAY;
869 }
870 
871 /** get a result from the level 2 data */
872 static
874  SCIP* scip, /**< SCIP data structure */
875  LEVEL2DATA* data, /**< level2 data */
876  LEVEL2RESULT** result /**< pointer to store result */
877  )
878 {
879  LEVEL2RESULT* tmpresult;
880  int i;
881 
882  assert(data != NULL);
883  assert(result != NULL);
884 
885  *result = NULL;
886 
887  /* we branched twice on the same variable; the result cannot be stored already */
888  if( data->branchvar1 == data->branchvar2 )
889  {
890  assert(SCIPvarGetType(SCIPgetVars(scip)[data->branchvar1]) != SCIP_VARTYPE_BINARY);
891  return SCIP_OKAY;
892  }
893 
894  SCIP_CALL( level2resultCreateFromData(scip, data, &tmpresult) );
895 
896  /* search for a level 2 result with the same branching decisions */
897  for( i = 0; i < data->nlevel2results; ++i )
898  {
899  if( level2resultEqual(data->level2results[i], tmpresult) )
900  {
901  *result = data->level2results[i];
902  }
903  }
904 
905  level2resultFree(scip, &tmpresult);
906 
907  return SCIP_OKAY;
908 }
909 
910 
911 /** store a new result in the level 2 data */
912 static
914  SCIP* scip, /**< SCIP data structure */
915  LEVEL2DATA* data, /**< level2 data */
916  SCIP_Real lpobjval, /**< LP objective value */
917  SCIP_Bool cutoff, /**< was the LP infeasible? */
918  SCIP_Bool valid, /**< is the LP value a valid dual bound? */
919  SCIP_Bool* duplicate /**< pointer to store whether information for the same branching decisions was already stored */
920  )
921 {
922  LEVEL2RESULT* result;
923  int i;
924 
925  assert(scip != NULL);
926  assert(data != NULL);
927  assert(duplicate != NULL);
929  *duplicate = FALSE;
930 
931  /* we branched twice on the same variable; the result cannot be re-used lated */
932  if( data->branchvar1 == data->branchvar2 )
933  {
934  assert(SCIPvarGetType(SCIPgetVars(scip)[data->branchvar1]) != SCIP_VARTYPE_BINARY);
935  return SCIP_OKAY;
936  }
937 
938  SCIP_CALL( level2dataEnsureSize(scip, data) );
939 
940  SCIP_CALL( level2resultCreateFromData(scip, data, &result) );
941 
942  result->lpobjval = lpobjval;
943  result->cutoff = cutoff;
944  result->valid = valid;
945 
946  /* search for a level 2 result with the same branching decisions*/
947  for( i = 0; i < data->nlevel2results; ++i )
948  {
949  if( level2resultEqual( data->level2results[i], result) )
950  {
951  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "same level2 node already processed:\n");
952  level2resultPrint(scip, data->level2results[i]);
953  level2resultPrint(scip, result);
954  *duplicate = TRUE;
955  }
956  }
957 
958  data->level2results[data->nlevel2results] = result;
959  ++data->nlevel2results;
960  assert(data->nlevel2results <= data->level2resultssize);
961 
962  return SCIP_OKAY;
963 }
964 
965 
966 /** The data that is preserved over multiple runs of the branching rule. */
967 typedef struct
968 {
969  BRANCHINGDECISION* olddecision; /**< The previous decision that gets used for the case that in the previous run
970  * only non-violating implied binary constraints were added.*/
971  SCIP_Longint oldnnodelpiterations; /**< node LP iterations when previous branching decision was stored */
972  SCIP_Longint oldnnodelps; /**< node LPs when previous branching decision was stored */
973  SCIP_Longint oldntotalnodes; /**< node at which previous branching decision was stored */
974  SCIP_Longint* lastbranchid; /**< The node id at which the var was last branched on (for a given branching
975  * var). */
976  SCIP_Longint* lastbranchnlps; /**< The number of (non-probing) LPs that where solved when the var was last
977  * branched on. */
978  SCIP_Real* lastbranchlpobjval; /**< The lp objval at which var was last branched on. */
979  BRANCHINGRESULTDATA** lastbranchupres; /**< The result of the last up branching for a given var. */
980  BRANCHINGRESULTDATA** lastbranchdownres; /**< The result of the last down branching for a given var. */
981  int restartindex; /**< The index at which the iteration over the number of candidates starts. */
982  int nvars; /**< The number of variables that can be stored in the arrays. */
985 /** The parameter that can be changed by the user/caller and alter the behaviour of the lookahead branching. */
986 typedef struct
987 {
988  SCIP_Longint reevalage; /**< The number of "normal" (not probing) lps that may have been solved before
989  * we stop using old data and start recalculating new first level data. */
990  SCIP_Longint reevalagefsb; /**< The number of "normal" (not probing) lps that may have been solved before
991  * we stop using old FSB data and start recalculating new first level data. */
992  int maxnviolatedcons; /**< The number of constraints (domain reductions and binary constraints) we
993  * want to gather before restarting the run. Set to -1 for an unbounded
994  * number of constraints. */
995  int maxnviolatedbincons;/**< The number of binary constraints we want to gather before restarting the
996  * run. Set to -1 for an undbounded number of binary constraints. */
997  int maxnviolateddomreds;/**< The number of domain reductions we want to gather before restarting the
998  * run. Set to -1 for an undbounded number of domain reductions. */
999  int recursiondepth; /**< How deep should the recursion go? Default for Lookahead: 2 */
1000  int maxncands; /**< If abbreviated == TRUE, at most how many candidates should be handled at the base node? */
1001  int maxndeepercands; /**< If abbreviated == TRUE, at most how many candidates should be handled in deeper nodes? */
1002  SCIP_Bool usedomainreduction; /**< indicates whether the data for domain reductions should be gathered and
1003  * used. */
1004  SCIP_Bool mergedomainreductions; /**< should domain reductions of feasible siblings should be merged? */
1005  SCIP_Bool prefersimplebounds; /**< should domain reductions only be applied if there are simple bound changes? */
1006  SCIP_Bool onlyvioldomreds; /**< Should only domain reductions that violate the LP solution be applied? */
1007  SCIP_Bool usebincons; /**< indicates whether the data for the implied binary constraints should
1008  * be gathered and used */
1009  int addbinconsrow; /**< should binary constraints be added as rows to the base LP?
1010  * (0: no, 1: separate, 2: as initial rows) */
1011  SCIP_Bool addnonviocons; /**< Should constraints be added, that are not violated by the base LP? */
1012  SCIP_Bool abbreviated; /**< Should the abbreviated version be used? */
1013  SCIP_Bool reusebasis; /**< If abbreviated == TRUE, should the solution lp-basis of the FSB run be
1014  * used in the first abbreviated level? */
1015  SCIP_Bool storeunviolatedsol; /**< Should a solution/decision be stored, to speed up the next iteration
1016  * after adding the constraints/domreds? */
1017  SCIP_Bool abbrevpseudo; /**< If abbreviated == TRUE, should pseudocost values be used, to approximate
1018  * the scoring? */
1019  SCIP_Bool level2avgscore; /**< should the average score be used for uninitialized scores in level 2? */
1020  SCIP_Bool level2zeroscore; /**< should uninitialized scores in level 2 be set to zero? */
1021  SCIP_Bool addclique; /**< add binary constraints with two variables found at the root node also as a clique? */
1022  SCIP_Bool propagate; /**< Should the problem be propagated before solving each inner node? */
1023  SCIP_Bool uselevel2data; /**< should branching data generated at depth level 2 be stored for re-using it? */
1024  SCIP_Bool applychildbounds; /**< should bounds known for child nodes be applied? */
1025  SCIP_Bool enforcemaxdomreds; /**< should the maximum number of domain reductions maxnviolateddomreds be enforced? */
1026  SCIP_Bool updatebranchingresults; /**< should branching results (and scores) be updated w.r.t. proven dual bounds? */
1027  SCIP_Bool inscoring; /**< are we currently in FSB-scoring (only used internally) */
1028  int maxproprounds; /**< maximum number of propagation rounds to perform at temporary nodes
1029  * (-1: unlimited, 0: SCIP default) */
1030  char scoringfunction; /**< scoring function at base level */
1031  char deeperscoringfunction; /**< scoring function at deeper levels */
1032  char scoringscoringfunction;/**< scoring function for FSB scoring */
1033  SCIP_Real minweight; /**< weight of the min gain of two child problems */
1034  SCIP_Real worsefactor; /**< if the FSB score is of a candidate is worse than the best by this factor, skip this candidate (-1: disable) */
1035  SCIP_Bool filterbymaxgain; /**< should lookahead branching only be applied if the max gain in level 1 is not uniquely that of the best candidate? */
1039 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC)
1040 #define MAXRESULT SCIP_DELAYNODE
1042 /** returns a human readable name for the given result enum value */
1043 static
1044 const char* getStatusString(
1045  SCIP_RESULT result /**< enum value to get the string representation for */
1046  )
1048  assert(result >= 1);
1049  assert(result <= 18);
1051  switch( result )
1052  {
1053  case SCIP_DIDNOTRUN:
1054  return "SCIP_DIDNOTRUN";
1055  case SCIP_DELAYED:
1056  return "SCIP_DELAYED";
1057  case SCIP_DIDNOTFIND:
1058  return "SCIP_DIDNOTFIND";
1059  case SCIP_FEASIBLE:
1060  return "SCIP_FEASIBLE";
1061  case SCIP_INFEASIBLE:
1062  return "SCIP_INFEASIBLE";
1063  case SCIP_UNBOUNDED:
1064  return "SCIP_UNBOUNDED";
1065  case SCIP_CUTOFF:
1066  return "SCIP_CUTOFF";
1067  case SCIP_SEPARATED:
1068  return "SCIP_SEPARATED";
1069  case SCIP_NEWROUND:
1070  return "SCIP_NEWROUND";
1071  case SCIP_REDUCEDDOM:
1072  return "SCIP_REDUCEDDOM";
1073  case SCIP_CONSADDED:
1074  return "SCIP_CONSADDED";
1075  case SCIP_CONSCHANGED:
1076  return "SCIP_CONSCHANGED";
1077  case SCIP_BRANCHED:
1078  return "SCIP_BRANCHED";
1079  case SCIP_SOLVELP:
1080  return "SCIP_SOLVELP";
1081  case SCIP_FOUNDSOL:
1082  return "SCIP_FOUNDSOL";
1083  case SCIP_SUSPENDED:
1084  return "SCIP_SUSPENDED";
1085  case SCIP_SUCCESS:
1086  return "SCIP_SUCCESS";
1087  case SCIP_DELAYNODE:
1088  return "SCIP_DELAYNODE";
1089  default:
1090  SCIPerrorMessage("result code %d not treated in lookahead branching rule\n", result);
1091  SCIPABORT();
1092  return "UNKNOWN";
1093  }
1094 }
1095 #endif
1096 
1097 #ifdef SCIP_STATISTIC
1098 /** The data used for some statistical analysis. */
1099 typedef struct
1100 {
1101  int* nresults; /**< Array of counters for each result state the lookahead branching finished.
1102  * The first (0) entry is unused, as the result states are indexed 1-based
1103  * and we use this index as our array index. */
1104  int* nsinglecutoffs; /**< The number of single cutoffs on a (probing) node per probingdepth. */
1105  int* nfullcutoffs; /**< The number of double cutoffs on a (probing) node per probingdepth. */
1106  int* nlpssolved; /**< The number of all lps solved for a given probingdepth (incl. FSB). */
1107  int* nlpssolvedfsb; /**< The number of lps solved by the initial FSB to get the FSB scores. */
1108  int* nduplicatelps; /**< The number of lps solved for duplicate grand-child nodes. */
1109  SCIP_Longint* nlpiterations; /**< The number of all lp iterations needed for a given probingdepth
1110  * (incl. FSB). */
1111  SCIP_Longint* nlpiterationsfsb; /**< The number of lp iterations needed to get the FSB scores. */
1112  int* npropdomred; /**< The number of domain reductions based on domain propagation per
1113  * progingdepth. */
1114  int* noldbranchused; /**< The number of times old branching data is used (see the reevalage
1115  * parameter in the CONFIGURATION struct) */
1116  int* noldbranchusedfsb; /**< The number of times old FSB scoring data is used (see the reevalagefsb
1117  * parameter in the CONFIGURATION struct) */
1118  int* chosenfsbcand; /**< If abbreviated, this is the number of times each candidate was finally
1119  * chosen by the following LAB */
1120  int* stopafterfsb; /**< If abbreviated, this is the number of times the rule was stopped after
1121  * scoring candidates by FSB, e.g., by adding constraints or domreds. */
1122  int* cutoffafterfsb; /**< If abbreviated, this is the number of times the rule was stopped after
1123  * scoring candidates by FSB because of a found cutoff. */
1124  int* domredafterfsb; /**< If abbreviated, this is the number of times the rule was stopped after
1125  * scoring candidates by FSB because of a found domain reduction. */
1126  int nsinglecandidate; /**< number of times a single candidate was given to the recursion routine */
1127  int nsingleafterfilter; /**< number of times a single candidate remained after filtering */
1128  int noldcandidate; /**< number of times the old candidate from last call with nonviolating
1129  * reductions was branched on */
1130  int nlperrorcalls; /**< number of times an LP error occured and LAB branched without completely
1131  * evaluating all candidates */
1132  int nlimitcalls; /**< number of times a time limit was reached and LAB branched without
1133  * completely evaluating all candidates */
1134  int ntotalresults; /**< The total sum of the entries in nresults. */
1135  int nbinconst; /**< The number of binary constraints added to the base node. */
1136  int nbinconstvio; /**< The number of binary constraints added to the base node, that are violated
1137  * by the LP at that node. */
1138  int ndomred; /**< The number of domain reductions added to the base node. */
1139  int ndomredvio; /**< The number of domain reductions added to the base node, that are violated
1140  * by the LP at that node. */
1141  int ndepthreached; /**< The number of times the branching was aborted due to a too small depth. */
1142  int ndomredcons; /**< The number of binary constraints ignored, as they would be dom reds. */
1143  int ncutoffproofnodes; /**< The number of nodes needed to prove all found cutoffs. */
1144  int ndomredproofnodes; /**< The number of nodes needed to prove all found domreds. */
1145  int ncliquesadded; /**< The number of cliques added in the root node. */
1146  int maxnbestcands; /**< if abbreviated, this is the maximum number of candidates to investigate */
1147  int recursiondepth; /**< The recursiondepth of the LAB. Can be used to access the depth-dependent
1148  * arrays contained in the statistics. */
1149 } STATISTICS;
1150 
1151 /** Initializes the statistics with the start values. */
1152 static
1153 void statisticsInit(
1154  STATISTICS* statistics /**< the statistics to be initialized */
1155  )
1156 {
1157  int i;
1158 
1159  assert(statistics != NULL);
1160  assert(statistics->recursiondepth > 0);
1161 
1162  statistics->nsinglecandidate = 0;
1163  statistics->nsingleafterfilter = 0;
1164  statistics->noldcandidate = 0;
1165  statistics->nlperrorcalls = 0;
1166  statistics->nlimitcalls = 0;
1167  statistics->ntotalresults = 0;
1168  statistics->nbinconst = 0;
1169  statistics->nbinconstvio = 0;
1170  statistics->ndomredvio = 0;
1171  statistics->ndepthreached = 0;
1172  statistics->ndomred = 0;
1173  statistics->ndomredcons = 0;
1174  statistics->ncutoffproofnodes = 0;
1175  statistics->ndomredproofnodes = 0;
1176  statistics->ncliquesadded = 0;
1177 
1178  for( i = 0; i <= MAXRESULT; i++)
1179  {
1180  statistics->nresults[i] = 0;
1181  }
1182 
1183  for( i = 0; i < statistics->recursiondepth; i++ )
1184  {
1185  statistics->noldbranchused[i] = 0;
1186  statistics->noldbranchusedfsb[i] = 0;
1187  statistics->npropdomred[i] = 0;
1188  statistics->nfullcutoffs[i] = 0;
1189  statistics->nlpssolved[i] = 0;
1190  statistics->nlpssolvedfsb[i] = 0;
1191  statistics->nduplicatelps[i] = 0;
1192  statistics->nlpiterations[i] = 0;
1193  statistics->nlpiterationsfsb[i] = 0;
1194  statistics->nsinglecutoffs[i] = 0;
1195  statistics->stopafterfsb[i] = 0;
1196  statistics->cutoffafterfsb[i] = 0;
1197  statistics->domredafterfsb[i] = 0;
1198  }
1199 
1200  for( i = 0; i < statistics->maxnbestcands; i++ )
1201  {
1202  statistics->chosenfsbcand[i] = 0;
1203  }
1204 }
1205 
1206 /** Prints the content of the statistics to stdout. */
1207 static
1208 void statisticsPrint(
1209  SCIP* scip, /**< SCIP data structure */
1210  STATISTICS* statistics /**< the statistics to print */
1211  )
1212 {
1213  assert(scip != NULL);
1214  assert(statistics != NULL);
1215  assert(statistics->recursiondepth > 0);
1216 
1217  /* only print something, if we have any statistics */
1218  if( statistics->ntotalresults > 0 )
1219  {
1220  int i;
1221 
1222  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Lookahead Branching was called <%i> times.\n", statistics->ntotalresults);
1223 
1224  for( i = 1; i <= MAXRESULT; i++ )
1225  {
1226  SCIP_RESULT currentresult = (SCIP_RESULT)i;
1227  /* see type_result.h for the id <-> enum mapping */
1228  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Result <%s> was chosen <%i> times\n", getStatusString(currentresult),
1229  statistics->nresults[i]);
1230  }
1231 
1232  for( i = 0; i < statistics->maxnbestcands; i++ )
1233  {
1234  if( statistics->chosenfsbcand[i] > 0 )
1235  {
1236  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "The %i. variable (w.r.t. the FSB score) was chosen as the final result %i times.\n",
1237  i+1, statistics->chosenfsbcand[i]);
1238  }
1239  }
1240 
1241  for( i = 0; i < statistics->recursiondepth; i++ )
1242  {
1243  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, branching was stopped after the scoring FSB %i times, %i times because of a cutoff and %i times because of a domain reduction\n",
1244  i, statistics->stopafterfsb[i], statistics->cutoffafterfsb[i], statistics->domredafterfsb[i]);
1245  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, <%i> fullcutoffs and <%i> single cutoffs were found.\n",
1246  i, statistics->nfullcutoffs[i], statistics->nsinglecutoffs[i]);
1247  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, <%i> LPs were solved, <%i> of them to calculate the FSB score, <%i> were saved for duplicate grandchildren.\n",
1248  i, statistics->nlpssolved[i], statistics->nlpssolvedfsb[i], statistics->nduplicatelps[i]);
1249  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, <%" SCIP_LONGINT_FORMAT "> iterations were needed to solve the LPs, <%"
1250  SCIP_LONGINT_FORMAT "> of them to calculate the FSB score.\n", i, statistics->nlpiterations[i],
1251  statistics->nlpiterationsfsb[i]);
1252  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, a decision was discarded <%i> times due to domain reduction because of"
1253  " propagation.\n", i, statistics->npropdomred[i]);
1254  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "In depth <%i>, old LAB branching results were used in <%i> cases, old FSB scores in <%d> cases.\n",
1255  i, statistics->noldbranchused[i], statistics->noldbranchusedfsb[i]);
1256  }
1257 
1258  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "One single branching candidate was given <%i> times, after filtering, a single candidate remained <%i> times.\n",
1259  statistics->nsinglecandidate, statistics->nsingleafterfilter);
1260  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "The old branching candidate was used <%i> times.\n",
1261  statistics->noldcandidate);
1262  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "An LP error led to branching before all candidates were evaluated <%i> times.\n",
1263  statistics->nlperrorcalls);
1264  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "A reached (time) limit led to branching before all candidates were evaluated <%i> times.\n",
1265  statistics->nlimitcalls);
1266  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Depth limit was reached <%i> times.\n", statistics->ndepthreached);
1267  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Ignored <%i> binary constraints, that would be domain reductions.\n",
1268  statistics->ndomredcons);
1269  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Added <%i> binary constraints, of which <%i> where violated by the base LP.\n",
1270  statistics->nbinconst, statistics->nbinconstvio);
1271  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Reduced the domain of <%i> vars, <%i> of them where violated by the base LP.\n",
1272  statistics->ndomred, statistics->ndomredvio);
1273  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Added <%i> cliques found as binary constraint in the root node\n",
1274  statistics->ncliquesadded);
1275  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Needed <%i> additional nodes to prove the cutoffs of base nodes\n",
1276  statistics->ncutoffproofnodes);
1277  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Needed <%i> additional nodes to prove the domain reductions\n",
1278  statistics->ndomredproofnodes);
1279  }
1280 }
1281 
1282 /** Helper struct to store the statistical data needed in a single run. */
1283 typedef struct
1284 {
1285  int ncutoffproofnodes; /**< The number of nodes needed to prove the current cutoff. */
1286 } LOCALSTATISTICS;
1287 
1288 /** Allocates the local statistics in buffer memory and initializes it with default values. */
1289 static
1290 SCIP_RETCODE localStatisticsAllocate(
1291  SCIP* scip, /**< SCIP data structure */
1292  LOCALSTATISTICS** localstats /**< pointer to the local statistics to allocate and initialize */
1293  )
1294 {
1295  assert(scip != NULL);
1296  assert(localstats != NULL);
1297 
1298  SCIP_CALL( SCIPallocBuffer(scip, localstats) );
1299 
1300  (*localstats)->ncutoffproofnodes = 0;
1301 
1302  return SCIP_OKAY;
1303 }
1304 
1305 /** Frees the allocated buffer memory of the local statistics. */
1306 static
1307 void localStatisticsFree(
1308  SCIP* scip, /**< SCIP data structure */
1309  LOCALSTATISTICS** localstats /**< pointer to the local statistics to be freed */
1310  )
1311 {
1312  assert(scip != NULL);
1313  assert(localstats != NULL);
1314 
1315  SCIPfreeBuffer(scip, localstats);
1316 }
1317 #endif
1318 
1319 /** branching rule data */
1320 struct SCIP_BranchruleData
1321 {
1322  CONFIGURATION* config; /**< the parameter that influence the behaviour of the lookahead branching */
1323  PERSISTENTDATA* persistent; /**< the data that persists over multiple branching decisions */
1324  SCIP_Bool isinitialized; /**< indicates whether the fields in this struct are initialized */
1325 #ifdef SCIP_STATISTIC
1326  STATISTICS* statistics; /**< statistical data container */
1327 #endif
1328 };
1329 
1330 /** all constraints that were created and may be added to the base node */
1331 typedef struct
1332 {
1333  SCIP_VAR*** consvars; /**< array containing the variables for each constraint to be created */
1334  int* nconsvars; /**< number of vars in each element of 'consvars' */
1335  SCIP_Bool* violated; /**< indicating whether a constraint is violated by the base solution */
1336  int nelements; /**< number of elements in 'consvars' and 'nconsvars' */
1337  int memorysize; /**< number of entries that the array 'consvars' may hold before the
1338  * array is reallocated. */
1339  int nviolatedcons; /**< number of constraints that are violated by the base LP solution. */
1340 } CONSTRAINTLIST;
1341 
1342 /** Allocate and initialize the list holding the constraints. */
1343 static
1345  SCIP* scip, /**< SCIP data structure */
1346  CONSTRAINTLIST** conslist, /**< Pointer to the list to be allocated and initialized. */
1347  int startsize /**< The number of entries the list initially can hold. */
1348  )
1350  assert(scip != NULL);
1351  assert(conslist != NULL);
1352  assert(startsize > 0);
1353 
1354  SCIP_CALL( SCIPallocBuffer(scip, conslist) );
1355  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*conslist)->consvars, startsize) );
1356  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*conslist)->nconsvars, startsize) );
1357  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*conslist)->violated, startsize) );
1358 
1359  /* We start without any constraints */
1360  (*conslist)->nelements = 0;
1361  (*conslist)->memorysize = startsize;
1362  (*conslist)->nviolatedcons = 0;
1363 
1364  return SCIP_OKAY;
1365 }
1366 
1367 /** Append an element to the end of the list of constraints. */
1368 static
1370  SCIP* scip, /**< SCIP data structure */
1371  CONSTRAINTLIST* list, /**< list to add the consvars to */
1372  SCIP_VAR** consvars, /**< array of variables for the constraint to be created later */
1373  int nconsvars, /**< number of elements in 'consvars' */
1374  SCIP_Bool violated /**< indicates whether the constraint is violated by the base lp */
1375  )
1376 {
1377  assert(scip != NULL);
1378  assert(list != NULL);
1379  assert(consvars != NULL);
1380  assert(nconsvars > 0);
1381 
1382  /* In case the list tries to hold more elements than it has space, reallocate */
1383  if( list->memorysize == list->nelements )
1384  {
1385  /* resize the array, such that it can hold the new element */
1386  int newmemsize = SCIPcalcMemGrowSize(scip, list->memorysize + 1);
1387  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &list->consvars, list->memorysize, newmemsize) );
1388  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &list->nconsvars, list->memorysize, newmemsize) );
1389  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &list->violated, list->memorysize, newmemsize) );
1390  list->memorysize = newmemsize;
1391  }
1392 
1393  /* Set the new vars at the first unused place, which is the length used as index */
1394  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &list->consvars[list->nelements], consvars, nconsvars) ); /*lint !e866*/
1395  list->nconsvars[list->nelements] = nconsvars;
1396  list->violated[list->nelements] = violated;
1397  list->nelements++;
1398 
1399  return SCIP_OKAY;
1400 }
1401 
1402 /** Free all resources of a constraint list in opposite order to the allocation. */
1403 static
1404 void constraintListFree(
1405  SCIP* scip, /**< SCIP data structure */
1406  CONSTRAINTLIST** conslist /**< Pointer to the list to be freed. */
1407  )
1408 {
1409  int i;
1410 
1411  assert(scip != NULL);
1412  assert(conslist != NULL);
1413 
1414  for( i = 0; i < (*conslist)->nelements; i++ )
1415  {
1416  SCIPfreeBlockMemoryArray(scip, &(*conslist)->consvars[i], (*conslist)->nconsvars[i]);
1417  }
1418 
1419  SCIPfreeBlockMemoryArray(scip, &(*conslist)->violated, (*conslist)->memorysize);
1420  SCIPfreeBlockMemoryArray(scip, &(*conslist)->nconsvars, (*conslist)->memorysize);
1421  SCIPfreeBlockMemoryArray(scip, &(*conslist)->consvars, (*conslist)->memorysize);
1422  SCIPfreeBuffer(scip, conslist);
1423 }
1424 
1425 /**
1426  * list of binary variables currently branched on
1427  * a down branching (x <= 0) is saved as the negated variable (1-x)
1428  * an up branching (x >= 1) is saved as the original variable (x)
1429  * these variables are used to build the binary constraint in case that a ('binary') branch is cut off
1430  */
1431 typedef struct
1432 {
1433  SCIP_VAR** binaryvars; /**< The binary variables currently branched on. */
1434  int nbinaryvars; /**< The number of entries in 'nbinaryvars'. */
1435  int memorysize; /**< The number of entries that the array 'binaryvars' may hold before the
1436  * array is reallocated. */
1437 } BINARYVARLIST;
1438 
1439 /** Allocates and initializes the BINARYVARLIST struct. */
1440 static
1442  SCIP* scip, /**< SCIP data structure */
1443  BINARYVARLIST** list, /**< Pointer to the list to be allocated and initialized. */
1444  int startsize /**< The number of entries the list initially can hold. */
1445  )
1447  assert(scip != NULL);
1448  assert(list != NULL);
1449  assert(startsize > 0);
1451  SCIP_CALL( SCIPallocBuffer(scip, list) );
1452  SCIP_CALL( SCIPallocBufferArray(scip, &(*list)->binaryvars, startsize) );
1453 
1454  /* We start with no entries and the (current) max length */
1455  (*list)->nbinaryvars = 0;
1456  (*list)->memorysize = startsize;
1457 
1458  return SCIP_OKAY;
1459 }
1460 
1461 /** Appends a binary variable to the list, reallocating the list if necessary. */
1462 static
1463 void binaryVarListAppend(
1464  SCIP* scip, /**< SCIP data structure */
1465  BINARYVARLIST* list, /**< The list to add the var to. */
1466  SCIP_VAR* vartoadd /**< The binary var to add to the list. */
1467  )
1468 {
1469  assert(scip != NULL);
1470  assert(list != NULL);
1471  assert(vartoadd != NULL);
1472  assert(SCIPvarIsBinary(vartoadd));
1473  assert(list->nbinaryvars < list->memorysize);
1474 
1475  /* Set the new var at the first unused place, which is the length used as index */
1476  list->binaryvars[list->nbinaryvars] = vartoadd;
1477  list->nbinaryvars++;
1479 
1480 /** Remove the last element from the list. */
1481 static
1482 void binaryVarListDrop(
1483  BINARYVARLIST* list /**< The list to remove the last element from. */
1484  )
1485 {
1486  assert(list != NULL);
1487  assert(list->nbinaryvars > 0);
1488  assert(list->binaryvars[list->nbinaryvars-1] != NULL);
1489 
1490  /* decrement the number of entries in the actual list */
1491  list->nbinaryvars--;
1492 }
1493 
1494 /** Frees all resources allocated by a BINARYVARLIST in opposite order of allocation. */
1495 static
1496 void binaryVarListFree(
1497  SCIP* scip, /**< SCIP data structure */
1498  BINARYVARLIST** list /**< Pointer to the list to free */
1499  )
1500 {
1501  assert(scip != NULL);
1502  assert(list != NULL);
1503 
1504  SCIPfreeBufferArray(scip, &(*list)->binaryvars);
1505  SCIPfreeBuffer(scip, list);
1506 }
1507 
1508 /** struct holding the relevant data for handling binary constraints */
1509 typedef struct
1510 {
1511  BINARYVARLIST* binaryvars; /**< current binary vars, used to fill the conslist */
1512  CONSTRAINTLIST* conslist; /**< list of constraints to be created */
1513 } BINCONSDATA;
1514 
1515 /** Allocate and initialize the BINCONSDATA struct. */
1516 static
1518  SCIP* scip, /**< SCIP data structure */
1519  BINCONSDATA** consdata, /**< Pointer to the struct to be allocated and initialized. */
1520  int maxdepth, /**< The depth of the recursion as an upper bound of branch vars to hold. */
1521  int nstartcons /**< The start size of the array containing the constraints. */
1522  )
1523 {
1524  assert(scip != NULL);
1525  assert(consdata != NULL);
1526  assert(maxdepth > 0);
1527  assert(nstartcons > 0);
1528 
1529  SCIP_CALL( SCIPallocBuffer(scip, consdata) );
1530  SCIP_CALL( binaryVarListCreate(scip, &(*consdata)->binaryvars, maxdepth) );
1531  SCIP_CALL( constraintListCreate(scip, &(*consdata)->conslist, nstartcons) );
1533  return SCIP_OKAY;
1534 }
1535 
1536 /** Free all resources in a BINCONSDATA in opposite order of allocation. */
1537 static
1538 void binConsDataFree(
1539  SCIP* scip, /**< SCIP data structure */
1540  BINCONSDATA** consdata /**< Pointer to the struct to be freed. */
1541  )
1542 {
1543  assert(scip != NULL);
1544  assert(consdata != NULL);
1545 
1546  constraintListFree(scip, &(*consdata)->conslist);
1547  binaryVarListFree(scip, &(*consdata)->binaryvars);
1548  SCIPfreeBuffer(scip, consdata);
1549 }
1550 
1551 /** A struct acting as a fixed list of candidates */
1552 typedef struct
1554  CANDIDATE** candidates; /**< the array of candidates */
1555  int ncandidates; /**< the number of actual entries in candidates (without trailing NULLs); this
1556  * is NOT the length of the candidates array, but the number of candidates in
1557  * it */
1558 } CANDIDATELIST;
1559 
1560 /** allocates the candidate list on the buffer WITHOUT initializing the contained array of candidates. */
1561 static
1563  SCIP* scip, /**< SCIP data structure */
1564  CANDIDATELIST** candidatelist, /**< the candidate list to allocate */
1565  int ncandidates /**< the number of candidates the list must hold */
1566  )
1568  assert(scip != NULL);
1569  assert(candidatelist != NULL);
1570  assert(ncandidates >= 0);
1571 
1572  SCIP_CALL( SCIPallocBuffer(scip, candidatelist) );
1573 
1574  if( ncandidates > 0 )
1575  {
1576  SCIP_CALL( SCIPallocBufferArray(scip, &(*candidatelist)->candidates, ncandidates) );
1577  }
1578  else
1579  (*candidatelist)->candidates = NULL;
1580 
1581  (*candidatelist)->ncandidates = ncandidates;
1582 
1583  return SCIP_OKAY;
1584 }
1585 
1586 /** allocates the given list and fills it with all fractional candidates of the current LP solution. */
1587 static
1589  SCIP* scip, /**< SCIP data structure */
1590  CANDIDATELIST** candidatelist /**< the list to allocate and fill */
1591  )
1592 {
1593  SCIP_VAR** lpcands;
1594  SCIP_Real* lpcandssol;
1595  SCIP_Real* lpcandsfrac;
1596  int nlpcands;
1597  int i;
1598 
1599  assert(scip != NULL);
1600  assert(candidatelist != NULL);
1601 
1602  /* get all fractional candidates */
1603  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, &nlpcands, NULL, NULL) );
1604 
1605  assert(lpcands != NULL);
1606  assert(lpcandssol != NULL);
1607  assert(lpcandsfrac != NULL);
1608 
1609  SCIP_CALL( candidateListCreate(scip, candidatelist, nlpcands) );
1610 
1611  for( i = 0; i < nlpcands; i++ )
1612  {
1613  CANDIDATE* candidate;
1614 
1615  SCIP_CALL( candidateCreate(scip, &candidate) );
1616  assert(candidate != NULL);
1617 
1618  candidate->branchvar = lpcands[i];
1619  candidate->branchval = lpcandssol[i];
1620  candidate->fracval = lpcandsfrac[i];
1621 
1622  (*candidatelist)->candidates[i] = candidate;
1623 
1624  LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "created candidate <%s>...\n",
1625  (candidate) != NULL ? SCIPvarGetName((candidate)->branchvar) : "none");
1626  }
1627 
1628  return SCIP_OKAY;
1629 }
1630 
1631 /** frees the allocated buffer memory of the candidate list and frees the contained candidates. */
1632 static
1634  SCIP* scip, /**< SCIP data structure */
1635  CANDIDATELIST** candidatelist /**< the list to be freed */
1636  )
1637 {
1638  int i;
1639 
1640  assert(scip != NULL);
1641  assert(candidatelist != NULL);
1642  assert((*candidatelist)->ncandidates > 0 || (*candidatelist)->candidates == NULL);
1643 
1644  if( (*candidatelist)->candidates != NULL )
1645  {
1646  for( i = (*candidatelist)->ncandidates - 1; i >= 0; i-- )
1647  {
1648  CANDIDATE* cand = (*candidatelist)->candidates[i];
1649  if( cand != NULL )
1650  {
1651  SCIP_CALL( candidateFree(scip, &cand) );
1652  }
1653  }
1654 
1655  SCIPfreeBufferArray(scip, &(*candidatelist)->candidates);
1656  }
1657  SCIPfreeBuffer(scip, candidatelist);
1658 
1659  return SCIP_OKAY;
1660 }
1661 
1662 /** keeps only the first candidates and frees the remaining ones */
1663 static
1665  SCIP* scip, /**< SCIP data structure */
1666  CANDIDATELIST* candidatelist, /**< the list to allocate and fill */
1667  int nindices /**< the number of candidates to keep (starting from 0) */
1668  )
1669 {
1670  int i;
1671 
1672  assert(scip != NULL);
1673  assert(candidatelist != NULL);
1674  assert(0 < nindices);
1675  assert(nindices <= candidatelist->ncandidates);
1676 
1677  /* only keep the first nindices candidates and free the remaining ones */
1678  for( i = nindices; i < candidatelist->ncandidates; i++ )
1679  {
1680  CANDIDATE* cand = candidatelist->candidates[i];
1681  if( cand != NULL )
1682  {
1683  SCIP_CALL( candidateFree(scip, &cand) );
1684  candidatelist->candidates[i] = NULL;
1685  }
1686  }
1687  candidatelist->ncandidates = nindices;
1688 
1689  return SCIP_OKAY;
1690 }
1691 
1692 /** all domain reductions found through cutoff of branches */
1693 typedef struct
1694 {
1695  SCIP_Real* lowerbounds; /**< The new lower bounds found for each variable in the problem. */
1696  SCIP_Real* upperbounds; /**< The new upper bounds found for each variable in the problem. */
1697  SCIP_Shortbool* baselpviolated; /**< Indicates whether the base lp solution violates the new bounds of a var.*/
1698  int nviolatedvars; /**< Tracks the number of vars that have a violated (by the base lp) new lower
1699  * or upper bound. */
1700  int nchangedvars; /**< Tracks the number of vars, that have a changed domain. (a change on both,
1701  * upper and lower bound, counts as one.) */
1702  int nsimplebounds; /**< number of changed bounds resulting from infeasible child nodes */
1703 #ifdef SCIP_STATISTIC
1704  int* lowerboundnproofs; /**< The number of nodes needed to prove the lower bound for each variable. */
1705  int* upperboundnproofs; /**< The number of nodes needed to prove the upper bound for each variable. */
1706 #endif
1709 /** allocate the struct on the buffer and initialize it with the default values */
1710 static
1712  SCIP* scip, /**< SCIP data structure */
1713  DOMAINREDUCTIONS** domreds /**< The struct that has to be allocated and initialized. */
1714  )
1716  SCIP_VAR** vars;
1717  int ntotalvars;
1718  int v;
1719 
1720  assert(scip != NULL);
1721  assert(domreds != NULL);
1722 
1723  /* The arrays saves the data for all variables in the problem via the ProbIndex. See SCIPvarGetProbindex() */
1724  vars = SCIPgetVars(scip);
1725  ntotalvars = SCIPgetNVars(scip);
1727  /* Allocate the struct and the contained arrays; initialize flags to FALSE */
1728  SCIP_CALL( SCIPallocBuffer(scip, domreds) );
1729  SCIP_CALL( SCIPallocBufferArray(scip, &(*domreds)->lowerbounds, ntotalvars) );
1730  SCIP_CALL( SCIPallocBufferArray(scip, &(*domreds)->upperbounds, ntotalvars) );
1731  SCIP_CALL( SCIPallocClearBufferArray(scip, &(*domreds)->baselpviolated, ntotalvars) );
1732 #ifdef SCIP_STATISTIC
1733  SCIP_CALL( SCIPallocClearBufferArray(scip, &(*domreds)->lowerboundnproofs, ntotalvars) );
1734  SCIP_CALL( SCIPallocClearBufferArray(scip, &(*domreds)->upperboundnproofs, ntotalvars) );
1735 #endif
1736 
1737  for( v = 0; v < ntotalvars; ++v )
1738  {
1739  (*domreds)->lowerbounds[v] = SCIPvarGetLbLocal(vars[v]);
1740  (*domreds)->upperbounds[v] = SCIPvarGetUbLocal(vars[v]);
1741  }
1742 
1743  /* At the start we have no domain reductions for any variable. */
1744  (*domreds)->nviolatedvars = 0;
1745  (*domreds)->nchangedvars = 0;
1746  (*domreds)->nsimplebounds = 0;
1747 
1748  return SCIP_OKAY;
1749 }
1750 
1751 /** frees the given DOMAINREDUCTIONS and all contained Arrays in the opposite order of allocation */
1752 static
1754  SCIP* scip, /**< SCIP data structure */
1755  DOMAINREDUCTIONS** domreds /**< Pointer to the struct to be freed. */
1756  )
1757 {
1758  assert(scip != NULL);
1759  assert(domreds != NULL);
1760 
1761 #ifdef SCIP_STATISTIC
1762  SCIPfreeBufferArray(scip, &(*domreds)->upperboundnproofs);
1763  SCIPfreeBufferArray(scip, &(*domreds)->lowerboundnproofs);
1764 #endif
1765  SCIPfreeBufferArray(scip, &(*domreds)->baselpviolated);
1766  SCIPfreeBufferArray(scip, &(*domreds)->upperbounds);
1767  SCIPfreeBufferArray(scip, &(*domreds)->lowerbounds);
1768  SCIPfreeBuffer(scip, domreds);
1769 }
1770 
1771 /** information about the current status of the branching */
1772 typedef struct
1773 {
1774  SCIP_Bool addedbinconss; /**< were binary constraints added? */
1775  SCIP_Bool depthtoosmall; /**< was the remaining depth too small to branch on? */
1776  SCIP_Bool lperror; /**< did an error occur while solving an LP */
1777  SCIP_Bool cutoff; /**< was the current node cut off? */
1778  SCIP_Bool domredcutoff; /**< was the current node cut off due to domain reductions? */
1779  SCIP_Bool domred; /**< were domain reductions added due to information obtained through
1780  * branching? */
1781  SCIP_Bool limitreached; /**< was a limit (time, node, user, ...) reached? */
1782  SCIP_Bool maxnconsreached; /**< was the max number of constraints (bin conss and dom red) reached? */
1783 } STATUS;
1784 
1785 /** Allocates the status on the buffer memory and initializes it with default values. */
1786 static
1788  SCIP* scip, /**< SCIP data structure */
1789  STATUS** status /**< the status to be allocated */
1790  )
1792  assert(scip != NULL);
1793  assert(status != NULL);
1795  SCIP_CALL( SCIPallocBuffer(scip, status) );
1797  (*status)->addedbinconss = FALSE;
1798  (*status)->depthtoosmall = FALSE;
1799  (*status)->lperror = FALSE;
1800  (*status)->cutoff = FALSE;
1801  (*status)->domred = FALSE;
1802  (*status)->domredcutoff = FALSE;
1803  (*status)->limitreached = FALSE;
1804  (*status)->maxnconsreached = FALSE;
1805 
1806  return SCIP_OKAY;
1807 }
1808 
1809 /** frees the allocated buffer memory of the status */
1810 static
1811 void statusFree(
1812  SCIP* scip, /**< SCIP data structure */
1813  STATUS** status /**< the status to be freed */
1814  )
1815 {
1816  assert(scip != NULL);
1817  assert(status != NULL);
1818  SCIPfreeBuffer(scip, status);
1819 }
1820 
1821 /** container struct to keep the calculated score for each variable */
1822 typedef struct
1823 {
1824  SCIP_Real* scores; /**< the scores for each problem variable */
1825  SCIP_Real* downgains; /**< the downgains for each problem variable */
1826  SCIP_Real* upgains; /**< the upgains for each problem variable */
1827  CANDIDATE** bestsortedcands; /**< array containing the best sorted variable indices w.r.t. their score */
1828  int nbestsortedcands; /**< number of elements in bestsortedcands */
1829  SCIP_Real scoresum; /**< sum of set scores */
1830  int nsetscores; /**< number of set scores */
1831 } SCORECONTAINER;
1832 
1833 /** resets the array containing the sorted indices w.r.t. their score. */
1834 static
1836  SCORECONTAINER* scorecontainer /**< the score container to reset */
1837  )
1838 {
1839  assert(scorecontainer != NULL);
1841  BMSclearMemoryArray(scorecontainer->bestsortedcands, scorecontainer->nbestsortedcands);
1844 /** allocates the score container and inits it with default values */
1845 static
1847  SCIP* scip, /**< SCIP data structure */
1848  SCORECONTAINER** scorecontainer, /**< pointer to the score container to init */
1849  CONFIGURATION* config /**< config struct with the user configuration */
1850  )
1851 {
1852  int ntotalvars;
1853  int ncands = config->maxncands;
1854  int i;
1855 
1856  assert(scip != NULL);
1857  assert(scorecontainer != NULL);
1858  assert(config != NULL);
1859 
1860  /* the container saves the score for all variables in the problem via the ProbIndex, see SCIPvarGetProbindex() */
1861  ntotalvars = SCIPgetNVars(scip);
1862 
1863  if( SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) < ncands )
1864  ncands = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
1865 
1866  SCIP_CALL( SCIPallocBuffer(scip, scorecontainer) );
1867  SCIP_CALL( SCIPallocBufferArray(scip, &(*scorecontainer)->scores, ntotalvars) );
1868  SCIP_CALL( SCIPallocBufferArray(scip, &(*scorecontainer)->downgains, ntotalvars) );
1869  SCIP_CALL( SCIPallocBufferArray(scip, &(*scorecontainer)->upgains, ntotalvars) );
1870  SCIP_CALL( SCIPallocBufferArray(scip, &(*scorecontainer)->bestsortedcands, ncands) );
1871 
1872  (*scorecontainer)->nbestsortedcands = ncands;
1873  (*scorecontainer)->scoresum = 0.0;
1874  (*scorecontainer)->nsetscores = 0;
1875 
1876  scoreContainterResetBestSortedCands(*scorecontainer);
1877 
1878  /* init the scores to something negative, as scores are always non negative */
1879  for( i = 0; i < ntotalvars; i++ )
1880  {
1881  (*scorecontainer)->scores[i] = -1.0;
1882  (*scorecontainer)->downgains[i] = -1.0;
1883  (*scorecontainer)->upgains[i] = -1.0;
1884  }
1885 
1886  return SCIP_OKAY;
1887 }
1888 
1889 /** Finds the insertion index for the given score in the candidate list. The score of each candidate is taken from the
1890  * scorecontainer. The first elements of the candidate list have to be sorted, as this method uses binary search to find
1891  * the correct insertion point
1892  */
1893 static
1894 int findInsertionPoint(
1895  SCIP* scip, /**< SCIP data structure */
1896  SCORECONTAINER* scorecontainer, /**< container with all the scores for each candidate */
1897  SCIP_Real scoretoinsert, /**< score to find the insertion index for */
1898  CANDIDATE** candidates, /**< candidate list where the first nsorted elements are sorted (w.r.t. their
1899  * score) */
1900  int ncandidates /**< number of elements in candidates to consider, starting from 0 */
1901  )
1902 {
1903  int left = 0;
1904  int right = ncandidates - 1;
1905 
1906  assert(scip != NULL);
1907  assert(scorecontainer != NULL);
1908  assert(candidates != NULL);
1909  assert(ncandidates >= 0);
1910 
1911  while( left <= right )
1912  {
1913  int mid = left + ((right - left) / 2);
1914  SCIP_Real midscore = -SCIPinfinity(scip);
1915  CANDIDATE *midcand = candidates[mid];
1916 
1917  if( midcand != NULL)
1918  {
1919  SCIP_VAR* midvar;
1920  int midindex;
1921 
1922  midvar = midcand->branchvar;
1923  midindex = SCIPvarGetProbindex(midvar);
1924  midscore = scorecontainer->scores[midindex];
1925  }
1926 
1927  if( SCIPisGT(scip, scoretoinsert, midscore) )
1928  right = mid - 1;
1929  else
1930  left = mid + 1;
1931  }
1932 
1933  return right + 1;
1934 }
1935 
1936 /** Inserts the given probindex into the sorted array in the container, moving all indices after it to the right. Then
1937  * returns the element that does not fit into the array any longer. */
1938 static
1940  SCORECONTAINER* scorecontainer, /**< container to insert the index into */
1941  CANDIDATE* candidate, /**< the probindex of a variable to store */
1942  int insertpoint /**< point to store the index at */
1943  )
1944 {
1945  int i;
1946  CANDIDATE* movecand = candidate;
1947 
1948  assert(scorecontainer != NULL);
1949  assert(candidate != NULL);
1950  assert(insertpoint >= 0);
1951 
1952  for( i = insertpoint; i < scorecontainer->nbestsortedcands; i++ )
1953  {
1954  CANDIDATE* oldcand = scorecontainer->bestsortedcands[i];
1955  scorecontainer->bestsortedcands[i] = movecand;
1956  movecand = oldcand;
1957  }
1958 
1959  return movecand;
1960 }
1961 
1962 /** sets the score for the variable in the score container */
1963 static
1965  SCIP* scip, /**< SCIP data structure */
1966  SCORECONTAINER* scorecontainer, /**< the container to write into */
1967  CANDIDATE* cand, /**< candidate to add the score for */
1968  SCIP_Real score, /**< score to add */
1969  SCIP_Real downgain, /**< LP gain in down child */
1970  SCIP_Real upgain /**< LP gain in up child */
1971  )
1972 {
1973  CANDIDATE* droppedcandidate;
1974  int probindex;
1975  int insertpoint;
1976 
1977  assert(scip != NULL);
1978  assert(scorecontainer != NULL);
1979  assert(cand != NULL);
1980  assert(SCIPisGE(scip, score, -0.2));
1981 
1982  probindex = SCIPvarGetProbindex(cand->branchvar);
1983  assert(probindex >= 0);
1984 
1985  if( scorecontainer->scores[probindex] < -0.5 )
1986  {
1987  ++scorecontainer->nsetscores;
1988  scorecontainer->scoresum += score;
1989  }
1990  else
1991  {
1992  scorecontainer->scoresum += (score - scorecontainer->scores[probindex]);
1993  }
1994 
1995  scorecontainer->scores[probindex] = score;
1996  scorecontainer->downgains[probindex] = downgain;
1997  scorecontainer->upgains[probindex] = upgain;
1998 
1999  /* find the point in the sorted array where the new score should be inserted */
2000  insertpoint = findInsertionPoint(scip, scorecontainer, score, scorecontainer->bestsortedcands,
2001  scorecontainer->nbestsortedcands);
2002 
2003  /* insert the current variable (cand) at the position calculated above, returning the candidate that
2004  * was removed at the end of the list; this candidate can be the given candidate for the case that the score does not
2005  * belong to the best ones */
2006  droppedcandidate = scoreContainerUpdateSortOrder(scorecontainer, cand, insertpoint);
2007 
2008  /* remove the warm start info from the dropped candidate */
2009  if( droppedcandidate != NULL )
2010  {
2011  SCIP_CALL( candidateFreeWarmStartInfo(scip, droppedcandidate) );
2012  }
2013 
2014  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Stored score <%.9g> for var <%s>.\n", score, SCIPvarGetName(cand->branchvar));
2015 
2016  return SCIP_OKAY;
2017 }
2018 
2019 /** Frees the score container and all of its contained arrays. */
2020 static
2022  SCIP* scip, /**< SCIP data structure */
2023  SCORECONTAINER** scorecontainer /**< score container to free */
2024  )
2025 {
2026  assert(scip != NULL);
2027  assert(scorecontainer != NULL);
2028 
2029  /* don't free the candidates inside the cands array, as those are handled by the candidate list */
2030  SCIPfreeBufferArray(scip, &(*scorecontainer)->bestsortedcands);
2031  SCIPfreeBufferArray(scip, &(*scorecontainer)->upgains);
2032  SCIPfreeBufferArray(scip, &(*scorecontainer)->downgains);
2033  SCIPfreeBufferArray(scip, &(*scorecontainer)->scores);
2034  SCIPfreeBuffer(scip, scorecontainer);
2035 
2036  return SCIP_OKAY;
2037 }
2038 
2039 /*
2040  * Local methods for the logic
2041  */
2042 
2043 /** branches recursively on all given candidates */
2044 static
2046  SCIP* scip, /**< SCIP data structure */
2047  STATUS* status, /**< current status */
2048  PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */
2049  CONFIGURATION* config, /**< the configuration of the branching rule */
2050  SCIP_SOL* baselpsol, /**< base lp solution */
2051  DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found */
2052  BINCONSDATA* binconsdata, /**< container collecting all binary constraints */
2053  CANDIDATELIST* candidatelist, /**< list of candidates to branch on */
2054  BRANCHINGDECISION* decision, /**< struct to store the final decision */
2055  SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores */
2056  LEVEL2DATA* level2data, /**< level 2 LP results data */
2057  int recursiondepth, /**< remaining recursion depth */
2058  SCIP_Real lpobjval, /**< LP objective value of current probing node*/
2059  SCIP_Real baselpobjval, /**< LP objective value of focus node (not probing) */
2060  SCIP_Longint* niterations, /**< pointer to store the total number of iterations for this variable */
2061  int* ndeepestcutoffs, /**< pointer to store the total number of cutoffs on the deepest level */
2062  SCIP_Real* bestgain, /**< pointer to store the best gain found with these candidates */
2063  SCIP_Real* totalgains, /**< pointer to store the sum over all gains that are valid in both children */
2064  int* ntotalgains, /**< pointer to store the number of gains summed in totalgains */
2065  int* ndeepestnodes /**< pointer to store the number of nodes processed in the deepest level */
2066 #ifdef SCIP_STATISTIC
2067  ,STATISTICS* statistics /**< general statistical data */
2068  ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */
2069  ,SCIP_Real* firstscoreptr /**< pointer to store score of first candidate, or NULL */
2070  ,SCIP_Real* bestscoreptr /**< pointer to store best score, or NULL */
2071 #endif
2072  );
2073 
2074 /** Adds the given lower bound to the DOMAINREDUCTIONS struct. */
2075 static
2076 void addLowerBound(
2077  SCIP* scip, /**< SCIP data structure */
2078  SCIP_VAR* var, /**< The variable the bound should be added for. */
2079  SCIP_Real lowerbound, /**< The new lower bound for the variable. */
2080  SCIP_SOL* baselpsol, /**< The LP solution of the base problem. Used to check whether the domain
2081  * reduction is violated by it. */
2082  SCIP_Bool simplechange, /**< does the change result from an infeasible child node? */
2083  DOMAINREDUCTIONS* domainreductions /**< The struct the domain reduction should be added to. */
2084 #ifdef SCIP_STATISTIC
2085  ,int nproofnodes /**< The number of nodes needed to prove the new lower bound. */
2086  ,int force /**< should the number of proof nodes be added even if the bound is known already? */
2087 #endif
2088  )
2089 {
2090  int varindex;
2091  SCIP_Real basesolutionval;
2092 
2093  assert(scip != NULL);
2094  assert(var != NULL);
2095  assert(baselpsol != NULL);
2096  assert(domainreductions != NULL);
2097 #ifdef SCIP_STATISTIC
2098  assert(nproofnodes >= 0);
2099 #endif
2100 
2101  /* The arrays inside DOMAINREDUCTIONS are indexed via the problem index. */
2102  varindex = SCIPvarGetProbindex(var);
2103 
2104  lowerbound = SCIPadjustedVarLb(scip, var, lowerbound);
2105 
2106  if( SCIPisLT(scip, domainreductions->lowerbounds[varindex], lowerbound) )
2107  {
2108  /* the new lower bound is stronger (greater) than the old one,
2109  * so we update the bound and number of proof nodes */
2110  domainreductions->lowerbounds[varindex] = lowerbound;
2111  domainreductions->nchangedvars++;
2112  if( simplechange )
2113  domainreductions->nsimplebounds++;
2114 #ifdef SCIP_STATISTIC
2115  domainreductions->lowerboundnproofs[varindex] = nproofnodes;
2116  }
2117  else
2118  {
2119  /* if the given lower bound is equal to the old one we take the smaller number of proof nodes */
2120  if( SCIPisEQ(scip, domainreductions->lowerbounds[varindex], lowerbound) &&
2121  (force || domainreductions->lowerboundnproofs[varindex] > nproofnodes) )
2122  domainreductions->lowerboundnproofs[varindex] = nproofnodes;
2123 #endif
2124  }
2125 
2126  /* we get the solution value to check whether the domain reduction is violated in the base LP */
2127  basesolutionval = SCIPgetSolVal(scip, baselpsol, var);
2128 
2129  /* in case the new lower bound is greater than the base solution val and the base solution val is not violated by a
2130  * previously found bound, we increment the nviolatedvars counter and set the baselpviolated flag */
2131  if( SCIPisFeasGT(scip, domainreductions->lowerbounds[varindex], basesolutionval)
2132  && !domainreductions->baselpviolated[varindex] )
2133  {
2134  domainreductions->baselpviolated[varindex] = TRUE;
2135  domainreductions->nviolatedvars++;
2136  }
2137 }
2138 
2139 /** Adds the given upper bound to the DOMAINREDUCTIONS struct. */
2140 static
2141 void addUpperBound(
2142  SCIP* scip, /**< SCIP data structure */
2143  SCIP_VAR* var, /**< The variable the bound should be added for. */
2144  SCIP_Real upperbound, /**< The new upper bound for the variable. */
2145  SCIP_SOL* baselpsol, /**< The LP solution of the base problem. Used to check whether the domain
2146  * reduction is violated by it. */
2147  SCIP_Bool simplechange, /**< does the change result from an infeasible child node? */
2148  DOMAINREDUCTIONS* domainreductions /**< The struct the domain reduction should be added to. */
2149 #ifdef SCIP_STATISTIC
2150  ,int nproofnodes /**< The number of nodes needed to prove the new lower bound. */
2151  ,int force /**< should the number of proof nodes be added even if the bound is known already? */
2152 #endif
2153  )
2154 {
2155  int varindex;
2156  SCIP_Real basesolutionval;
2157 
2158  assert(scip != NULL);
2159  assert(var != NULL);
2160  assert(baselpsol != NULL);
2161  assert(domainreductions != NULL);
2162 #ifdef SCIP_STATISTIC
2163  assert(nproofnodes >= 0);
2164 #endif
2165 
2166  /* The arrays inside DOMAINREDUCTIONS are indexed via the problem index. */
2167  varindex = SCIPvarGetProbindex(var);
2168 
2169  upperbound = SCIPadjustedVarUb(scip, var, upperbound);
2170 
2171  if( SCIPisLE(scip, domainreductions->upperbounds[varindex], upperbound) )
2172  {
2173 #ifdef SCIP_STATISTIC
2174  /* if the given upper bound is equal to the old one we take the smaller number of proof nodes */
2175  if( SCIPisEQ(scip, domainreductions->upperbounds[varindex], upperbound) &&
2176  (force || domainreductions->upperboundnproofs[varindex] > nproofnodes) )
2177  domainreductions->upperboundnproofs[varindex] = nproofnodes;
2178 #endif
2179  }
2180  else
2181  {
2182  /* the new upper bound is stronger (smaller) than the old one,
2183  * so we update the bound and number of proof nodes */
2184  domainreductions->upperbounds[varindex] = upperbound;
2185  domainreductions->nchangedvars++;
2186  if( simplechange )
2187  domainreductions->nsimplebounds++;
2188 #ifdef SCIP_STATISTIC
2189  domainreductions->upperboundnproofs[varindex] = nproofnodes;
2190 #endif
2191  }
2192 
2193  /* We get the solution value to check whether the domain reduction is violated in the base LP */
2194  basesolutionval = SCIPgetSolVal(scip, baselpsol, var);
2195 
2196  /* In case the new upper bound is smaller than the base solution val and the base solution val is not violated by a
2197  * previously found bound, we increment the nviolatedvars counter and set the baselpviolated flag. */
2198  if( SCIPisFeasLT(scip, domainreductions->upperbounds[varindex], basesolutionval)
2199  && !domainreductions->baselpviolated[varindex] )
2200  {
2201  domainreductions->baselpviolated[varindex] = TRUE;
2202  domainreductions->nviolatedvars++;
2203  }
2204 }
2205 
2206 /** apply the domain reductions from a single struct to another one; this may be used in case one of the two child
2207  * problems of a variable is infeasible
2208  */
2209 static
2211  SCIP* scip, /**< SCIP data structure */
2212  SCIP_SOL* baselpsol, /**< The LP solution of the base problem. Used to check whether the domain
2213  * reduction is violated by it. */
2214  int maxstoredomreds, /**< maximum number of domain reductions to store */
2215  DOMAINREDUCTIONS* targetdomreds, /**< The target that should be filled with the merged data. */
2216  DOMAINREDUCTIONS* domreds /**< source domain reductions */
2217  )
2218 {
2219  SCIP_VAR** vars;
2220  int nvars;
2221  int i;
2222 
2223  assert(scip != NULL);
2224  assert(baselpsol != NULL);
2225  assert(targetdomreds != NULL);
2226  assert(domreds != NULL);
2227 
2228  /* as the bounds are tracked for all vars we have to iterate over all vars */
2229  vars = SCIPgetVars(scip);
2230  nvars = SCIPgetNVars(scip);
2231 
2232  assert(vars != NULL);
2233  assert(nvars > 0);
2234 
2235  for( i = 0; i < nvars; i++ )
2236  {
2237  if( targetdomreds->nviolatedvars >= maxstoredomreds )
2238  return;
2239 
2240 #ifdef SCIP_STATISTIC
2241  /* adjust the proof nodes */
2242  addLowerBound(scip, vars[i], domreds->lowerbounds[i], baselpsol, TRUE, targetdomreds,
2243  domreds->lowerboundnproofs[i], FALSE);
2244 #else
2245  addLowerBound(scip, vars[i], domreds->lowerbounds[i], baselpsol, TRUE, targetdomreds);
2246 #endif
2247 
2248  if( targetdomreds->nviolatedvars >= maxstoredomreds )
2249  return;
2250 
2251 #ifdef SCIP_STATISTIC
2252  addUpperBound(scip, vars[i], domreds->upperbounds[i], baselpsol, TRUE, targetdomreds,
2253  domreds->upperboundnproofs[i], FALSE);
2254 #else
2255  addUpperBound(scip, vars[i], domreds->upperbounds[i], baselpsol, TRUE, targetdomreds);
2256 #endif
2257  }
2258 }
2259 
2260 /**
2261  * merges the domain reduction data from the two given branching children data into the target parent data
2262  */
2263 static
2265  SCIP* scip, /**< SCIP data structure */
2266  SCIP_SOL* baselpsol, /**< The LP solution of the base problem. Used to check whether the domain
2267  * reduction is violated by it. */
2268  int maxstoredomreds, /**< maximum number of domain reductions to store */
2269  DOMAINREDUCTIONS* targetdomreds, /**< The target that should be filled with the merged data. */
2270  DOMAINREDUCTIONS* downdomreds, /**< One of the source DOMAINREDUCTIONS. */
2271  DOMAINREDUCTIONS* updomreds /**< The other source DOMAINREDUCTIONS. */
2272  )
2273 {
2274  SCIP_VAR** vars;
2275  int nvars;
2276  int i;
2277 
2278  assert(scip != NULL);
2279  assert(baselpsol != NULL);
2280  assert(targetdomreds != NULL);
2281  assert(downdomreds != NULL);
2282  assert(updomreds != NULL);
2283 
2284  /* as the bounds are tracked for all vars we have to iterate over all vars */
2285  vars = SCIPgetVars(scip);
2286  nvars = SCIPgetNVars(scip);
2287 
2288  assert(vars != NULL);
2289  assert(nvars > 0);
2290 
2291  LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Combining domain reductions from up and down child.\n");
2292  LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Previous number of changed variable domains: %d\n",
2293  targetdomreds->nchangedvars);
2294 
2295  LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Number of changed variable domains in up child: %d\n",
2296  updomreds->nchangedvars);
2297  LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Number of changed variable domains in down child: %d\n",
2298  downdomreds->nchangedvars);
2299 
2300  for( i = 0; i < nvars; i++ )
2301  {
2302  SCIP_Real newlowerbound;
2303  SCIP_Real newupperbound;
2304 
2305  assert(vars[i] != NULL);
2306 
2307  if( targetdomreds->nviolatedvars >= maxstoredomreds )
2308  return;
2309 
2310  /* the MIN of both lower bounds represents a valid lower bound at the parent node */
2311  newlowerbound = MIN(downdomreds->lowerbounds[i], updomreds->lowerbounds[i]);
2312 
2313  /* This MIN can now be added via the default add method */
2314 #ifdef SCIP_STATISTIC
2315  addLowerBound(scip, vars[i], newlowerbound, baselpsol, FALSE, targetdomreds,
2316  MIN(4, downdomreds->lowerboundnproofs[i] + updomreds->lowerboundnproofs[i] + 2), FALSE);
2317 #else
2318  addLowerBound(scip, vars[i], newlowerbound, baselpsol, FALSE, targetdomreds);
2319 #endif
2320 
2321  if( targetdomreds->nviolatedvars >= maxstoredomreds )
2322  return;
2323 
2324  /* the MAX of both upper bounds represents a valid upper bound at the parent node */
2325  newupperbound = MAX(downdomreds->upperbounds[i], updomreds->upperbounds[i]);
2326 
2327  /* This MAX can now be added via the default add method */
2328 #ifdef SCIP_STATISTIC
2329  addUpperBound(scip, vars[i], newupperbound, baselpsol, FALSE, targetdomreds,
2330  MIN(4, downdomreds->upperboundnproofs[i] + updomreds->upperboundnproofs[i] + 2), FALSE);
2331 #else
2332  addUpperBound(scip, vars[i], newupperbound, baselpsol, FALSE, targetdomreds);
2333 #endif
2334  }
2335 
2336  LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Subsequent number of changed variable domains: %d\n",
2337  targetdomreds->nchangedvars);
2338 }
2339 
2340 /** Applies the domain reductions to the current node. */
2341 static
2343  SCIP* scip, /**< SCIP data structure */
2344  CONFIGURATION* config, /**< the configuration of the branching rule */
2345  SCIP_SOL* baselpsol, /**< The LP solution of the base problem. Used to check whether the domain
2346  * reduction is violated by it. */
2347  DOMAINREDUCTIONS* domreds, /**< The domain reductions that should be applied to the current node. */
2348  SCIP_Bool* domredcutoff, /**< pointer to store whether a cutoff was found due to domain reductions */
2349  SCIP_Bool* domred /**< pointer to store whether a domain change was added */
2350 #ifdef SCIP_STATISTIC
2351  ,STATISTICS* statistics /**< The statistics container. */
2352 #endif
2353  )
2354 {
2355  int i;
2356  SCIP_VAR** probvars;
2357  int nprobvars;
2358 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC)
2359  int nboundsadded = 0;
2360  int nboundsaddedvio = 0;
2361 #endif
2362 
2363  assert(scip != NULL);
2364  assert(baselpsol != NULL);
2365  assert(domreds != NULL);
2366  assert(domredcutoff != NULL);
2367  assert(domred != NULL);
2368 #ifdef SCIP_STATISTIC
2369  assert(statistics != NULL);
2370 #endif
2371 
2372  /* initially we have no cutoff */
2373  *domredcutoff = FALSE;
2374 
2375  /* as the bounds are tracked for all vars we have to iterate over all vars */
2376  probvars = SCIPgetVars(scip);
2377  nprobvars = SCIPgetNVars(scip);
2378 
2379  assert(probvars != NULL);
2380  assert(nprobvars > 0);
2381 
2382  if( config->prefersimplebounds && domreds->nsimplebounds == 0 )
2383  return SCIP_OKAY;
2384 
2385  for( i = 0; i < nprobvars && !(*domredcutoff); i++ )
2386  {
2387  SCIP_VAR* var;
2388  SCIP_Real proposedbound;
2389  SCIP_Real baselpval;
2390 #ifdef SCIP_DEBUG
2391  SCIP_Real oldbound;
2392 #endif
2393  SCIP_Bool infeasible;
2394  SCIP_Bool tightened;
2395 
2396  var = probvars[i];
2397 
2398  assert(var != NULL);
2399 
2400  baselpval = SCIPgetSolVal(scip, baselpsol, var);
2401 
2402  if( SCIPisGT(scip, domreds->lowerbounds[i], SCIPvarGetLbLocal(var)) )
2403  {
2404  /* apply lower bound */
2405 #ifdef SCIP_DEBUG
2406  oldbound = SCIPvarGetLbLocal(var);
2407 #endif
2408  proposedbound = domreds->lowerbounds[i];
2409 
2410  if( config->onlyvioldomreds && SCIPisGE(scip, baselpval, proposedbound) )
2411  continue;
2412 
2413  /* add the new bound */
2414  SCIP_CALL( SCIPtightenVarLb(scip, var, proposedbound, TRUE, &infeasible, &tightened) );
2415 
2416 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC)
2417  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Variable <%s>, old lower bound <%g>, proposed lower bound <%g>, new "
2418  "lower bound <%g>\n", SCIPvarGetName(var), oldbound, proposedbound, SCIPvarGetLbLocal(var));
2419 #endif
2420 
2421  if( infeasible )
2422  {
2423  /* the domain reduction may result in an empty model (ub < lb) */
2424  *domredcutoff = TRUE;
2425  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The domain reduction of variable <%s> resulted in an empty "
2426  "model.\n", SCIPvarGetName(var));
2427  }
2428  else if( tightened )
2429  {
2430  /* the lb is now strictly greater than before */
2431  *domred = TRUE;
2432 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC)
2433  nboundsadded++;
2434 #endif
2435 #ifdef SCIP_STATISTIC
2436  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The lower bound of variable <%s> was successfully tightened (%d).\n",
2437  SCIPvarGetName(var), domreds->lowerboundnproofs[i]);
2438  statistics->ndomredproofnodes += domreds->lowerboundnproofs[i];
2439 #endif
2440 
2441 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC)
2442  if( SCIPisLT(scip, baselpval, SCIPvarGetLbLocal(var)) )
2443  {
2444  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The lower bound of variable <%s> is violated by the base lp "
2445  "value <%g>.\n", SCIPvarGetName(var), baselpval);
2446 
2447  nboundsaddedvio++;
2448  }
2449 #endif
2450  }
2451  }
2452 
2453  if( SCIPisLT(scip, domreds->upperbounds[i], SCIPvarGetUbLocal(var)) )
2454  {
2455  /* apply upper bound */
2456 #ifdef SCIP_DEBUG
2457  oldbound = SCIPvarGetUbLocal(var);
2458 #endif
2459  proposedbound = domreds->upperbounds[i];
2460 
2461  if( config->onlyvioldomreds && SCIPisLE(scip, baselpval, proposedbound) )
2462  continue;
2463 
2464  /* add the new bound */
2465  SCIP_CALL( SCIPtightenVarUb(scip, var, proposedbound, TRUE, &infeasible, &tightened) );
2466 
2467 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC)
2468  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Variable <%s>, old upper bound <%g>, proposed upper bound <%g>, new "
2469  "upper bound <%g>\n", SCIPvarGetName(var), oldbound, proposedbound, SCIPvarGetUbLocal(var));
2470 #endif
2471 
2472  if( infeasible )
2473  {
2474  /* the domain reduction may result in an empty model (ub < lb) */
2475  *domredcutoff = TRUE;
2476  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The domain reduction of variable <%s> resulted in an empty "
2477  "model.\n", SCIPvarGetName(var));
2478  }
2479  else if( tightened )
2480  {
2481  /* the ub is now strictly smaller than before */
2482  *domred = TRUE;
2483 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC)
2484  nboundsadded++;
2485 #endif
2486 #ifdef SCIP_STATISTIC
2487  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The upper bound of variable <%s> was successfully tightened (%d).\n",
2488  SCIPvarGetName(var), domreds->upperboundnproofs[i]);
2489  statistics->ndomredproofnodes += domreds->upperboundnproofs[i];
2490 #endif
2491 
2492 #if defined(SCIP_DEBUG) || defined(SCIP_STATISTIC)
2493  if( SCIPisGT(scip, baselpval, SCIPvarGetUbLocal(var)) )
2494  {
2495  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The upper bound of variable <%s> is violated by the base lp "
2496  "value <%g>.\n", SCIPvarGetName(var), baselpval);
2497 
2498  nboundsaddedvio++;
2499  }
2500 #endif
2501  }
2502  }
2503  }
2504 
2505 #ifdef SCIP_STATISTIC
2506  statistics->ndomred += nboundsadded;
2507  statistics->ndomredvio += nboundsaddedvio;
2508 #endif
2509 
2510  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Truly changed <%d> domains of the problem, <%d> of them are violated by the "
2511  "base lp.\n", nboundsadded, nboundsaddedvio);
2512  return SCIP_OKAY;
2513 }
2514 
2515 /** Copies the current LP solution into the given pointer. Needs to be freed after usage! */
2516 static
2518  SCIP* scip, /**< SCIP data structure */
2519  SCIP_SOL** lpsol /**< pointer to store the solution into */
2520  )
2521 {
2522  assert(scip != NULL);
2523  assert(lpsol != NULL);
2524 
2525  /* create temporary solution */
2526  SCIP_CALL( SCIPcreateLPSol(scip, lpsol, NULL) );
2527 
2528  /* unlink the solution, so that newly solved lps don't have any influence on our copy */
2529  SCIP_CALL( SCIPunlinkSol(scip, *lpsol) );
2530 
2531  return SCIP_OKAY;
2533 
2534 /** Executes the branching on a given variable with a given value. */
2535 static
2537  SCIP* scip /**< SCIP data structure */,
2538  CONFIGURATION* config, /**< config struct with the user configuration */
2539  BRANCHINGDECISION* decision /**< the decision with all the needed data */
2540  )
2541 {
2542  SCIP_VAR* bestvar;
2543  SCIP_Real bestval;
2544  SCIP_NODE* downchild = NULL;
2545  SCIP_NODE* upchild = NULL;
2546 
2547  assert(scip != NULL);
2548  assert(decision != NULL);
2549  assert(config != NULL);
2550 
2551  bestvar = decision->branchvar;
2552  bestval = decision->branchval;
2553  assert(bestvar != NULL);
2554 
2555  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Effective branching on var <%s> with value <%g(%g)>. Old domain: [%g..%g].\n",
2556  SCIPvarGetName(bestvar), bestval, SCIPgetSolVal(scip, NULL, bestvar), SCIPvarGetLbLocal(bestvar), SCIPvarGetUbLocal(bestvar));
2557 
2558  assert(!SCIPisIntegral(scip, bestval));
2559 
2560  /* branch on the given variable */
2561  assert(SCIPisLT(scip, SCIPvarGetLbLocal(bestvar), bestval));
2562  assert(SCIPisLT(scip, bestval, SCIPvarGetUbLocal(bestvar)));
2563  SCIP_CALL( SCIPbranchVarVal(scip, bestvar, bestval, &downchild, NULL, &upchild) );
2564 
2565  SCIPdebugMsg(scip, "down child (node %" SCIP_LONGINT_FORMAT "): branching bound change <%s> <= %g\n",
2566  SCIPnodeGetNumber(downchild), SCIPvarGetName(bestvar), SCIPfeasFloor(scip, bestval));
2567  SCIPdebugMsg(scip, "up child (node %" SCIP_LONGINT_FORMAT "): branching bound change <%s> >= %g\n",
2568  SCIPnodeGetNumber(upchild), SCIPvarGetName(bestvar), SCIPfeasCeil(scip, bestval));
2569 
2570  assert(downchild != NULL);
2571  assert(upchild != NULL);
2572 
2573  /* update the lower bounds in the children; we must not do this if columns are missing in the LP
2574  * (e.g., because we are doing branch-and-price) or the problem should be solved exactly */
2575  if( SCIPallColsInLP(scip) && !SCIPisExactSolve(scip) )
2576  {
2577  SCIP_Real bestdown = decision->downdb;
2578  SCIP_Bool bestdownvalid = decision->downdbvalid;
2579  SCIP_Real bestup = decision->updb;
2580  SCIP_Bool bestupvalid = decision->updbvalid;
2581  SCIP_Real provedbound = decision->proveddb;
2582 
2583  /* update the lower bound for the LPs for further children of both created nodes */
2584  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
2585  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
2586 
2587  if( decision->boundsvalid && config->applychildbounds )
2588  {
2589  SCIP_VAR** vars;
2590  int nvars;
2591  int i;
2592 
2593  assert(decision->downlowerbounds != NULL);
2594  assert(decision->downupperbounds != NULL);
2595  assert(decision->uplowerbounds != NULL);
2596  assert(decision->upupperbounds != NULL);
2597 
2598  nvars = SCIPgetNVars(scip);
2599  vars = SCIPgetVars(scip);
2600 
2601  assert(nvars == decision->boundssize);
2602 
2603  for( i = 0; i < nvars; i++ )
2604  {
2605  SCIP_VAR* var = vars[i];
2606  SCIP_Real currentlb;
2607  SCIP_Real currentub;
2608  SCIP_Real newlb = decision->downlowerbounds[i];
2609  SCIP_Real newub = decision->downupperbounds[i];
2610  assert(var != NULL);
2611 
2612  currentlb = SCIPvarGetLbLocal(var);
2613  currentub = SCIPvarGetUbLocal(var);
2614 
2615  /* update the lower bound of the lower child in case it is better than the current one */
2616  if( SCIPisGT(scip, newlb, currentlb) )
2617  {
2618  SCIP_CALL( SCIPchgVarLbNode(scip, downchild, var, newlb) );
2619 
2620  SCIPdebugMsg(scip, "down child (node %" SCIP_LONGINT_FORMAT "): add bound change <%s> >= %g\n",
2621  SCIPnodeGetNumber(downchild), SCIPvarGetName(var), newlb);
2622  }
2623 
2624  /* update the upper bound of the lower child in case it is better than the current one AND it is not the
2625  * branching variable, as its upper bound is already updated
2626  */
2627  if( SCIPisLT(scip, newub, currentub) && var != bestvar )
2628  {
2629  SCIP_CALL( SCIPchgVarUbNode(scip, downchild, var, newub) );
2630 
2631  SCIPdebugMsg(scip, "down child (node %" SCIP_LONGINT_FORMAT "): add bound change <%s> <= %g\n",
2632  SCIPnodeGetNumber(downchild), SCIPvarGetName(var), newub);
2633  }
2634 
2635  newlb = decision->uplowerbounds[i];
2636  newub = decision->upupperbounds[i];
2637 
2638  /* update the lower bound of the upper child in case it is better than the current one AND it is not the
2639  * branching variable, as its lower bound is already updated
2640  */
2641  if( SCIPisGT(scip, newlb, currentlb) && var != bestvar)
2642  {
2643  SCIP_CALL( SCIPchgVarLbNode(scip, upchild, var, newlb) );
2644 
2645  SCIPdebugMsg(scip, "up child (node %" SCIP_LONGINT_FORMAT "): add bound change <%s> >= %g\n",
2646  SCIPnodeGetNumber(upchild), SCIPvarGetName(var), newlb);
2647  }
2648 
2649  /* update the upper bound of the upper child in case it is better than the current one */
2650  if( SCIPisLT(scip, newub, currentub) )
2651  {
2652  SCIP_CALL( SCIPchgVarUbNode(scip, upchild, var, newub) );
2653 
2654  SCIPdebugMsg(scip, "up child (node %" SCIP_LONGINT_FORMAT "): add bound change <%s> <= %g\n",
2655  SCIPnodeGetNumber(upchild), SCIPvarGetName(var), newub);
2656  }
2657  }
2658  }
2659  }
2660  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, " -> down child's lowerbound: %.9g, estimate: %.9g\n",
2661  SCIPnodeGetLowerbound(downchild), SCIPnodeGetEstimate(downchild));
2662  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, " -> up child's lowerbound: %.9g, estimate: %.9g\n",
2663  SCIPnodeGetLowerbound(upchild), SCIPnodeGetEstimate(upchild));
2664 
2665  return SCIP_OKAY;
2666 }
2667 
2668 /** Get the number of iterations the last LP needed */
2669 static
2671  SCIP* scip, /**< SCIP data structure */
2672  SCIP_Longint* iterations /**< pointer to store the number of iterations */
2673  )
2674 {
2675  SCIP_LPI* lpi;
2676  int tmpiter;
2677 
2678  assert(scip != NULL);
2679  assert(iterations != NULL);
2680 
2681  /* get the LP interface of the last solved LP */
2682  SCIP_CALL( SCIPgetLPI(scip, &lpi) );
2683 
2684  /* get the number of iterations from the interface */
2685  SCIP_CALL( SCIPlpiGetIterations(lpi, &tmpiter) );
2686 
2687  *iterations = (SCIP_Longint)tmpiter;
2688 
2689  return SCIP_OKAY;
2690 }
2691 
2692 /** Creates a new probing node with a new bound for the given candidate and solves the corresponding LP. */
2693 static
2695  SCIP* scip, /**< SCIP data structure */
2696  CONFIGURATION* config, /**< configuration to control the behavior */
2697  SCIP_Bool downbranching, /**< the branching direction */
2698  CANDIDATE* candidate, /**< the candidate to branch on */
2699  BRANCHINGRESULTDATA* resultdata, /**< pointer to the result data which gets filled with the status */
2700  SCIP_SOL* baselpsol, /**< the base lp solution */
2701  DOMAINREDUCTIONS* domreds, /**< struct to store the domain reduction found during propagation */
2702  STATUS* status /**< status will contain updated lperror and limit fields */
2703  )
2704 {
2705  SCIP_Real oldupperbound;
2706  SCIP_Real oldlowerbound;
2707  SCIP_Real newbound;
2708  SCIP_LPSOLSTAT solstat;
2709  SCIP_VAR* branchvar;
2710  SCIP_Real branchval;
2711 
2712  assert(scip != NULL);
2713  assert(candidate != NULL);
2714  assert(resultdata != NULL);
2715  assert(status != NULL);
2716  assert(config != NULL);
2717  assert(status != NULL);
2718 
2719  branchvar = candidate->branchvar;
2720  branchval = candidate->branchval;
2721 
2722  assert(branchvar != NULL);
2723  assert(!SCIPisFeasIntegral(scip, branchval));
2724 
2725  if( downbranching )
2726  {
2727  /* round the given value down, so that it can be used as the new upper bound */
2728  newbound = SCIPfeasFloor(scip, branchval);
2729  }
2730  else
2731  {
2732  /* round the given value up, so that it can be used as the new lower bound */
2733  newbound = SCIPfeasCeil(scip, branchval);
2734  }
2735 
2736  oldupperbound = SCIPvarGetUbLocal(branchvar);
2737  oldlowerbound = SCIPvarGetLbLocal(branchvar);
2738 
2739 #ifdef SCIP_DEBUG
2740  if( downbranching )
2741  {
2742  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "DownBranching: Var=<%s>, Proposed upper bound=<%g>, "
2743  "old bounds=[<%g>..<%g>], new bounds=[<%g>..<%g>]\n", SCIPvarGetName(branchvar), newbound, oldlowerbound,
2744  oldupperbound, oldlowerbound, newbound);
2745  }
2746  else
2747  {
2748  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "UpBranching: Var=<%s>, Proposed lower bound=<%g>, "
2749  "old bounds=[<%g>..<%g>], new bounds=[<%g>..<%g>]\n", SCIPvarGetName(branchvar), newbound, oldlowerbound,
2750  oldupperbound, newbound, oldupperbound);
2751  }
2752 #endif
2753 
2754  if( (downbranching && newbound < oldlowerbound - 0.5)
2755  || (!downbranching && newbound > oldupperbound + 0.5) )
2756  {
2757  /* if lb > ub we can cutoff this node */
2758  resultdata->cutoff = TRUE;
2759 
2760  return SCIP_OKAY;
2761  }
2762 
2763  assert(!resultdata->cutoff);
2764 
2765  SCIP_CALL( SCIPnewProbingNode(scip) );
2766 
2767  if( downbranching )
2768  {
2769  /* down branching preparations */
2770  if( SCIPisFeasLT(scip, newbound, oldupperbound) )
2771  {
2772  /* If the new upper bound is smaller than the old upper bound and also
2773  * greater than (or equal to) the old lower bound, we set the new upper bound.
2774  * oldLowerBound <= newUpperBound < oldUpperBound */
2775  SCIP_CALL( SCIPchgVarUbProbing(scip, branchvar, newbound) );
2776  }
2777  }
2778  else
2779  {
2780  /* up branching preparations */
2781  if( SCIPisFeasGT(scip, newbound, oldlowerbound) )
2782  {
2783  /* If the new lower bound is greater than the old lower bound and also
2784  * smaller than (or equal to) the old upper bound, we set the new lower bound.
2785  * oldLowerBound < newLowerBound <= oldUpperBound
2786  */
2787  SCIP_CALL( SCIPchgVarLbProbing(scip, branchvar, newbound) );
2788  }
2789  }
2790 
2791  /* restore the stored LP data (e.g., the basis) from a filtering run */
2792  if( candidateHasWarmStartInfo(candidate, downbranching) )
2793  {
2794  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Restoring lp information for %s branch of variable <%s>\n",
2795  downbranching ? "down" : "up", SCIPvarGetName(branchvar));
2796  SCIP_CALL( candidateLoadWarmStartInfo(scip, candidate, downbranching) );
2797  }
2798 
2799  /* apply domain propagation */
2800  if( config->propagate )
2801  {
2802  SCIP_Longint ndomredsfound = 0;
2803 
2804  SCIP_CALL( SCIPpropagateProbing(scip, config->maxproprounds, &resultdata->cutoff, &ndomredsfound) );
2805 
2806  if( ndomredsfound > 0 )
2807  {
2808  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Found %" SCIP_LONGINT_FORMAT " domain reductions via propagation.\n", ndomredsfound);
2809 
2810  /* domreds != NULL iff config->usedomainreduction */
2811  if( domreds != NULL )
2812  {
2813  int i;
2814  SCIP_VAR** problemvars = SCIPgetVars(scip);
2815  int nproblemvars = SCIPgetNVars(scip);
2816 
2817  assert(problemvars != NULL);
2818 
2819  assert(config->usedomainreduction);
2820 
2821  for( i = 0; i < nproblemvars; i++ )
2822  {
2823  SCIP_Real lowerbound;
2824  SCIP_Real upperbound;
2825  SCIP_VAR* var = problemvars[i];
2826  assert(var != NULL);
2827 
2828  lowerbound = SCIPvarGetLbLocal(var);
2829  upperbound = SCIPvarGetUbLocal(var);
2830 #ifdef SCIP_STATISTIC
2831  addLowerBound(scip, var, lowerbound, baselpsol, FALSE, domreds, 0, FALSE);
2832  addUpperBound(scip, var, upperbound, baselpsol, FALSE, domreds, 0, FALSE);
2833 #else
2834  addLowerBound(scip, var, lowerbound, baselpsol, FALSE, domreds);
2835  addUpperBound(scip, var, upperbound, baselpsol, FALSE, domreds);
2836 #endif
2837  }
2838  }
2839  }
2840  }
2841 
2842  if( !resultdata->cutoff )
2843  {
2844  /* solve the prepared probing LP */
2845  SCIP_CALL( SCIPsolveProbingLP(scip, -1, &status->lperror, &resultdata->cutoff) );
2846 
2847  /* store the number of iterations needed */
2848  SCIP_CALL( getNIterationsLastLP(scip, &resultdata->niterations) );
2849 
2850  solstat = SCIPgetLPSolstat(scip);
2851  assert(solstat != SCIP_LPSOLSTAT_UNBOUNDEDRAY);
2852 
2853  /* for us an error occurred, if an error during the solving occurred or the lp could not be solved but was not
2854  * cutoff */
2855  status->lperror = status->lperror || (solstat == SCIP_LPSOLSTAT_NOTSOLVED && resultdata->cutoff == FALSE);
2856 
2857  /* if we seem to have reached a {time, iteration}-limit or the user cancelled the execution, we want to stop
2858  * further calculations and instead return the current calculation state */
2859  status->limitreached = (solstat == SCIP_LPSOLSTAT_ITERLIMIT) || (solstat == SCIP_LPSOLSTAT_TIMELIMIT);
2860 
2861  if( resultdata->cutoff )
2862  {
2863  resultdata->objval = SCIPinfinity(scip);
2864  resultdata->dualbound = SCIPinfinity(scip);
2865  resultdata->dualboundvalid = TRUE;
2866  }
2867  else if( !status->limitreached && !status->lperror )
2868  {
2869  SCIP_Bool foundsol = FALSE;
2870 
2871  SCIP_CALL( SCIPtryStrongbranchLPSol(scip, &foundsol, &resultdata->cutoff) );
2872 
2873  /* if we have no error, we save the new objective value and the cutoff decision in the resultdata */
2874  resultdata->objval = SCIPgetLPObjval(scip);
2875  resultdata->dualbound = SCIPgetLPObjval(scip);
2876  resultdata->dualboundvalid = TRUE;
2877  resultdata->cutoff = resultdata->cutoff || SCIPisGE(scip, resultdata->objval, SCIPgetCutoffbound(scip));
2878 
2879  assert(solstat != SCIP_LPSOLSTAT_INFEASIBLE || resultdata->cutoff);
2880  }
2881  }
2882 
2883  return SCIP_OKAY;
2884 }
2885 
2886 /** Creates a logic or constraint based on the given 'consvars'. This array has to consist of the negated
2887  * versions of the variables present on a cutoff "path" (path means all variables from the root directly
2888  * to the cutoff node).
2889  * Let x_1, ..., x_n be the variables on a path to a cutoff with the branchings x_i <= 1 for all i.
2890  * Summed up the constraints would look like x_1 + ... x_n <= n-1.
2891  * Let y_i = 1 - x_i. Then we have y_1 + ... + y_n >= 1 which is a logic or constraint.
2892  */
2893 static
2895  SCIP* scip, /**< SCIP data structure */
2896  CONFIGURATION* config, /**< configuration containing flags changing the behavior */
2897  SCIP_CONS** constraint, /**< pointer to store the created constraint in */
2898  char* constraintname, /**< name of the new constraint */
2899  SCIP_VAR** consvars, /**< array containing the negated binary vars */
2900  int nconsvars /**< the number of elements in 'consvars' */
2901  )
2902 {
2903  SCIP_Bool initial;
2904  SCIP_Bool separate;
2905  SCIP_Bool removable;
2906  SCIP_Bool enforce = FALSE;
2907  SCIP_Bool check = FALSE;
2908  SCIP_Bool propagate = TRUE;
2909  SCIP_Bool local = TRUE;
2910  SCIP_Bool modifiable = FALSE;
2911  SCIP_Bool dynamic = FALSE;
2912  SCIP_Bool stickingatnode = FALSE;
2913 
2914  assert(scip != NULL);
2915  assert(config != NULL);
2916  assert(constraint != NULL);
2917  assert(constraintname != NULL);
2918  assert(consvars != NULL);
2919  assert(nconsvars > 0);
2920 
2921  initial = (config->addbinconsrow == 2);
2922  separate = (config->addbinconsrow == 1);
2923  removable = (config->addbinconsrow == 1);
2924 
2925  /* creating a logic or constraint based on the list of vars in 'consvars'.
2926  * A logic or constraints looks like that: y_1 + ... + y_n >= 1.
2927  */
2928  SCIP_CALL( SCIPcreateConsLogicor(scip, constraint, constraintname, nconsvars, consvars, initial, separate, enforce,
2929  check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2930  return SCIP_OKAY;
2931 }
2932 
2933 /**
2934  * Create a name for the binary constraint.
2935  */
2936 static
2938  SCIP_VAR** binaryvars, /**< the variables contained in the constraint */
2939  int nbinaryvars, /**< the number of elements in 'binaryvars' */
2940  char* constraintname /**< the char pointer to store the name in */
2941  )
2942 {
2943  int i;
2944 
2945  assert(binaryvars != NULL);
2946  assert(nbinaryvars > 0);
2947  assert(constraintname != NULL);
2948  assert(binaryvars[0] != NULL);
2949 
2950  (void) SCIPsnprintf(constraintname, SCIP_MAXSTRLEN, "lookahead_bin_%s", SCIPvarGetName(binaryvars[0]));
2951 
2952  for( i = 1; i < nbinaryvars; i++ )
2953  {
2954  size_t oldlen;
2955  SCIP_VAR* var = binaryvars[i];
2956  assert(var != NULL);
2957 
2958  oldlen = strlen(constraintname);
2959  (void) strncat(constraintname, "_", SCIP_MAXSTRLEN-oldlen);
2960  (void) strncat(constraintname, SCIPvarGetName(var), SCIP_MAXSTRLEN-oldlen-1);
2961  }
2962 }
2963 
2964 /**
2965  * Add the constraints found during the lookahead branching.
2966  * The implied binary bounds were found when two or more consecutive branchings of binary variables were cutoff. Then these
2967  * branching constraints can be combined into a single 'binary constraint'.
2968  */
2969 static
2971  SCIP* scip, /**< SCIP data structure */
2972  CONFIGURATION* config, /**< the configuration of the branching rule */
2973  BINCONSDATA* binconsdata, /**< collected binary constraints */
2974  SCIP_SOL* baselpsol /**< the original lp solution, used to check the violation of the constraint */
2975 #ifdef SCIP_STATISTIC
2976  ,STATISTICS* statistics /**< statistics data */
2977 #endif
2978  )
2979 {
2980  assert(scip != NULL);
2981  assert(config != NULL);
2982  assert(binconsdata != NULL);
2983  assert(baselpsol != NULL);
2984  assert(binconsdata->binaryvars != NULL);
2985  assert(binconsdata->binaryvars->nbinaryvars > 0);
2986 
2987  /* if we only have one var for the constraint, we can ignore it as it is already added as a domain reduction. */
2988  if( binconsdata->binaryvars->nbinaryvars > 1 )
2989  {
2990  int i;
2991  SCIP_VAR** negatedvars;
2992  SCIP_Real lhssum = 0.0;
2993  SCIP_Bool violated;
2994 
2995  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Adding binary constraint for <%i> vars.\n",
2996  binconsdata->binaryvars->nbinaryvars);
2997 
2998  SCIP_CALL( SCIPallocBufferArray(scip, &negatedvars, binconsdata->binaryvars->nbinaryvars) );
2999 
3000  for( i = 0; i < binconsdata->binaryvars->nbinaryvars; i++ )
3001  {
3002  SCIP_VAR* var = binconsdata->binaryvars->binaryvars[i];
3003  assert(var != NULL);
3004  assert(SCIPvarIsBinary(var));
3005 
3006  SCIP_CALL( SCIPgetNegatedVar(scip, var, &negatedvars[i]) );
3007  lhssum += SCIPgetSolVal(scip, baselpsol, negatedvars[i]);
3008  }
3009 
3010  violated = (lhssum < 1);
3011 
3012  if( config->addnonviocons || violated )
3013  {
3014  SCIP_CALL( constraintListAppend(scip, binconsdata->conslist, negatedvars,
3015  binconsdata->binaryvars->nbinaryvars, violated) );
3016 
3017  /* the constraint we will be building is a logic or: we have a list of binary variables that were
3018  * cutoff while we branched on with >= 1. So we have the constraint: x_1 + ... + x_n <= n-1.
3019  * Let y = (1-x), then we have an equivalent formulation: y_1 + ... + y_n >= 1. If the base lp
3020  * is violating this constraint we count this for our number of violated constraints and bounds. */
3021  if( violated )
3022  binconsdata->conslist->nviolatedcons++;
3023  }
3024 
3025  SCIPfreeBufferArray(scip, &negatedvars);
3026  }
3027 #ifdef SCIP_STATISTIC
3028  else
3029  {
3030  assert(statistics != NULL);
3031  statistics->ndomredcons++;
3032  }
3033 #endif
3034 
3035  return SCIP_OKAY;
3036 }
3037 
3038 /** applies the binary constraints to the original problem. */
3039 static
3041  SCIP* scip, /**< SCIP data structure */
3042  SCIP_NODE* basenode, /**< original branching node */
3043  CONSTRAINTLIST* conslist, /**< list of constraints to be added */
3044  CONFIGURATION* config, /**< the configuration of the branching rule */
3045  SCIP_Bool* consadded, /**< pointer to store whether at least one constraint was added */
3046  SCIP_Bool* cutoff, /**< pointer to store whether the original problem was made infeasible */
3047  SCIP_Bool* boundchange /**< pointer to store whether a bound change has been applied by adding the
3048  * constraint as a clique */
3049 #ifdef SCIP_STATISTIC
3050  ,STATISTICS* statistics /**< statistics data */
3051 #endif
3052  )
3053 {
3054  int nconsadded = 0;
3055  int i;
3056 #ifdef SCIP_STATISTIC
3057  int nvioconsadded = 0;
3058 
3059  assert(statistics != NULL);
3060 #endif
3061  assert(basenode != NULL);
3062  assert(conslist != NULL);
3063  assert(config != NULL);
3064  assert(consadded != NULL);
3065  assert(cutoff != NULL);
3066  assert(boundchange != NULL);
3067 
3068  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "processing %d binary constraints.\n", conslist->nelements);
3069 
3070  if( conslist->nelements == 0 )
3071  return SCIP_OKAY;
3072 
3073  for( i = 0; i < conslist->nelements; i++ )
3074  {
3075  SCIP_VAR** vars = conslist->consvars[i];
3076  int nvars = conslist->nconsvars[i];
3077  int v;
3078 #ifdef SCIP_STATISTIC
3079  SCIP_Bool violated = conslist->violated[i];
3080 #endif
3081 
3082  assert(vars != NULL);
3083 
3084  for( v = 0; v < nvars; ++v )
3085  {
3086  assert(vars[v] != NULL);
3087  assert(SCIPvarIsBinary(vars[v]));
3088 
3089  if( SCIPvarGetLbLocal(vars[v]) > 0.5 )
3090  break;
3091  }
3092 
3093  /* no variable is fixed to 1 yet, so constraint is not redundant */
3094  if( v == nvars )
3095  {
3096  SCIP_CONS* constraint;
3097  char constraintname[SCIP_MAXSTRLEN];
3098 
3099  /* create a name for the new constraint */
3100  createBinaryConstraintName(vars, nvars, constraintname);
3101  /* create the constraint with the freshly created name */
3102  SCIP_CALL( createBinaryConstraint(scip, config, &constraint, constraintname, vars, nvars) );
3103 
3104 #ifdef PRINTNODECONS
3105  SCIPinfoMessage(scip, NULL, "Created constraint:\n");
3106  SCIP_CALL( SCIPprintCons(scip, constraint, NULL) );
3107  SCIPinfoMessage(scip, NULL, "\n");
3108 #endif
3109  /* add the constraint to the given node */
3110  SCIP_CALL( SCIPaddConsNode(scip, basenode, constraint, NULL) );
3111 
3112  nconsadded++;
3113 
3114 #ifdef SCIP_STATISTIC
3115  if( violated )
3116  nvioconsadded++;
3117 #endif
3118 
3119  /* release the constraint, as it is no longer needed */
3120  SCIP_CALL( SCIPreleaseCons(scip, &constraint) );
3121 
3122  /* a 2-variable logicor constraint can be expressend as a clique on the negated variables;
3123  * add it to the clique table if we are at the root node */
3124  if( nvars == 2 && config->addclique && SCIPgetNNodes(scip) == 1 )
3125  {
3126  SCIP_Bool* values;
3127  SCIP_Bool infeasible;
3128  int nbdchgs;
3129 
3130  SCIP_CALL( SCIPallocClearBufferArray(scip, &values, nvars) );
3131 
3132  /* a two-variable logicor constraint x + y >= 1 yields the implication x == 0 -> y == 1, and is represented
3133  * by the clique inequality ~x + ~y <= 1
3134  */
3135  SCIP_CALL( SCIPaddClique(scip, vars, values, nvars, FALSE, &infeasible, &nbdchgs) );
3136 
3137 #ifdef SCIP_STATISTIC
3138  statistics->ncliquesadded++;
3139 #endif
3140 
3141  if( infeasible )
3142  *cutoff = TRUE;
3143 
3144  if( nbdchgs > 0 )
3145  *boundchange = TRUE;
3146 
3147  SCIPfreeBufferArray(scip, &values);
3148  }
3149  }
3150  }
3151 
3152  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "added %d/%d binary constraints.\n", nconsadded, conslist->nelements);
3153 
3154  if( nconsadded > 0 )
3155  {
3156  *consadded = TRUE;
3157 
3158 #ifdef SCIP_STATISTIC
3159  statistics->nbinconst += nconsadded;
3160  statistics->nbinconstvio += nvioconsadded;
3161 #endif
3162  }
3163 
3164  return SCIP_OKAY;
3165 }
3166 
3167 /** checks whether the given bounds are still the bounds of the given variable */
3168 static
3170  SCIP* scip, /**< SCIP data structure */
3171  SCIP_VAR* var, /**< variable to check the bounds of */
3172  SCIP_Real lowerbound, /**< reference lower bound */
3173  SCIP_Real upperbound /**< reference upper bound */
3174  )
3175 {
3176  assert(scip != NULL);
3177  assert(var != NULL);
3178  assert(SCIPisFeasIntegral(scip, lowerbound));
3179  assert(SCIPisFeasIntegral(scip, upperbound));
3180  assert(!SCIPisEQ(scip, lowerbound, upperbound));
3181  assert(SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS);
3182 
3183  /* due to roundings the value might have changed slightly without an actual influence on the integral value */
3184  return SCIPvarGetLbLocal(var) > lowerbound + 0.5 || SCIPvarGetUbLocal(var) < upperbound - 0.5;
3185 }
3186 
3187 /** Checks whether the branching rule should continue or terminate with the currently gathered data */
3188 static
3190  STATUS* status, /**< current status */
3191  SCIP_Bool checkdomreds /**< should domain reductions be checked? */
3192  )
3193 {
3194  assert(status != NULL);
3195 
3196  return !status->lperror && !status->cutoff && !status->limitreached
3197  && !status->maxnconsreached && (!checkdomreds || !status->domred);
3198 }
3199 
3200 /** Checks whether the branching rule should continue or terminate with the currently gathered data. Additionally decrements
3201  * the given loopcounter. This is needed to better emulate the behavior of FSB by LAB with a depth of 1. */
3202 static
3204  STATUS* status, /**< current status */
3205  int* loopcounter /**< the counter to decrement */
3206  )
3207 {
3208  SCIP_Bool branchfurther;
3209 
3210  assert(status != NULL);
3211  assert(loopcounter != NULL);
3212 
3213  branchfurther = isBranchFurther(status, FALSE);
3214 
3215  if( !branchfurther )
3216  (*loopcounter)--;
3217 
3218  return branchfurther;
3219 }
3220 
3221 /** determines whether the previous LAB result of a variable should be reused */
3222 static
3224  SCIP* scip, /**< SCIP data structure */
3225  PERSISTENTDATA* persistent, /**< data storage over multiple calls to the rule */
3226  CONFIGURATION* config, /**< the configuration of the branching rule */
3227  SCIP_VAR* branchvar /**< variable to check */
3228  )
3229 {
3230  assert(scip != NULL);
3231  assert(config != NULL);
3232  assert(branchvar != NULL);
3233 
3234  /* an old branching can be reused, if we are still at the same node and just a few LPs were solved in between */
3235  if( config->inscoring )
3236  {
3237  return SCIPgetVarStrongbranchNode(scip, branchvar) == SCIPgetNNodes(scip)
3238  && SCIPgetVarStrongbranchLPAge(scip, branchvar) < config->reevalagefsb;
3239  }
3240  else
3241  {
3242  return persistent->lastbranchid[SCIPvarGetProbindex(branchvar)] == SCIPgetNNodes(scip)
3243  && SCIPgetNLPs(scip) - persistent->lastbranchnlps[SCIPvarGetProbindex(branchvar)] < config->reevalage;
3244  }
3245 }
3246 
3247 /** retrieves previous LAB result for the given variable */
3248 static
3250  SCIP* scip, /**< SCIP data structure */
3251  PERSISTENTDATA* persistent, /**< data storage over multiple calls to the rule */
3252  CONFIGURATION* config, /**< the configuration of the branching rule */
3253  SCIP_VAR* branchvar, /**< variable to get previous results for */
3254  BRANCHINGRESULTDATA* downbranchingresult,/**< pointer to store the previous down result in */
3255  BRANCHINGRESULTDATA* upbranchingresult, /**< pointer to store the previous up result in */
3256  SCIP_Real* oldlpobjval /**< pointer to store the previous base lp objval in */
3257  )
3258 {
3259  assert(scip != NULL);
3260  assert(persistent != NULL);
3261  assert(branchvar != NULL);
3262  assert(downbranchingresult != NULL);
3263  assert(upbranchingresult != NULL);
3264  assert(oldlpobjval != NULL);
3265 
3266  if( config->inscoring )
3267  {
3268  SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchvar, &downbranchingresult->dualbound, &upbranchingresult->dualbound,
3269  &downbranchingresult->dualboundvalid, &upbranchingresult->dualboundvalid, NULL, oldlpobjval) );
3270  downbranchingresult->objval = downbranchingresult->dualbound;
3271  upbranchingresult->objval = upbranchingresult->dualbound;
3272  }
3273  else
3274  {
3275  int varindex = SCIPvarGetProbindex(branchvar);
3276 
3277  branchingResultDataCopy(persistent->lastbranchdownres[varindex], downbranchingresult);
3278  branchingResultDataCopy(persistent->lastbranchupres[varindex], upbranchingresult);
3279  *oldlpobjval = persistent->lastbranchlpobjval[varindex];
3280  }
3281 
3282 #ifdef SCIP_DEBUG
3283  {
3284  SCIP_Real downgain;
3285  SCIP_Real upgain;
3286 
3287  downgain = MAX(downbranchingresult->dualbound - *oldlpobjval, 0);
3288  upgain = MAX(upbranchingresult->dualbound - *oldlpobjval, 0);
3289 
3290  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Lookahead branching on variable <%s> already performed (lpage=%"
3291  SCIP_LONGINT_FORMAT ", down=%.9g (%+g), up=%.9g (%+g))\n", SCIPvarGetName(branchvar),
3292  SCIPgetNLPs(scip) - persistent->lastbranchnlps[SCIPvarGetProbindex(branchvar)],
3293  downbranchingresult->dualbound, downgain, upbranchingresult->dualbound, upgain);
3294  }
3295 #endif
3296 
3297  return SCIP_OKAY;
3298 }
3299 
3300 /** stores the LAB result for use in a later call to the branching rule */
3301 static
3303  SCIP* scip, /**< SCIP data structure */
3304  PERSISTENTDATA* persistent, /**< data storage over multiple calls to the rule */
3305  CONFIGURATION* config, /**< the configuration of the branching rule */
3306  SCIP_VAR* branchvar, /**< variable to store previous results for */
3307  SCIP_Real branchval, /**< the value of branchvar */
3308  BRANCHINGRESULTDATA* downbranchingresult,/**< down branching result to store */
3309  BRANCHINGRESULTDATA* upbranchingresult, /**< up branching result to store */
3310  SCIP_Real lpobjval /**< base lp obj val */
3311  )
3312 {
3313  assert(scip != NULL);
3314  assert(persistent != NULL);
3315  assert(branchvar != NULL);
3316  assert(downbranchingresult != NULL);
3317  assert(upbranchingresult != NULL);
3318 
3319  if( config->inscoring )
3320  {
3321  SCIP_Longint niterations = downbranchingresult->niterations + upbranchingresult->niterations;
3322 
3323  SCIP_CALL( SCIPsetVarStrongbranchData(scip, branchvar, lpobjval, branchval, downbranchingresult->dualbound,
3324  upbranchingresult->dualbound, downbranchingresult->dualboundvalid, upbranchingresult->dualboundvalid, niterations,
3325  INT_MAX) );
3326  }
3327  else
3328  {
3329  int varindex = SCIPvarGetProbindex(branchvar);
3330 
3331  branchingResultDataCopy(downbranchingresult, persistent->lastbranchdownres[varindex]);
3332  branchingResultDataCopy(upbranchingresult, persistent->lastbranchupres[varindex]);
3333  persistent->lastbranchlpobjval[varindex] = lpobjval;
3334  persistent->lastbranchid[varindex] = SCIPgetNNodes(scip);
3335  persistent->lastbranchnlps[varindex] = SCIPgetNLPs(scip);
3336  }
3337 
3338  return SCIP_OKAY;
3339 }
3340 
3341 /** calculates the FSB scores for the given candidates */
3342 static
3344  SCIP* scip, /**< SCIP data structure */
3345  STATUS* status, /**< current status */
3346  PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */
3347  CONFIGURATION* config, /**< the configuration of the branching rule */
3348  SCIP_SOL* baselpsol, /**< base lp solution */
3349  DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found; or NULL */
3350  BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */
3351  CANDIDATELIST* candidatelist, /**< list containing all candidates to consider */
3352  BRANCHINGDECISION* decision, /**< struct to store the final decision */
3353  SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */
3354  LEVEL2DATA* level2data, /**< level 2 LP results data */
3355  SCIP_Real lpobjval /**< base LP objective value */
3356 #ifdef SCIP_STATISTIC
3357  ,STATISTICS* statistics /**< general statistical data */
3358  ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */
3359 #endif
3360  )
3361 {
3362  assert(scip != NULL);
3363  assert(config != NULL);
3364  assert(candidatelist != NULL);
3365  assert(status != NULL);
3366  assert(scorecontainer != NULL);
3367  assert(SCIPinProbing(scip));
3368  assert(SCIPgetProbingDepth(scip) >= 0 && SCIPgetProbingDepth(scip) < config->recursiondepth);
3369 
3370  /* inform configuration that we are in scoring mode now */
3371  config->inscoring = TRUE;
3372 
3373 #ifdef SCIP_STATISTIC
3374  SCIP_CALL( selectVarRecursive(scip, status, persistent, config, baselpsol, domainreductions,
3375  binconsdata, candidatelist, decision, scorecontainer, level2data, 1,
3376  lpobjval, lpobjval, NULL, NULL, NULL, NULL, NULL, NULL,
3377  statistics, localstats, NULL, NULL) );
3378 #else
3379  SCIP_CALL( selectVarRecursive(scip, status, persistent, config, baselpsol, domainreductions,
3380  binconsdata, candidatelist, decision, scorecontainer, level2data, 1,
3381  lpobjval, lpobjval, NULL, NULL, NULL, NULL, NULL, NULL) );
3382 #endif
3383 
3384  /* inform configuration that we leave scoring mode now */
3385  config->inscoring = FALSE;
3386 
3387  return SCIP_OKAY;
3388 }
3389 
3390 #ifdef SCIP_DEBUG
3391 /** prints the given candidate list */
3392 static
3393 void printCandidates(
3394  SCIP* scip, /**< SCIP data structure */
3395  SCIP_VERBLEVEL lvl, /**< verbosity level to print the list in */
3396  CANDIDATELIST* candidatelist /**< the list to be printed */
3397  )
3398 {
3399  int ncands;
3400  int i;
3401 
3402  assert(scip != NULL);
3403  assert(candidatelist != NULL);
3404 
3405  ncands = candidatelist->ncandidates;
3406 
3407  LABdebugMessagePrint(scip, lvl, "[");
3408 
3409  for( i = 0; i < ncands; i++ )
3410  {
3411  CANDIDATE* cand = candidatelist->candidates[i];
3412 
3413  assert(cand != NULL);
3414  assert(cand->branchvar != NULL);
3415 
3416  LABdebugMessagePrint(scip, lvl, "%s", SCIPvarGetName(cand->branchvar));
3417  if(i != ncands-1)
3418  {
3419  LABdebugMessagePrint(scip, lvl, ", ");
3420  }
3421  }
3422  LABdebugMessagePrint(scip, lvl, "]\n");
3423 }
3424 #endif
3425 
3426 /** calculates the score based on the down and up branching result */
3427 static
3429  SCIP* scip, /**< SCIP data structure */
3430  SCIP_VAR* branchvar, /**< variable to get the score for */
3431  BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */
3432  BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */
3433  SCIP_Real lpobjval /**< objective value to get difference to as gain */
3434  )
3435 {
3436  SCIP_Real score;
3437  SCIP_Real downgain = SCIPsumepsilon(scip);
3438  SCIP_Real upgain = SCIPsumepsilon(scip);
3439 
3440  assert(scip != NULL);
3441  assert(branchvar != NULL);
3442  assert(downbranchingresult != NULL);
3443  assert(upbranchingresult != NULL);
3444 
3445  /* the gain is the difference of the dualbound of a child and the reference objective value;
3446  * by bounding it by zero we are safe from numerical troubles
3447  */
3448  if( !downbranchingresult->cutoff )
3449  downgain = MAX(downgain, downbranchingresult->dualbound - lpobjval);
3450  if( !upbranchingresult->cutoff )
3451  upgain = MAX(upgain, upbranchingresult->dualbound - lpobjval);
3452 
3453  downgain = 100.0 * downgain;
3454  upgain = 100.0 * upgain;
3455 
3456  /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat
3457  * realistic gain for the infeasible child;
3458  * if both children are infeasible we just reset the initial zero values again
3459  */
3460  if( downbranchingresult->cutoff )
3461  downgain = 2 * upgain;
3462  if( upbranchingresult->cutoff )
3463  upgain = 2 * downgain;
3464 
3465  score = SCIPgetBranchScore(scip, branchvar, downgain, upgain);
3466 
3467  return score;
3468 }
3469 
3470 /** calculates the score based on the down and up branching result */
3471 static
3473  SCIP* scip, /**< SCIP data structure */
3474  SCIP_VAR* branchvar, /**< variable to get the score for */
3475  BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */
3476  BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */
3477  SCIP_Real lpobjval /**< objective value to get difference to as gain */
3478  )
3479 {
3480  SCIP_Real lpscore;
3481  SCIP_Real dbscore;
3482  SCIP_Real score;
3483  SCIP_Real downgain = SCIPsumepsilon(scip);
3484  SCIP_Real upgain = SCIPsumepsilon(scip);
3485 
3486  assert(scip != NULL);
3487  assert(branchvar != NULL);
3488  assert(downbranchingresult != NULL);
3489  assert(upbranchingresult != NULL);
3490 
3491  /* the gain is the difference of the dualbound of a child and the reference objective value;
3492  * by bounding it by zero we are safe from numerical troubles
3493  */
3494  if( !downbranchingresult->cutoff )
3495  downgain = MAX(downgain, downbranchingresult->objval - lpobjval);
3496  if( !upbranchingresult->cutoff )
3497  upgain = MAX(upgain, upbranchingresult->objval - lpobjval);
3498 
3499  downgain = 100.0 * downgain;
3500  upgain = 100.0 * upgain;
3501 
3502  /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat
3503  * realistic gain for the infeasible child;
3504  * if both children are infeasible we just reset the initial zero values again
3505  */
3506  if( downbranchingresult->cutoff )
3507  downgain = 2 * upgain;
3508  if( upbranchingresult->cutoff )
3509  upgain = 2 * downgain;
3510 
3511  lpscore = SCIPgetBranchScore(scip, branchvar, downgain, upgain);
3512 
3513  /* the gain is the difference of the dualbound of a child and the reference objective value;
3514  * by bounding it by zero we are safe from numerical troubles
3515  */
3516  if( !downbranchingresult->cutoff )
3517  downgain = MAX(SCIPsumepsilon(scip), downbranchingresult->dualbound - lpobjval); /*lint !e666*/
3518  if( !upbranchingresult->cutoff )
3519  upgain = MAX(SCIPsumepsilon(scip), upbranchingresult->dualbound - lpobjval); /*lint !e666*/
3520 
3521  downgain = 100.0 * downgain;
3522  upgain = 100.0 * upgain;
3523 
3524  /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat
3525  * realistic gain for the infeasible child;
3526  * if both children are infeasible we just reset the initial zero values again
3527  */
3528  if( downbranchingresult->cutoff )
3529  downgain = 2 * upgain;
3530  if( upbranchingresult->cutoff )
3531  upgain = 2 * downgain;
3532 
3533  dbscore = SCIPgetBranchScore(scip, branchvar, downgain, upgain);
3534 
3535  score = SCIPgetBranchScore(scip, branchvar, lpscore, dbscore);
3536 
3537  return score;
3538 }
3539 
3540 /** calculates the score based on the down and up branching scores */
3541 static
3543  SCIP* scip, /**< SCIP data structure */
3544  SCIP_VAR* branchvar, /**< variable to get the score for */
3545  BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */
3546  BRANCHINGRESULTDATA* upbranchingresult /**< branching result of the up branch */
3547  )
3548 {
3549  SCIP_Real score;
3550  SCIP_Real downscore;
3551  SCIP_Real upscore;
3552 
3553  assert(scip != NULL);
3554  assert(branchvar != NULL);
3555  assert(downbranchingresult != NULL);
3556  assert(upbranchingresult != NULL);
3558  assert(downbranchingresult->deeperscore >= -0.2 || downbranchingresult->cutoff || SCIPisStopped(scip));
3559  assert(upbranchingresult->deeperscore >= -0.2 || upbranchingresult->cutoff || SCIPisStopped(scip));
3560 
3561  downscore = sqrt(downbranchingresult->deeperscore);
3562  upscore = sqrt(upbranchingresult->deeperscore);
3563 
3564  downscore = MAX(downscore, SCIPsumepsilon(scip)); /*lint !e666*/
3565  upscore = MAX(upscore, SCIPsumepsilon(scip)); /*lint !e666*/
3566 
3567  if( downbranchingresult->cutoff )
3568  downscore = 2 * upscore;
3569  if( upbranchingresult->cutoff )
3570  upscore = 2 * downscore;
3571 
3572  score = SCIPgetBranchScore(scip, branchvar, downscore, upscore);
3573 
3574  return score;
3575 }
3576 
3577 /** calculates the score based on the down and up branching scores */
3578 static
3580  SCIP* scip, /**< SCIP data structure */
3581  SCIP_VAR* branchvar, /**< variable to get the score for */
3582  BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */
3583  BRANCHINGRESULTDATA* upbranchingresult /**< branching result of the up branch */
3584  )
3585 {
3586  SCIP_Real score;
3587  SCIP_Real downscore;
3588  SCIP_Real upscore;
3589  SCIP_Real totaldowngains;
3590  SCIP_Real totalupgains;
3591  SCIP_Real nlowestlevelcutoffs;
3592  int ntotaldowngains;
3593  int ntotalupgains;
3595  assert(scip != NULL);
3596  assert(branchvar != NULL);
3597  assert(downbranchingresult != NULL);
3598  assert(upbranchingresult != NULL);
3599 
3600  assert(downbranchingresult->deeperscore >= -0.2 || downbranchingresult->cutoff || SCIPisStopped(scip));
3601  assert(upbranchingresult->deeperscore >= -0.2 || upbranchingresult->cutoff || SCIPisStopped(scip));
3602 
3603  nlowestlevelcutoffs = (1.0 * downbranchingresult->ndeepestcutoffs + upbranchingresult->ndeepestcutoffs)/(MAX(1,downbranchingresult->ndeepestnodes + upbranchingresult->ndeepestnodes));
3604  totaldowngains = downbranchingresult->totalgains;
3605  totalupgains = upbranchingresult->totalgains;
3606  ntotaldowngains = MAX(1, downbranchingresult->ntotalgains);
3607  ntotalupgains = MAX(1, upbranchingresult->ntotalgains);
3608 
3609  downscore = sqrt(downbranchingresult->deeperscore);
3610  upscore = sqrt(upbranchingresult->deeperscore);
3611 
3612  downscore = MAX(downscore, SCIPsumepsilon(scip)); /*lint !e666*/
3613  upscore = MAX(upscore, SCIPsumepsilon(scip)); /*lint !e666*/
3614 
3615  if( downbranchingresult->cutoff )
3616  downscore = 2 * upscore;
3617  if( upbranchingresult->cutoff )
3618  upscore = 2 * downscore;
3619 
3620  score = SCIPgetBranchScore(scip, branchvar, downscore, upscore);
3621 
3622  downscore = sqrt(totaldowngains/ntotaldowngains);
3623  upscore = sqrt(totalupgains/ntotalupgains);
3624 
3625  downscore = MAX(downscore, SCIPsumepsilon(scip)); /*lint !e666*/
3626  upscore = MAX(upscore, SCIPsumepsilon(scip)); /*lint !e666*/
3627 
3628  score += SCIPgetBranchScore(scip, branchvar, downscore, upscore)*nlowestlevelcutoffs;
3629 
3630  return score;
3631 }
3632 
3633 /** calculates the combined gain, weighted with parameters given by the user configuration */
3634 static
3636  SCIP* scip, /**< SCIP data structure */
3637  CONFIGURATION* config, /**< LAB configuration */
3638  BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */
3639  BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */
3640  SCIP_Real lpobjval /**< objective value to get difference to as gain */
3641  )
3642 {
3643  SCIP_Real downgain = 0.0;
3644  SCIP_Real upgain = 0.0;
3645 
3646  assert(config != NULL);
3647  assert(downbranchingresult != NULL);
3648  assert(upbranchingresult != NULL);
3649 
3650  /* the gain is the difference of the dualbound of a child and the reference objective value;
3651  * by bounding it by zero we are safe from numerical troubles
3652  */
3653  if( !downbranchingresult->cutoff )
3654  downgain = MAX(0, downbranchingresult->dualbound - lpobjval);
3655  if( !upbranchingresult->cutoff )
3656  upgain = MAX(0, upbranchingresult->dualbound - lpobjval);
3657 
3658  if( config->scoringfunction == 's' )
3659  {
3660  if( downbranchingresult->cutoff )
3661  downgain = SCIPinfinity(scip);
3662  if( upbranchingresult->cutoff )
3663  upgain = SCIPinfinity(scip);
3664  }
3665  else
3666  {
3667  /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat
3668  * realistic gain for the infeasible child;
3669  * if both children are infeasible we just reset the initial zero values again
3670  */
3671  if( downbranchingresult->cutoff )
3672  downgain = upgain;
3673  if( upbranchingresult->cutoff )
3674  upgain = downgain;
3675  }
3676 
3677  return config->minweight * MIN(downgain, upgain) + (1.0 - config->minweight) * MAX(downgain, upgain);
3678 }
3679 
3680 /** calculates the score as mentioned in the lookahead branching paper by Glankwamdee and Linderoth;
3681  * their score scales the number of cutoffs on the last layer of a 2-level temporary branching tree with the average gain of
3682  * every last level problem; together with the best gain for each branch of a variable we get the final score
3683  */
3684 static
3686  BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */
3687  BRANCHINGRESULTDATA* upbranchingresult /**< branching result of the up branch */
3688  )
3689 {
3690  SCIP_Real bestdowngain;
3691  SCIP_Real bestupgain;
3692  SCIP_Real totaldowngains;
3693  SCIP_Real totalupgains;
3694  int nlowestlevelcutoffs;
3695  int ntotaldowngains;
3696  int ntotalupgains;
3697 
3698  assert(downbranchingresult != NULL);
3699  assert(upbranchingresult != NULL);
3701  nlowestlevelcutoffs = downbranchingresult->ndeepestcutoffs + upbranchingresult->ndeepestcutoffs;
3702  bestdowngain = downbranchingresult->bestgain;
3703  bestupgain = upbranchingresult->bestgain;
3704  totaldowngains = downbranchingresult->totalgains;
3705  totalupgains = upbranchingresult->totalgains;
3706  ntotaldowngains = MAX(1, downbranchingresult->ntotalgains);
3707  ntotalupgains = MAX(1, upbranchingresult->ntotalgains);
3708 
3709  return bestdowngain + bestupgain + (totaldowngains/ntotaldowngains + totalupgains/ntotalupgains)*nlowestlevelcutoffs;
3710 }
3711 
3712 /** calculates the score as mentioned in the lookahead branching paper by Glankwamdee and Linderoth;
3713  * their score scales the number of cutoffs on the last layer of a 2-level temporary branching tree with the average gain of
3714  * every last level problem; together with the best gain for each branch of a variable we get the final score
3715  */
3716 static
3718  CONFIGURATION* config, /**< LAB configuration */
3719  BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */
3720  BRANCHINGRESULTDATA* upbranchingresult /**< branching result of the up branch */
3721  )
3722 {
3723  SCIP_Real bestdowngain;
3724  SCIP_Real bestupgain;
3725  SCIP_Real totaldowngains;
3726  SCIP_Real totalupgains;
3727  SCIP_Real nlowestlevelcutoffs;
3728  int ntotaldowngains;
3729  int ntotalupgains;
3730 
3731  assert(downbranchingresult != NULL);
3732  assert(upbranchingresult != NULL);
3733 
3734  nlowestlevelcutoffs = (1.0 * downbranchingresult->ndeepestcutoffs + upbranchingresult->ndeepestcutoffs)/(downbranchingresult->ndeepestnodes + upbranchingresult->ndeepestnodes);
3735  bestdowngain = downbranchingresult->bestgain;
3736  bestupgain = upbranchingresult->bestgain;
3737  totaldowngains = downbranchingresult->totalgains;
3738  totalupgains = upbranchingresult->totalgains;
3739  ntotaldowngains = MAX(1, downbranchingresult->ntotalgains);
3740  ntotalupgains = MAX(1, upbranchingresult->ntotalgains);
3741 
3742  return config->minweight*MIN(bestdowngain, bestupgain) + (1.0 - config->minweight)*MAX(bestdowngain, bestupgain) + (totaldowngains/ntotaldowngains + totalupgains/ntotalupgains)*nlowestlevelcutoffs;
3743 }
3744 
3745 static
3747  SCIP* scip, /**< SCIP data structure */
3748  SCIP_VAR* branchvar, /**< variable to get the score for */
3749  BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */
3750  BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */
3751  SCIP_Real lpobjval /**< objective value to get difference to as gain */
3752  )
3753 {
3754  SCIP_Real score;
3755  SCIP_Real downgain = SCIPsumepsilon(scip);
3756  SCIP_Real upgain = SCIPsumepsilon(scip);
3757  SCIP_Real gap;
3758  int nlowestlevelcutoffs;
3759 
3760  assert(downbranchingresult != NULL);
3761  assert(upbranchingresult != NULL);
3762 
3763  nlowestlevelcutoffs = 0;
3764 
3765  /* the gain is the difference of the dualbound of a child and the reference objective value;
3766  * by bounding it by zero we are safe from numerical troubles
3767  */
3768  if( !downbranchingresult->cutoff )
3769  {
3770  nlowestlevelcutoffs += downbranchingresult->ndeepestcutoffs;
3771  downgain = MAX(downgain, downbranchingresult->dualbound - lpobjval);
3772  }
3773  if( !upbranchingresult->cutoff )
3774  {
3775  nlowestlevelcutoffs += upbranchingresult->ndeepestcutoffs;
3776  upgain = MAX(upgain, upbranchingresult->dualbound - lpobjval);
3777  }
3778 
3779  /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat
3780  * realistic gain for the infeasible child;
3781  * if both children are infeasible we just reset the initial zero values again
3782  */
3783  if( downbranchingresult->cutoff )
3784  {
3785  nlowestlevelcutoffs += 2 * SCIPgetNPseudoBranchCands(scip);
3786  downgain = 2 * upgain;
3787  }
3788  if( upbranchingresult->cutoff )
3789  {
3790  nlowestlevelcutoffs += 2 * SCIPgetNPseudoBranchCands(scip);
3791  upgain = 2 * downgain;
3792  }
3793 
3794  gap = SCIPgetCutoffbound(scip) - lpobjval;
3795 
3796  downgain = downgain/gap;
3797  upgain = upgain/gap;
3798 
3799  score = 1.0 * nlowestlevelcutoffs + SCIPgetBranchScore(scip, branchvar, downgain, upgain);
3800 
3801  return score;
3802 }
3803 
3804 static
3806  SCIP* scip, /**< SCIP data structure */
3807  SCIP_VAR* branchvar, /**< variable to get the score for */
3808  BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */
3809  BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */
3810  SCIP_Real lpobjval /**< objective value to get difference to as gain */
3811  )
3812 {
3813  SCIP_Real score;
3814  SCIP_Real downgain = SCIPsumepsilon(scip);
3815  SCIP_Real upgain = SCIPsumepsilon(scip);
3816  SCIP_Real gap;
3817  int factor;
3818  SCIP_Real nlowestlevelcutoffs;
3819 
3820  assert(downbranchingresult != NULL);
3821  assert(upbranchingresult != NULL);
3822 
3823  assert(downbranchingresult->ndeepestnodes + upbranchingresult->ndeepestnodes > 0 || (downbranchingresult->cutoff && upbranchingresult->cutoff));
3824 
3825  nlowestlevelcutoffs = (1.0 * downbranchingresult->ndeepestcutoffs + upbranchingresult->ndeepestcutoffs)/(1 + downbranchingresult->ndeepestnodes + upbranchingresult->ndeepestnodes);
3826 
3827  factor = SCIPgetNPseudoBranchCands(scip);
3828  if( factor > SCIPgetNLPRows(scip) )
3829  factor = SCIPgetNLPRows(scip);
3830  factor = factor * factor;
3831 
3832  /* the gain is the difference of the dualbound of a child and the reference objective value;
3833  * by bounding it by zero we are safe from numerical troubles
3834  */
3835  if( !downbranchingresult->cutoff )
3836  {
3837  downgain = MAX(downgain, downbranchingresult->dualbound - lpobjval);
3838  }
3839  if( !upbranchingresult->cutoff )
3840  {
3841  upgain = MAX(upgain, upbranchingresult->dualbound - lpobjval);
3842  }
3843 
3844  /* in case a child is infeasible and therefore cutoff we take the gain of the other child to receive a somewhat
3845  * realistic gain for the infeasible child;
3846  * if both children are infeasible we just reset the initial zero values again
3847  */
3848  if( downbranchingresult->cutoff )
3849  {
3850  downgain = 2 * upgain;
3851  }
3852  if( upbranchingresult->cutoff )
3853  {
3854  upgain = 2 * downgain;
3855  }
3856 
3857  gap = SCIPgetCutoffbound(scip) - lpobjval;
3858 
3859  downgain = downgain/gap;
3860  upgain = upgain/gap;
3861 
3862  score = factor * nlowestlevelcutoffs + SCIPgetBranchScore(scip, branchvar, downgain, upgain);
3863 
3864  return score;
3865 }
3866 
3867 /** scoring method that selects an actual scoring method based on the user configuration */
3868 static
3870  SCIP* scip, /**< SCIP data structure */
3871  CONFIGURATION* config, /**< LAB configuration */
3872  SCIP_VAR* branchvar, /**< variable to get the score for */
3873  BRANCHINGRESULTDATA* downbranchingresult,/**< branching result of the down branch */
3874  BRANCHINGRESULTDATA* upbranchingresult, /**< branching result of the up branch */
3875  SCIP_Real lpobjval, /**< objective value to get difference to as gain */
3876  SCIP_Real baselpobjval /**< base objective value to get difference to as gain */
3877  )
3878 {
3879  SCIP_Real score;
3880  char scoringfunction;
3881 
3882  assert(scip != NULL);
3883  assert(config != NULL);
3884  assert(branchvar != NULL);
3885  assert(downbranchingresult != NULL);
3886  assert(upbranchingresult != NULL);
3887 
3888  if( config->inscoring )
3889  scoringfunction = config->scoringscoringfunction;
3890  else if( SCIPgetProbingDepth(scip) > 0 )
3891  scoringfunction = config->deeperscoringfunction;
3892  else
3893  scoringfunction = config->scoringfunction;
3894 
3895  switch( scoringfunction )
3896  {
3897  case 's':
3898  score = calculateScaledCutoffScore(downbranchingresult, upbranchingresult);
3899  break;
3900  case 'w':
3901  score = calculateWeightedCutoffScore(config, downbranchingresult, upbranchingresult);
3902  break;
3903  case 'f':
3904  score = calculateWeightedGain(scip, config, downbranchingresult, upbranchingresult, baselpobjval);
3905  break;
3906  case 'p':
3907  score = calculateScoreFromDeeperscore(scip, branchvar, downbranchingresult, upbranchingresult);
3908  break;
3909  case 'a':
3910  score = calculateScoreFromDeeperscoreAndCutoffs(scip, branchvar, downbranchingresult, upbranchingresult);
3911  break;
3912  case 'l':
3913  score = calculateScoreFromResult2(scip, branchvar, downbranchingresult, upbranchingresult, lpobjval);
3914  break;
3915  case 'c':
3916  score = calculateCutoffScore(scip, branchvar, downbranchingresult, upbranchingresult, lpobjval);
3917  break;
3918  case 'r':
3919  score = calculateRelCutoffScore(scip, branchvar, downbranchingresult, upbranchingresult, lpobjval);
3920  break;
3921  case 'x':
3922  score = calculateScoreFromResult(scip, branchvar, downbranchingresult, upbranchingresult, baselpobjval);
3923  break;
3924  default:
3925  assert(scoringfunction == 'd');
3926  score = calculateScoreFromResult(scip, branchvar, downbranchingresult, upbranchingresult, lpobjval);
3927  }
3928 
3929  return score;
3930 }
3931 
3932 /** calculates the score based on the pseudocosts of the given variable */
3933 static
3935  SCIP* scip, /**< SCIP data structure */
3936  CANDIDATE* lpcand /**< candidate to get the score for */
3937  )
3938 {
3939  SCIP_Real downpseudocost;
3940  SCIP_Real uppseudocost;
3941  SCIP_Real score;
3942 
3943  assert(scip != NULL);
3944  assert(lpcand != NULL);
3945 
3946  downpseudocost = SCIPgetVarPseudocostVal(scip, lpcand->branchvar, 0-lpcand->fracval);
3947  uppseudocost = SCIPgetVarPseudocostVal(scip, lpcand->branchvar, 1-lpcand->fracval);
3948 
3949  score = SCIPgetBranchScore(scip, lpcand->branchvar, downpseudocost, uppseudocost);
3950 
3951  return score;
3952 }
3953 
3954 #ifdef SCIP_DEBUG
3955 /** prints the names of the candidates of the given candidate list with their corresponding scores */
3956 static
3957 void printCandidateList(
3958  SCIP* scip, /**< SCIP data structure */
3959  CANDIDATELIST* candidatelist, /**< list to be printed */
3960  SCORECONTAINER* scorecontainer /**< container with all scores */
3961  )
3962 {
3963  int i;
3964 
3965  assert(scip != NULL);
3966  assert(candidatelist != NULL);
3967  assert(scorecontainer != NULL);
3968 
3969  for( i = 0; i < candidatelist->ncandidates; i++ )
3970  {
3971  SCIP_VAR* var = candidatelist->candidates[i]->branchvar;
3972  SCIP_Real score = scorecontainer->scores[SCIPvarGetProbindex(var)];
3973 
3974  assert(var != NULL);
3975 
3976  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, " Index %2i: Var %s Score %.9g\n", i, SCIPvarGetName(var), score);
3977  }
3978 }
3979 #endif
3980 
3981 /** sorts the best candidates (w.r.t. the score in the container) of the candidate list to the front of the list */
3982 static
3984  SCIP* scip, /**< SCIP data structure */
3985  CANDIDATELIST* candidatelist, /**< candidates to be sorted */
3986  SCORECONTAINER* scorecontainer, /**< container with the scores for each candidate */
3987  int nbestcandidates /**< number of candidates that should be kept sorted at the start of the list*/
3988  )
3989 {
3990  int i;
3991 
3992  assert(scip != NULL);
3993  assert(candidatelist != NULL);
3994  assert(scorecontainer != NULL);
3995  assert(candidatelist->ncandidates > 0);
3996  assert(nbestcandidates <= candidatelist->ncandidates);
3997 
3998  for( i = 1; i < candidatelist->ncandidates; i++ )
3999  {
4000  CANDIDATE* movecand = candidatelist->candidates[i];
4001  int moveprobindex;
4002  SCIP_Real movescore;
4003  int nsorted;
4004  int insertionindex;
4005  assert(movecand != NULL);
4006 
4007  moveprobindex = SCIPvarGetProbindex(movecand->branchvar);
4008  movescore = scorecontainer->scores[moveprobindex];
4009 
4010  /* the length of the sorted portion of the array, starting at 0 */
4011  nsorted = MIN(i, nbestcandidates);
4012 
4013  insertionindex = findInsertionPoint(scip, scorecontainer, movescore, candidatelist->candidates, nsorted);
4014 
4015  assert(insertionindex <= nsorted);
4016 
4017  /* if no change has to be made, skip the reordering;
4018  * if the insertionindex lies after the sorted block, skip the reordering
4019  */
4020  if( insertionindex != i && insertionindex < nsorted )
4021  {
4022  int j;
4023  CANDIDATE* reordercand = movecand;
4024 
4025  /* move everything inside the sorted block one place further */
4026  for( j = insertionindex; j < nsorted; j++ )
4027  {
4028  CANDIDATE* oldcand = candidatelist->candidates[j];
4029  assert(oldcand != NULL);
4030 
4031  candidatelist->candidates[j] = reordercand;
4032  reordercand = oldcand;
4033  }
4034  /* the dropped element gets placed in the position of the actually moved element */
4035  candidatelist->candidates[i] = reordercand;
4036  }
4037  }
4038 
4039 #ifdef SCIP_DEBUG
4040  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "All %i candidates, with the first %i candidates sorted by their FSB score:"
4041  "\n", candidatelist->ncandidates, nbestcandidates);
4042  printCandidateList(scip, candidatelist, scorecontainer);
4043 #endif
4044 }
4045 
4046 /** checks whether the given candidates is reliable, so that its pseudocosts may be used */
4047 static
4049  SCIP* scip, /**< SCIP data structure */
4050  SCIP_VAR* branchvar /**< var to check for reliability */
4051  )
4052 {
4053  SCIP_Real size;
4054  SCIP_Real downsize;
4055  SCIP_Real upsize;
4056  SCIP_Real reliable = 5;
4057 
4058  assert(scip != NULL);
4059  assert(branchvar != NULL);
4060 
4063  size = MIN(downsize, upsize);
4064 
4065  return size >= reliable;
4066 }
4067 
4068 /** checks whether the current problem is feasible or cutoff */
4069 static
4071  SCIP* scip /**< SCIP data structure */
4072  )
4073 {
4074  assert(scip != NULL);
4075 
4076  return (SCIPgetCutoffdepth(scip) <= SCIPgetDepth(scip));
4077 }
4078 
4079 /** Ensures that the scores are present in the scorecontainer for each of the candidates to consider */
4080 static
4082  SCIP* scip, /**< SCIP data structure */
4083  STATUS* status, /**< current status */
4084  PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */
4085  CONFIGURATION* config, /**< the configuration of the branching rule */
4086  SCIP_SOL* baselpsol, /**< base lp solution */
4087  DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found; or NULL */
4088  BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */
4089  CANDIDATELIST* allcandidates, /**< list containing all candidates to consider */
4090  BRANCHINGDECISION* decision, /**< struct to store the final decision */
4091  SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */
4092  LEVEL2DATA* level2data, /**< level 2 LP results data */
4093  SCIP_Real lpobjval /**< base LP objective value */
4094 #ifdef SCIP_STATISTIC
4095  ,STATISTICS* statistics /**< general statistical data */
4096  ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */
4097 #endif
4098  )
4099 {
4100  int i;
4101  int nunscoredcandidates = 0;
4102  int* candidateunscored;
4103 
4104  assert(scip != NULL);
4105  assert(config != NULL);
4106  assert(status != NULL);
4107  assert(allcandidates != NULL);
4108  assert(scorecontainer != NULL);
4109  assert(allcandidates->candidates != NULL || allcandidates->ncandidates == 0);
4110 
4111  SCIP_CALL( SCIPallocBufferArray(scip, &candidateunscored, allcandidates->ncandidates) );
4112 
4113  /* filter the candidates based on the presence of a score in the 'scorecontainer'. Only those without a score need a
4114  * new one.
4115  */
4116  for( i = 0; i < allcandidates->ncandidates; i++ )
4117  {
4118  CANDIDATE* lpcand = allcandidates->candidates[i];
4119  SCIP_VAR* branchvar = lpcand->branchvar;
4120  int probindex = SCIPvarGetProbindex(branchvar);
4121  SCIP_Real knownscore = scorecontainer->scores[probindex];
4122 
4123  assert(lpcand != NULL);
4124  assert(branchvar != NULL);
4125 
4126  if( SCIPisLT(scip, knownscore, 0.0) )
4127  {
4128  if( config->abbrevpseudo && isCandidateReliable(scip, branchvar) )
4129  {
4130  SCIP_Real score = calculateScoreFromPseudocosts(scip, lpcand);
4131  SCIP_CALL( scoreContainerSetScore(scip, scorecontainer, lpcand, score, 0.0, 0.0) );
4132  }
4133  else if( config->level2avgscore && SCIPgetProbingDepth(scip) > 0 )
4134  {
4135  assert(scorecontainer->nsetscores > 0);
4136  SCIP_CALL( scoreContainerSetScore(scip, scorecontainer, lpcand,
4137  scorecontainer->scoresum / scorecontainer->nsetscores, 0.0, 0.0) );
4138  }
4139  else if( config->level2zeroscore && SCIPgetProbingDepth(scip) > 0 )
4140  {
4141  assert(scorecontainer->nsetscores > 0);
4142  SCIP_CALL( scoreContainerSetScore(scip, scorecontainer, lpcand,
4143  -0.1, 0.0, 0.0) );
4144  }
4145  else
4146  {
4147  /* score is unknown and needs to be calculated */
4148  candidateunscored[nunscoredcandidates] = i;
4149  nunscoredcandidates++;
4150  }
4151  }
4152  }
4153 
4154  if( nunscoredcandidates > 0 )
4155  {
4156  CANDIDATELIST* unscoredcandidates;
4157 
4158  /* allocate the list of candidates without any score (gets updated further on) */
4159  SCIP_CALL( candidateListCreate(scip, &unscoredcandidates, nunscoredcandidates) );
4160 
4161  /* move the unscored candidates to the temp list */
4162  for( i = 0; i < nunscoredcandidates; i++ )
4163  {
4164  int candindex = candidateunscored[i];
4165 
4166  assert(allcandidates->candidates[candindex] != NULL);
4167 
4168  unscoredcandidates->candidates[i] = allcandidates->candidates[candindex];
4169  }
4170 
4171 #ifdef SCIP_DEBUG
4172  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Of the given %i candidates, %i have no score: ",
4173  allcandidates->ncandidates, nunscoredcandidates);
4174  printCandidates(scip, SCIP_VERBLEVEL_HIGH, unscoredcandidates);
4175  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Calculating the FSB result to get a score for the remaining "
4176  "candidates.\n");
4177 #endif
4178 
4179  /* Calculate all remaining FSB scores and collect the scores in the container */;
4180 #ifdef SCIP_STATISTIC
4181  SCIP_CALL( getFSBResult(scip, status, persistent, config, baselpsol, domainreductions, binconsdata, unscoredcandidates,
4182  decision, scorecontainer, level2data, lpobjval, statistics, localstats) );
4183 #else
4184  SCIP_CALL( getFSBResult(scip, status, persistent, config, baselpsol, domainreductions, binconsdata, unscoredcandidates,
4185  decision, scorecontainer, level2data, lpobjval) );
4186 #endif
4187 
4188  /* move the now scored candidates back to the original list */
4189  for( i = 0; i < nunscoredcandidates; i++ )
4190  {
4191  assert(allcandidates->candidates[candidateunscored[i]] == unscoredcandidates->candidates[i]);
4192 
4193  assert(unscoredcandidates->candidates[i] != NULL);
4194  unscoredcandidates->candidates[i] = NULL;
4195  }
4196 
4197  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Calculated the scores for the remaining candidates\n");
4198 
4199  SCIP_CALL( candidateListFree(scip, &unscoredcandidates) );
4200  }
4201 
4202  /* reset the best sorted indices, as those are only valid on the FSB run already completed */
4203  scoreContainterResetBestSortedCands(scorecontainer);
4204 
4205  SCIPfreeBufferArray(scip, &candidateunscored);
4206 
4207  return SCIP_OKAY;
4208 }
4209 
4210 /** Get the candidates to temporarily branch on. In the LAB case this is the complete list of possible candidates. In the
4211  * ALAB case only the 'best' candidates are returned. */
4212 static
4214  SCIP* scip, /**< SCIP data structure */
4215  STATUS* status, /**< current status */
4216  PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */
4217  CONFIGURATION* config, /**< the configuration of the branching rule */
4218  SCIP_SOL* baselpsol, /**< base lp solution */
4219  DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found; or NULL */
4220  BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */
4221  CANDIDATELIST* candidatelist, /**< list of candidates to branch on */
4222  BRANCHINGDECISION* decision, /**< struct to store the final decision */
4223  SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */
4224  LEVEL2DATA* level2data, /**< level 2 LP results data */
4225  SCIP_Real lpobjval /**< base LP objective value */
4226 #ifdef SCIP_STATISTIC
4227  ,STATISTICS* statistics /**< general statistical data */
4228  ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */
4229 #endif
4230  )
4231 {
4232  assert(scip != NULL);
4233  assert(config != NULL);
4234  assert(status != NULL);
4235  assert(candidatelist != NULL);
4236  assert(SCIPinProbing(scip));
4237 
4238  /* abbreviated LAB: only use the "best" candidates */
4239  if( config->abbreviated )
4240  {
4241  assert(scorecontainer != NULL);
4242 
4243  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Getting the best (at most) %i of the given %i candidates: ",
4244  config->maxncands, candidatelist->ncandidates);
4245 #ifdef SCIP_DEBUG
4246  printCandidates(scip, SCIP_VERBLEVEL_HIGH, candidatelist);
4247 #endif
4248 
4249  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "%s", "Ensuring that all candidates have a score.\n");
4250 #ifdef SCIP_STATISTIC
4251  SCIP_CALL( ensureScoresPresent(scip, status, persistent, config, baselpsol, domainreductions, binconsdata, candidatelist,
4252  decision, scorecontainer, level2data, lpobjval, statistics, localstats) );
4253 #else
4254  SCIP_CALL( ensureScoresPresent(scip, status, persistent, config, baselpsol, domainreductions, binconsdata, candidatelist,
4255  decision, scorecontainer, level2data, lpobjval) );
4256 #endif
4257 
4258  /* if we didn't find any domreds or constraints during the FSB scoring, we branch on */
4259  if( isBranchFurther(status, SCIPgetProbingDepth(scip) == 0) )
4260  {
4261  int nusedcands;
4262  int i;
4263 
4264  if( SCIPgetProbingDepth(scip) == 0 || config->maxndeepercands == 0 )
4265  nusedcands = MIN(config->maxncands, candidatelist->ncandidates);
4266  else
4267  nusedcands = MIN(config->maxndeepercands, candidatelist->ncandidates);
4268 
4269  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "%s", "Filter the candidates by their score.\n");
4270 
4271  sortFirstCandidatesByScore(scip, candidatelist, scorecontainer, nusedcands);
4272 
4273  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Best candidate according to FSB scores: <%s>\n",
4274  SCIPvarGetName(candidatelist->candidates[0]->branchvar));
4275 
4276  if( config->worsefactor >= 0 )
4277  {
4278  for( i = 1; i < nusedcands; ++i )
4279  {
4280  if( scorecontainer->scores[SCIPvarGetProbindex(candidatelist->candidates[0]->branchvar)] >
4281  config->worsefactor * scorecontainer->scores[SCIPvarGetProbindex(candidatelist->candidates[i]->branchvar)] )
4282  break;
4283  }
4284  nusedcands = i;
4285  }
4286 
4287  if( config->filterbymaxgain && SCIPgetProbingDepth(scip) == 0 )
4288  {
4289  SCIP_Real maxgain;
4290  SCIP_Real bestmaxgain = MAX(scorecontainer->downgains[SCIPvarGetProbindex(candidatelist->candidates[0]->branchvar)],
4291  scorecontainer->upgains[SCIPvarGetProbindex(candidatelist->candidates[0]->branchvar)]); /*lint !e666*/
4292 
4293  if( bestmaxgain == 0.0 )
4294  nusedcands = 1;
4295  else
4296  {
4297  for( i = nusedcands - 1; i >= 1; --i )
4298  {
4299  maxgain = MAX(scorecontainer->downgains[SCIPvarGetProbindex(candidatelist->candidates[i]->branchvar)],
4300  scorecontainer->upgains[SCIPvarGetProbindex(candidatelist->candidates[i]->branchvar)]); /*lint !e666*/
4301 
4302  if( SCIPisSumLE(scip, maxgain / bestmaxgain, 1.0) )
4303  {
4304  --nusedcands;
4305 
4306  if( i < nusedcands )
4307  {
4308  CANDIDATE* tmp = candidatelist->candidates[i];
4309  candidatelist->candidates[i] = candidatelist->candidates[nusedcands];
4310  candidatelist->candidates[nusedcands] = tmp;
4311  }
4312  }
4313  }
4314  }
4315  }
4316 
4317  if( SCIPgetProbingDepth(scip) > 0 && scorecontainer->scores[SCIPvarGetProbindex(candidatelist->candidates[0]->branchvar)] > -0.05)
4318  {
4319  for( i = 1; i < nusedcands; ++i )
4320  {
4321  if( scorecontainer->scores[SCIPvarGetProbindex(candidatelist->candidates[i]->branchvar)] < -0.05 )
4322  break;
4323  }
4324  nusedcands = i;
4325  }
4326 
4327  SCIP_CALL( candidateListKeep(scip, candidatelist, nusedcands) );
4328  }
4329 #ifdef SCIP_DEBUG
4330  else
4331  {
4332  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Strong Branching would have stopped.\n");
4333  }
4334 #endif
4335 
4336  if( isCurrentNodeCutoff(scip) )
4337  status->cutoff = TRUE;
4338  }
4339  else
4340  {
4341  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Getting the branching candidates by selecting all candidates.\n");
4342  }
4343 
4344  return SCIP_OKAY;
4345 }
4346 
4347 /** Executes the general branching on a variable in a given direction (up/down) and repeats the algorithm from the new node */
4348 static
4350  SCIP* scip, /**< SCIP data structure */
4351  STATUS* status, /**< current status */
4352  CONFIGURATION* config, /**< the configuration of the branching rule */
4353  SCIP_SOL* baselpsol, /**< the base lp solution */
4354  CANDIDATE* candidate, /**< candidate to branch on */
4355  SCIP_Real localbaselpsolval, /**< the objective value of the current temporary problem */
4356  SCIP_Real baselpobjval, /**< LP objective value of focus node (not probing) */
4357  int recursiondepth, /**< remaining recursion depth */
4358  DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found; or NULL */
4359  BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */
4360  LEVEL2DATA* level2data, /**< level 2 LP results data */
4361  BRANCHINGRESULTDATA* branchingresult, /**< container to store the result of the branching in */
4362  SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */
4363  SCIP_Bool downbranching /**< should we branch up or down in here? */
4364 #ifdef SCIP_STATISTIC
4365  ,STATISTICS* statistics /**< general statistical data */
4366  ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */
4367 #endif
4368  )
4369 {
4370  int probingdepth;
4371  SCIP_VAR* branchvar;
4372  SCIP_Real branchvalfrac;
4373  SCIP_Real branchval;
4374  SCIP_Bool varisbinary;
4375  SCIP_Bool solvedlp = TRUE;
4376 
4377  assert(scip != NULL);
4378  assert(status != NULL);
4379  assert(config != NULL);
4380  assert(candidate != NULL);
4381  assert(branchingresult != NULL);
4382 
4383  branchvar = candidate->branchvar;
4384  branchvalfrac = candidate->fracval;
4385  branchval = candidate->branchval;
4386 
4387  assert(branchvar != NULL);
4388 
4389  probingdepth = SCIPgetProbingDepth(scip);
4390  varisbinary = SCIPvarIsBinary(branchvar);
4391 
4392  if( binconsdata != NULL && varisbinary )
4393  {
4394  if( downbranching )
4395  {
4396  /* In case that the branch variable is binary, add the negated var to the list.
4397  * This list is used to generate a set packing constraint for cutoff branches which were reached by only using
4398  * binary variables.
4399  * DownBranching on a binary variable x means: x <= 0
4400  * When this cutoff occurs we have that: x >= 1 <=> 1-x <= 0
4401  */
4402  SCIP_VAR* negbranchvar;
4403 
4404  SCIP_CALL( SCIPgetNegatedVar(scip, branchvar, &negbranchvar) );
4405 
4406  assert(negbranchvar != NULL);
4407 
4408  binaryVarListAppend(scip, binconsdata->binaryvars, negbranchvar);
4409  }
4410  else
4411  {
4412  /* In case that the branch variable is binary, add the var to the list.
4413  * This list is used to generate a set packing constraint for cutoff branches which were reached by only using
4414  * binary variables.
4415  * UpBranching on a binary variable x means: x >= 1
4416  * When this cutoff occurs we have that: x <= 0
4417  */
4418  binaryVarListAppend(scip, binconsdata->binaryvars, branchvar);
4419  }
4420  }
4421 
4422  if( level2data != NULL )
4423  {
4424  SCIP_Real newbound = downbranching ? SCIPfeasFloor(scip, branchval) : SCIPfeasCeil(scip, branchval);
4425 
4426  if( SCIPgetProbingDepth(scip) == 0 )
4427  {
4428  assert(SCIPvarGetProbindex(branchvar) >= 0);
4429  level2data->branchvar1 = (unsigned int) SCIPvarGetProbindex(branchvar);
4430  level2data->branchdir1 = !downbranching;
4431  level2data->branchval1 = newbound;
4432  }
4433  else
4434  {
4435  LEVEL2RESULT* result;
4436 
4437  assert(SCIPgetProbingDepth(scip) == 1);
4438  assert(SCIPvarGetProbindex(branchvar) >= 0);
4439 
4440  level2data->branchvar2 = (unsigned int) SCIPvarGetProbindex(branchvar);
4441  level2data->branchdir2 = !downbranching;
4442  level2data->branchval2 = newbound;
4443 
4444  SCIP_CALL( level2dataGetResult(scip, level2data, &result) );
4445 
4446  /* we already processed a similar level 2 node */
4447  if( result != NULL )
4448  {
4449  solvedlp = FALSE;
4450 #ifdef SCIP_STATISTIC
4451  statistics->nduplicatelps[probingdepth]++;
4452 #endif
4453  branchingresult->objval = result->lpobjval;
4454  branchingresult->dualbound = result->lpobjval;
4455  branchingresult->dualboundvalid = result->valid;
4456  branchingresult->cutoff = result->cutoff;
4457  branchingresult->niterations = 0;
4458 
4459  if( !branchingresult->cutoff && branchingresult->dualboundvalid
4460  && SCIPisGE(scip, branchingresult->objval, SCIPgetCutoffbound(scip)) )
4461  branchingresult->cutoff = TRUE;
4462 
4464  "Use old %s branching result on var <%s> with 'val > %g' and bounds [<%g>..<%g>]: objval <%.9g>, cutoff <%d> "
4465  "(the parent objval was <%.9g>)\n",
4466  downbranching ? "down" : "up", SCIPvarGetName(branchvar), branchval, SCIPvarGetLbLocal(branchvar),
4467  SCIPvarGetUbLocal(branchvar), branchingresult->objval, branchingresult->cutoff, localbaselpsolval);
4468  }
4469  }
4470  }
4471 
4472  if( solvedlp )
4473  {
4474  SCIP_CALL( executeBranching(scip, config, downbranching, candidate, branchingresult, baselpsol, domainreductions,
4475  status) );
4476 
4477  assert(SCIPgetProbingDepth(scip) == 1 || SCIPgetProbingDepth(scip) == 2);
4478 
4479  if( level2data != NULL && SCIPgetProbingDepth(scip) == 2)
4480  {
4481  SCIP_Bool duplicate;
4482 
4483  SCIP_CALL( level2dataStoreResult(scip, level2data, branchingresult->objval, branchingresult->cutoff, branchingresult->dualboundvalid, &duplicate) );
4484  assert(!duplicate);
4485  }
4486 
4487 #ifdef SCIP_STATISTIC
4488  statistics->nlpssolved[probingdepth]++;
4489  statistics->nlpiterations[probingdepth] += branchingresult->niterations;
4490 
4491  if( config->inscoring )
4492  {
4493  statistics->nlpssolvedfsb[probingdepth]++;
4494  statistics->nlpiterationsfsb[probingdepth] += branchingresult->niterations;
4495  }
4496 #endif
4497  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Solving the LP took %" SCIP_LONGINT_FORMAT " iterations (status %d).\n",
4498  branchingresult->niterations, SCIPgetLPSolstat(scip));
4499 
4500 #ifdef SCIP_DEBUG
4501  if( status->lperror )
4502  {
4503  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The LP could not be solved.\n");
4504  }
4505  else if( branchingresult->cutoff )
4506  {
4507  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The solved LP was infeasible and as such is cutoff\n");
4508  }
4509  else
4510  {
4511  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The solved LP was feasible and has an objval <%.9g> (the parent objval was "
4512  "<%.9g>)\n", branchingresult->objval, localbaselpsolval);
4513  }
4514 #endif
4515  }
4516 
4517  if( !branchingresult->cutoff && !status->lperror && !status->limitreached )
4518  {
4519  SCIP_Real localgain;
4520 
4521  localgain = MAX(0, branchingresult->objval - localbaselpsolval);
4522 
4523  /* update pseudo costs */
4524  if( downbranching )
4525  {
4526  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchvar, 0.0 - branchvalfrac, localgain, 1.0) );
4527  }
4528  else
4529  {
4530  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchvar, 1.0 - branchvalfrac, localgain, 1.0) );
4531  }
4532  }
4533 
4534  if( solvedlp && !branchingresult->cutoff && !status->lperror && !status->limitreached )
4535  {
4536  /* store the warm start information in the candidate, so that it can be reused in a later branching */
4537  if( config->reusebasis && config->inscoring )
4538  {
4539  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Storing warm start information for %s branching on var <%s>\n",
4540  downbranching ? "down" : "up", SCIPvarGetName(branchvar));
4541 
4542  SCIP_CALL( candidateStoreWarmStartInfo(scip, candidate, downbranching) );
4543  }
4544 
4545  if( recursiondepth > 1 && !config->inscoring )
4546  {
4547  CANDIDATELIST* candidatelist;
4548 
4549  SCIP_CALL( candidateListGetAllFractionalCandidates(scip, &candidatelist) );
4550  assert(candidatelist != NULL);
4551 
4552  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "%sbranching has <%i> candidates.\n", downbranching ? "Down" : "Up",
4553  candidatelist->ncandidates);
4554 
4555  if( candidatelist->ncandidates > 0 )
4556  {
4557  BRANCHINGDECISION* deeperdecision;
4558  STATUS* deeperstatus;
4559  PERSISTENTDATA* deeperpersistent = NULL;
4560  SCIP_Real deeperlpobjval = branchingresult->objval;
4561 #ifdef SCIP_STATISTIC
4562  LOCALSTATISTICS* deeperlocalstats;
4563 
4564  SCIP_CALL( localStatisticsAllocate(scip, &deeperlocalstats) );
4565 #endif
4566  SCIP_CALL( statusCreate(scip, &deeperstatus) );
4567 
4568  SCIP_CALL( branchingDecisionCreate(scip, &deeperdecision) );
4569 
4570 #ifdef SCIP_STATISTIC
4571  SCIP_CALL( filterCandidates(scip, deeperstatus, deeperpersistent, config, baselpsol, domainreductions, binconsdata, candidatelist,
4572  deeperdecision, scorecontainer, level2data, deeperlpobjval,
4573  statistics, localstats) );
4574 #else
4575  SCIP_CALL( filterCandidates(scip, deeperstatus, deeperpersistent, config, baselpsol, domainreductions, binconsdata, candidatelist,
4576  deeperdecision, scorecontainer, level2data, deeperlpobjval) );
4577 #endif
4578  if( deeperstatus->lperror )
4579  {
4580  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "ignoring lperror in filtering call...\n");
4581  deeperstatus->lperror = FALSE;
4582  }
4583  if( deeperstatus->cutoff )
4584  {
4585  branchingresult->ndeepestnodes += 2;
4586  branchingresult->ndeepestcutoffs += 2;
4587  }
4588 
4589  /* the status may have changed because of FSB to get the best candidates */
4590  if( isBranchFurther(deeperstatus, FALSE) )
4591  {
4592  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Now the objval is <%.9g>\n", branchingresult->objval);
4593 
4594 #ifdef SCIP_STATISTIC
4595  deeperlocalstats->ncutoffproofnodes = 0;
4596  SCIP_CALL( selectVarRecursive(scip, deeperstatus, deeperpersistent, config, baselpsol, domainreductions,
4597  binconsdata, candidatelist, deeperdecision, scorecontainer, level2data, recursiondepth - 1,
4598  deeperlpobjval, baselpobjval, &branchingresult->niterations, &branchingresult->ndeepestcutoffs,
4599  &branchingresult->bestgain, &branchingresult->totalgains, &branchingresult->ntotalgains,
4600  &branchingresult->ndeepestnodes,
4601  statistics, deeperlocalstats, NULL, NULL) );
4602 #else
4603  SCIP_CALL( selectVarRecursive(scip, deeperstatus, deeperpersistent, config, baselpsol, domainreductions,
4604  binconsdata, candidatelist, deeperdecision, scorecontainer, level2data, recursiondepth - 1,
4605  deeperlpobjval, baselpobjval, &branchingresult->niterations, &branchingresult->ndeepestcutoffs,
4606  &branchingresult->bestgain, &branchingresult->totalgains, &branchingresult->ntotalgains,
4607  &branchingresult->ndeepestnodes) );
4608 #endif
4609 
4610  assert(deeperstatus->cutoff || deeperstatus->domred || deeperstatus->lperror
4611  || branchingresult->ndeepestnodes == 8
4612  || branchingresult->ndeepestnodes == 2 * candidatelist->ncandidates
4613  || SCIPisStopped(scip));
4614 
4615  /* the proved dual bound of the deeper branching cannot be less than the current dual bound, as every deeper
4616  * node has more/tighter constraints and as such cannot be better than the base LP. */
4617  assert(SCIPisGE(scip, deeperdecision->proveddb, branchingresult->dualbound));
4618  branchingresult->dualbound = deeperdecision->proveddb;
4619  branchingresult->deeperscore = deeperdecision->score;
4620  branchingresult->dualboundvalid = TRUE;
4621  }
4622 #ifdef SCIP_STATISTIC
4623  else
4624  {
4625  assert(SCIPgetProbingDepth(scip) == probingdepth + 1);
4626 
4627  statistics->stopafterfsb[probingdepth+1]++;
4628 
4629  if( deeperstatus->cutoff )
4630  {
4631  statistics->cutoffafterfsb[probingdepth+1]++;
4632  }
4633  else if( deeperstatus->domred )
4634  {
4635  statistics->domredafterfsb[probingdepth+1]++;
4636  }
4637  }
4638 #endif
4639  /* deeperstatus->cutoff is TRUE, if any up/down child pair of the up child were cutoff */
4640  if( deeperstatus->cutoff )
4641  {
4642  branchingresult->cutoff = TRUE;
4643 #ifdef SCIP_STATISTIC
4644  localstats->ncutoffproofnodes += deeperlocalstats->ncutoffproofnodes;
4645 #endif
4646  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Both deeper children were cutoff, so the %s branch is "
4647  "cutoff\n", downbranching ? "down" : "up");
4648  }
4649 
4650  branchingDecisionFree(scip, &deeperdecision);
4651  statusFree(scip, &deeperstatus);
4652 #ifdef SCIP_STATISTIC
4653  localStatisticsFree(scip, &deeperlocalstats);
4654 #endif
4655  }
4656  else
4657  {
4658  branchingresult->deeperscore = (branchingresult->dualbound - baselpobjval) * (branchingresult->dualbound - baselpobjval) * 10;
4659  }
4660  SCIP_CALL( candidateListFree(scip, &candidatelist) );
4661  }
4662  }
4663 
4664  if( recursiondepth == 1 && !config->inscoring )
4665  {
4666  branchingresult->ndeepestnodes++;
4667  /* this is a cutoff on the lowest tree level */
4668  if( branchingresult->cutoff )
4669  {
4670  branchingresult->ndeepestcutoffs++;
4671  }
4672  }
4673 
4674  if( binconsdata != NULL && varisbinary )
4675  {
4676  /* the current branching child is infeasible and we only branched on binary variables in lookahead branching */
4677  if( solvedlp && branchingresult->cutoff && !status->lperror && SCIPallColsInLP(scip)
4678  && binconsdata->binaryvars->nbinaryvars == (probingdepth + 1) )
4679  {
4680 #ifdef SCIP_STATISTIC
4681  SCIP_CALL( addBinaryConstraint(scip, config, binconsdata, baselpsol, statistics) );
4682 #else
4683  SCIP_CALL( addBinaryConstraint(scip, config, binconsdata, baselpsol) );
4684 #endif
4685  }
4686 
4687  binaryVarListDrop(binconsdata->binaryvars);
4688  }
4689 
4690  /* reset the probing depth to undo the previous branching */
4691  SCIP_CALL( SCIPbacktrackProbing(scip, probingdepth) );
4692 
4693  return SCIP_OKAY;
4694 }
4695 
4696 /** branches recursively on all given candidates */
4697 static
4699  SCIP* scip, /**< SCIP data structure */
4700  STATUS* status, /**< current status */
4701  PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */
4702  CONFIGURATION* config, /**< the configuration of the branching rule */
4703  SCIP_SOL* baselpsol, /**< base lp solution */
4704  DOMAINREDUCTIONS* domainreductions, /**< container collecting all domain reductions found; or NULL */
4705  BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */
4706  CANDIDATELIST* candidatelist, /**< list of candidates to branch on */
4707  BRANCHINGDECISION* decision, /**< struct to store the final decision */
4708  SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */
4709  LEVEL2DATA* level2data, /**< level 2 LP results data */
4710  int recursiondepth, /**< remaining recursion depth */
4711  SCIP_Real lpobjval, /**< LP objective value of current probing node*/
4712  SCIP_Real baselpobjval, /**< LP objective value of focus node (not probing) */
4713  SCIP_Longint* niterations, /**< pointer to store the total number of iterations for this variable; or NULL*/
4714  int* ndeepestcutoffs, /**< pointer to store the total number of cutoffs on the deepest level; or NULL */
4715  SCIP_Real* bestgain, /**< pointer to store the best gain found with these candidates; or NULL */
4716  SCIP_Real* totalgains, /**< pointer to store the sum over all gains that are valid in both children;
4717  * or NULL, if bestgain == NULL */
4718  int* ntotalgains, /**< pointer to store the number of gains summed in totalgains;
4719  * or NULL, if bestgain == NULL */
4720  int* ndeepestnodes /**< pointer to store the number of nodes processed in the deepest level */
4721 #ifdef SCIP_STATISTIC
4722  ,STATISTICS* statistics /**< general statistical data */
4723  ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */
4724  ,SCIP_Real* firstscoreptr /**< pointer to store score of first candidate, or NULL */
4725  ,SCIP_Real* bestscoreptr /**< pointer to store best score, or NULL */
4726 #endif
4727  )
4728 {
4729  BRANCHINGRESULTDATA* downbranchingresult = NULL;
4730  BRANCHINGRESULTDATA* upbranchingresult = NULL;
4731  BRANCHINGRESULTDATA* bestdownbranchingresult = NULL;
4732  BRANCHINGRESULTDATA* bestupbranchingresult = NULL;
4733  SCIP_LPI* lpi;
4734  SCIP_Real bestscore = -SCIPinfinity(scip);
4735  SCIP_Real bestscorelowerbound;
4736  SCIP_Real bestscoreupperbound;
4737  SCIP_Real bestscoringlpobjval = -SCIPinfinity(scip);
4738  int start = 0;
4739  int i;
4740  int c;
4741  int nlpcands;
4742  int probingdepth;
4743  SCIP_Bool stopafterinfeasible = FALSE;
4744 
4745  assert(scip != NULL);
4746  assert(status != NULL);
4747  assert(config != NULL);
4748  assert(!config->usedomainreduction || domainreductions != NULL);
4749  assert(candidatelist != NULL);
4750  assert(candidatelist->ncandidates > 0);
4751  assert(decision != NULL);
4752  assert(recursiondepth >= 1);
4753 #ifdef SCIP_STATISTIC
4754  assert(statistics != NULL);
4755 
4756  if( firstscoreptr != NULL )
4757  *firstscoreptr = -1.0;
4758  if( bestscoreptr != NULL )
4759  *bestscoreptr = -1.0;
4760 #endif
4761 
4762  nlpcands = candidatelist->ncandidates;
4763  probingdepth = SCIPgetProbingDepth(scip);
4764  assert(probingdepth >= 0 && probingdepth < config->recursiondepth);
4765 
4766  if( persistent != NULL && (!config->abbreviated || config->inscoring) && probingdepth == 0 )
4767  start = persistent->restartindex;
4768 
4769  /* init default decision */
4770  decision->branchvar = candidatelist->candidates[0]->branchvar;
4771  decision->branchval = candidatelist->candidates[0]->branchval;
4772  decision->downdb = lpobjval;
4773  decision->downdbvalid = TRUE;
4774  decision->updb = lpobjval;
4775  decision->updbvalid = TRUE;
4776  decision->proveddb = lpobjval;
4777  decision->score = 0.0;
4778 
4779  bestscorelowerbound = SCIPvarGetLbLocal(decision->branchvar);
4780  bestscoreupperbound = SCIPvarGetUbLocal(decision->branchvar);
4781 
4782  SCIP_CALL( branchingResultDataCreate(scip, &downbranchingresult) );
4783  SCIP_CALL( branchingResultDataCreate(scip, &upbranchingresult) );
4784 
4785  SCIP_CALL( branchingResultDataCreate(scip, &bestdownbranchingresult) );
4786  SCIP_CALL( branchingResultDataCreate(scip, &bestupbranchingresult) );
4787 
4788  assert(downbranchingresult != NULL);
4789  assert(upbranchingresult != NULL);
4790 
4791  if( config->inscoring )
4792  {
4793  SCIP_CALL( SCIPgetBoolParam(scip, "branching/forceallchildren", &stopafterinfeasible) );
4794  stopafterinfeasible = !stopafterinfeasible;
4795  }
4796 
4797  SCIP_CALL( SCIPgetLPI(scip, &lpi) );
4798 
4799 #ifdef SCIP_DEBUG
4800  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Started selectVarRecursive with <%i> candidates: ", nlpcands);
4801  printCandidates(scip, SCIP_VERBLEVEL_HIGH, candidatelist);
4802 #endif
4803 
4804  LABdebugMessage(scip, SCIP_VERBLEVEL_FULL, "Starting loop from index %d\n", start);
4805 
4806  /* iterate over all current branching candidates and evaluate their two potential child nodes by:
4807  * - potentially applying domain propagation at each node before
4808  * - solving the LP at the nodes to obtain a dual bound
4809  * - potentially evaluating branching candidates at the potential child node again by applying this method recursively
4810  *
4811  * some improvements of the general scheme:
4812  * - results obtained for a candidate in a previous lookahead branching call at this node may be re-used
4813  * - while i counts the number of candidates evaluated in this call, we do not always start at the front
4814  * of the candidate array, but rather store at which index we stopped last time (e.g., because a domain reduction was
4815  * found and applied) and start from that index next time. Even though the set of branching candidates is probably different
4816  * it is often reasonably close and we avoid evaluating the same variables again and again.
4817  */
4818  for( i = 0, c = start;
4819  isBranchFurtherLoopDecrement(status, &c) && i < nlpcands && !SCIPisStopped(scip); i++, c++)
4820  {
4821  DOMAINREDUCTIONS* downdomainreductions = NULL;
4822  DOMAINREDUCTIONS* updomainreductions = NULL;
4823  SCIP_Bool useoldbranching = FALSE;
4824  SCIP_Real oldlpobjval = -SCIPinfinity(scip);
4825  CANDIDATE* candidate;
4826  SCIP_VAR* branchvar;
4827  SCIP_Real branchval;
4828  SCIP_Real branchlb;
4829  SCIP_Real branchub;
4830 
4831  c = c % nlpcands;
4832 
4833  candidate = candidatelist->candidates[c];
4834 
4835  assert(candidate != NULL);
4836 
4837  branchvar = candidate->branchvar;
4838  branchval = candidate->branchval;
4839 
4840  assert(branchvar != NULL);
4841 
4842  branchlb = SCIPvarGetLbLocal(branchvar);
4843  branchub = SCIPvarGetUbLocal(branchvar);
4844 
4845  if( SCIPisEQ(scip, branchlb, branchub) )
4846  {
4847  /* if both bounds are equal the variable is fixed and we cannot branch
4848  * this may happen if domain propagation on other candidates finds better bounds for the current candidate
4849  */
4850  status->domred = TRUE;
4851 #ifdef SCIP_STATISTIC
4852  statistics->npropdomred[probingdepth]++;
4853 #endif
4854  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Domain Propagation changed the bounds of a branching candidate."
4855  "\n");
4856  continue;
4857  }
4858 
4859  /* @todo apply already found domainreductions for this candidate? */
4860 
4861 #ifdef SCIP_STATISTIC
4862  /* Reset the cutoffproofnodes, as the number of proof nodes from previous branching vars (which where not
4863  * cutoff, as we didn't break the loop) is not relevant for the min total sum of proof nodes.
4864  */
4865  localstats->ncutoffproofnodes = 0;
4866 #endif
4867 
4868  branchingResultDataInit(scip, downbranchingresult);
4869  branchingResultDataInit(scip, upbranchingresult);
4870 
4871  /* use old lookahead branching result, if last call on this variable is not too long ago */
4872  if( persistent != NULL && (config->inscoring || probingdepth == 0) && isUseOldBranching(scip, persistent, config, branchvar) )
4873  {
4874  SCIP_CALL( getOldBranching(scip, persistent, config, branchvar, downbranchingresult, upbranchingresult,
4875  &oldlpobjval) );
4876  useoldbranching = TRUE;
4877 #ifdef SCIP_STATISTIC
4878  if( config->inscoring )
4879  statistics->noldbranchusedfsb[probingdepth]++;
4880  else
4881  statistics->noldbranchused[probingdepth]++;
4882 #endif
4883  }
4884  else
4885  {
4886  SCIP_Bool down;
4887  int k;
4888 
4889  LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, "Started branching on var <%s> with val <%g> and bounds "
4890  "[<%g>..<%g>]\n", SCIPvarGetName(branchvar), branchval, SCIPvarGetLbLocal(branchvar),
4891  SCIPvarGetUbLocal(branchvar));
4892 
4893  if( config->usedomainreduction )
4894  {
4895  SCIP_CALL( domainReductionsCreate(scip, &downdomainreductions) );
4896  SCIP_CALL( domainReductionsCreate(scip, &updomainreductions) );
4897  }
4898 
4899  down = SCIPisStrongbranchDownFirst(scip, branchvar);
4900 
4901  /* @todo break if result is infeasible (probably only in first layer)? */
4902  for( k = 0; k < 2; ++k )
4903  {
4904  DOMAINREDUCTIONS* localdomainreductions;
4905  BRANCHINGRESULTDATA* localbranchingresult;
4906  BRANCHINGRESULTDATA* otherbranchingresult;
4907 
4908  localdomainreductions = down ? downdomainreductions : updomainreductions;
4909  localbranchingresult = down ? downbranchingresult : upbranchingresult;
4910  otherbranchingresult = down ? upbranchingresult : downbranchingresult;
4911 
4912 #ifdef SCIP_STATISTIC
4913  SCIP_CALL( executeBranchingRecursive(scip, status, config, baselpsol, candidate, lpobjval, baselpobjval,
4914  recursiondepth, localdomainreductions, binconsdata, level2data, localbranchingresult, scorecontainer,
4915  down, statistics, localstats) );
4916 #else
4917 
4918  SCIP_CALL( executeBranchingRecursive(scip, status, config, baselpsol, candidate, lpobjval, baselpobjval,
4919  recursiondepth, localdomainreductions, binconsdata, level2data, localbranchingresult, scorecontainer,
4920  down) );
4921 #endif
4922 
4923  /* check whether a new solutions rendered the previous child infeasible */
4924  if( SCIPallColsInLP(scip) && !otherbranchingresult->cutoff )
4925  {
4926  if( k == 1 && SCIPisGE(scip, otherbranchingresult->dualbound, SCIPgetCutoffbound(scip)) )
4927  {
4928  otherbranchingresult->cutoff = TRUE;
4930  "The %s branching changed the cutoffbound and rendered the %s branching result infeasible.\n",
4931  down ? "down" : "up", down ? "up" : "down");
4932  }
4933  }
4934  if( stopafterinfeasible && k == 0 && localbranchingresult->cutoff )
4935  break;
4936 
4937  /* the second iteration of the loop should branch in the other direction */
4938  down = !down;
4939  }
4940 
4941  LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, "-> down=%.9g (gain=%.9g, valid=%u, inf=%u), up=%.9g "
4942  "(gain=%.9g, valid=%u, inf=%u)\n", downbranchingresult->dualbound,
4943  downbranchingresult->dualbound - lpobjval, downbranchingresult->dualboundvalid,
4944  downbranchingresult->cutoff, upbranchingresult->dualbound, upbranchingresult->dualbound - lpobjval,
4945  upbranchingresult->dualboundvalid, upbranchingresult->cutoff);
4946 
4947  if( niterations != NULL )
4948  *niterations += downbranchingresult->niterations + upbranchingresult->niterations;
4949 
4950  /* store results of branching call */
4951  if( persistent != NULL && !upbranchingresult->cutoff && !downbranchingresult->cutoff && (config->inscoring || probingdepth == 0) )
4952  {
4953  SCIP_CALL( updateOldBranching(scip, persistent, config, branchvar, branchval, downbranchingresult,
4954  upbranchingresult, lpobjval) );
4955  }
4956  }
4957 
4958  if( ndeepestcutoffs != NULL )
4959  *ndeepestcutoffs += downbranchingresult->ndeepestcutoffs + upbranchingresult->ndeepestcutoffs;
4960 
4961  if( ndeepestnodes != NULL )
4962  *ndeepestnodes += downbranchingresult->ndeepestnodes + upbranchingresult->ndeepestnodes;
4963 
4964  if( !status->lperror && !status->limitreached )
4965  {
4966  SCIP_Real scoringlpobjval = useoldbranching ? oldlpobjval : lpobjval;
4967  SCIP_Real score = calculateScore(scip, config, branchvar, downbranchingresult, upbranchingresult,
4968  scoringlpobjval, baselpobjval);
4969 
4970 #ifdef SCIP_STATISTIC
4971  if( i == 0 && firstscoreptr != NULL )
4972  *firstscoreptr = score;
4973 #endif
4974 
4975  if( bestgain != NULL && !config->inscoring && SCIPgetProbingDepth(scip) == 1 && !useoldbranching )
4976  {
4977  assert(totalgains != NULL);
4978  assert(ntotalgains != NULL);
4979 
4980  *bestgain = MAX(*bestgain, score);
4981 
4982  if( !downbranchingresult->cutoff && !upbranchingresult->cutoff )
4983  {
4984  (*totalgains) += score;
4985  (*ntotalgains)++;
4986  }
4987  }
4988 
4989  /* both child nodes are infeasible -> the current node is infeasible */
4990  if( SCIPallColsInLP(scip) && upbranchingresult->cutoff && downbranchingresult->cutoff )
4991  {
4992  LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, " -> variable <%s> is infeasible in both directions\n",
4993  SCIPvarGetName(branchvar));
4994 
4995  /* this cutoff may be transferred to a higher level as a domain reduction/valid bound */
4996  status->cutoff = TRUE;
4997 #ifdef SCIP_STATISTIC
4998  statistics->nfullcutoffs[probingdepth]++;
4999  localstats->ncutoffproofnodes += 2;
5000 #endif
5001  }
5002  /* up child is infeasible */
5003  else if( SCIPallColsInLP(scip) && upbranchingresult->cutoff )
5004  {
5005  LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, " -> variable <%s> is infeasible in upward branch\n",
5006  SCIPvarGetName(branchvar));
5007 
5008  /* apply down branching bound change at current node if we proved that this node is really infeasible and
5009  * parameters are set accordingly
5010  */
5011  if( config->usedomainreduction && !useoldbranching )
5012  {
5013 #ifdef SCIP_STATISTIC
5014  assert(localstats->ncutoffproofnodes == 0 || localstats->ncutoffproofnodes == 2);
5015  addUpperBound(scip, branchvar, branchval, baselpsol, TRUE, domainreductions,
5016  2 + localstats->ncutoffproofnodes, TRUE);
5017 #else
5018  addUpperBound(scip, branchvar, branchval, baselpsol, TRUE, domainreductions);
5019 #endif
5020  }
5021 
5022  /* the proved bound is given by the bound of the down child alone */
5023  if( downbranchingresult->dualboundvalid )
5024  {
5025  decision->proveddb = MAX(decision->proveddb, downbranchingresult->dualbound);
5026  }
5027 
5028 #ifdef SCIP_STATISTIC
5029  statistics->nsinglecutoffs[probingdepth]++;
5030 #endif
5031  }
5032  /* down child is infeasible */
5033  else if( SCIPallColsInLP(scip) && downbranchingresult->cutoff )
5034  {
5035  LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, " -> variable <%s> is infeasible in downward branch\n",
5036  SCIPvarGetName(branchvar));
5037 
5038  /* apply up branching bound change at current node if we proved that this node is really infeasible and
5039  * parameters are set accordingly
5040  */
5041  if( config->usedomainreduction && !useoldbranching )
5042  {
5043 #ifdef SCIP_STATISTIC
5044  assert(localstats->ncutoffproofnodes == 0 || localstats->ncutoffproofnodes == 2);
5045  addLowerBound(scip, branchvar, branchval, baselpsol, TRUE, domainreductions,
5046  2 + localstats->ncutoffproofnodes, TRUE);
5047 #else
5048  addLowerBound(scip, branchvar, branchval, baselpsol, TRUE, domainreductions);
5049 #endif
5050  }
5051 
5052  /* the proved bound is given by the bound of the up child alone */
5053  if( upbranchingresult->dualboundvalid )
5054  {
5055  decision->proveddb = MAX(decision->proveddb, upbranchingresult->dualbound);
5056  }
5057 
5058 #ifdef SCIP_STATISTIC
5059  statistics->nsinglecutoffs[probingdepth]++;
5060 #endif
5061  }
5062  /* "normal" case: both child nodes are LP-feasible */
5063  else
5064  {
5065  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Neither branch is cut off and no limit reached.\n");
5066 
5067  /* the proved dual bound is the minimum of the dual bounds of both child nodes */
5068  if( upbranchingresult->dualboundvalid && downbranchingresult->dualboundvalid )
5069  {
5070  decision->proveddb = MAX(decision->proveddb, MIN(upbranchingresult->dualbound,
5071  downbranchingresult->dualbound));
5072  }
5073  }
5074 
5075  /* merge domain changes from the two child nodes */
5076  if( updomainreductions != NULL && config->usedomainreduction && SCIPallColsInLP(scip) )
5077  {
5078  int maxstoredomreds = INT_MAX;
5079 
5080  assert(downdomainreductions != NULL);
5081 
5082  if( config->enforcemaxdomreds && config->maxnviolateddomreds > 0)
5083  maxstoredomreds = config->maxnviolateddomreds;
5084 
5085  if( !upbranchingresult->cutoff && !downbranchingresult->cutoff && config->mergedomainreductions )
5086  applyDeeperDomainReductions(scip, baselpsol, maxstoredomreds, domainreductions, downdomainreductions,
5087  updomainreductions);
5088  else if( upbranchingresult->cutoff && !downbranchingresult->cutoff )
5089  applySingleDeeperDomainReductions(scip, baselpsol, maxstoredomreds, domainreductions, downdomainreductions);
5090  else if( downbranchingresult->cutoff && !upbranchingresult->cutoff )
5091  applySingleDeeperDomainReductions(scip, baselpsol, maxstoredomreds, domainreductions, updomainreductions);
5092  }
5093 
5094  if( config->updatebranchingresults && bestscore > -1.0 &&
5095  (SCIPisGT(scip, decision->proveddb, bestdownbranchingresult->dualbound)
5096  || SCIPisGT(scip, decision->proveddb, bestupbranchingresult->dualbound)) )
5097  {
5098  SCIP_Real newscore;
5099 
5100  bestdownbranchingresult->dualbound = MAX(bestdownbranchingresult->dualbound, decision->proveddb);
5101  bestupbranchingresult->dualbound = MAX(bestupbranchingresult->dualbound, decision->proveddb);
5102 
5103  newscore = calculateScore(scip, config, decision->branchvar, bestdownbranchingresult, bestupbranchingresult,
5104  bestscoringlpobjval, baselpobjval);
5105 
5106  if( newscore > bestscore )
5107  {
5108  bestscore = newscore;
5109 
5110 #ifdef SCIP_STATISTIC
5111  if( bestscoreptr != NULL )
5112  *bestscoreptr = newscore;
5113 #endif
5114  decision->score = newscore;
5115  decision->downdb = bestdownbranchingresult->dualbound;
5116  decision->updb = bestupbranchingresult->dualbound;
5117  }
5118  }
5119 
5120  /* the current candidate variable has a better score than the best candidate investigated so far */
5121  if( SCIPisRelGT(scip, score, bestscore) )
5122  {
5123  int nvars = SCIPgetNVars(scip);
5124 
5125  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Old best var <%s> with bounds [<%g>..<%g>] and score %.9g\n",
5126  SCIPvarGetName(decision->branchvar), bestscorelowerbound, bestscoreupperbound, bestscore);
5127 
5128  bestscore = score;
5129 
5130 #ifdef SCIP_STATISTIC
5131  if( bestscoreptr != NULL )
5132  *bestscoreptr = score;
5133 #endif
5134  decision->branchvar = candidate->branchvar;
5135  decision->branchval = candidate->branchval;
5136  decision->downdb = downbranchingresult->dualbound;
5137  decision->downdbvalid = downbranchingresult->dualboundvalid;
5138  decision->updb = upbranchingresult->dualbound;
5139  decision->updbvalid = upbranchingresult->dualboundvalid;
5140  decision->score = score;
5141 
5142  branchingResultDataCopy(downbranchingresult, bestdownbranchingresult);
5143  branchingResultDataCopy(upbranchingresult, bestupbranchingresult);
5144 
5145  /* store domain reductions found at the child nodes */
5146  if( !config->inscoring && updomainreductions != NULL )
5147  {
5148  assert(downdomainreductions != NULL);
5149 
5150  SCIP_CALL( branchingDecisionEnsureBoundArraysSize(scip, decision, nvars) );
5151 
5152  BMScopyMemoryArray(decision->uplowerbounds, updomainreductions->lowerbounds, nvars);
5153  BMScopyMemoryArray(decision->upupperbounds, updomainreductions->upperbounds, nvars);
5154  BMScopyMemoryArray(decision->downlowerbounds, downdomainreductions->lowerbounds, nvars);
5155  BMScopyMemoryArray(decision->downupperbounds, downdomainreductions->upperbounds, nvars);
5156  decision->boundsvalid = TRUE;
5157  }
5158  else
5159  {
5160  decision->boundsvalid = FALSE;
5161  }
5162 
5163  bestscorelowerbound = branchlb;
5164  bestscoreupperbound = branchub;
5165  bestscoringlpobjval = scoringlpobjval;
5166  assert(!SCIPisEQ(scip, bestscorelowerbound, bestscoreupperbound));
5167 
5168  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "New best var <%s> with bounds [<%g>..<%g>] and score %.9g\n",
5169  SCIPvarGetName(decision->branchvar), bestscorelowerbound, bestscoreupperbound, bestscore);
5170  }
5171 
5172 #ifdef SCIP_DEBUG
5173  LABdebugMessage(scip, SCIP_VERBLEVEL_NORMAL, " -> cand %d/%d var <%s> (solval=%.9g, downgain=%.9g->%.9g, upgain=%.9g->%.9g,"
5174  " score=%.9g) -- best: <%s> (%.9g)\n", c, nlpcands, SCIPvarGetName(branchvar), branchval,
5175  MAX(downbranchingresult->objval - scoringlpobjval, 0), MAX(downbranchingresult->dualbound - scoringlpobjval, 0),
5176  MAX(upbranchingresult->objval - scoringlpobjval, 0), MAX(upbranchingresult->dualbound - scoringlpobjval, 0),
5177  score, SCIPvarGetName(decision->branchvar), bestscore);
5178 #endif
5179 
5180  if( config->inscoring )
5181  {
5182  assert(scorecontainer != NULL);
5183  /* only for abbreviated lookahead branching: we are in the FSB filtering step and store the score for this
5184  * variable and the warm starting basis to reuse it in the subsequent lookahead evaluation of the best
5185  * candidates
5186  */
5187  SCIP_CALL( scoreContainerSetScore(scip, scorecontainer, candidate, score,
5188  downbranchingresult->dualbound - scoringlpobjval, upbranchingresult->dualbound - scoringlpobjval) );
5189  }
5190 
5191  if( probingdepth == 0 && (binconsdata != NULL || domainreductions != NULL) && !useoldbranching
5192  && (config->maxnviolatedcons >= 0 || config->maxnviolatedbincons >= 0 || config->maxnviolateddomreds >= 0 ) )
5193  {
5194  int nbincons = 0;
5195  int ndomreds = 0;
5196 
5197  if( binconsdata != NULL )
5198  {
5199  assert(binconsdata != NULL); /* for lint */
5200  nbincons = binconsdata->conslist->nviolatedcons;
5201  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Found %d binary constraints (%d violated by the LP solution)\n",
5202  binconsdata->conslist->nelements, nbincons);
5203 
5204  if( (config->maxnviolatedbincons > 0) && (nbincons >= config->maxnviolatedbincons) )
5205  {
5206  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The max number of violated binary constraints <%i> is "
5207  "exceeded.\n", config->maxnviolatedbincons);
5208  status->maxnconsreached = TRUE;
5209  }
5210  }
5211 
5212  if( domainreductions != NULL )
5213  {
5214  assert(domainreductions != NULL); /* for lint */
5215  ndomreds = domainreductions->nviolatedvars;
5216  if( config->prefersimplebounds && ndomreds > domainreductions->nsimplebounds )
5217  ndomreds = domainreductions->nsimplebounds;
5218 
5219  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Found %d bound changes (%d violated by the LP solution)\n",
5220  domainreductions->nchangedvars, ndomreds);
5221 
5222  if( (config->maxnviolateddomreds > 0) && (ndomreds >= config->maxnviolateddomreds) )
5223  {
5224  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The max number of violated bound changes <%i> is "
5225  "exceeded.\n", config->maxnviolateddomreds);
5226  status->maxnconsreached = TRUE;
5227  }
5228  }
5229 
5230  if( config->maxnviolatedcons > 0 && (nbincons + ndomreds >= config->maxnviolatedcons) )
5231  {
5232  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "The max number of violated binary constraints and bound "
5233  "changes <%d> is exceeded.\n", config->maxnviolatedcons);
5234  status->maxnconsreached = TRUE;
5235  }
5236  }
5237  }
5238 
5239  if( !(status->domred && decision->branchvar == candidate->branchvar) && areBoundsChanged(scip, decision->branchvar, bestscorelowerbound, bestscoreupperbound) )
5240  {
5241  /* in case the bounds of the current highest scored solution have changed due to domain propagation during
5242  * the lookahead branching we can/should not branch on this variable but instead report the domain
5243  * reduction */
5244  status->domred = TRUE;
5245 #ifdef SCIP_STATISTIC
5246  statistics->npropdomred[probingdepth]++;
5247 #endif
5248  LABdebugMessage(scip, SCIP_VERBLEVEL_HIGH, "Domain Propagation changed the bounds of a branching candidate."
5249  "\n");
5250  }
5251 
5252  /* free domain reductions */
5253  if( updomainreductions != NULL )
5254  {
5255  assert(downdomainreductions != NULL);
5256 
5257  domainReductionsFree(scip, &updomainreductions);
5258  domainReductionsFree(scip, &downdomainreductions);
5259  }
5260  }
5261 
5262  branchingResultDataFree(scip, &bestupbranchingresult);
5263  branchingResultDataFree(scip, &bestdownbranchingresult);
5264 
5265  branchingResultDataFree(scip, &upbranchingresult);
5266  branchingResultDataFree(scip, &downbranchingresult);
5267 
5268  if( persistent != NULL && (!config->abbreviated || config->inscoring) && probingdepth == 0 )
5269  {
5270  persistent->restartindex = c;
5271  }
5272 
5273  return SCIP_OKAY;
5274 }
5275 
5276 /** checks whether the current decision should be stored. This is the case if we found domain reductions
5277  * or constraints that will be applied, but none of them cuts off the current LP solution.
5278  * Then our current decision still holds true for the next call and can be reused without further calculations
5279  */
5280 static
5282  CONFIGURATION* config, /**< the configuration of the branching rule */
5283  BINCONSDATA* binconsdata, /**< container collecting all binary constraints; or NULL */
5284  DOMAINREDUCTIONS* domainreductions /**< container collecting all domain reductions found; or NULL */
5285  )
5286 {
5287  assert(config != NULL);
5288 
5289  if( !config->storeunviolatedsol )
5290  return FALSE;
5291 
5292  /* there are violating binary constraints */
5293  if( binconsdata != NULL && binconsdata->conslist->nviolatedcons > 0 )
5294  return FALSE;
5295 
5296  /* there are violating domain changes */
5297  if( domainreductions != NULL && domainreductions->nviolatedvars > 0 )
5298  return FALSE;
5299 
5300  /* return TRUE if there is at least one domain change or binary constraint */
5301  return (domainreductions != NULL && domainreductions->nchangedvars > 0)
5302  || (binconsdata != NULL && binconsdata->conslist->nelements > 0);
5303 }
5304 
5305 /** starting point to obtain a branching decision via LAB/ALAB. */
5306 static
5308  SCIP* scip, /**< SCIP data structure */
5309  CONFIGURATION* config, /**< the configuration of the branching rule */
5310  PERSISTENTDATA* persistent, /**< container to store data over multiple calls to the branching rule; or NULL */
5311  STATUS* status, /**< current status */
5312  BRANCHINGDECISION* decision, /**< struct to store the final decision */
5313  SCORECONTAINER* scorecontainer, /**< container to retrieve already calculated scores; or NULL */
5314  CANDIDATELIST* candidatelist /**< list of candidates to branch on */
5315 #ifdef SCIP_STATISTIC
5316  ,STATISTICS* statistics /**< general statistical data */
5317  ,LOCALSTATISTICS* localstats /**< local statistics, may be disregarded */
5318 #endi