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