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