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