Scippy

SCIP

Solving Constraint Integer Programs

branch.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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch.c
17  * @ingroup OTHER_CFILES
18  * @brief methods for branching rules and branching candidate storage
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Gerald Gamrath
22  * @author Stefan Heinz
23  * @author Michael Winkler
24  * @author Stefan Vigerske
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 
29 #include <assert.h>
30 #include <string.h>
31 
32 #include "scip/def.h"
33 #include "blockmemshell/memory.h"
34 #include "scip/set.h"
35 #include "scip/stat.h"
36 #include "scip/clock.h"
37 #include "scip/paramset.h"
38 #include "scip/event.h"
39 #include "scip/lp.h"
40 #include "scip/var.h"
41 #include "scip/prob.h"
42 #include "scip/tree.h"
43 #include "scip/sepastore.h"
44 #include "scip/scip.h"
45 #include "scip/branch.h"
46 #include "scip/solve.h"
47 
48 #include "scip/struct_branch.h"
49 
50 /*
51  * memory growing methods for dynamically allocated arrays
52  */
53 
54 /** ensures, that lpcands array can store at least num entries */
55 static
57  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
58  SCIP_SET* set, /**< global SCIP settings */
59  int num /**< minimum number of entries to store */
60  )
61 {
62  assert(branchcand->nlpcands <= branchcand->lpcandssize);
63 
64  if( num > branchcand->lpcandssize )
65  {
66  int newsize;
67 
68  newsize = SCIPsetCalcMemGrowSize(set, num);
69  SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcands, newsize) );
70  SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcandssol, newsize) );
71  SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcandsfrac, newsize) );
72  branchcand->lpcandssize = newsize;
73  }
74  assert(num <= branchcand->lpcandssize);
75 
76  return SCIP_OKAY;
77 }
78 
79 /** ensures, that pseudocands array can store at least num entries */
80 static
82  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
83  SCIP_SET* set, /**< global SCIP settings */
84  int num /**< minimum number of entries to store */
85  )
86 {
87  assert(branchcand->npseudocands <= branchcand->pseudocandssize);
88 
89  if( num > branchcand->pseudocandssize )
90  {
91  int newsize;
92 
93  newsize = SCIPsetCalcMemGrowSize(set, num);
94  SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->pseudocands, newsize) );
95  branchcand->pseudocandssize = newsize;
96  }
97  assert(num <= branchcand->pseudocandssize);
98 
99  return SCIP_OKAY;
100 }
101 
102 /** ensures, that externcands array can store at least num entries */
103 static
105  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
106  SCIP_SET* set, /**< global SCIP settings */
107  int num /**< minimum number of entries to store */
108  )
109 {
110  assert(branchcand->nexterncands <= branchcand->externcandssize);
111 
112  if( num > branchcand->externcandssize )
113  {
114  int newsize;
115 
116  newsize = SCIPsetCalcMemGrowSize(set, num);
117  SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcands, newsize) );
118  SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcandsscore, newsize) );
119  SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcandssol, newsize) );
120  branchcand->externcandssize = newsize;
121  }
122  assert(num <= branchcand->externcandssize);
123 
124  return SCIP_OKAY;
125 }
126 
127 
128 
129 /*
130  * branching candidate storage methods
131  */
132 
133 /** creates a branching candidate storage */
135  SCIP_BRANCHCAND** branchcand /**< pointer to store branching candidate storage */
136  )
137 {
138  assert(branchcand != NULL);
139 
140  SCIP_ALLOC( BMSallocMemory(branchcand) );
141  (*branchcand)->lpcands = NULL;
142  (*branchcand)->lpcandssol = NULL;
143  (*branchcand)->lpcandsfrac = NULL;
144  (*branchcand)->externcands = NULL;
145  (*branchcand)->externcandssol = NULL;
146  (*branchcand)->externcandsscore = NULL;
147  (*branchcand)->pseudocands = NULL;
148  (*branchcand)->lpcandssize = 0;
149  (*branchcand)->nlpcands = 0;
150  (*branchcand)->nimpllpfracs = 0;
151  (*branchcand)->npriolpcands = 0;
152  (*branchcand)->npriolpbins = 0;
153  (*branchcand)->lpmaxpriority = INT_MIN;
154  (*branchcand)->externcandssize = 0;
155  (*branchcand)->nexterncands = 0;
156  (*branchcand)->nprioexterncands = 0;
157  (*branchcand)->nprioexternbins = 0;
158  (*branchcand)->nprioexternints = 0;
159  (*branchcand)->nprioexternimpls = 0;
160  (*branchcand)->externmaxpriority = INT_MIN;
161  (*branchcand)->pseudocandssize = 0;
162  (*branchcand)->npseudocands = 0;
163  (*branchcand)->npriopseudocands = 0;
164  (*branchcand)->npriopseudobins = 0;
165  (*branchcand)->npriopseudoints = 0;
166  (*branchcand)->pseudomaxpriority = INT_MIN;
167 
168  SCIPbranchcandInvalidate(*branchcand);
169 
170  return SCIP_OKAY;
171 }
172 
173 /** frees branching candidate storage */
175  SCIP_BRANCHCAND** branchcand /**< pointer to store branching candidate storage */
176  )
177 {
178  assert(branchcand != NULL);
179 
180  BMSfreeMemoryArrayNull(&(*branchcand)->lpcands);
181  BMSfreeMemoryArrayNull(&(*branchcand)->lpcandssol);
182  BMSfreeMemoryArrayNull(&(*branchcand)->lpcandsfrac);
183  BMSfreeMemoryArrayNull(&(*branchcand)->pseudocands);
184  BMSfreeMemoryArrayNull(&(*branchcand)->externcands);
185  BMSfreeMemoryArrayNull(&(*branchcand)->externcandsscore);
186  BMSfreeMemoryArrayNull(&(*branchcand)->externcandssol);
187  BMSfreeMemory(branchcand);
188 
189  return SCIP_OKAY;
190 }
191 
192 /** resets branching candidates storage */
194  SCIP_BRANCHCAND* branchcand /**< pointer to store branching candidate storage */
195  )
196 {
197  assert(branchcand != NULL);
198 
199  branchcand->validlpcandslp = -1;
200 }
201 
202 /** calculates branching candidates for LP solution branching (fractional variables) */
203 static
205  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
206  SCIP_SET* set, /**< global SCIP settings */
207  SCIP_STAT* stat, /**< problem statistics */
208  SCIP_LP* lp /**< current LP data */
209  )
210 {
211  assert(branchcand != NULL);
212  assert(stat != NULL);
213  assert(branchcand->validlpcandslp <= stat->lpcount);
214  assert(lp != NULL);
215  assert(lp->solved);
217 
218  SCIPsetDebugMsg(set, "calculating LP branching candidates: validlp=%" SCIP_LONGINT_FORMAT ", lpcount=%" SCIP_LONGINT_FORMAT "\n",
219  branchcand->validlpcandslp, stat->lpcount);
220 
221  /* check, if the current LP branching candidate array is invalid */
222  if( branchcand->validlpcandslp < stat->lpcount )
223  {
224  SCIP_COL** cols;
225  SCIP_VAR* var;
226  SCIP_COL* col;
227  SCIP_Real primsol;
228  SCIP_Real frac;
229  SCIP_VARTYPE vartype;
230  int branchpriority;
231  int ncols;
232  int c;
233  int insertpos;
234 
235  SCIPsetDebugMsg(set, " -> recalculating LP branching candidates\n");
236 
237  cols = SCIPlpGetCols(lp);
238  ncols = SCIPlpGetNCols(lp);
239 
240  /* construct the LP branching candidate set, moving the candidates with maximal priority to the front */
241  SCIP_CALL( ensureLpcandsSize(branchcand, set, ncols) );
242 
243  branchcand->lpmaxpriority = INT_MIN / 2;
244  branchcand->nlpcands = 0;
245  branchcand->nimpllpfracs = 0;
246  branchcand->npriolpcands = 0;
247  branchcand->npriolpbins = 0;
248  for( c = 0; c < ncols; ++c )
249  {
250  col = cols[c];
251  assert(col != NULL);
252  assert(col->lppos == c);
253  assert(col->lpipos >= 0);
254 
255  primsol = SCIPcolGetPrimsol(col);
256  assert(primsol < SCIP_INVALID);
257  assert(SCIPsetIsInfinity(set, -col->lb) || SCIPsetIsFeasGE(set, primsol, col->lb));
258  assert(SCIPsetIsInfinity(set, col->ub) || SCIPsetIsFeasLE(set, primsol, col->ub));
259 
260  /* count values at infinity as integral */
261  if( SCIPsetIsInfinity(set, REALABS(primsol)) )
262  continue;
263 
264  var = col->var;
265  assert(var != NULL);
266  assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
267  assert(SCIPvarGetCol(var) == col);
268 
269  /* LP branching candidates are fractional binary and integer variables; implicit variables are kept at the end
270  * of the candidates array for some rounding heuristics
271  */
272  vartype = SCIPvarGetType(var);
273  if( vartype == SCIP_VARTYPE_CONTINUOUS )
274  continue;
275 
276  /* ignore fixed variables (due to numerics, it is possible, that the LP solution of a fixed integer variable
277  * (with large fixed value) is fractional in terms of absolute feasibility measure)
278  */
279  if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
280  continue;
281 
282  /* check, if the LP solution value is fractional */
283  frac = SCIPsetFeasFrac(set, primsol);
284 
285  /* The fractionality should not be smaller than -feastol, however, if the primsol is large enough
286  * and close to an integer, fixed precision floating point arithmetic might give us values slightly
287  * smaller than -feastol. Originally, the "frac >= -feastol"-check was within SCIPsetIsFeasFracIntegral(),
288  * however, we relaxed it to "frac >= -2*feastol" and have the stricter check here for small-enough primsols.
289  */
290  assert(SCIPsetIsGE(set, frac, -SCIPsetFeastol(set)) || (primsol > 1e14 * SCIPsetFeastol(set)));
291 
292  if( SCIPsetIsFeasFracIntegral(set, frac) )
293  continue;
294 
295  /* insert candidate in candidate list */
296  branchpriority = SCIPvarGetBranchPriority(var);
297  insertpos = branchcand->nlpcands + branchcand->nimpllpfracs;
298  assert(insertpos < branchcand->lpcandssize);
299 
300  if( vartype == SCIP_VARTYPE_IMPLINT )
301  branchpriority = INT_MIN;
302 
303  assert(vartype == SCIP_VARTYPE_IMPLINT || branchpriority >= INT_MIN/2);
304  /* ensure that implicit variables are stored at the end of the array */
305  if( vartype != SCIP_VARTYPE_IMPLINT && branchcand->nimpllpfracs > 0 )
306  {
307  assert(branchcand->lpcands[branchcand->nlpcands] != NULL
308  && SCIPvarGetType(branchcand->lpcands[branchcand->nlpcands]) == SCIP_VARTYPE_IMPLINT );
309 
310  branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->nlpcands];
311  branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->nlpcands];
312  branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->nlpcands];
313 
314  insertpos = branchcand->nlpcands;
315  }
316 
317  if( branchpriority > branchcand->lpmaxpriority )
318  {
319  /* candidate has higher priority than the current maximum:
320  * move it to the front and declare it to be the single best candidate
321  */
322  if( insertpos != 0 )
323  {
324  branchcand->lpcands[insertpos] = branchcand->lpcands[0];
325  branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[0];
326  branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[0];
327  insertpos = 0;
328  }
329  branchcand->npriolpcands = 1;
330  branchcand->npriolpbins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0);
331  branchcand->lpmaxpriority = branchpriority;
332  }
333  else if( branchpriority == branchcand->lpmaxpriority )
334  {
335  /* candidate has equal priority as the current maximum:
336  * move away the first non-maximal priority candidate, move the current candidate to the correct
337  * slot (binaries first) and increase the number of maximal priority candidates
338  */
339  if( insertpos != branchcand->npriolpcands )
340  {
341  branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->npriolpcands];
342  branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->npriolpcands];
343  branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->npriolpcands];
344  insertpos = branchcand->npriolpcands;
345  }
346  branchcand->npriolpcands++;
347  if( vartype == SCIP_VARTYPE_BINARY )
348  {
349  if( insertpos != branchcand->npriolpbins )
350  {
351  branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->npriolpbins];
352  branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->npriolpbins];
353  branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->npriolpbins];
354  insertpos = branchcand->npriolpbins;
355  }
356  branchcand->npriolpbins++;
357  }
358  }
359  /* insert variable at the correct position of the candidates storage */
360  branchcand->lpcands[insertpos] = var;
361  branchcand->lpcandssol[insertpos] = primsol;
362  branchcand->lpcandsfrac[insertpos] = frac;
363 
364  /* increase the counter depending on the variable type */
365  if( vartype != SCIP_VARTYPE_IMPLINT )
366  branchcand->nlpcands++;
367  else
368  branchcand->nimpllpfracs++;
369 
370  SCIPsetDebugMsg(set, " -> candidate %d: var=<%s>, sol=%g, frac=%g, prio=%d (max: %d) -> pos %d\n",
371  branchcand->nlpcands, SCIPvarGetName(var), primsol, frac, branchpriority, branchcand->lpmaxpriority,
372  insertpos);
373  }
374 
375 #ifndef NDEBUG
376  /* in debug mode we assert that the variables are positioned correctly (binaries and integers first,
377  * implicit integers last)
378  */
379  for( c = 0; c < branchcand->nlpcands + branchcand->nimpllpfracs; ++c )
380  {
381  assert(c >= branchcand->nlpcands || SCIPvarGetType(branchcand->lpcands[c]) != SCIP_VARTYPE_IMPLINT);
382  assert(c < branchcand->nlpcands || SCIPvarGetType(branchcand->lpcands[c]) == SCIP_VARTYPE_IMPLINT);
383  }
384 #endif
385 
386  branchcand->validlpcandslp = stat->lpcount;
387  }
388  assert(0 <= branchcand->npriolpcands && branchcand->npriolpcands <= branchcand->nlpcands);
389 
390  SCIPsetDebugMsg(set, " -> %d fractional variables (%d of maximal priority)\n", branchcand->nlpcands, branchcand->npriolpcands);
391 
392  return SCIP_OKAY;
393 }
394 
395 /** gets branching candidates for LP solution branching (fractional variables) */
397  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
398  SCIP_SET* set, /**< global SCIP settings */
399  SCIP_STAT* stat, /**< problem statistics */
400  SCIP_LP* lp, /**< current LP data */
401  SCIP_VAR*** lpcands, /**< pointer to store the array of LP branching candidates, or NULL */
402  SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */
403  SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */
404  int* nlpcands, /**< pointer to store the number of LP branching candidates, or NULL */
405  int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */
406  int* nfracimplvars /**< pointer to store the number of implicit fractional variables, or NULL */
407  )
408 {
409  /* calculate branching candidates */
410  SCIP_CALL( branchcandCalcLPCands(branchcand, set, stat, lp) );
411 
412  /* assign return values */
413  if( lpcands != NULL )
414  *lpcands = branchcand->lpcands;
415  if( lpcandssol != NULL )
416  *lpcandssol = branchcand->lpcandssol;
417  if( lpcandsfrac != NULL )
418  *lpcandsfrac = branchcand->lpcandsfrac;
419  if( nlpcands != NULL )
420  *nlpcands = branchcand->nlpcands;
421  if( npriolpcands != NULL )
422  *npriolpcands = (set->branch_preferbinary && branchcand->npriolpbins > 0 ? branchcand->npriolpbins
423  : branchcand->npriolpcands);
424  if( nfracimplvars != NULL )
425  *nfracimplvars = branchcand->nimpllpfracs;
426 
427  return SCIP_OKAY;
428 }
429 
430 /** gets external branching candidates */
432  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
433  SCIP_VAR*** externcands, /**< pointer to store the array of external branching candidates, or NULL */
434  SCIP_Real** externcandssol, /**< pointer to store the array of external candidate solution values, or NULL */
435  SCIP_Real** externcandsscore, /**< pointer to store the array of external candidate scores, or NULL */
436  int* nexterncands, /**< pointer to store the number of external branching candidates, or NULL */
437  int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */
438  int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */
439  int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */
440  int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority,
441  * or NULL */
442  )
443 {
444  assert(branchcand != NULL);
445 
446  /* assign return values */
447  if( externcands != NULL )
448  *externcands = branchcand->externcands;
449  if( externcandssol != NULL )
450  *externcandssol = branchcand->externcandssol;
451  if( externcandsscore != NULL )
452  *externcandsscore = branchcand->externcandsscore;
453  if( nexterncands != NULL )
454  *nexterncands = branchcand->nexterncands;
455  if( nprioexterncands != NULL )
456  *nprioexterncands = branchcand->nprioexterncands;
457  if( nprioexternbins != NULL )
458  *nprioexternbins = branchcand->nprioexternbins;
459  if( nprioexternints != NULL )
460  *nprioexternints = branchcand->nprioexternints;
461  if( nprioexternimpls != NULL )
462  *nprioexternimpls = branchcand->nprioexternimpls;
463 
464  return SCIP_OKAY;
465 }
466 
467 /** gets maximal branching priority of LP branching candidates */
469  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
470  )
471 {
472  assert(branchcand != NULL);
473 
474  return branchcand->lpmaxpriority;
475 }
476 
477 /** gets number of LP branching candidates with maximal branch priority */
479  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
480  )
481 {
482  assert(branchcand != NULL);
483 
484  return branchcand->npriolpcands;
485 }
486 
487 /** gets maximal branching priority of external branching candidates */
489  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
490  )
491 {
492  assert(branchcand != NULL);
493 
494  return branchcand->externmaxpriority;
495 }
496 
497 /** gets number of external branching candidates */
499  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
500  )
501 {
502  assert(branchcand != NULL);
503 
504  return branchcand->nexterncands;
505 }
506 
507 /** gets number of external branching candidates with maximal branch priority */
509  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
510  )
511 {
512  assert(branchcand != NULL);
513 
514  return branchcand->nprioexterncands;
515 }
516 
517 /** gets number of binary external branching candidates with maximal branch priority */
519  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
520  )
521 {
522  assert(branchcand != NULL);
523 
524  return branchcand->nprioexternbins;
525 }
526 
527 /** gets number of integer external branching candidates with maximal branch priority */
529  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
530  )
531 {
532  assert(branchcand != NULL);
533 
534  return branchcand->nprioexternints;
535 }
536 
537 /** gets number of implicit integer external branching candidates with maximal branch priority */
539  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
540  )
541 {
542  assert(branchcand != NULL);
543 
544  return branchcand->nprioexternimpls;
545 }
546 
547 /** gets number of continuous external branching candidates with maximal branch priority */
549  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
550  )
551 {
552  assert(branchcand != NULL);
553 
554  return branchcand->nprioexterncands - branchcand->nprioexternbins - branchcand->nprioexternints - branchcand->nprioexternimpls;
555 }
556 
557 /** insert variable, its score and its solution value into the external branching candidate storage
558  * the absolute difference of the current lower and upper bounds of the variable must be at least epsilon
559  */
561  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
562  SCIP_SET* set, /**< global SCIP settings */
563  SCIP_VAR* var, /**< variable to insert */
564  SCIP_Real score, /**< score of external candidate, e.g. infeasibility */
565  SCIP_Real solval /**< value of the variable in the current solution */
566  )
567 {
568  SCIP_VARTYPE vartype;
569  int branchpriority;
570  int insertpos;
571 
572  assert(branchcand != NULL);
573  assert(var != NULL);
574  assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); /* the variable should not be fixed yet */
575  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || !SCIPsetIsEQ(set, SCIPsetCeil(set, SCIPvarGetLbLocal(var)), SCIPsetFloor(set, SCIPvarGetUbLocal(var)))); /* a discrete variable should also not be fixed, even after rounding bounds to integral values */
576  assert(SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR || !SCIPsetIsEQ(set, SCIPvarGetMultaggrLbLocal(var, set), SCIPvarGetMultaggrUbLocal(var, set))); /* also the current bounds of a multi-aggregated variable should not be fixed yet */
577  assert(branchcand->nprioexterncands <= branchcand->nexterncands);
578  assert(branchcand->nexterncands <= branchcand->externcandssize);
579 
580  vartype = SCIPvarGetType(var);
581  branchpriority = SCIPvarGetBranchPriority(var);
582  insertpos = branchcand->nexterncands;
583 
584  SCIP_CALL( ensureExterncandsSize(branchcand, set, branchcand->nexterncands+1) );
585 
586  SCIPsetDebugMsg(set, "inserting external candidate <%s> of type %d and priority %d into candidate set (maxprio: %d), score = %g, solval = %g\n",
587  SCIPvarGetName(var), vartype, branchpriority, branchcand->externmaxpriority, score, solval);
588 
589  /* insert the variable into externcands, making sure, that the highest priority candidates are at the front
590  * and ordered binaries, integers, implicit integers, continuous
591  */
592  if( branchpriority > branchcand->externmaxpriority )
593  {
594  /* candidate has higher priority than the current maximum:
595  * move it to the front and declare it to be the single best candidate
596  */
597  branchcand->externcands[insertpos] = branchcand->externcands[0];
598  branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[0];
599  branchcand->externcandssol[insertpos] = branchcand->externcandssol[0];
600 
601  insertpos = 0;
602 
603  branchcand->nprioexterncands = 1;
604  branchcand->nprioexternbins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0);
605  branchcand->nprioexternints = (vartype == SCIP_VARTYPE_INTEGER ? 1 : 0);
606  branchcand->nprioexternimpls = (vartype == SCIP_VARTYPE_IMPLINT ? 1 : 0);
607  branchcand->externmaxpriority = branchpriority;
608  }
609  else if( branchpriority == branchcand->externmaxpriority )
610  {
611  /* candidate has equal priority as the current maximum:
612  * move away the first non-maximal priority candidate, move the current candidate to the correct
613  * slot (binaries first, integers next, implicit integers next, continuous last) and increase the number
614  * of maximal priority candidates
615  */
616  if( insertpos != branchcand->nprioexterncands )
617  {
618  branchcand->externcands[insertpos] = branchcand->externcands[branchcand->nprioexterncands];
619  branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[branchcand->nprioexterncands];
620  branchcand->externcandssol[insertpos] = branchcand->externcandssol[branchcand->nprioexterncands];
621 
622  insertpos = branchcand->nprioexterncands;
623  }
624  branchcand->nprioexterncands++;
625  if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER || vartype == SCIP_VARTYPE_IMPLINT )
626  {
627  if( insertpos != branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls )
628  {
629  branchcand->externcands[insertpos] =
630  branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
631  branchcand->externcandsscore[insertpos] =
632  branchcand->externcandsscore[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
633  branchcand->externcandssol[insertpos] =
634  branchcand->externcandssol[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
635 
636  insertpos = branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls;
637  }
638  branchcand->nprioexternimpls++;
639 
640  if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER )
641  {
642  if( insertpos != branchcand->nprioexternbins + branchcand->nprioexternints )
643  {
644  branchcand->externcands[insertpos] =
645  branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints];
646  branchcand->externcandsscore[insertpos] =
647  branchcand->externcandsscore[branchcand->nprioexternbins + branchcand->nprioexternints];
648  branchcand->externcandssol[insertpos] =
649  branchcand->externcandssol[branchcand->nprioexternbins + branchcand->nprioexternints];
650 
651  insertpos = branchcand->nprioexternbins + branchcand->nprioexternints;
652  }
653  branchcand->nprioexternints++;
654  branchcand->nprioexternimpls--;
655 
656  if( vartype == SCIP_VARTYPE_BINARY )
657  {
658  if( insertpos != branchcand->nprioexternbins )
659  {
660  branchcand->externcands[insertpos] = branchcand->externcands[branchcand->nprioexternbins];
661  branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[branchcand->nprioexternbins];
662  branchcand->externcandssol[insertpos] = branchcand->externcandssol[branchcand->nprioexternbins];
663 
664  insertpos = branchcand->nprioexternbins;
665  }
666  branchcand->nprioexternbins++;
667  branchcand->nprioexternints--;
668  }
669  }
670  }
671  }
672  branchcand->externcands[insertpos] = var;
673  branchcand->externcandsscore[insertpos] = score;
674  branchcand->externcandssol[insertpos] = solval;
675  branchcand->nexterncands++;
676 
677  SCIPsetDebugMsg(set, " -> inserted at position %d (nprioexterncands=%d)\n", insertpos, branchcand->nprioexterncands);
678 
679  assert(0 <= branchcand->nprioexterncands && branchcand->nprioexterncands <= branchcand->nexterncands);
680  assert(0 <= branchcand->nprioexternbins && branchcand->nprioexternbins <= branchcand->nprioexterncands);
681  assert(0 <= branchcand->nprioexternints && branchcand->nprioexternints <= branchcand->nprioexterncands);
682  assert(0 <= branchcand->nprioexternimpls && branchcand->nprioexternimpls <= branchcand->nprioexterncands);
683 
684  return SCIP_OKAY;
685 }
686 
687 /** removes all external candidates from the storage for external branching */
689  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
690  )
691 {
692  assert(branchcand != NULL);
693 
694  branchcand->nexterncands = 0;
695  branchcand->nprioexterncands = 0;
696  branchcand->nprioexternbins = 0;
697  branchcand->nprioexternints = 0;
698  branchcand->nprioexternimpls = 0;
699  branchcand->externmaxpriority = INT_MIN;
700 }
701 
702 /** checks whether the given variable is contained in the candidate storage for external branching */
704  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
705  SCIP_VAR* var /**< variable to look for */
706  )
707 {
708  int branchpriority;
709  int i;
710 
711  assert(branchcand != NULL);
712  assert(var != NULL);
713  assert(branchcand->nprioexterncands <= branchcand->nexterncands);
714  assert(branchcand->nexterncands <= branchcand->externcandssize);
715 
716  branchpriority = SCIPvarGetBranchPriority(var);
717 
718  /* look for the variable in the externcands, using the fact, that the highest priority candidates are at the front
719  * and ordered binaries, integers, implicit integers, continuous
720  */
721  if( branchpriority > branchcand->externmaxpriority )
722  {
723  /* the branching priority of the variable is higher than the maximal priority contained in the array;
724  * the variable can thus not be contained */
725  return FALSE;
726  }
727  if( branchpriority == branchcand->externmaxpriority )
728  {
729  SCIP_VARTYPE vartype;
730 
731  vartype = SCIPvarGetType(var);
732 
733  /* variable has equal priority as the current maximum:
734  * look for it in the correct slot (binaries first, integers next, implicit integers next, continuous last)
735  */
736  if( vartype == SCIP_VARTYPE_BINARY )
737  {
738  /* the variable is binary, look at the first branchcand->nprioexternbins slots */
739  for( i = 0; i < branchcand->nprioexternbins; i++ )
740  if( branchcand->externcands[i] == var )
741  return TRUE;
742  return FALSE;
743  }
744  if( vartype == SCIP_VARTYPE_INTEGER )
745  {
746  /* the variable is integer, look at the slots containing integers */
747  for( i = 0; i < branchcand->nprioexternints; i++ )
748  if( branchcand->externcands[branchcand->nprioexternbins + i] == var )
749  return TRUE;
750  return FALSE;
751  }
752  if( vartype == SCIP_VARTYPE_IMPLINT )
753  {
754  /* the variable is implicit integer, look at the slots containing implicit integers */
755  for( i = 0; i < branchcand->nprioexternimpls; i++ )
756  if( branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints + i] == var )
757  return TRUE;
758  return FALSE;
759  }
760  /* the variable is continuous, look at the slots containing continuous variables */
761  assert(vartype == SCIP_VARTYPE_CONTINUOUS);
762  for( i = branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls;
763  i < branchcand->nprioexterncands; i++ )
764  if( branchcand->externcands[i] == var )
765  return TRUE;
766  return FALSE;
767  }
768  /* the branching priority of the variable is lower than the maximal priority contained in the array;
769  * look for the variable in the candidates which do not have maximal priority */
770  assert(branchpriority < branchcand->externmaxpriority);
771 
772  for( i = branchcand->nprioexterncands; i < branchcand->nexterncands; i++ )
773  if( branchcand->externcands[i] == var )
774  return TRUE;
775  return FALSE;
776 }
777 
778 /** gets branching candidates for pseudo solution branching (non-fixed variables) */
780  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
781  SCIP_SET* set, /**< global SCIP settings */
782  SCIP_PROB* prob, /**< problem data */
783  SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
784  int* npseudocands, /**< pointer to store the number of pseudo branching candidates, or NULL */
785  int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
786  )
787 {
788  assert(branchcand != NULL);
789 
790 #ifndef NDEBUG
791  /* check, if the current pseudo branching candidate array is correct */
792  {
793  SCIP_VAR* var;
794  int npcs;
795  int v;
796 
797  assert(prob != NULL);
798 
799  /* pseudo branching candidates are non-fixed binary, integer, and implicit integer variables */
800  npcs = 0;
801  for( v = 0; v < prob->nbinvars + prob->nintvars + prob->nimplvars; ++v )
802  {
803  var = prob->vars[v];
804  assert(var != NULL);
806  assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY
809  assert(SCIPsetIsFeasIntegral(set, SCIPvarGetLbLocal(var)));
810  assert(SCIPsetIsFeasIntegral(set, SCIPvarGetUbLocal(var)));
811  assert(SCIPsetIsLE(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
812 
813  if( SCIPsetIsLT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
814  {
815  assert(0 <= var->pseudocandindex && var->pseudocandindex < branchcand->npseudocands);
816  assert(branchcand->pseudocands[var->pseudocandindex] == var);
817  npcs++;
818  }
819  else
820  {
821  assert(var->pseudocandindex == -1);
822  }
823  }
824  assert(branchcand->npseudocands == npcs);
825  for (v = 0; v < branchcand->npriopseudocands; ++v)
826  assert( branchcand->pseudocands[v]->branchpriority == branchcand->pseudomaxpriority );
827  }
828 #endif
829 
830  /* assign return values */
831  if( pseudocands != NULL )
832  *pseudocands = branchcand->pseudocands;
833  if( npseudocands != NULL )
834  *npseudocands = branchcand->npseudocands;
835  if( npriopseudocands != NULL )
836  *npriopseudocands = (set->branch_preferbinary && branchcand->npriopseudobins > 0 ? branchcand->npriopseudobins
837  : branchcand->npriopseudocands);
838 
839  return SCIP_OKAY;
840 }
841 
842 /** gets number of branching candidates for pseudo solution branching (non-fixed variables) */
844  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
845  )
846 {
847  assert(branchcand != NULL);
848 
849  return branchcand->npseudocands;
850 }
851 
852 /** gets number of branching candidates with maximal branch priority for pseudo solution branching */
854  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
855  )
856 {
857  assert(branchcand != NULL);
858 
859  return branchcand->npriopseudocands;
860 }
861 
862 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching */
864  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
865  )
866 {
867  assert(branchcand != NULL);
868 
869  return branchcand->npriopseudobins;
870 }
871 
872 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching */
874  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
875  )
876 {
877  assert(branchcand != NULL);
878 
879  return branchcand->npriopseudoints;
880 }
881 
882 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching */
884  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
885  )
886 {
887  assert(branchcand != NULL);
888 
889  return branchcand->npriopseudocands - branchcand->npriopseudobins - branchcand->npriopseudoints;
890 }
891 
892 /** insert pseudocand at given position, or to the first positions of the maximal priority candidates, using the
893  * given position as free slot for the other candidates
894  */
895 static
897  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
898  SCIP_VAR* var, /**< variable to insert */
899  int insertpos /**< free position to insert the variable */
900  )
901 {
902  SCIP_VARTYPE vartype;
903  int branchpriority;
904 
905  assert(branchcand != NULL);
906  assert(var != NULL);
907  assert(branchcand->npriopseudocands <= insertpos && insertpos < branchcand->npseudocands);
908  assert(branchcand->npseudocands <= branchcand->pseudocandssize);
909 
910  vartype = SCIPvarGetType(var);
911  branchpriority = SCIPvarGetBranchPriority(var);
912 
913  SCIPdebugMessage("inserting pseudo candidate <%s> of type %d and priority %d into candidate set at position %d (maxprio: %d)\n",
914  SCIPvarGetName(var), vartype, branchpriority, insertpos, branchcand->pseudomaxpriority);
915 
916  /* insert the variable into pseudocands, making sure, that the highest priority candidates are at the front
917  * and ordered binaries, integers, implicit integers
918  */
919  if( branchpriority > branchcand->pseudomaxpriority )
920  {
921  /* candidate has higher priority than the current maximum:
922  * move it to the front and declare it to be the single best candidate
923  */
924  if( insertpos != 0 )
925  {
926  branchcand->pseudocands[insertpos] = branchcand->pseudocands[0];
927  branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
928  insertpos = 0;
929  }
930  branchcand->npriopseudocands = 1;
931  branchcand->npriopseudobins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0);
932  branchcand->npriopseudoints = (vartype == SCIP_VARTYPE_INTEGER ? 1 : 0);
933  branchcand->pseudomaxpriority = branchpriority;
934  }
935  else if( branchpriority == branchcand->pseudomaxpriority )
936  {
937  /* candidate has equal priority as the current maximum:
938  * move away the first non-maximal priority candidate, move the current candidate to the correct
939  * slot (binaries first, integers next, implicit integers last) and increase the number of maximal priority candidates
940  */
941  if( insertpos != branchcand->npriopseudocands )
942  {
943  branchcand->pseudocands[insertpos] = branchcand->pseudocands[branchcand->npriopseudocands];
944  branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
945  insertpos = branchcand->npriopseudocands;
946  }
947  branchcand->npriopseudocands++;
948  if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER )
949  {
950  if( insertpos != branchcand->npriopseudobins + branchcand->npriopseudoints )
951  {
952  branchcand->pseudocands[insertpos] =
953  branchcand->pseudocands[branchcand->npriopseudobins + branchcand->npriopseudoints];
954  branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
955  insertpos = branchcand->npriopseudobins + branchcand->npriopseudoints;
956  }
957  branchcand->npriopseudoints++;
958 
959  if( vartype == SCIP_VARTYPE_BINARY )
960  {
961  if( insertpos != branchcand->npriopseudobins )
962  {
963  branchcand->pseudocands[insertpos] = branchcand->pseudocands[branchcand->npriopseudobins];
964  branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
965  insertpos = branchcand->npriopseudobins;
966  }
967  branchcand->npriopseudobins++;
968  branchcand->npriopseudoints--;
969  }
970  }
971  }
972  branchcand->pseudocands[insertpos] = var;
973  var->pseudocandindex = insertpos;
974 
975  SCIPdebugMessage(" -> inserted at position %d (npriopseudocands=%d)\n", insertpos, branchcand->npriopseudocands);
976 
977  assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
978  assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
979  assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
980 }
981 
982 /** sorts the pseudo branching candidates, such that the candidates of maximal priority are at the front,
983  * ordered by binaries, integers, implicit integers
984  */
985 static
987  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
988  )
989 {
990  SCIP_VAR* var;
991  int i;
992 
993  assert(branchcand != NULL);
994  assert(branchcand->npriopseudocands == 0); /* is only be called after removal of last maximal candidate */
995  assert(branchcand->npriopseudobins == 0);
996  assert(branchcand->npriopseudoints == 0);
997 
998  SCIPdebugMessage("resorting pseudo candidates\n");
999 
1000  branchcand->pseudomaxpriority = INT_MIN;
1001 
1002  for( i = 0; i < branchcand->npseudocands; ++i )
1003  {
1004  var = branchcand->pseudocands[i];
1005  assert(var->pseudocandindex == i);
1006 
1007  if( SCIPvarGetBranchPriority(var) >= branchcand->pseudomaxpriority )
1008  branchcandInsertPseudoCand(branchcand, var, i);
1009  }
1010 
1011  assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
1012  assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
1013  assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
1014 #ifndef NDEBUG
1015  {
1016  for (i = 0; i < branchcand->npriopseudocands; ++i)
1017  assert( branchcand->pseudocands[i]->branchpriority == branchcand->pseudomaxpriority );
1018  }
1019 #endif
1020 }
1021 
1022 /** removes pseudo candidate from pseudocands array
1023  */
1024 static
1026  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1027  SCIP_VAR* var /**< variable to remove */
1028  )
1029 {
1030  int freepos;
1031 
1032  assert(branchcand != NULL);
1033  assert(var != NULL);
1034  assert(var->pseudocandindex < branchcand->npseudocands);
1035  assert(branchcand->pseudocands[var->pseudocandindex] == var);
1036  assert(branchcand->pseudocands[branchcand->npseudocands-1] != NULL);
1037 
1038  /* Note that the branching priority of the variable to be removed is not necessarily equal to pseudomaxpriority, since
1039  * the status of the variable might have changed, leading to a change in the branching priority. Moreover, if the
1040  * variable was part of an aggregation, even other variables might at this point have different priorities. */
1041  SCIPdebugMessage("removing pseudo candidate <%s> of type %d and priority %d at %d from candidate set (maxprio: %d)\n",
1043  branchcand->pseudomaxpriority);
1044 
1045  /* delete the variable from pseudocands, making sure, that the highest priority candidates are at the front
1046  * and ordered binaries, integers, implicit integers
1047  */
1048  freepos = var->pseudocandindex;
1049  var->pseudocandindex = -1;
1050  assert(0 <= freepos && freepos < branchcand->npseudocands);
1051 
1052  if( freepos < branchcand->npriopseudobins )
1053  {
1054  /* a binary candidate of maximal priority was removed */
1055  assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
1056  if( freepos != branchcand->npriopseudobins - 1 )
1057  {
1058  branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npriopseudobins - 1];
1059  branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1060  freepos = branchcand->npriopseudobins - 1;
1061  }
1062  branchcand->npriopseudobins--;
1063  branchcand->npriopseudoints++;
1064  }
1065 
1066  if( freepos < branchcand->npriopseudobins + branchcand->npriopseudoints )
1067  {
1068  /* a binary or integer candidate of maximal priority was removed */
1070  if( freepos != branchcand->npriopseudobins + branchcand->npriopseudoints - 1 )
1071  {
1072  branchcand->pseudocands[freepos] =
1073  branchcand->pseudocands[branchcand->npriopseudobins + branchcand->npriopseudoints - 1];
1074  branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1075  freepos = branchcand->npriopseudobins + branchcand->npriopseudoints - 1;
1076  }
1077  branchcand->npriopseudoints--;
1078  }
1079 
1080  if( freepos < branchcand->npriopseudocands )
1081  {
1082  /* a candidate of maximal priority was removed */
1083  if( freepos != branchcand->npriopseudocands - 1 )
1084  {
1085  branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npriopseudocands - 1];
1086  branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1087  freepos = branchcand->npriopseudocands - 1;
1088  }
1089  branchcand->npriopseudocands--;
1090  }
1091  if( freepos != branchcand->npseudocands - 1 )
1092  {
1093  branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npseudocands - 1];
1094  branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1095  }
1096  branchcand->npseudocands--;
1097 
1098  assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
1099  assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
1100  assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
1101 
1102  /* if all maximal priority candidates were removed, resort the array s.t. the new maximal priority candidates
1103  * are at the front
1104  */
1105  if( branchcand->npriopseudocands == 0 )
1106  branchcandSortPseudoCands(branchcand);
1107 }
1108 
1109 /** removes variable from branching candidate list */
1111  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1112  SCIP_VAR* var /**< variable that changed its bounds */
1113  )
1114 {
1115  assert(var != NULL);
1116 
1117  /* make sure, variable is not member of the pseudo branching candidate list */
1118  if( var->pseudocandindex >= 0 )
1119  {
1120  branchcandRemovePseudoCand(branchcand, var);
1121  }
1122 
1123  return SCIP_OKAY;
1124 }
1125 
1126 /** updates branching candidate list for a given variable */
1128  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1129  SCIP_SET* set, /**< global SCIP settings */
1130  SCIP_VAR* var /**< variable that changed its bounds */
1131  )
1132 {
1133  assert(branchcand != NULL);
1134  assert(var != NULL);
1135 
1138  && SCIPsetIsLT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
1139  {
1140  /* variable is neither continuous nor fixed and has non-empty domain: make sure it is member of the pseudo branching candidate list */
1141  if( var->pseudocandindex == -1 )
1142  {
1143  SCIP_CALL( ensurePseudocandsSize(branchcand, set, branchcand->npseudocands+1) );
1144 
1145  branchcand->npseudocands++;
1146  branchcandInsertPseudoCand(branchcand, var, branchcand->npseudocands-1);
1147  }
1148  }
1149  else
1150  {
1157  || SCIPsetIsGE(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
1158 
1159  /* variable is continuous or fixed or has empty domain: make sure it is not member of the pseudo branching candidate list */
1160  SCIP_CALL( SCIPbranchcandRemoveVar(branchcand, var) );
1161  }
1162 
1163  return SCIP_OKAY;
1164 }
1165 
1166 /** updates branching priority of the given variable and update the pseudo candidate array if needed */
1168  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1169  SCIP_SET* set, /**< global SCIP settings */
1170  SCIP_VAR* var, /**< variable that changed its bounds */
1171  int branchpriority /**< branch priority of the variable */
1172  )
1173 {
1174  int oldbranchpriority;
1175  int pseudomaxpriority;
1176 
1177  assert(branchcand != NULL);
1178 
1179  oldbranchpriority = SCIPvarGetBranchPriority(var);
1180 
1181  if( oldbranchpriority == branchpriority )
1182  return SCIP_OKAY;
1183 
1184  pseudomaxpriority = branchcand->pseudomaxpriority;
1185 
1186  /* if the variable currently belongs to the priority set or the new branching priority is larger than the current one,
1187  * remove it from the pseudo branch candidate array */
1188  if( oldbranchpriority == pseudomaxpriority || branchpriority > pseudomaxpriority )
1189  {
1190  SCIP_CALL( SCIPbranchcandRemoveVar(branchcand, var) );
1191  assert(var->pseudocandindex == -1);
1192  }
1193 
1194  /* change the branching priority of the variable */
1195  SCIP_CALL( SCIPvarChgBranchPriority(var, branchpriority) );
1196 
1197  /* if the variable is not part of the pseudo branching candidate array, check if it is a pseudo branching candidate
1198  * and add it if so */
1199  SCIP_CALL( SCIPbranchcandUpdateVar(branchcand, set, var) );
1200 
1201  return SCIP_OKAY;
1202 }
1203 
1204 
1205 
1206 /*
1207  * branching rule methods
1208  */
1209 
1210 /** compares two branching rules w. r. to their priority */
1211 SCIP_DECL_SORTPTRCOMP(SCIPbranchruleComp)
1212 { /*lint --e{715}*/
1213  return ((SCIP_BRANCHRULE*)elem2)->priority - ((SCIP_BRANCHRULE*)elem1)->priority;
1214 }
1215 
1216 /** comparison method for sorting branching rules w.r.t. to their name */
1217 SCIP_DECL_SORTPTRCOMP(SCIPbranchruleCompName)
1218 {
1220 }
1221 
1222 /** method to call, when the priority of a branching rule was changed */
1223 static
1224 SCIP_DECL_PARAMCHGD(paramChgdBranchrulePriority)
1225 { /*lint --e{715}*/
1226  SCIP_PARAMDATA* paramdata;
1227 
1228  paramdata = SCIPparamGetData(param);
1229  assert(paramdata != NULL);
1230 
1231  /* use SCIPsetBranchrulePriority() to mark the branchrules unsorted */
1232  SCIP_CALL( SCIPsetBranchrulePriority(scip, (SCIP_BRANCHRULE*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
1233 
1234  return SCIP_OKAY;
1235 }
1236 
1237 /** copies the given branchrule to a new scip */
1239  SCIP_BRANCHRULE* branchrule, /**< branchrule */
1240  SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
1241  )
1242 {
1243  assert(branchrule != NULL);
1244  assert(set != NULL);
1245  assert(set->scip != NULL);
1246 
1247  if( branchrule->branchcopy != NULL )
1248  {
1249  SCIPsetDebugMsg(set, "including branching rule %s in subscip %p\n", SCIPbranchruleGetName(branchrule), (void*)set->scip);
1250  SCIP_CALL( branchrule->branchcopy(set->scip, branchrule) );
1251  }
1252 
1253  return SCIP_OKAY;
1254 }
1255 
1256 /** internal method for creating a branching rule */
1257 static
1259  SCIP_BRANCHRULE** branchrule, /**< pointer to store branching rule */
1260  SCIP_SET* set, /**< global SCIP settings */
1261  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1262  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
1263  const char* name, /**< name of branching rule */
1264  const char* desc, /**< description of branching rule */
1265  int priority, /**< priority of the branching rule */
1266  int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
1267  SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
1268  * compared to best node's dual bound for applying branching rule
1269  * (0.0: only on current best node, 1.0: on all nodes) */
1270  SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule */
1271  SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */
1272  SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */
1273  SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */
1274  SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
1275  SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
1276  SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
1277  SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */
1278  SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
1279  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
1280  )
1281 {
1282  char paramname[SCIP_MAXSTRLEN];
1283  char paramdesc[SCIP_MAXSTRLEN];
1284 
1285  assert(branchrule != NULL);
1286  assert(name != NULL);
1287  assert(desc != NULL);
1288 
1289  SCIP_ALLOC( BMSallocMemory(branchrule) );
1290  BMSclearMemory(*branchrule);
1291 
1292  SCIP_ALLOC( BMSduplicateMemoryArray(&(*branchrule)->name, name, strlen(name)+1) );
1293  SCIP_ALLOC( BMSduplicateMemoryArray(&(*branchrule)->desc, desc, strlen(desc)+1) );
1294  (*branchrule)->priority = priority;
1295  (*branchrule)->maxdepth = maxdepth;
1296  (*branchrule)->maxbounddist = maxbounddist;
1297  (*branchrule)->branchcopy = branchcopy;
1298  (*branchrule)->branchfree = branchfree;
1299  (*branchrule)->branchinit = branchinit;
1300  (*branchrule)->branchexit = branchexit;
1301  (*branchrule)->branchinitsol = branchinitsol;
1302  (*branchrule)->branchexitsol = branchexitsol;
1303  (*branchrule)->branchexeclp = branchexeclp;
1304  (*branchrule)->branchexecext = branchexecext;
1305  (*branchrule)->branchexecps = branchexecps;
1306  (*branchrule)->branchruledata = branchruledata;
1307  SCIP_CALL( SCIPclockCreate(&(*branchrule)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
1308  SCIP_CALL( SCIPclockCreate(&(*branchrule)->branchclock, SCIP_CLOCKTYPE_DEFAULT) );
1309  (*branchrule)->nlpcalls = 0;
1310  (*branchrule)->nexterncalls = 0;
1311  (*branchrule)->npseudocalls = 0;
1312  (*branchrule)->ncutoffs = 0;
1313  (*branchrule)->ncutsfound = 0;
1314  (*branchrule)->nconssfound = 0;
1315  (*branchrule)->ndomredsfound = 0;
1316  (*branchrule)->nchildren = 0;
1317  (*branchrule)->initialized = FALSE;
1318 
1319  /* add parameters */
1320  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/priority", name);
1321  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of branching rule <%s>", name);
1322  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
1323  &(*branchrule)->priority, FALSE, priority, INT_MIN/4, INT_MAX/4,
1324  paramChgdBranchrulePriority, (SCIP_PARAMDATA*)(*branchrule)) ); /*lint !e740*/
1325  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/maxdepth", name);
1326  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal depth level, up to which branching rule <%s> should be used (-1 for no limit)", name);
1327  SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
1328  &(*branchrule)->maxdepth, FALSE, maxdepth, -1, SCIP_MAXTREEDEPTH,
1329  NULL, NULL) ); /*lint !e740*/
1330  (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/maxbounddist", name);
1331  (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for applying branching rule (0.0: only on current best node, 1.0: on all nodes)");
1332  SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname, paramdesc,
1333  &(*branchrule)->maxbounddist, FALSE, maxbounddist, 0.0, 1.0,
1334  NULL, NULL) ); /*lint !e740*/
1335 
1336  return SCIP_OKAY;
1337 }
1338 
1339 /** creates a branching rule */
1341  SCIP_BRANCHRULE** branchrule, /**< pointer to store branching rule */
1342  SCIP_SET* set, /**< global SCIP settings */
1343  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1344  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
1345  const char* name, /**< name of branching rule */
1346  const char* desc, /**< description of branching rule */
1347  int priority, /**< priority of the branching rule */
1348  int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
1349  SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
1350  * compared to best node's dual bound for applying branching rule
1351  * (0.0: only on current best node, 1.0: on all nodes) */
1352  SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule */
1353  SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */
1354  SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */
1355  SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */
1356  SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
1357  SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
1358  SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
1359  SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */
1360  SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
1361  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
1362  )
1363 {
1364  assert(branchrule != NULL);
1365  assert(name != NULL);
1366  assert(desc != NULL);
1367 
1368  SCIP_CALL_FINALLY( doBranchruleCreate(branchrule, set, messagehdlr, blkmem, name, desc, priority, maxdepth,
1369  maxbounddist, branchcopy, branchfree, branchinit, branchexit, branchinitsol, branchexitsol, branchexeclp,
1370  branchexecext, branchexecps, branchruledata), (void) SCIPbranchruleFree(branchrule, set) );
1371 
1372  return SCIP_OKAY;
1373 }
1374 
1375 /** frees memory of branching rule */
1377  SCIP_BRANCHRULE** branchrule, /**< pointer to branching rule data structure */
1378  SCIP_SET* set /**< global SCIP settings */
1379  )
1380 {
1381  assert(branchrule != NULL);
1382  if( *branchrule == NULL )
1383  return SCIP_OKAY;
1384  assert(!(*branchrule)->initialized);
1385  assert(set != NULL);
1386 
1387  /* call destructor of branching rule */
1388  if( (*branchrule)->branchfree != NULL )
1389  {
1390  SCIP_CALL( (*branchrule)->branchfree(set->scip, *branchrule) );
1391  }
1392 
1393  SCIPclockFree(&(*branchrule)->branchclock);
1394  SCIPclockFree(&(*branchrule)->setuptime);
1395  BMSfreeMemoryArrayNull(&(*branchrule)->name);
1396  BMSfreeMemoryArrayNull(&(*branchrule)->desc);
1397  BMSfreeMemory(branchrule);
1398 
1399  return SCIP_OKAY;
1400 }
1401 
1402 /** initializes branching rule */
1404  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1405  SCIP_SET* set /**< global SCIP settings */
1406  )
1407 {
1408  assert(branchrule != NULL);
1409  assert(set != NULL);
1410 
1411  if( branchrule->initialized )
1412  {
1413  SCIPerrorMessage("branching rule <%s> already initialized\n", branchrule->name);
1414  return SCIP_INVALIDCALL;
1415  }
1416 
1417  if( set->misc_resetstat )
1418  {
1419  SCIPclockReset(branchrule->setuptime);
1420  SCIPclockReset(branchrule->branchclock);
1421  branchrule->nlpcalls = 0;
1422  branchrule->nexterncalls = 0;
1423  branchrule->npseudocalls = 0;
1424  branchrule->ncutoffs = 0;
1425  branchrule->ncutsfound = 0;
1426  branchrule->nconssfound = 0;
1427  branchrule->ndomredsfound = 0;
1428  branchrule->nchildren = 0;
1429  }
1430 
1431  if( branchrule->branchinit != NULL )
1432  {
1433  /* start timing */
1434  SCIPclockStart(branchrule->setuptime, set);
1435 
1436  SCIP_CALL( branchrule->branchinit(set->scip, branchrule) );
1437 
1438  /* stop timing */
1439  SCIPclockStop(branchrule->setuptime, set);
1440  }
1441  branchrule->initialized = TRUE;
1442 
1443  return SCIP_OKAY;
1444 }
1445 
1446 /** deinitializes branching rule */
1448  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1449  SCIP_SET* set /**< global SCIP settings */
1450  )
1451 {
1452  assert(branchrule != NULL);
1453  assert(set != NULL);
1454 
1455  if( !branchrule->initialized )
1456  {
1457  SCIPerrorMessage("branching rule <%s> not initialized\n", branchrule->name);
1458  return SCIP_INVALIDCALL;
1459  }
1460 
1461  if( branchrule->branchexit != NULL )
1462  {
1463  /* start timing */
1464  SCIPclockStart(branchrule->setuptime, set);
1465 
1466  SCIP_CALL( branchrule->branchexit(set->scip, branchrule) );
1467 
1468  /* stop timing */
1469  SCIPclockStop(branchrule->setuptime, set);
1470  }
1471  branchrule->initialized = FALSE;
1472 
1473  return SCIP_OKAY;
1474 }
1475 
1476 /** informs branching rule that the branch and bound process is being started */
1478  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1479  SCIP_SET* set /**< global SCIP settings */
1480  )
1481 {
1482  assert(branchrule != NULL);
1483  assert(set != NULL);
1484 
1485  /* call solving process initialization method of branching rule */
1486  if( branchrule->branchinitsol != NULL )
1487  {
1488  /* start timing */
1489  SCIPclockStart(branchrule->setuptime, set);
1490 
1491  SCIP_CALL( branchrule->branchinitsol(set->scip, branchrule) );
1492 
1493  /* stop timing */
1494  SCIPclockStop(branchrule->setuptime, set);
1495  }
1496 
1497  return SCIP_OKAY;
1498 }
1499 
1500 /** informs branching rule that the branch and bound process data is being freed */
1502  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1503  SCIP_SET* set /**< global SCIP settings */
1504  )
1505 {
1506  assert(branchrule != NULL);
1507  assert(set != NULL);
1508 
1509  /* call solving process deinitialization method of branching rule */
1510  if( branchrule->branchexitsol != NULL )
1511  {
1512  /* start timing */
1513  SCIPclockStart(branchrule->setuptime, set);
1514 
1515  SCIP_CALL( branchrule->branchexitsol(set->scip, branchrule) );
1516 
1517  /* stop timing */
1518  SCIPclockStop(branchrule->setuptime, set);
1519  }
1520 
1521  return SCIP_OKAY;
1522 }
1523 
1524 /** executes branching rule for fractional LP solution */
1526  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1527  SCIP_SET* set, /**< global SCIP settings */
1528  SCIP_STAT* stat, /**< problem statistics */
1529  SCIP_TREE* tree, /**< branch and bound tree */
1530  SCIP_SEPASTORE* sepastore, /**< separation storage */
1531  SCIP_Real cutoffbound, /**< global upper cutoff bound */
1532  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
1533  SCIP_RESULT* result /**< pointer to store the result of the callback method */
1534  )
1535 {
1536  assert(branchrule != NULL);
1537  assert(set != NULL);
1538  assert(tree != NULL);
1539  assert(tree->focusnode != NULL);
1540  assert(tree->nchildren == 0);
1541  assert(result != NULL);
1542 
1543  *result = SCIP_DIDNOTRUN;
1544  if( branchrule->branchexeclp != NULL
1545  && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) )
1546  {
1547  SCIP_Real loclowerbound;
1548  SCIP_Real glblowerbound;
1549  SCIP_Bool runbranchrule;
1550 
1551  loclowerbound = SCIPnodeGetLowerbound(tree->focusnode);
1552  glblowerbound = SCIPtreeGetLowerbound(tree, set);
1553 
1554  /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1555  if( SCIPsetIsInfinity(set, -glblowerbound) )
1556  runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1557  else
1558  {
1559  assert(!SCIPsetIsInfinity(set, -loclowerbound));
1560  runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1561  }
1562 
1563  if( runbranchrule )
1564  {
1565  SCIP_Longint oldndomchgs;
1566  SCIP_Longint oldnprobdomchgs;
1567  SCIP_Longint oldnactiveconss;
1568  int oldncuts;
1569 
1570  SCIPsetDebugMsg(set, "executing LP branching rule <%s>\n", branchrule->name);
1571 
1572  oldndomchgs = stat->nboundchgs + stat->nholechgs;
1573  oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
1574  oldncuts = SCIPsepastoreGetNCuts(sepastore);
1575  oldnactiveconss = stat->nactiveconssadded;
1576 
1577  /* start timing */
1578  SCIPclockStart(branchrule->branchclock, set);
1579 
1580  /* call external method */
1581  SCIP_CALL( branchrule->branchexeclp(set->scip, branchrule, allowaddcons, result) );
1582 
1583  /* stop timing */
1584  SCIPclockStop(branchrule->branchclock, set);
1585 
1586  /* evaluate result */
1587  if( *result != SCIP_CUTOFF
1588  && *result != SCIP_CONSADDED
1589  && *result != SCIP_REDUCEDDOM
1590  && *result != SCIP_SEPARATED
1591  && *result != SCIP_BRANCHED
1592  && *result != SCIP_DIDNOTFIND
1593  && *result != SCIP_DIDNOTRUN )
1594  {
1595  SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from LP solution branching\n",
1596  branchrule->name, *result);
1597  return SCIP_INVALIDRESULT;
1598  }
1599  if( *result == SCIP_CONSADDED && !allowaddcons )
1600  {
1601  SCIPerrorMessage("branching rule <%s> added a constraint in LP solution branching without permission\n",
1602  branchrule->name);
1603  return SCIP_INVALIDRESULT;
1604  }
1605 
1606  /* update statistics */
1607  if( *result != SCIP_DIDNOTRUN )
1608  branchrule->nlpcalls++;
1609  if( *result == SCIP_CUTOFF )
1610  branchrule->ncutoffs++;
1611  if( *result != SCIP_BRANCHED )
1612  {
1613  assert(tree->nchildren == 0);
1614 
1615  /* update domain reductions; therefore remove the domain
1616  * reduction counts which were generated in probing mode */
1617  branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
1618  branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
1619 
1620  branchrule->ncutsfound += SCIPsepastoreGetNCuts(sepastore) - oldncuts; /*lint !e776*/
1621  branchrule->nconssfound += stat->nactiveconssadded - oldnactiveconss; /*lint !e776*/
1622  }
1623  else
1624  branchrule->nchildren += tree->nchildren;
1625  }
1626  }
1627 
1628  return SCIP_OKAY;
1629 }
1630 
1631 /** executes branching rule for external branching candidates */
1633  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1634  SCIP_SET* set, /**< global SCIP settings */
1635  SCIP_STAT* stat, /**< problem statistics */
1636  SCIP_TREE* tree, /**< branch and bound tree */
1637  SCIP_SEPASTORE* sepastore, /**< separation storage */
1638  SCIP_Real cutoffbound, /**< global upper cutoff bound */
1639  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
1640  SCIP_RESULT* result /**< pointer to store the result of the callback method */
1641  )
1642 {
1643  assert(branchrule != NULL);
1644  assert(set != NULL);
1645  assert(tree != NULL);
1646  assert(tree->focusnode != NULL);
1647  assert(tree->nchildren == 0);
1648  assert(result != NULL);
1649 
1650  *result = SCIP_DIDNOTRUN;
1651  if( branchrule->branchexecext != NULL
1652  && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) )
1653  {
1654  SCIP_Real loclowerbound;
1655  SCIP_Real glblowerbound;
1656  SCIP_Bool runbranchrule;
1657 
1658  loclowerbound = SCIPnodeGetLowerbound(tree->focusnode);
1659  glblowerbound = SCIPtreeGetLowerbound(tree, set);
1660  assert(!SCIPsetIsInfinity(set, loclowerbound));
1661 
1662  /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1663  if( SCIPsetIsInfinity(set, -glblowerbound) )
1664  runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1665  else
1666  {
1667  assert(!SCIPsetIsInfinity(set, -loclowerbound));
1668  runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1669  }
1670 
1671  if( runbranchrule )
1672  {
1673  SCIP_Longint oldndomchgs;
1674  SCIP_Longint oldnprobdomchgs;
1675  int oldncuts;
1676  int oldnactiveconss;
1677 
1678  SCIPsetDebugMsg(set, "executing external solution branching rule <%s>\n", branchrule->name);
1679 
1680  oldndomchgs = stat->nboundchgs + stat->nholechgs;
1681  oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
1682  oldncuts = SCIPsepastoreGetNCuts(sepastore);
1683  oldnactiveconss = stat->nactiveconss;
1684 
1685  /* start timing */
1686  SCIPclockStart(branchrule->branchclock, set);
1687 
1688  /* call external method */
1689  SCIP_CALL( branchrule->branchexecext(set->scip, branchrule, allowaddcons, result) );
1690 
1691  /* stop timing */
1692  SCIPclockStop(branchrule->branchclock, set);
1693 
1694  /* evaluate result */
1695  if( *result != SCIP_CUTOFF
1696  && *result != SCIP_CONSADDED
1697  && *result != SCIP_REDUCEDDOM
1698  && *result != SCIP_SEPARATED
1699  && *result != SCIP_BRANCHED
1700  && *result != SCIP_DIDNOTFIND
1701  && *result != SCIP_DIDNOTRUN )
1702  {
1703  SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from external solution branching\n",
1704  branchrule->name, *result);
1705  return SCIP_INVALIDRESULT;
1706  }
1707  if( *result == SCIP_CONSADDED && !allowaddcons )
1708  {
1709  SCIPerrorMessage("branching rule <%s> added a constraint in external solution branching without permission\n",
1710  branchrule->name);
1711  return SCIP_INVALIDRESULT;
1712  }
1713 
1714  /* update statistics */
1715  if( *result != SCIP_DIDNOTRUN )
1716  branchrule->nexterncalls++;
1717  if( *result == SCIP_CUTOFF )
1718  branchrule->ncutoffs++;
1719  if( *result != SCIP_BRANCHED )
1720  {
1721  assert(tree->nchildren == 0);
1722 
1723  /* update domain reductions; therefore remove the domain
1724  * reduction counts which were generated in probing mode */
1725  branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
1726  branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
1727 
1728  branchrule->ncutsfound += SCIPsepastoreGetNCuts(sepastore) - oldncuts; /*lint !e776*/
1729  branchrule->nconssfound += stat->nactiveconss - oldnactiveconss; /*lint !e776*/
1730  }
1731  else
1732  branchrule->nchildren += tree->nchildren;
1733  }
1734  }
1735  return SCIP_OKAY;
1736 }
1737 
1738 /** executes branching rule for not completely fixed pseudo solution */
1740  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1741  SCIP_SET* set, /**< global SCIP settings */
1742  SCIP_STAT* stat, /**< problem statistics */
1743  SCIP_TREE* tree, /**< branch and bound tree */
1744  SCIP_Real cutoffbound, /**< global upper cutoff bound */
1745  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
1746  SCIP_RESULT* result /**< pointer to store the result of the callback method */
1747  )
1748 {
1749  assert(branchrule != NULL);
1750  assert(set != NULL);
1751  assert(tree != NULL);
1752  assert(tree->nchildren == 0);
1753  assert(result != NULL);
1754 
1755  *result = SCIP_DIDNOTRUN;
1756  if( branchrule->branchexecps != NULL
1757  && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) )
1758  {
1759  SCIP_Real loclowerbound;
1760  SCIP_Real glblowerbound;
1761  SCIP_Bool runbranchrule;
1762 
1763  loclowerbound = SCIPnodeGetLowerbound(tree->focusnode);
1764  glblowerbound = SCIPtreeGetLowerbound(tree, set);
1765 
1766  /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1767  if( SCIPsetIsInfinity(set, -glblowerbound) )
1768  runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1769  else
1770  {
1771  assert(!SCIPsetIsInfinity(set, -loclowerbound));
1772  runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1773  }
1774 
1775  if( runbranchrule )
1776  {
1777  SCIP_Longint oldndomchgs;
1778  SCIP_Longint oldnprobdomchgs;
1779  SCIP_Longint oldnactiveconss;
1780 
1781  SCIPsetDebugMsg(set, "executing pseudo branching rule <%s>\n", branchrule->name);
1782 
1783  oldndomchgs = stat->nboundchgs + stat->nholechgs;
1784  oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
1785  oldnactiveconss = stat->nactiveconss;
1786 
1787  /* start timing */
1788  SCIPclockStart(branchrule->branchclock, set);
1789 
1790  /* call external method */
1791  SCIP_CALL( branchrule->branchexecps(set->scip, branchrule, allowaddcons, result) );
1792 
1793  /* stop timing */
1794  SCIPclockStop(branchrule->branchclock, set);
1795 
1796  /* evaluate result */
1797  if( *result != SCIP_CUTOFF
1798  && *result != SCIP_CONSADDED
1799  && *result != SCIP_REDUCEDDOM
1800  && *result != SCIP_BRANCHED
1801  && *result != SCIP_DIDNOTFIND
1802  && *result != SCIP_DIDNOTRUN )
1803  {
1804  SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from pseudo solution branching\n",
1805  branchrule->name, *result);
1806  return SCIP_INVALIDRESULT;
1807  }
1808  if( *result == SCIP_CONSADDED && !allowaddcons )
1809  {
1810  SCIPerrorMessage("branching rule <%s> added a constraint in pseudo solution branching without permission\n",
1811  branchrule->name);
1812  return SCIP_INVALIDRESULT;
1813  }
1814 
1815  /* update statistics */
1816  if( *result != SCIP_DIDNOTRUN )
1817  branchrule->npseudocalls++;
1818  if( *result == SCIP_CUTOFF )
1819  branchrule->ncutoffs++;
1820  if( *result != SCIP_BRANCHED )
1821  {
1822  assert(tree->nchildren == 0);
1823 
1824  /* update domain reductions; therefore remove the domain
1825  * reduction counts which were generated in probing mode */
1826  branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
1827  branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
1828 
1829  branchrule->nconssfound += stat->nactiveconss - oldnactiveconss;
1830  }
1831  else
1832  branchrule->nchildren += tree->nchildren;
1833  }
1834  }
1835 
1836  return SCIP_OKAY;
1837 }
1838 
1839 /** gets user data of branching rule */
1841  SCIP_BRANCHRULE* branchrule /**< branching rule */
1842  )
1843 {
1844  assert(branchrule != NULL);
1845 
1846  return branchrule->branchruledata;
1847 }
1848 
1849 /** sets user data of branching rule; user has to free old data in advance! */
1851  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1852  SCIP_BRANCHRULEDATA* branchruledata /**< new branching rule user data */
1853  )
1854 {
1855  assert(branchrule != NULL);
1856 
1857  branchrule->branchruledata = branchruledata;
1858 }
1859 
1860 /** sets copy method of branching rule */
1862  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1863  SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
1864  )
1865 {
1866  assert(branchrule != NULL);
1867 
1868  branchrule->branchcopy = branchcopy;
1869 }
1870 
1871 /** sets destructor method of branching rule */
1873  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1874  SCIP_DECL_BRANCHFREE ((*branchfree)) /**< destructor of branching rule */
1875  )
1876 {
1877  assert(branchrule != NULL);
1878 
1879  branchrule->branchfree = branchfree;
1880 }
1881 
1882 /** sets initialization method of branching rule */
1884  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1885  SCIP_DECL_BRANCHINIT ((*branchinit)) /**< initialize branching rule */
1886  )
1887 {
1888  assert(branchrule != NULL);
1889 
1890  branchrule->branchinit = branchinit;
1891 }
1892 
1893 /** sets deinitialization method of branching rule */
1895  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1896  SCIP_DECL_BRANCHEXIT ((*branchexit)) /**< deinitialize branching rule */
1897  )
1898 {
1899  assert(branchrule != NULL);
1900 
1901  branchrule->branchexit = branchexit;
1902 }
1903 
1904 /** sets solving process initialization method of branching rule */
1906  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1907  SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
1908  )
1909 {
1910  assert(branchrule != NULL);
1911 
1912  branchrule->branchinitsol = branchinitsol;
1913 }
1914 
1915 /** sets solving process deinitialization method of branching rule */
1917  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1918  SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
1919  )
1920 {
1921  assert(branchrule != NULL);
1922 
1923  branchrule->branchexitsol = branchexitsol;
1924 }
1925 
1926 
1927 
1928 /** sets branching execution method for fractional LP solutions */
1930  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1931  SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
1932  )
1933 {
1934  assert(branchrule != NULL);
1935 
1936  branchrule->branchexeclp = branchexeclp;
1937 }
1938 
1939 /** sets branching execution method for external candidates */
1941  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1942  SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
1943  )
1944 {
1945  assert(branchrule != NULL);
1946 
1947  branchrule->branchexecext = branchexecext;
1948 }
1949 
1950 /** sets branching execution method for not completely fixed pseudo solutions */
1952  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1953  SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
1954  )
1955 {
1956  assert(branchrule != NULL);
1957 
1958  branchrule->branchexecps = branchexecps;
1959 }
1960 
1961 /** gets name of branching rule */
1963  SCIP_BRANCHRULE* branchrule /**< branching rule */
1964  )
1965 {
1966  assert(branchrule != NULL);
1967 
1968  return branchrule->name;
1969 }
1970 
1971 /** gets description of branching rule */
1973  SCIP_BRANCHRULE* branchrule /**< branching rule */
1974  )
1975 {
1976  assert(branchrule != NULL);
1977 
1978  return branchrule->desc;
1979 }
1980 
1981 /** gets priority of branching rule */
1983  SCIP_BRANCHRULE* branchrule /**< branching rule */
1984  )
1985 {
1986  assert(branchrule != NULL);
1987 
1988  return branchrule->priority;
1989 }
1990 
1991 /** sets priority of branching rule */
1993  SCIP_BRANCHRULE* branchrule, /**< branching rule */
1994  SCIP_SET* set, /**< global SCIP settings */
1995  int priority /**< new priority of the branching rule */
1996  )
1997 {
1998  assert(branchrule != NULL);
1999  assert(set != NULL);
2000 
2001  branchrule->priority = priority;
2002  set->branchrulessorted = FALSE;
2003 }
2004 
2005 /** gets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
2007  SCIP_BRANCHRULE* branchrule /**< branching rule */
2008  )
2009 {
2010  assert(branchrule != NULL);
2011 
2012  return branchrule->maxdepth;
2013 }
2014 
2015 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
2017  SCIP_BRANCHRULE* branchrule, /**< branching rule */
2018  int maxdepth /**< new maxdepth of the branching rule */
2019  )
2020 {
2021  assert(branchrule != NULL);
2022  assert(maxdepth >= -1);
2023 
2024  branchrule->maxdepth = maxdepth;
2025 }
2026 
2027 /** gets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
2029  SCIP_BRANCHRULE* branchrule /**< branching rule */
2030  )
2031 {
2032  assert(branchrule != NULL);
2033 
2034  return branchrule->maxbounddist;
2035 }
2036 
2037 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
2039  SCIP_BRANCHRULE* branchrule, /**< branching rule */
2040  SCIP_Real maxbounddist /**< new maxbounddist of the branching rule */
2041  )
2042 {
2043  assert(branchrule != NULL);
2044  assert(maxbounddist >= -1);
2045 
2046  branchrule->maxbounddist = maxbounddist;
2047 }
2048 
2049 /** enables or disables all clocks of \p branchrule, depending on the value of the flag */
2051  SCIP_BRANCHRULE* branchrule, /**< the branching rule for which all clocks should be enabled or disabled */
2052  SCIP_Bool enable /**< should the clocks of the branching rule be enabled? */
2053  )
2054 {
2055  assert(branchrule != NULL);
2056 
2057  SCIPclockEnableOrDisable(branchrule->setuptime, enable);
2058  SCIPclockEnableOrDisable(branchrule->branchclock, enable);
2059 }
2060 
2061 /** gets time in seconds used in this branching rule for setting up for next stages */
2063  SCIP_BRANCHRULE* branchrule /**< branching rule */
2064  )
2065 {
2066  assert(branchrule != NULL);
2067 
2068  return SCIPclockGetTime(branchrule->setuptime);
2069 }
2070 
2071 /** gets time in seconds used in this branching rule */
2073  SCIP_BRANCHRULE* branchrule /**< branching rule */
2074  )
2075 {
2076  assert(branchrule != NULL);
2077 
2078  return SCIPclockGetTime(branchrule->branchclock);
2079 }
2080 
2081 /** gets the total number of times, the branching rule was called on an LP solution */
2083  SCIP_BRANCHRULE* branchrule /**< branching rule */
2084  )
2085 {
2086  assert(branchrule != NULL);
2087 
2088  return branchrule->nlpcalls;
2089 }
2090 
2091 /** gets the total number of times, the branching rule was called on an external solution */
2093  SCIP_BRANCHRULE* branchrule /**< branching rule */
2094  )
2095 {
2096  assert(branchrule != NULL);
2097 
2098  return branchrule->nexterncalls;
2099 }
2100 
2101 /** gets the total number of times, the branching rule was called on a pseudo solution */
2103  SCIP_BRANCHRULE* branchrule /**< branching rule */
2104  )
2105 {
2106  assert(branchrule != NULL);
2107 
2108  return branchrule->npseudocalls;
2109 }
2110 
2111 /** gets the total number of times, the branching rule detected a cutoff */
2113  SCIP_BRANCHRULE* branchrule /**< branching rule */
2114  )
2115 {
2116  assert(branchrule != NULL);
2117 
2118  return branchrule->ncutoffs;
2119 }
2120 
2121 /** gets the total number of cuts, the branching rule separated */
2123  SCIP_BRANCHRULE* branchrule /**< branching rule */
2124  )
2125 {
2126  assert(branchrule != NULL);
2127 
2128  return branchrule->ncutsfound;
2129 }
2130 
2131 /** gets the total number of constraints, the branching rule added to the respective local nodes (not counting constraints
2132  * that were added to the child nodes as branching decisions)
2133  */
2135  SCIP_BRANCHRULE* branchrule /**< branching rule */
2136  )
2137 {
2138  assert(branchrule != NULL);
2139 
2140  return branchrule->nconssfound;
2141 }
2142 
2143 /** gets the total number of domain reductions, the branching rule found */
2145  SCIP_BRANCHRULE* branchrule /**< branching rule */
2146  )
2147 {
2148  assert(branchrule != NULL);
2149 
2150  return branchrule->ndomredsfound;
2151 }
2152 
2153 /** gets the total number of children, the branching rule created */
2155  SCIP_BRANCHRULE* branchrule /**< branching rule */
2156  )
2157 {
2158  assert(branchrule != NULL);
2159 
2160  return branchrule->nchildren;
2161 }
2162 
2163 /** is branching rule initialized? */
2165  SCIP_BRANCHRULE* branchrule /**< branching rule */
2166  )
2167 {
2168  assert(branchrule != NULL);
2169 
2170  return branchrule->initialized;
2171 }
2172 
2173 
2174 
2175 
2176 /*
2177  * branching methods
2178  */
2179 
2180 /** calculates the branching score out of the gain predictions for a binary branching */
2182  SCIP_SET* set, /**< global SCIP settings */
2183  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
2184  SCIP_Real downgain, /**< prediction of objective gain for rounding downwards */
2185  SCIP_Real upgain /**< prediction of objective gain for rounding upwards */
2186  )
2187 {
2188  SCIP_Real score;
2189  SCIP_Real eps;
2190 
2191  assert(set != NULL);
2192 
2193  /* adjust scores near zero to always yield product score greater than 0 */
2194  eps = SCIPsetSumepsilon(set);
2195  if( set->branch_sumadjustscore )
2196  {
2197  /* adjust scores by adding eps to keep near zero score differences between variables */
2198  downgain = downgain + eps;
2199  upgain = upgain + eps;
2200  }
2201  else
2202  {
2203  /* disregard near zero score differences between variables and consider the branching factor for them */
2204  downgain = MAX(downgain, eps);
2205  upgain = MAX(upgain, eps);
2206  }
2207 
2208  switch( set->branch_scorefunc )
2209  {
2210  case 's': /* linear sum score function */
2211  /* weigh the two child nodes with branchscorefac and 1-branchscorefac */
2212  if( downgain > upgain )
2213  score = set->branch_scorefac * downgain + (1.0-set->branch_scorefac) * upgain;
2214  else
2215  score = set->branch_scorefac * upgain + (1.0-set->branch_scorefac) * downgain;
2216  break;
2217 
2218  case 'p': /* product score function */
2219  score = downgain * upgain;
2220  break;
2221  case 'q': /* quotient score function */
2222  if( downgain > upgain )
2223  score = upgain * upgain / downgain;
2224  else
2225  score = downgain * downgain / upgain;
2226  break;
2227  default:
2228  SCIPerrorMessage("invalid branching score function <%c>\n", set->branch_scorefunc);
2229  SCIPABORT();
2230  score = 0.0;
2231  }
2232 
2233  /* apply the branch factor of the variable */
2234  if( var != NULL )
2235  score *= SCIPvarGetBranchFactor(var);
2236 
2237  return score;
2238 }
2239 
2240 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children */
2242  SCIP_SET* set, /**< global SCIP settings */
2243  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
2244  int nchildren, /**< number of children that the branching will create */
2245  SCIP_Real* gains /**< prediction of objective gain for each child */
2246  )
2247 {
2248  SCIP_Real min1;
2249  SCIP_Real min2;
2250  int c;
2251 
2252  assert(nchildren == 0 || gains != NULL);
2253 
2254  /* search for the two minimal gains in the child list and use these to calculate the branching score */
2255  min1 = SCIPsetInfinity(set);
2256  min2 = SCIPsetInfinity(set);
2257  for( c = 0; c < nchildren; ++c )
2258  {
2259  if( gains[c] < min1 )
2260  {
2261  min2 = min1;
2262  min1 = gains[c];
2263  }
2264  else if( gains[c] < min2 )
2265  min2 = gains[c];
2266  }
2267 
2268  return SCIPbranchGetScore(set, var, min1, min2);
2269 }
2270 
2271 /** computes a branching point for a (not necessarily discrete) variable
2272  * a suggested branching point is first projected onto the box
2273  * if no point is suggested, then the value in the current LP or pseudo solution is used
2274  * if this value is at infinity, then 0.0 projected onto the bounds and then moved inside the interval is used
2275  * for a discrete variable, it is ensured that the returned value is fractional
2276  * for a continuous variable, the parameter branching/clamp defines how far a branching point need to be from the bounds of a variable
2277  * the latter is only applied if no point has been suggested, or the suggested point is not inside the variable's interval
2278  */
2280  SCIP_SET* set, /**< global SCIP settings */
2281  SCIP_TREE* tree, /**< branch and bound tree */
2282  SCIP_VAR* var, /**< variable, of which the branching point should be computed */
2283  SCIP_Real suggestion /**< suggestion for branching point, or SCIP_INVALID if no suggestion */
2284  )
2285 {
2286  SCIP_Real branchpoint;
2287  SCIP_Real lb;
2288  SCIP_Real ub;
2289 
2290  assert(set != NULL);
2291  assert(var != NULL);
2292 
2293  lb = SCIPvarGetLbLocal(var);
2294  ub = SCIPvarGetUbLocal(var);
2295 
2296  /* for a fixed variable, we cannot branch further */
2297  assert(!SCIPsetIsEQ(set, lb, ub));
2298 
2299  if( !SCIPsetIsInfinity(set, REALABS(suggestion)) )
2300  {
2301  /* use user suggested branching point */
2302 
2303  /* first, project it onto the current domain */
2304  branchpoint = MAX(lb, MIN(suggestion, ub));
2305 
2307  {
2308  /* if it is a discrete variable, then round it down and up and accept this choice */
2309  if( SCIPsetIsEQ(set, branchpoint, ub) )
2310  {
2311  /* in the right branch, variable is fixed to its current upper bound */
2312  return SCIPsetFloor(set, branchpoint) - 0.5;
2313  }
2314  else
2315  {
2316  /* in the left branch, variable is fixed to its current lower bound */
2317  return SCIPsetFloor(set, branchpoint) + 0.5;
2318  }
2319  }
2320  else if( (SCIPsetIsInfinity(set, -lb) || SCIPsetIsRelGT(set, branchpoint, lb)) &&
2321  (SCIPsetIsInfinity(set, ub) || SCIPsetIsRelLT(set, branchpoint, ub)) )
2322  {
2323  /* if it is continuous and inside the box, then accept it */
2324  return branchpoint;
2325  }
2326  /* if it is continuous and suggestion is on of the bounds, continue below */
2327  }
2328  else
2329  {
2330  /* if no point is suggested, try the LP or pseudo solution */
2331  branchpoint = SCIPvarGetSol(var, SCIPtreeHasCurrentNodeLP(tree));
2332 
2333  if( REALABS(branchpoint) > 1e+12 )
2334  {
2335  /* if the value in the LP or pseudosolution is large (here 1e+12), use 0.0 (will be projected onto bounds below) */
2336  branchpoint = 0.0;
2337  }
2338  else if( SCIPtreeHasCurrentNodeLP(tree) && set->branch_midpull > 0.0 && !SCIPsetIsInfinity(set, -lb) && !SCIPsetIsInfinity(set, ub) )
2339  {
2340  /* if the value is from the LP and midpull is activated, then push towards middle of domain */
2341  SCIP_Real midpull = set->branch_midpull;
2342  SCIP_Real glb;
2343  SCIP_Real gub;
2344  SCIP_Real reldomainwidth;
2345 
2346  /* shrink midpull if width of local domain, relative to global domain, is small
2347  * that is, if there has been already one or several branchings on this variable, then give more emphasis on LP solution
2348  *
2349  * do this only if the relative domain width is below the minreldomainwidth value
2350  */
2351  glb = SCIPvarGetLbGlobal(var);
2352  gub = SCIPvarGetUbGlobal(var);
2353  assert(glb < gub);
2354 
2355  if( !SCIPsetIsInfinity(set, -glb) && !SCIPsetIsInfinity(set, gub) )
2356  reldomainwidth = (ub - lb) / (gub - glb);
2357  else
2358  reldomainwidth = SCIPsetEpsilon(set);
2359 
2360  if( reldomainwidth < set->branch_midpullreldomtrig )
2361  midpull *= reldomainwidth;
2362 
2363  branchpoint = midpull * (lb+ub) / 2.0 + (1.0 - midpull) * branchpoint;
2364  }
2365 
2366  /* make sure branchpoint is on interval, below we make sure that it is within bounds for continuous vars */
2367  branchpoint = MAX(lb, MIN(branchpoint, ub));
2368  }
2369 
2370  /* if value is at +/- infty, then choose some value a bit off from bounds or 0.0 */
2371  if( SCIPsetIsInfinity(set, branchpoint) )
2372  {
2373  /* if value is at +infty, then the upper bound should be at infinity */
2374  assert(SCIPsetIsInfinity(set, ub));
2375 
2376  /* choose 0.0 or something above lower bound if lower bound > 0 */
2377  if( SCIPsetIsPositive(set, lb) )
2378  branchpoint = lb + 1000.0;
2379  else
2380  branchpoint = 0.0;
2381  }
2382  else if( SCIPsetIsInfinity(set, -branchpoint) )
2383  {
2384  /* if value is at -infty, then the lower bound should be at -infinity */
2385  assert(SCIPsetIsInfinity(set, -lb));
2386 
2387  /* choose 0.0 or something below upper bound if upper bound < 0 */
2388  if( SCIPsetIsNegative(set, ub) )
2389  branchpoint = ub - 1000.0;
2390  else
2391  branchpoint = 0.0;
2392  }
2393 
2394  assert(SCIPsetIsInfinity(set, ub) || SCIPsetIsLE(set, branchpoint, ub));
2395  assert(SCIPsetIsInfinity(set, -lb) || SCIPsetIsGE(set, branchpoint, lb));
2396 
2397  if( SCIPvarGetType(var) >= SCIP_VARTYPE_IMPLINT )
2398  {
2399  if( !SCIPsetIsInfinity(set, -lb) || !SCIPsetIsInfinity(set, ub) )
2400  {
2401  /* if one bound is missing, we are temporarily guessing the other one, so we can apply the clamp below */
2402  if( SCIPsetIsInfinity(set, ub) )
2403  {
2404  ub = lb + MIN(MAX(0.5 * REALABS(lb), 1000), 0.9 * (SCIPsetInfinity(set) - lb)); /*lint !e666*/
2405  }
2406  else if( SCIPsetIsInfinity(set, -lb) )
2407  {
2408  lb = ub - MIN(MAX(0.5 * REALABS(ub), 1000), 0.9 * (SCIPsetInfinity(set) + ub)); /*lint !e666*/
2409  }
2410 
2411  /* if branching point is too close to the bounds, move more into the middle of the interval */
2412  if( SCIPrelDiff(ub, lb) <= 2.02 * SCIPsetEpsilon(set) )
2413  {
2414  /* for very tiny intervals we set it exactly into the middle */
2415  branchpoint = (lb+ub)/2.0;
2416  }
2417  else
2418  {
2419  /* otherwise we project it away from the bounds */
2420  SCIP_Real minbrpoint;
2421  SCIP_Real maxbrpoint;
2422  SCIP_Real scale;
2423  SCIP_Real lbabs;
2424  SCIP_Real ubabs;
2425 
2426  lbabs = REALABS(lb);
2427  ubabs = REALABS(ub);
2428 
2429  scale = MAX3(lbabs, ubabs, 1.0);
2430 
2431  /* the minimal branching point should be
2432  * - set->clamp away from the lower bound - relative to the local domain size
2433  * - SCIPsetEpsilon(set)*scale above the lower bound - in absolute value
2434  */
2435  minbrpoint = (1.0 - set->branch_clamp) * lb + set->branch_clamp * ub;
2436  minbrpoint = MAX(lb + 1.01*SCIPsetEpsilon(set)*scale, minbrpoint); /*lint !e666*/
2437 
2438  /* the maximal branching point should be
2439  * - set->clamp away from the upper bound - relative to the local domain size
2440  * - SCIPsetEpsilon(set)*scale below the upper bound - in absolute value
2441  */
2442  maxbrpoint = set->branch_clamp * lb + (1.0 - set->branch_clamp) * ub;
2443  maxbrpoint = MIN(ub - 1.01*SCIPsetEpsilon(set)*scale, maxbrpoint); /*lint !e666*/
2444 
2445  /* project branchpoint into [minbrpoint, maxbrpoint] */
2446  branchpoint = MAX(minbrpoint, MIN(branchpoint, maxbrpoint));
2447 
2448  /* if selected branching point is close to 0.0 and bounds are away from 0.0, it often makes sense to branch exactly on 0.0 */
2449  if( SCIPsetIsFeasZero(set, branchpoint) && SCIPsetIsFeasNegative(set, lb) && SCIPsetIsFeasPositive(set, ub) )
2450  branchpoint = 0.0;
2451 
2452  assert(SCIPsetIsRelLT(set, SCIPvarGetLbLocal(var), branchpoint));
2453  assert(SCIPsetIsRelLT(set, branchpoint, SCIPvarGetUbLocal(var)));
2454  }
2455  }
2456 
2457  /* ensure fractional branching point for implicit integer variables */
2458  if( SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT && SCIPsetIsIntegral(set, branchpoint) )
2459  {
2460  /* if branchpoint is integral but not on bounds, then it should be one of the value {lb+1, ..., ub-1} */
2461  assert(SCIPsetIsGE(set, SCIPsetRound(set, branchpoint), lb + 1.0));
2462  assert(SCIPsetIsLE(set, SCIPsetRound(set, branchpoint), ub - 1.0));
2463  /* if branchpoint is integral, create one branch with x <= x'-1 and one with x >= x'
2464  * @todo could in the same way be x <= x' and x >= x'+1; is there some easy way to know which is better?
2465  */
2466  return branchpoint - 0.5;
2467  }
2468 
2469  return branchpoint;
2470  }
2471  else
2472  {
2473  /* discrete variables */
2474  if( branchpoint <= lb + 0.5 )
2475  {
2476  /* if branchpoint is on lower bound, create one branch with x = lb and one with x >= lb+1 */
2477  return lb + 0.5;
2478  }
2479  else if( branchpoint >= ub - 0.5 )
2480  {
2481  /* if branchpoint is on upper bound, create one branch with x = ub and one with x <= ub-1 */
2482  return ub - 0.5;
2483  }
2484  else if( SCIPsetIsIntegral(set, branchpoint) )
2485  {
2486  /* if branchpoint is integral but not on bounds, then it should be one of the value {lb+1, ..., ub-1} */
2487  assert(SCIPsetIsGE(set, SCIPsetRound(set, branchpoint), lb + 1.0));
2488  assert(SCIPsetIsLE(set, SCIPsetRound(set, branchpoint), ub - 1.0));
2489  /* if branchpoint is integral, create one branch with x <= x'-1 and one with x >= x'
2490  * @todo could in the same way be x <= x' and x >= x'+1; is there some easy way to know which is better? */
2491  return branchpoint - 0.5;
2492  }
2493  else
2494  {
2495  /* branchpoint is somewhere between bounds and fractional, so just round down and up */
2496  return branchpoint;
2497  }
2498  }
2499 }
2500 
2501 /** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN;
2502  * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional
2503  * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority
2504  */
2506  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
2507  SCIP_SET* set, /**< global SCIP settings */
2508  SCIP_STAT* stat, /**< problem statistics */
2509  SCIP_PROB* transprob, /**< transformed problem after presolve */
2510  SCIP_PROB* origprob, /**< original problem */
2511  SCIP_TREE* tree, /**< branch and bound tree */
2512  SCIP_REOPT* reopt, /**< reoptimization data structure */
2513  SCIP_LP* lp, /**< current LP data */
2514  SCIP_SEPASTORE* sepastore, /**< separation storage */
2515  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2516  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2517  SCIP_Real cutoffbound, /**< global upper cutoff bound */
2518  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
2519  SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
2520  )
2521 {
2522  int i;
2523  int nalllpcands; /* sum of binary, integer, and implicit branching candidates */
2524 
2525  assert(branchcand != NULL);
2526  assert(result != NULL);
2527 
2528  *result = SCIP_DIDNOTRUN;
2529 
2530  /* calculate branching candidates */
2531  SCIP_CALL( branchcandCalcLPCands(branchcand, set, stat, lp) );
2532  assert(0 <= branchcand->npriolpcands && branchcand->npriolpcands <= branchcand->nlpcands);
2533  assert((branchcand->npriolpcands == 0) == (branchcand->nlpcands == 0));
2534 
2535  SCIPsetDebugMsg(set, "branching on LP solution with %d (+%d) fractional (+implicit fractional) variables (%d of maximal priority)\n",
2536  branchcand->nlpcands, branchcand->nimpllpfracs, branchcand->npriolpcands);
2537 
2538  nalllpcands = branchcand->nlpcands + branchcand->nimpllpfracs;
2539  /* do nothing, if no fractional variables exist */
2540  if( nalllpcands == 0 )
2541  return SCIP_OKAY;
2542 
2543  /* if there is a non-fixed variable with higher priority than the maximal priority of the fractional candidates,
2544  * use pseudo solution branching instead
2545  */
2546  if( branchcand->pseudomaxpriority > branchcand->lpmaxpriority )
2547  {
2548  SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cutoffbound,
2549  allowaddcons, result) );
2550  assert(*result != SCIP_DIDNOTRUN && *result != SCIP_DIDNOTFIND);
2551  return SCIP_OKAY;
2552  }
2553 
2554  /* sort the branching rules by priority */
2556 
2557  /* try all branching rules until one succeeded to branch */
2558  for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2559  {
2560  SCIP_CALL( SCIPbranchruleExecLPSol(set->branchrules[i], set, stat, tree, sepastore, cutoffbound, allowaddcons, result) );
2561  }
2562 
2563  if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND )
2564  {
2565  SCIP_VAR* var;
2566  SCIP_Real factor;
2567  SCIP_Real bestfactor;
2568  int priority;
2569  int bestpriority;
2570  int bestcand;
2571 
2572  /* no branching method succeeded in choosing a branching: just branch on the first fractional variable with maximal
2573  * priority, and out of these on the one with maximal branch factor
2574  */
2575  bestcand = -1;
2576  bestpriority = INT_MIN;
2577  bestfactor = SCIP_REAL_MIN;
2578  for( i = 0; i < nalllpcands; ++i )
2579  {
2580  priority = SCIPvarGetBranchPriority(branchcand->lpcands[i]);
2581  factor = SCIPvarGetBranchFactor(branchcand->lpcands[i]);
2582  if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) )
2583  {
2584  bestcand = i;
2585  bestpriority = priority;
2586  bestfactor = factor;
2587  }
2588  }
2589  assert(0 <= bestcand && bestcand < nalllpcands);
2590 
2591  var = branchcand->lpcands[bestcand];
2592  assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS);
2593  assert(branchcand->nlpcands == 0 || SCIPvarGetType(var) != SCIP_VARTYPE_IMPLINT);
2594 
2595  assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2596 
2597  SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, SCIP_INVALID,
2598  NULL, NULL, NULL) );
2599 
2600  *result = SCIP_BRANCHED;
2601  }
2602 
2603  return SCIP_OKAY;
2604 }
2605 
2606 /** calls branching rules to branch on an external solution; if no external branching candidates exist, the result is SCIP_DIDNOTRUN */
2608  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
2609  SCIP_SET* set, /**< global SCIP settings */
2610  SCIP_STAT* stat, /**< problem statistics */
2611  SCIP_PROB* transprob, /**< transformed problem after presolve */
2612  SCIP_PROB* origprob, /**< original problem */
2613  SCIP_TREE* tree, /**< branch and bound tree */
2614  SCIP_REOPT* reopt, /**< reoptimization data structure */
2615  SCIP_LP* lp, /**< current LP data */
2616  SCIP_SEPASTORE* sepastore, /**< separation storage */
2617  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2618  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2619  SCIP_Real cutoffbound, /**< global upper cutoff bound */
2620  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
2621  SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
2622  )
2623 {
2624  int i;
2625 
2626  assert(branchcand != NULL);
2627  assert(result != NULL);
2628  assert(0 <= branchcand->nprioexterncands && branchcand->nprioexterncands <= branchcand->nexterncands);
2629  assert((branchcand->nprioexterncands == 0) == (branchcand->nexterncands == 0));
2630 
2631  *result = SCIP_DIDNOTRUN;
2632 
2633  SCIPsetDebugMsg(set, "branching on external solution with %d branching candidates (%d of maximal priority)\n",
2634  branchcand->nexterncands, branchcand->nprioexterncands);
2635 
2636  /* do nothing, if no external candidates exist */
2637  if( branchcand->nexterncands == 0 )
2638  return SCIP_OKAY;
2639 
2640  /* if there is a non-fixed variable with higher priority than the maximal priority of the external candidates,
2641  * use pseudo solution branching instead
2642  */
2643  if( branchcand->pseudomaxpriority > branchcand->externmaxpriority )
2644  {
2645  /* @todo: adjust this, that also LP branching might be called, if lpmaxpriority != externmaxpriority.
2646  * Therefor, it has to be clear which of both has the higher priority
2647  */
2648  SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cutoffbound,
2649  allowaddcons, result) );
2650  assert(*result != SCIP_DIDNOTRUN && *result != SCIP_DIDNOTFIND);
2651  return SCIP_OKAY;
2652  }
2653 
2654  /* sort the branching rules by priority */
2656 
2657  /* try all branching rules until one succeeded to branch */
2658  for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2659  {
2660  SCIP_CALL( SCIPbranchruleExecExternSol(set->branchrules[i], set, stat, tree, sepastore, cutoffbound, allowaddcons, result) );
2661  }
2662 
2663  if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND )
2664  {
2665  SCIP_VAR* var;
2666  SCIP_Real val;
2667  SCIP_Real bestfactor;
2668  SCIP_Real bestdomain;
2669  int bestpriority;
2670  int bestcand;
2671 
2672  /* if all branching rules did nothing, then they should also not have cleared all branching candidates */
2673  assert(branchcand->nexterncands > 0);
2674 
2675  /* no branching method succeeded in choosing a branching: just branch on the first branching candidates with maximal
2676  * priority, and out of these on the one with maximal branch factor, and out of these on the one with largest domain
2677  */
2678  bestcand = -1;
2679  bestpriority = INT_MIN;
2680  bestfactor = SCIP_REAL_MIN;
2681  bestdomain = 0.0;
2682  for( i = 0; i < branchcand->nexterncands; ++i )
2683  {
2684  SCIP_VAR* cand;
2685  SCIP_Real domain;
2686  SCIP_Real factor;
2687  int priority;
2688 
2689  cand = branchcand->externcands[i];
2690  priority = SCIPvarGetBranchPriority(cand);
2691  factor = SCIPvarGetBranchFactor(cand);
2692 
2693  /* the domain size is infinite, iff one of the bounds is infinite */
2695  domain = SCIPsetInfinity(set);
2696  else
2697  domain = SCIPvarGetUbLocal(cand) - SCIPvarGetLbLocal(cand);
2698 
2699  /* choose variable with higher priority, higher factor, larger domain (in that order) */
2700  if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) || (priority == bestpriority && factor == bestfactor && domain > bestdomain) ) /*lint !e777*/
2701  {
2702  bestcand = i;
2703  bestpriority = priority;
2704  bestfactor = factor;
2705  bestdomain = domain;
2706  }
2707  }
2708  assert(0 <= bestcand && bestcand < branchcand->nexterncands);
2709 
2710  var = branchcand->externcands[bestcand];
2711  val = SCIPbranchGetBranchingPoint(set, tree, var, branchcand->externcandssol[bestcand]);
2712  assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2713  assert(SCIPrelDiff(SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var)) <= 2.02 * SCIPsetEpsilon(set)
2714  || SCIPsetIsLT(set, SCIPvarGetLbLocal(var), val));
2715  assert(SCIPrelDiff(SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var)) <= 2.02 * SCIPsetEpsilon(set)
2716  || SCIPsetIsLT(set, val, SCIPvarGetUbLocal(var)));
2717 
2718  SCIPsetDebugMsg(set, "no branching method succeeded; fallback selected to branch on variable <%s> with bounds [%g, %g] on value %g\n",
2719  SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), val);
2720 
2721  SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, val,
2722  NULL, NULL, NULL) );
2723 
2724  if( tree->nchildren >= 1 )
2725  *result = SCIP_BRANCHED;
2726  /* if the bounds are too close, it may happen that we cannot branch but rather fix the variable */
2727  else
2728  {
2729  assert(SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2730  *result = SCIP_REDUCEDDOM;
2731  }
2732  }
2733 
2734  return SCIP_OKAY;
2735 }
2736 
2737 /** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN */
2739  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
2740  SCIP_SET* set, /**< global SCIP settings */
2741  SCIP_STAT* stat, /**< problem statistics */
2742  SCIP_PROB* transprob, /**< transformed problem after presolve */
2743  SCIP_PROB* origprob, /**< original problem */
2744  SCIP_TREE* tree, /**< branch and bound tree */
2745  SCIP_REOPT* reopt, /**< reoptimization data structure */
2746  SCIP_LP* lp, /**< current LP data */
2747  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2748  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2749  SCIP_Real cutoffbound, /**< global upper cutoff bound */
2750  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
2751  SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
2752  )
2753 {
2754  int i;
2755 
2756  assert(branchcand != NULL);
2757  assert(result != NULL);
2758 
2759  SCIPsetDebugMsg(set, "branching on pseudo solution with %d unfixed variables\n", branchcand->npseudocands);
2760 
2761  *result = SCIP_DIDNOTRUN;
2762 
2763  /* do nothing, if no unfixed variables exist */
2764  if( branchcand->npseudocands == 0 )
2765  return SCIP_OKAY;
2766 
2767  /* sort the branching rules by priority */
2769 
2770  /* try all branching rules until one succeeded to branch */
2771  for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2772  {
2773  SCIP_CALL( SCIPbranchruleExecPseudoSol(set->branchrules[i], set, stat, tree, cutoffbound, allowaddcons, result) );
2774  }
2775 
2776  if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND )
2777  {
2778  SCIP_VAR* var;
2779  SCIP_Real factor;
2780  SCIP_Real bestfactor;
2781  int priority;
2782  int bestpriority;
2783  int bestcand;
2784 
2785  /* no branching method succeeded in choosing a branching: just branch on the first unfixed variable with maximal
2786  * priority, and out of these on the one with maximal branch factor
2787  */
2788  bestcand = -1;
2789  bestpriority = INT_MIN;
2790  bestfactor = SCIP_REAL_MIN;
2791  for( i = 0; i < branchcand->npseudocands; ++i )
2792  {
2793  priority = SCIPvarGetBranchPriority(branchcand->pseudocands[i]);
2794  factor = SCIPvarGetBranchFactor(branchcand->pseudocands[i]);
2795  if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) )
2796  {
2797  bestcand = i;
2798  bestpriority = priority;
2799  bestfactor = factor;
2800  }
2801  }
2802  assert(0 <= bestcand && bestcand < branchcand->npseudocands);
2803 
2804  var = branchcand->pseudocands[bestcand];
2805  assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS);
2806  assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2807 
2808  SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, SCIP_INVALID,
2809  NULL, NULL, NULL) );
2810 
2811  *result = SCIP_BRANCHED;
2812  }
2813 
2814  return SCIP_OKAY;
2815 }
2816 
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Real * lpcandssol
Definition: struct_branch.h:40
int SCIPbranchcandGetNPrioExternBins(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:518
SCIP_RETCODE SCIPbranchruleCreate(SCIP_BRANCHRULE **branchrule, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_DECL_BRANCHCOPY((*branchcopy)), SCIP_DECL_BRANCHFREE((*branchfree)), SCIP_DECL_BRANCHINIT((*branchinit)), SCIP_DECL_BRANCHEXIT((*branchexit)), SCIP_DECL_BRANCHINITSOL((*branchinitsol)), SCIP_DECL_BRANCHEXITSOL((*branchexitsol)), SCIP_DECL_BRANCHEXECLP((*branchexeclp)), SCIP_DECL_BRANCHEXECEXT((*branchexecext)), SCIP_DECL_BRANCHEXECPS((*branchexecps)), SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1340
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6200
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1840
internal methods for managing events
SCIP_Bool SCIPbranchruleIsInitialized(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2164
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6258
SCIP_RETCODE SCIPtreeBranchVar(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: tree.c:5420
SCIP_Bool SCIPsetIsFeasZero(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6708
SCIP_DECL_SORTPTRCOMP(SCIPbranchruleComp)
Definition: branch.c:1211
void SCIPbranchruleSetCopy(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: branch.c:1861
SCIP_Longint ncutsfound
Definition: struct_branch.h:78
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:141
internal methods for branch and bound tree
SCIP_Real SCIPbranchruleGetMaxbounddist(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2028
SCIP_Real SCIPsetFeastol(SCIP_SET *set)
Definition: set.c:6107
SCIP_Real SCIPvarGetBranchFactor(SCIP_VAR *var)
Definition: var.c:18070
SCIP_Real SCIPsetFloor(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6387
SCIP_RETCODE SCIPbranchruleExitsol(SCIP_BRANCHRULE *branchrule, SCIP_SET *set)
Definition: branch.c:1501
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7452
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:670
SCIP_Longint SCIPbranchruleGetNChildren(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2154
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
#define SCIP_DECL_BRANCHEXECPS(x)
Definition: type_branch.h:167
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_Longint ndomredsfound
Definition: struct_branch.h:81
internal methods for clocks and timing issues
int SCIPbranchcandGetNPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:843
SCIP_BRANCHRULEDATA * branchruledata
Definition: struct_branch.h:94
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6323
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:78
void SCIPbranchruleSetFree(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: branch.c:1872
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:426
int nintvars
Definition: struct_prob.h:63
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
SCIP_RETCODE SCIPbranchcandCreate(SCIP_BRANCHCAND **branchcand)
Definition: branch.c:134
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6065
SCIP_Longint nactiveconssadded
Definition: struct_stat.h:115
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:13256
int SCIPbranchcandGetNPrioExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:508
const char * SCIPbranchruleGetDesc(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1972
SCIP_Real SCIPbranchGetScore(SCIP_SET *set, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: branch.c:2181
#define SCIP_DECL_BRANCHFREE(x)
Definition: type_branch.h:66
SCIP_Longint nholechgs
Definition: struct_stat.h:107
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:351
#define FALSE
Definition: def.h:87
int lppos
Definition: struct_lp.h:163
SCIP_Longint SCIPbranchruleGetNDomredsFound(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2144
SCIP_Bool SCIPsetIsFeasIntegral(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6741
SCIP_Bool solved
Definition: struct_lp.h:357
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11063
SCIP_RETCODE SCIPbranchExecPseudo(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:2738
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:281
int SCIPbranchcandGetNPrioPseudoImpls(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:883
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
int SCIPtreeGetCurrentDepth(SCIP_TREE *tree)
Definition: tree.c:8392
SCIP_Longint SCIPbranchruleGetNCutoffs(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2112
internal methods for branching rules and branching candidate storage
void SCIPbranchcandClearExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:688
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5779
SCIP_Real SCIPsetRound(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6409
#define SCIP_DECL_BRANCHEXECEXT(x)
Definition: type_branch.h:146
SCIP_RETCODE SCIPbranchruleInitsol(SCIP_BRANCHRULE *branchrule, SCIP_SET *set)
Definition: branch.c:1477
#define SCIPdebugMessage
Definition: pub_message.h:87
int nimplvars
Definition: struct_prob.h:64
static SCIP_RETCODE ensureLpcandsSize(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, int num)
Definition: branch.c:56
SCIP_Longint SCIPbranchruleGetNExternCalls(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2092
internal methods for handling parameter settings
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6334
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:251
#define SCIP_DECL_BRANCHEXITSOL(x)
Definition: type_branch.h:104
#define BMSfreeMemory(ptr)
Definition: memory.h:138
static SCIP_RETCODE ensureExterncandsSize(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, int num)
Definition: branch.c:104
int SCIPbranchcandGetExternMaxPrio(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:488
SCIP_RETCODE SCIPbranchruleExecLPSol(SCIP_BRANCHRULE *branchrule, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_SEPASTORE *sepastore, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:1525
int SCIPbranchcandGetNPrioExternInts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:528
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:13081
SCIP_Real SCIPsetCeil(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6398
internal methods for LP management
SCIP_Bool SCIPsetIsFeasFracIntegral(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6752
int SCIPbranchcandGetNPrioPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:853
Definition: heur_padm.c:123
real eps
int branchpriority
Definition: struct_var.h:256
SCIP_RETCODE SCIPbranchruleExecPseudoSol(SCIP_BRANCHRULE *branchrule, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:1739
int SCIPlpGetNCols(SCIP_LP *lp)
Definition: lp.c:17508
SCIP_Longint nexterncalls
Definition: struct_branch.h:75
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6294
SCIP_RETCODE SCIPbranchExecLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:2505
int pseudocandindex
Definition: struct_var.h:247
int SCIPbranchcandGetNExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:498
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_Bool SCIPsetIsLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6240
SCIP_RETCODE SCIPbranchcandAddExternCand(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: branch.c:560
#define SCIP_DECL_BRANCHINIT(x)
Definition: type_branch.h:74
SCIP_Real lb
Definition: struct_lp.h:129
SCIP_RETCODE SCIPvarChgBranchPriority(SCIP_VAR *var, int branchpriority)
Definition: var.c:11686
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
Definition: lp.c:16929
#define SCIP_DECL_BRANCHCOPY(x)
Definition: type_branch.h:58
SCIP_RETCODE SCIPbranchcandGetExternCands(SCIP_BRANCHCAND *branchcand, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: branch.c:431
internal methods for storing and manipulating the main problem
#define SCIPerrorMessage
Definition: pub_message.h:55
SCIP_VAR ** lpcands
Definition: struct_branch.h:39
SCIP_Real maxbounddist
Definition: struct_branch.h:71
SCIP_Real SCIPbranchruleGetSetupTime(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2062
SCIP_Real SCIPbranchGetBranchingPoint(SCIP_SET *set, SCIP_TREE *tree, SCIP_VAR *var, SCIP_Real suggestion)
Definition: branch.c:2279
SCIP_Longint lpcount
Definition: struct_stat.h:181
void SCIPclockReset(SCIP_CLOCK *clck)
Definition: clock.c:200
SCIP_COL ** SCIPlpGetCols(SCIP_LP *lp)
Definition: lp.c:17498
#define SCIP_DECL_BRANCHINITSOL(x)
Definition: type_branch.h:93
SCIP_RETCODE SCIPbranchruleExit(SCIP_BRANCHRULE *branchrule, SCIP_SET *set)
Definition: branch.c:1447
int SCIPsepastoreGetNCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1091
#define SCIP_DECL_BRANCHEXECLP(x)
Definition: type_branch.h:125
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
SCIP_RETCODE SCIPbranchcandGetPseudoCands(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_PROB *prob, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: branch.c:779
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:429
void SCIPbranchruleSetInit(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: branch.c:1883
SCIP_Real * externcandsscore
Definition: struct_branch.h:43
SCIP_RETCODE SCIPbranchcandGetLPCands(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: branch.c:396
int SCIPbranchcandGetNPrioLPCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:478
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Real * externcandssol
Definition: struct_branch.h:44
SCIP_Longint SCIPbranchruleGetNConssFound(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2134
#define REALABS(x)
Definition: def.h:201
SCIP_Bool SCIPsetIsRelGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:7143
SCIP_RETCODE SCIPsetBranchrulePriority(SCIP *scip, SCIP_BRANCHRULE *branchrule, int priority)
Definition: scip_branch.c:325
static SCIP_RETCODE branchcandCalcLPCands(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: branch.c:204
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:384
SCIP_Longint SCIPbranchruleGetNLPCalls(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2082
SCIP_Bool SCIPsetIsFeasGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6686
SCIP_Real SCIPbranchruleGetTime(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2072
SCIP_RETCODE SCIPsetAddIntParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:3014
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6222
SCIP_Bool SCIPbranchcandContainsExternCand(SCIP_BRANCHCAND *branchcand, SCIP_VAR *var)
Definition: branch.c:703
internal methods for storing separated cuts
int SCIPbranchcandGetLPMaxPrio(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:468
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6642
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:136
SCIP_Longint nprobboundchgs
Definition: struct_stat.h:108
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:161
void SCIPbranchruleSetMaxdepth(SCIP_BRANCHRULE *branchrule, int maxdepth)
Definition: branch.c:2016
SCIP_Longint SCIPbranchruleGetNCutsFound(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2122
internal methods for problem variables
void SCIPbranchruleSetExecLp(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: branch.c:1929
void SCIPbranchruleSetPriority(SCIP_BRANCHRULE *branchrule, SCIP_SET *set, int priority)
Definition: branch.c:1992
SCIP_Bool SCIPsetIsIntegral(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6345
#define SCIP_Bool
Definition: def.h:84
SCIP_Longint npseudocalls
Definition: struct_branch.h:76
SCIP_Real SCIPsetSumepsilon(SCIP_SET *set)
Definition: set.c:6097
int SCIPbranchcandGetNPrioExternConts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:548
int nbinvars
Definition: struct_prob.h:62
static const char * paramname[]
Definition: lpi_msk.c:4998
int SCIPvarGetBranchPriority(SCIP_VAR *var)
Definition: var.c:18082
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:176
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1850
#define MAX(x, y)
Definition: tclique_def.h:83
void SCIPbranchruleEnableOrDisableClocks(SCIP_BRANCHRULE *branchrule, SCIP_Bool enable)
Definition: branch.c:2050
#define SCIPsetDebugMsg
Definition: set.h:1755
SCIP_CLOCK * branchclock
Definition: struct_branch.h:96
SCIP_Bool SCIPsetIsRelLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:7099
static SCIP_DECL_PARAMCHGD(paramChgdBranchrulePriority)
Definition: branch.c:1224
SCIP_Bool SCIPtreeHasCurrentNodeLP(SCIP_TREE *tree)
Definition: tree.c:8409
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition: var.c:17621
SCIP_Real SCIPbranchGetScoreMultiple(SCIP_SET *set, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: branch.c:2241
SCIP_RETCODE SCIPbranchcandUpdateVar(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_VAR *var)
Definition: branch.c:1127
void SCIPbranchruleSetExecPs(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: branch.c:1951
SCIP_RETCODE SCIPbranchruleExecExternSol(SCIP_BRANCHRULE *branchrule, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_SEPASTORE *sepastore, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:1632
SCIP_Real ub
Definition: struct_lp.h:130
#define BMSclearMemory(ptr)
Definition: memory.h:122
void SCIPbranchcandInvalidate(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:193
#define SCIP_MAXTREEDEPTH
Definition: def.h:320
SCIP_RETCODE SCIPbranchcandFree(SCIP_BRANCHCAND **branchcand)
Definition: branch.c:174
void SCIPbranchruleSetInitsol(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: branch.c:1905
int SCIPbranchruleGetMaxdepth(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2006
SCIP_Real SCIPsetFeasFrac(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6798
int SCIPparamGetInt(SCIP_PARAM *param)
Definition: paramset.c:725
#define SCIP_REAL_MIN
Definition: def.h:179
void SCIPbranchruleSetExecExt(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: branch.c:1940
void SCIPsetSortBranchrules(SCIP_SET *set)
Definition: set.c:4920
int nactiveconss
Definition: struct_stat.h:230
int lpipos
Definition: struct_lp.h:164
SCIP_Longint SCIPbranchruleGetNPseudoCalls(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:2102
internal methods for main solving loop and node processing
SCIP_Longint nchildren
Definition: struct_branch.h:82
SCIP_CLOCK * setuptime
Definition: struct_branch.h:95
void SCIPbranchruleSetExitsol(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: branch.c:1916
SCIP_RETCODE SCIPbranchruleInit(SCIP_BRANCHRULE *branchrule, SCIP_SET *set)
Definition: branch.c:1403
SCIP_RETCODE SCIPbranchruleCopyInclude(SCIP_BRANCHRULE *branchrule, SCIP_SET *set)
Definition: branch.c:1238
int SCIPbranchcandGetNPrioPseudoBins(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:863
SCIP_Longint nconssfound
Definition: struct_branch.h:79
SCIP_Longint validlpcandslp
Definition: struct_branch.h:46
static SCIP_RETCODE doBranchruleCreate(SCIP_BRANCHRULE **branchrule, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_DECL_BRANCHCOPY((*branchcopy)), SCIP_DECL_BRANCHFREE((*branchfree)), SCIP_DECL_BRANCHINIT((*branchinit)), SCIP_DECL_BRANCHEXIT((*branchexit)), SCIP_DECL_BRANCHINITSOL((*branchinitsol)), SCIP_DECL_BRANCHEXITSOL((*branchexitsol)), SCIP_DECL_BRANCHEXECLP((*branchexeclp)), SCIP_DECL_BRANCHEXECEXT((*branchexecext)), SCIP_DECL_BRANCHEXECPS((*branchexecps)), SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1258
SCIP_Longint nboundchgs
Definition: struct_stat.h:106
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17370
static void branchcandSortPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:986
#define SCIP_Real
Definition: def.h:177
internal methods for problem statistics
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1962
SCIP_VAR ** vars
Definition: struct_prob.h:55
datastructures for branching rules and branching candidate storage
SCIP_RETCODE SCIPbranchruleFree(SCIP_BRANCHRULE **branchrule, SCIP_SET *set)
Definition: branch.c:1376
SCIP_VAR ** pseudocands
Definition: struct_branch.h:45
SCIP_Bool SCIPsetIsFeasPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6719
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define SCIP_INVALID
Definition: def.h:197
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:120
SCIP_Bool initialized
Definition: struct_branch.h:99
void SCIPbranchruleSetMaxbounddist(SCIP_BRANCHRULE *branchrule, SCIP_Real maxbounddist)
Definition: branch.c:2038
#define SCIP_Longint
Definition: def.h:162
void SCIPbranchruleSetExit(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: branch.c:1894
static void branchcandRemovePseudoCand(SCIP_BRANCHCAND *branchcand, SCIP_VAR *var)
Definition: branch.c:1025
static void branchcandInsertPseudoCand(SCIP_BRANCHCAND *branchcand, SCIP_VAR *var, int insertpos)
Definition: branch.c:896
SCIP_VAR * var
Definition: struct_lp.h:151
SCIP_RETCODE SCIPbranchcandRemoveVar(SCIP_BRANCHCAND *branchcand, SCIP_VAR *var)
Definition: branch.c:1110
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
SCIP_Real SCIPvarGetMultaggrUbLocal(SCIP_VAR *var, SCIP_SET *set)
Definition: var.c:8496
SCIP_Real SCIPsetEpsilon(SCIP_SET *set)
Definition: set.c:6087
int SCIPbranchcandGetNPrioPseudoInts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:873
enum SCIP_Vartype SCIP_VARTYPE
Definition: type_var.h:60
int nchildren
Definition: struct_tree.h:214
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_Real SCIPtreeGetLowerbound(SCIP_TREE *tree, SCIP_SET *set)
Definition: tree.c:7245
common defines and data types used in all packages of SCIP
SCIP_Longint ncutoffs
Definition: struct_branch.h:77
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:430
SCIP_RETCODE SCIPsetAddRealParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: set.c:3062
SCIP_Longint nlpcalls
Definition: struct_branch.h:74
#define SCIP_ALLOC(x)
Definition: def.h:395
SCIP_RETCODE SCIPbranchExecExtern(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:2607
#define SCIPABORT()
Definition: def.h:356
SCIP_Longint nprobholechgs
Definition: struct_stat.h:109
SCIP_Real SCIPvarGetMultaggrLbLocal(SCIP_VAR *var, SCIP_SET *set)
Definition: var.c:8430
SCIP_Real * lpcandsfrac
Definition: struct_branch.h:41
#define SCIP_DECL_BRANCHEXIT(x)
Definition: type_branch.h:82
SCIP_VAR ** externcands
Definition: struct_branch.h:42
SCIP callable library.
SCIP_Bool SCIPsetIsFeasNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6730
SCIP_RETCODE SCIPbranchcandUpdateVarBranchPriority(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_VAR *var, int branchpriority)
Definition: branch.c:1167
SCIP_NODE * focusnode
Definition: struct_tree.h:182
int SCIPbranchcandGetNPrioExternImpls(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:538
int SCIPbranchruleGetPriority(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1982
static SCIP_RETCODE ensurePseudocandsSize(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, int num)
Definition: branch.c:81
memory allocation routines