Scippy

SCIP

Solving Constraint Integer Programs

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