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