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