Scippy

SCIP

Solving Constraint Integer Programs

branch_pscost.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch_pscost.c
17  * @brief pseudo costs branching rule
18  * @author Tobias Achterberg
19  * @author Stefan Vigerske
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/branch_pscost.h"
28 #include "scip/pub_misc.h"
29 
30 #define BRANCHRULE_NAME "pscost"
31 #define BRANCHRULE_DESC "branching on pseudo cost values"
32 #define BRANCHRULE_PRIORITY 2000
33 #define BRANCHRULE_MAXDEPTH -1
34 #define BRANCHRULE_MAXBOUNDDIST 1.0
35 
36 #define BRANCHRULE_STRATEGIES "cdsu" /**< possible pseudo cost multiplication strategies for branching on external candidates */
37 #define BRANCHRULE_STRATEGY_DEFAULT 'u' /**< default pseudo cost multiplication strategy */
38 #define BRANCHRULE_SCOREMINWEIGHT_DEFAULT 0.8 /**< default weight for minimum of scores of a branching candidate */
39 #define BRANCHRULE_SCOREMAXWEIGHT_DEFAULT 1.3 /**< default weight for maximum of scores of a branching candidate */
40 #define BRANCHRULE_SCORESUMWEIGHT_DEFAULT 0.1 /**< default weight for sum of scores of a branching candidate */
41 #define BRANCHRULE_NCHILDREN_DEFAULT 2 /**< default number of children in n-ary branching */
42 #define BRANCHRULE_NARYMAXDEPTH_DEFAULT -1 /**< default maximal depth where to do n-ary branching */
43 #define BRANCHRULE_NARYMINWIDTH_DEFAULT 0.001 /**< default minimal domain width in children when doing n-ary branching */
44 #define BRANCHRULE_NARYWIDTHFAC_DEFAULT 2.0 /**< default factor of domain width in n-ary branching */
45 #define BRANCHRULE_RANDSEED_DEFAULT 47 /**< initial random seed */
46 
47 
48 #define WEIGHTEDSCORING(data, min, max, sum) \
49  ((data)->scoreminweight * (min) + (data)->scoremaxweight * (max) + (data)->scoresumweight * (sum))
50 
51 /** branching rule data */
52 struct SCIP_BranchruleData
53 {
54  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
55 
56  char strategy; /**< strategy for computing score of external candidates */
57  SCIP_Real scoreminweight; /**< weight for minimum of scores of a branching candidate */
58  SCIP_Real scoremaxweight; /**< weight for maximum of scores of a branching candidate */
59  SCIP_Real scoresumweight; /**< weight for sum of scores of a branching candidate */
60 
61  char updatestrategy; /**< strategy used to update pseudo costs of continuous variables */
62 
63  int nchildren; /**< targeted number of children in n-ary branching */
64  int narymaxdepth; /**< maximal depth where to do n-ary branching, -1 to turn off */
65  SCIP_Real naryminwidth; /**< minimal domain width in children when doing n-ary branching, relative to global bounds */
66  SCIP_Real narywidthfactor; /**< factor of domain width in n-ary branching */
67 };
68 
69 /*
70  * Local methods
71  */
72 
73 /** checks if a given branching candidate is better than a previous one and updates the best branching candidate accordingly */
74 static
76  SCIP* scip, /**< SCIP data structure */
77  SCIP_BRANCHRULEDATA* branchruledata, /**< branching rule data */
78  SCIP_VAR** bestvar, /**< best branching candidate */
79  SCIP_Real* bestbrpoint, /**< branching point for best branching candidate */
80  SCIP_Real* bestscore, /**< score of best branching candidate */
81  SCIP_Real* bestrndscore, /**< random score of the best branching candidate */
82  SCIP_VAR* cand, /**< branching candidate to consider */
83  SCIP_Real candscoremin, /**< minimal score of branching candidate */
84  SCIP_Real candscoremax, /**< maximal score of branching candidate */
85  SCIP_Real candscoresum, /**< sum of scores of branching candidate */
86  SCIP_Real candrndscore, /**< random score of branching candidate */
87  SCIP_Real candsol /**< proposed branching point of branching candidate */
88 )
89 {
90  SCIP_Real candbrpoint;
91  SCIP_Real branchscore;
92 
93  SCIP_Real deltaminus;
94  SCIP_Real deltaplus;
95 
96  SCIP_Real pscostdown;
97  SCIP_Real pscostup;
98 
99  char strategy;
100 
101  assert(scip != NULL);
102  assert(branchruledata != NULL);
103  assert(bestvar != NULL);
104  assert(bestbrpoint != NULL);
105  assert(bestscore != NULL);
106  assert(cand != NULL);
107 
108  /* a branching variable candidate should either be an active problem variable or a multi-aggregated variable */
109  assert(SCIPvarIsActive(SCIPvarGetProbvar(cand)) ||
111 
113  {
114  /* for a multi-aggregated variable, we call updateBestCandidate function recursively with all variables in the multi-aggregation */
115  SCIP_VAR** multvars;
116  int nmultvars;
117  int i;
118  SCIP_Bool success;
119  SCIP_Real multvarlb;
120  SCIP_Real multvarub;
121 
122  cand = SCIPvarGetProbvar(cand);
123  multvars = SCIPvarGetMultaggrVars(cand);
124  nmultvars = SCIPvarGetMultaggrNVars(cand);
125 
126  /* if we have a candidate branching point, then first register only aggregation variables
127  * for which we can compute a corresponding branching point too (see also comments below)
128  * if this fails, then register all (unfixed) aggregation variables, thereby forgetting about candsol
129  */
130  success = FALSE;
131  if( candsol != SCIP_INVALID ) /*lint !e777*/
132  {
133  SCIP_Real* multscalars;
134  SCIP_Real minact;
135  SCIP_Real maxact;
136  SCIP_Real aggrvarsol;
137  SCIP_Real aggrvarsol1;
138  SCIP_Real aggrvarsol2;
139 
140  multscalars = SCIPvarGetMultaggrScalars(cand);
141 
142  /* for computing the branching point, we need the current bounds of the multi-aggregated variable */
143  minact = SCIPcomputeVarLbLocal(scip, cand);
144  maxact = SCIPcomputeVarUbLocal(scip, cand);
145 
146  for( i = 0; i < nmultvars; ++i )
147  {
148  /* skip fixed variables */
149  multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]);
150  multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]);
151  if( SCIPisEQ(scip, multvarlb, multvarub) )
152  continue;
153 
154  assert(multscalars != NULL);
155  assert(multscalars[i] != 0.0);
156 
157  /* we cannot ensure that both the upper bound in the left node and the lower bound in the right node
158  * will be candsol by a clever choice for the branching point of multvars[i],
159  * but we can try to ensure that at least one of them will be at candsol
160  */
161  if( multscalars[i] > 0.0 )
162  {
163  /* cand >= candsol
164  * if multvars[i] >= (candsol - (maxact - multscalars[i] * ub(multvars[i]))) / multscalars[i]
165  * = (candsol - maxact) / multscalars[i] + ub(multvars[i])
166  */
167  aggrvarsol1 = (candsol - maxact) / multscalars[i] + multvarub;
168 
169  /* cand <= candsol
170  * if multvars[i] <= (candsol - (minact - multscalar[i] * lb(multvars[i]))) / multscalars[i]
171  * = (candsol - minact) / multscalars[i] + lb(multvars[i])
172  */
173  aggrvarsol2 = (candsol - minact) / multscalars[i] + multvarlb;
174  }
175  else
176  {
177  /* cand >= candsol
178  * if multvars[i] <= (candsol - (maxact - multscalars[i] * lb(multvars[i]))) / multscalars[i]
179  * = (candsol - maxact) / multscalars[i] + lb(multvars[i])
180  */
181  aggrvarsol2 = (candsol - maxact) / multscalars[i] + multvarlb;
182 
183  /* cand <= candsol
184  * if multvars[i] >= (candsol - (minact - multscalar[i] * ub(multvars[i]))) / multscalars[i]
185  * = (candsol - minact) / multscalars[i] + ub(multvars[i])
186  */
187  aggrvarsol1 = (candsol - minact) / multscalars[i] + multvarub;
188  }
189 
190  /* by the above choice, aggrvarsol1 <= ub(multvars[i]) and aggrvarsol2 >= lb(multvars[i])
191  * if aggrvarsol1 <= lb(multvars[i]) or aggrvarsol2 >= ub(multvars[i]), then choose the other one
192  * if both are out of bounds, then give up
193  * if both are inside bounds, then choose the one closer to 0.0 (someone has better idea???)
194  */
195  if( SCIPisFeasLE(scip, aggrvarsol1, multvarlb) )
196  {
197  if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) )
198  continue;
199  else
200  aggrvarsol = aggrvarsol2;
201  }
202  else
203  {
204  if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) )
205  aggrvarsol = aggrvarsol1;
206  else
207  aggrvarsol = REALABS(aggrvarsol1) < REALABS(aggrvarsol2) ? aggrvarsol1 : aggrvarsol2;
208  }
209  success = TRUE;
210 
211  SCIP_CALL( updateBestCandidate(scip, branchruledata, bestvar, bestbrpoint, bestscore, bestrndscore,
212  multvars[i], candscoremin, candscoremax, candscoresum, candrndscore, aggrvarsol) );
213  }
214  }
215 
216  if( !success )
217  for( i = 0; i < nmultvars; ++i )
218  {
219  /* skip fixed variables */
220  multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]);
221  multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]);
222  if( SCIPisEQ(scip, multvarlb, multvarub) )
223  continue;
224 
225  SCIP_CALL( updateBestCandidate(scip, branchruledata, bestvar, bestbrpoint, bestscore, bestrndscore,
226  multvars[i], candscoremin, candscoremax, candscoresum, candrndscore, SCIP_INVALID) );
227  }
228 
229  assert(*bestvar != NULL); /* if all variables were fixed, something is strange */
230 
231  return SCIP_OKAY;
232  }
233 
234  /* select branching point for this variable */
235  candbrpoint = SCIPgetBranchingPoint(scip, cand, candsol);
236  assert(candbrpoint >= SCIPvarGetLbLocal(cand));
237  assert(candbrpoint <= SCIPvarGetUbLocal(cand));
238 
239  /* we cannot branch on a huge value for a discrete variable, because we simply cannot enumerate such huge integer values in floating point
240  * arithmetics
241  */
242  if( SCIPvarGetType(cand) != SCIP_VARTYPE_CONTINUOUS && (SCIPisHugeValue(scip, candbrpoint) || SCIPisHugeValue(scip, -candbrpoint)) )
243  return SCIP_OKAY;
244 
245  assert(SCIPvarGetType(cand) == SCIP_VARTYPE_CONTINUOUS || !SCIPisIntegral(scip, candbrpoint));
246 
248  strategy = (branchruledata->strategy == 'u' ? branchruledata->updatestrategy : branchruledata->strategy);
249  else
250  strategy = (branchruledata->strategy == 'u' ? 'l' : branchruledata->strategy);
251 
252  switch( strategy )
253  {
254  case 'l':
255  if( SCIPisInfinity(scip, SCIPgetSolVal(scip, NULL, cand)) || SCIPgetSolVal(scip, NULL, cand) <= SCIPadjustedVarUb(scip, cand, candbrpoint) )
256  deltaminus = 0.0;
257  else
258  deltaminus = SCIPgetSolVal(scip, NULL, cand) - SCIPadjustedVarUb(scip, cand, candbrpoint);
259  if( SCIPisInfinity(scip, -SCIPgetSolVal(scip, NULL, cand)) || SCIPgetSolVal(scip, NULL, cand) >= SCIPadjustedVarLb(scip, cand, candbrpoint) )
260  deltaplus = 0.0;
261  else
262  deltaplus = SCIPadjustedVarLb(scip, cand, candbrpoint) - SCIPgetSolVal(scip, NULL, cand);
263  break;
264 
265  case 'd':
266  if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(cand)) )
267  deltaminus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
268  else
269  deltaminus = SCIPadjustedVarUb(scip, cand, candbrpoint) - SCIPvarGetLbLocal(cand);
270 
271  if( SCIPisInfinity(scip, SCIPvarGetUbLocal(cand)) )
272  deltaplus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
273  else
274  deltaplus = SCIPvarGetUbLocal(cand) - SCIPadjustedVarLb(scip, cand, candbrpoint);
275  break;
276 
277  case 's':
278  if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(cand)) )
279  deltaplus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
280  else
281  deltaplus = SCIPadjustedVarUb(scip, cand, candbrpoint) - SCIPvarGetLbLocal(cand);
282 
283  if( SCIPisInfinity(scip, SCIPvarGetUbLocal(cand)) )
284  deltaminus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
285  else
286  deltaminus = SCIPvarGetUbLocal(cand) - SCIPadjustedVarLb(scip, cand, candbrpoint);
287  break;
288 
289  case 'v':
290  deltaplus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
291  deltaminus = deltaplus;
292  break;
293 
294  default :
295  SCIPerrorMessage("branching strategy %c unknown\n", strategy);
296  SCIPABORT();
297  return SCIP_INVALIDDATA; /*lint !e527*/
298  }
299 
300  if( SCIPisInfinity(scip, deltaminus) || SCIPisInfinity(scip, deltaplus) )
301  {
302  branchscore = SCIPinfinity(scip);
303  }
304  else
305  {
306  pscostdown = SCIPgetVarPseudocostVal(scip, cand, -deltaminus);
307  pscostup = SCIPgetVarPseudocostVal(scip, cand, deltaplus);
308  branchscore = SCIPgetBranchScore(scip, cand, pscostdown, pscostup);
309  assert(!SCIPisNegative(scip, branchscore));
310  }
311  SCIPdebugMsg(scip, "branching score variable <%s>[%g,%g] = %g; wscore = %g; type=%d bestbrscore=%g\n",
312  SCIPvarGetName(cand), SCIPvarGetLbLocal(cand), SCIPvarGetUbLocal(cand), branchscore, WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum),
313  SCIPvarGetType(cand), *bestscore);
314 
315  if( SCIPisInfinity(scip, branchscore) )
316  branchscore = 0.9*SCIPinfinity(scip);
317 
318  if( SCIPisSumGT(scip, branchscore, *bestscore) )
319  {
320  (*bestscore) = branchscore;
321  (*bestrndscore) = candrndscore;
322  (*bestvar) = cand;
323  (*bestbrpoint) = candbrpoint;
324  return SCIP_OKAY;
325 
326  }
327 
328  /* if score of candidate is worse than bestscore, stay with best candidate */
329  if( !SCIPisSumEQ(scip, branchscore, *bestscore) )
330  return SCIP_OKAY;
331 
332  if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(*bestvar)) && SCIPisInfinity(scip, SCIPvarGetUbLocal(*bestvar)) )
333  {
334  /* best candidate is unbounded -> we prefer to branch on it */
335  if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(cand)) && SCIPisInfinity(scip, SCIPvarGetUbLocal(cand)) &&
336  SCIPrandomGetReal(branchruledata->randnumgen, 0.0, 1.0) <= 0.5
337  )
338  {
339  /* but if the new candidate is also unbounded (thus as good as best candidate),
340  * then switch to the candidate with 50% probability to reduce performance variability
341  */
342  (*bestscore) = branchscore;
343  (*bestrndscore) = candrndscore;
344  (*bestvar) = cand;
345  (*bestbrpoint) = candbrpoint;
346  }
347 
348  return SCIP_OKAY;
349  }
350 
351  /* best candidate has a finite lower or upper bound -> consider taking the other candidate */
352 
353  if( (SCIPisInfinity(scip, -SCIPvarGetLbLocal(cand)) || SCIPisInfinity(scip, SCIPvarGetUbLocal(cand))) &&
354  (SCIPisInfinity(scip, -SCIPvarGetLbLocal(*bestvar)) || SCIPisInfinity(scip, SCIPvarGetUbLocal(*bestvar))) )
355  {
356  /* both candidates are unbounded, but one side may be finite (for bestcand we know there is one)
357  * take the candidate with the larger bound on the bounded side (hope that this avoids branching on always the same variable)
358  * this will also prefer unbounded variables over bounded ones
359  */
360  if( SCIPvarGetUbLocal(cand) > SCIPvarGetUbLocal(*bestvar) || SCIPvarGetLbLocal(cand) < SCIPvarGetLbLocal(*bestvar) )
361  {
362  /* cand is better than bestvar */
363  (*bestscore) = branchscore;
364  (*bestrndscore) = candrndscore;
365  (*bestvar) = cand;
366  (*bestbrpoint) = candbrpoint;
367  return SCIP_OKAY;
368  }
369 
370  if( SCIPvarGetUbLocal(*bestvar) > SCIPvarGetUbLocal(cand) || SCIPvarGetLbLocal(*bestvar) < SCIPvarGetLbLocal(cand) )
371  {
372  /* bestvar is better than cand */
373  return SCIP_OKAY;
374  }
375 
376  /* both are equally good */
377  }
378 
379  if( SCIPvarGetType(*bestvar) == SCIPvarGetType(cand) )
380  {
381  /* if both have the same type, take the one with larger relative diameter */
383  {
384  /* cand has larger diameter than bestvar*/
385  (*bestscore) = branchscore;
386  (*bestrndscore) = candrndscore;
387  (*bestvar) = cand;
388  (*bestbrpoint) = candbrpoint;
389  return SCIP_OKAY;
390  }
391 
393  {
394  /* bestvar has larger diameter than cand */
395  return SCIP_OKAY;
396  }
397  }
398 
399  /* take the one with better type ("more discrete") */
400  if( SCIPvarGetType(*bestvar) > SCIPvarGetType(cand) )
401  {
402  /* cand is more discrete than bestvar */
403  (*bestscore) = branchscore;
404  (*bestrndscore) = candrndscore;
405  (*bestvar) = cand;
406  (*bestbrpoint) = candbrpoint;
407  return SCIP_OKAY;
408  }
409  if( SCIPvarGetType(*bestvar) < SCIPvarGetType(cand) )
410  {
411  /* bestvar is more discrete than cand */
412  return SCIP_OKAY;
413  }
414 
415  /* cand seems to be as good as the currently best one (bestvar); use the random score as a final tie-breaker */
416  if( candrndscore >= (*bestrndscore) )
417  {
418  (*bestscore) = branchscore;
419  (*bestrndscore) = candrndscore;
420  (*bestvar) = cand;
421  (*bestbrpoint) = candbrpoint;
422  }
423 
424  return SCIP_OKAY;
425 }
426 
427 /** selects the branching variable from given candidate array */
428 static
430  SCIP* scip, /**< SCIP data structure */
431  SCIP_BRANCHRULE* branchrule, /**< branching rule */
432  SCIP_VAR** cands, /**< array of branching candidates */
433  SCIP_Real* candssol, /**< array of candidate solution values */
434  SCIP_Real* candsscore, /**< array of candidate scores */
435  int ncands, /**< the number of candidates */
436  SCIP_VAR** brvar, /**< pointer to store the selected branching candidate or NULL if none */
437  SCIP_Real* brpoint /**< pointer to store branching point of selected branching variable */
438  )
439 { /*lint --e{850}*/
440  SCIP_BRANCHRULEDATA* branchruledata;
441 
442  SCIP_VAR* cand;
443  SCIP_Real candsol;
444 
445  SCIP_Real bestbranchscore;
446  SCIP_Real bestrndscore;
447 
448  SCIP_Real scoremin;
449  SCIP_Real scoresum;
450  SCIP_Real scoremax;
451 
452  SCIP_VAR** candssorted;
453  int* candsorigidx;
454 
455  int i;
456  int j;
457 
458  assert(brvar != NULL);
459  assert(brpoint != NULL);
460 
461  (*brvar) = NULL;
462  (*brpoint) = SCIP_INVALID;
463 
464  if( ncands == 0 )
465  return SCIP_OKAY;
466 
467  branchruledata = SCIPbranchruleGetData(branchrule);
468  assert(branchruledata != NULL);
469 
470  /* sort branching candidates (in a copy), such that same variables are on consecutive positions */
471  SCIP_CALL( SCIPduplicateBufferArray(scip, &candssorted, cands, ncands) );
472  SCIP_CALL( SCIPallocBufferArray(scip, &candsorigidx, ncands) );
473  for( i = 0; i < ncands; ++i )
474  candsorigidx[i] = i;
475 
476  SCIPsortPtrInt((void**)candssorted, candsorigidx, SCIPvarComp, ncands);
477 
478  bestbranchscore = -1.0;
479  bestrndscore = -1.0;
480 
481  for( i = 0; i < ncands; ++i )
482  {
483  cand = candssorted[i];
484 
485  /* there should be no fixed branching candidates */
486  assert(!SCIPisEQ(scip, SCIPvarGetLbLocal(cand), SCIPvarGetUbLocal(cand)));
487 
488  /* compute min, sum, and max of all registered scores for this variables
489  * set candsol to a valid value, if someone registered one */
490  scoremin = candsscore[candsorigidx[i]];
491  scoresum = scoremin;
492  scoremax = scoremin;
493  candsol = candssol[candsorigidx[i]];
494  for( j = i+1 ; j < ncands && SCIPvarCompare(candssorted[j], cand) == 0; ++j )
495  {
496  assert(candsscore[candsorigidx[j]] >= 0.0);
497  scoresum += candsscore[candsorigidx[j]];
498  if( candsscore[candsorigidx[j]] < scoremin )
499  scoremin = candsscore[candsorigidx[j]];
500  else if( candsscore[candsorigidx[j]] > scoremax )
501  scoremax = candsscore[candsorigidx[j]];
502 
503  /* @todo if there are two valid externcandssol available for the same variable, should we take the one closer to the middle of the domain? */
504  if( SCIPisInfinity(scip, REALABS(candsol)) )
505  candsol = candssol[candsorigidx[j]];
506  }
507  /* set i to last occurrence of cand in candssorted (instead of first one as before), so in next round we look at another variable */
508  i = j-1;
509  assert(candssorted[i] == cand);
510 
511  /* check if new candidate is better than previous candidate (if any) */
512  SCIP_CALL( updateBestCandidate(scip, branchruledata, brvar, brpoint, &bestbranchscore, &bestrndscore, cand,
513  scoremin, scoremax, scoresum, SCIPrandomGetReal(branchruledata->randnumgen, 0.0, 1.0), candsol) );
514  }
515 
516  /* there were candidates, but no variable was selected; this can only happen if the branching points are huge values
517  * for all variables on which we cannot branch
518  * @todo delay the node?
519  */
520  if( (*brvar) == NULL )
521  {
522  SCIPerrorMessage("no branching could be created: all external candidates have huge bounds\n");
523  SCIPABORT();
524  return SCIP_BRANCHERROR; /*lint !e527*/
525  }
526 
527  /* free buffer arrays */
528  SCIPfreeBufferArray(scip, &candssorted);
529  SCIPfreeBufferArray(scip, &candsorigidx);
530 
531  return SCIP_OKAY;
532 }
533 
534 /*
535  * Callback methods
536  */
537 
538 /** copy method for branchrule plugins (called when SCIP copies plugins) */
539 static
540 SCIP_DECL_BRANCHCOPY(branchCopyPscost)
541 { /*lint --e{715}*/
542  assert(scip != NULL);
543  assert(branchrule != NULL);
544  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
545 
546  /* call inclusion method of branchrule */
548 
549  return SCIP_OKAY;
550 }
551 
552 /** destructor of branching rule to free user data (called when SCIP is exiting) */
553 static
554 SCIP_DECL_BRANCHFREE(branchFreePscost)
555 { /*lint --e{715}*/
556  SCIP_BRANCHRULEDATA* branchruledata;
557 
558  /* get branching rule data */
559  branchruledata = SCIPbranchruleGetData(branchrule);
560  assert(branchruledata != NULL);
561 
562  /* free branching rule data */
563  SCIPfreeBlockMemory(scip, &branchruledata);
564  SCIPbranchruleSetData(branchrule, NULL);
565 
566  return SCIP_OKAY;
567 }
568 
569 /** initialization method of branching rule (called after problem was transformed) */
570 static
571 SCIP_DECL_BRANCHINIT(branchInitPscost)
572 { /*lint --e{715}*/
573  SCIP_BRANCHRULEDATA* branchruledata;
574 
575  /* initialize branching rule data */
576  branchruledata = SCIPbranchruleGetData(branchrule);
577  assert(branchruledata != NULL);
578 
579  /* create a random number generator */
580  SCIP_CALL( SCIPrandomCreate(&branchruledata->randnumgen, SCIPblkmem(scip),
582 
583  return SCIP_OKAY;
584 }
585 
586 /** deinitialization method of branching rule */
587 static
588 SCIP_DECL_BRANCHEXIT(branchExitPscost)
589 { /*lint --e{715}*/
590  SCIP_BRANCHRULEDATA* branchruledata;
591 
592  /* get branching rule data */
593  branchruledata = SCIPbranchruleGetData(branchrule);
594  assert(branchruledata != NULL);
595 
596  /* free random number generator */
597  SCIPrandomFree(&branchruledata->randnumgen);
598 
599  return SCIP_OKAY;
600 }
601 
602 /** branching execution method for fractional LP solutions */
603 static
604 SCIP_DECL_BRANCHEXECLP(branchExeclpPscost)
605 { /*lint --e{715}*/
606  SCIP_VAR** lpcands;
607  SCIP_Real* lpcandssol;
608  SCIP_Real bestscore;
609  SCIP_Real bestrootdiff;
610  int nlpcands;
611  int bestcand;
612  int c;
613 
614  assert(branchrule != NULL);
615  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
616  assert(scip != NULL);
617  assert(result != NULL);
618 
619  SCIPdebugMsg(scip, "Execlp method of pscost branching\n");
620 
621  /* get branching candidates */
622  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, NULL, &nlpcands, NULL) );
623  assert(nlpcands > 0);
624 
625  bestcand = -1;
626  bestscore = -SCIPinfinity(scip);
627  bestrootdiff = 0.0;
628  for( c = 0; c < nlpcands; ++c )
629  {
630  SCIP_Real score;
631  SCIP_Real rootsolval;
632  SCIP_Real rootdiff;
633 
634  score = SCIPgetVarPseudocostScore(scip, lpcands[c], lpcandssol[c]);
635  rootsolval = SCIPvarGetRootSol(lpcands[c]);
636  rootdiff = REALABS(lpcandssol[c] - rootsolval);
637  if( SCIPisSumGT(scip, score, bestscore) || (SCIPisSumEQ(scip, score, bestscore) && rootdiff > bestrootdiff) )
638  {
639  bestcand = c;
640  bestscore = score;
641  bestrootdiff = rootdiff;
642  }
643  }
644  assert(0 <= bestcand && bestcand < nlpcands);
645  assert(!SCIPisFeasIntegral(scip, lpcandssol[bestcand]));
646  assert(!SCIPisFeasIntegral(scip, SCIPvarGetSol(lpcands[bestcand], TRUE)));
647 
648  /* perform the branching */
649  SCIPdebugMsg(scip, " -> %d cands, selected cand %d: variable <%s> (solval=%g, score=%g)\n",
650  nlpcands, bestcand, SCIPvarGetName(lpcands[bestcand]), lpcandssol[bestcand], bestscore);
651 
652  /* perform the branching */
653  SCIP_CALL( SCIPbranchVar(scip, lpcands[bestcand], NULL, NULL, NULL) );
654  *result = SCIP_BRANCHED;
655 
656  return SCIP_OKAY;
657 }
658 
659 
660 /** branching execution method for external candidates */
661 static
662 SCIP_DECL_BRANCHEXECEXT(branchExecextPscost)
663 { /*lint --e{715}*/
664  SCIP_BRANCHRULEDATA* branchruledata;
665  SCIP_VAR** externcands;
666  SCIP_Real* externcandssol;
667  SCIP_Real* externcandsscore;
668  int nprioexterncands;
669  SCIP_VAR* brvar;
670  SCIP_Real brpoint;
671  int nchildren;
672 
673  assert(branchrule != NULL);
674  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
675  assert(scip != NULL);
676  assert(result != NULL);
677 
678  branchruledata = SCIPbranchruleGetData(branchrule);
679  assert(branchruledata != NULL);
680 
681  SCIPdebugMsg(scip, "Execext method of pscost branching\n");
682 
683  /* get branching candidates */
684  SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, &externcandsscore, NULL, &nprioexterncands, NULL, NULL, NULL) );
685  assert(nprioexterncands > 0);
686 
687  /* get current update strategy for pseudo costs, if our multiplier rule is 'u' */
688  if( branchruledata->strategy == 'u' )
689  {
690  SCIP_CALL( SCIPgetCharParam(scip, "branching/lpgainnormalize", &branchruledata->updatestrategy) );
691  }
692 
693  /* select branching variable */
694  SCIP_CALL( selectBranchVar(scip, branchrule, externcands, externcandssol, externcandsscore, nprioexterncands, &brvar, &brpoint) );
695 
696  if( brvar == NULL )
697  {
698  SCIPerrorMessage("branchExecextPscost failed to select a branching variable from %d candidates\n", nprioexterncands);
699  *result = SCIP_DIDNOTRUN;
700  return SCIP_OKAY;
701  }
702 
703  assert(SCIPvarIsActive(SCIPvarGetProbvar(brvar)));
704 
705  SCIPdebugMsg(scip, "branching on variable <%s>: new intervals: [%g, %g] and [%g, %g]\n",
706  SCIPvarGetName(brvar), SCIPvarGetLbLocal(brvar), SCIPadjustedVarUb(scip, brvar, brpoint), SCIPadjustedVarLb(scip, brvar, brpoint), SCIPvarGetUbLocal(brvar));
707 
708  if( branchruledata->nchildren > 2 && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) <= branchruledata->narymaxdepth )
709  {
710  /* do n-ary branching */
711  SCIP_Real minwidth;
712 
713  minwidth = 0.0;
715  minwidth = branchruledata->naryminwidth * (SCIPvarGetUbGlobal(brvar) - SCIPvarGetLbGlobal(brvar));
716 
717  SCIP_CALL( SCIPbranchVarValNary(scip, brvar, brpoint, branchruledata->nchildren, minwidth, branchruledata->narywidthfactor, &nchildren) );
718  }
719  else
720  {
721  /* do binary branching */
722  SCIP_CALL( SCIPbranchVarValNary(scip, brvar, brpoint, 2, 0.0, 1.0, &nchildren) );
723  }
724 
725  if( nchildren > 1 )
726  {
727  *result = SCIP_BRANCHED;
728  }
729  else
730  {
731  /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
732  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(brvar), SCIPvarGetUbLocal(brvar)));
733  *result = SCIP_REDUCEDDOM;
734  }
735 
736  return SCIP_OKAY;
737 }
738 
739 
740 /*
741  * branching specific interface methods
742  */
743 
744 /** creates the pseudo cost branching rule and includes it in SCIP */
746  SCIP* scip /**< SCIP data structure */
747  )
748 {
749  SCIP_BRANCHRULEDATA* branchruledata;
750  SCIP_BRANCHRULE* branchrule;
751 
752  /* create pscost branching rule data */
753  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
754 
755  /* include allfullstrong branching rule */
757  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
758 
759  assert(branchrule != NULL);
760 
761  /* set non-fundamental callbacks via specific setter functions*/
762  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyPscost) );
763  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreePscost) );
764  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitPscost) );
765  SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitPscost) );
766  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpPscost) );
767  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextPscost) );
768 
769  SCIP_CALL( SCIPaddCharParam(scip, "branching/" BRANCHRULE_NAME "/strategy",
770  "strategy for utilizing pseudo-costs of external branching candidates (multiply as in pseudo costs 'u'pdate rule, or by 'd'omain reduction, or by domain reduction of 's'ibling, or by 'v'ariable score)",
771  &branchruledata->strategy, FALSE, BRANCHRULE_STRATEGY_DEFAULT, BRANCHRULE_STRATEGIES, NULL, NULL) );
772 
773  SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/minscoreweight",
774  "weight for minimum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
775  &branchruledata->scoreminweight, TRUE, BRANCHRULE_SCOREMINWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
776 
777  SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/maxscoreweight",
778  "weight for maximum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
779  &branchruledata->scoremaxweight, TRUE, BRANCHRULE_SCOREMAXWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
780 
781  SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/sumscoreweight",
782  "weight for sum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
783  &branchruledata->scoresumweight, TRUE, BRANCHRULE_SCORESUMWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
784 
785  SCIP_CALL( SCIPaddIntParam(scip, "branching/" BRANCHRULE_NAME "/nchildren",
786  "number of children to create in n-ary branching",
787  &branchruledata->nchildren, FALSE, BRANCHRULE_NCHILDREN_DEFAULT, 2, INT_MAX, NULL, NULL) );
788 
789  SCIP_CALL( SCIPaddIntParam(scip, "branching/" BRANCHRULE_NAME "/narymaxdepth",
790  "maximal depth where to do n-ary branching, -1 to turn off",
791  &branchruledata->narymaxdepth, FALSE, BRANCHRULE_NARYMAXDEPTH_DEFAULT, -1, INT_MAX, NULL, NULL) );
792 
793  SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/naryminwidth",
794  "minimal domain width in children when doing n-ary branching, relative to global bounds",
795  &branchruledata->naryminwidth, FALSE, BRANCHRULE_NARYMINWIDTH_DEFAULT, 0.0, 1.0, NULL, NULL) );
796 
797  SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/narywidthfactor",
798  "factor of domain width in n-ary branching when creating nodes with increasing distance from branching value",
799  &branchruledata->narywidthfactor, FALSE, BRANCHRULE_NARYWIDTHFAC_DEFAULT, 1.0, SCIP_REAL_MAX, NULL, NULL) );
800 
801  return SCIP_OKAY;
802 }
803 
804 /** selects a branching variable, due to pseudo cost, from the given candidate array and returns this variable together
805  * with a branching point */
807  SCIP* scip, /**< SCIP data structure */
808  SCIP_VAR** branchcands, /**< branching candidates */
809  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
810  SCIP_Real* branchcandsscore, /**< array of candidate scores */
811  int nbranchcands, /**< number of branching candidates */
812  SCIP_VAR** var, /**< pointer to store the variable to branch on, or NULL if none */
813  SCIP_Real* brpoint /**< pointer to store the branching point for the branching variable, will be fractional for a discrete variable */
814  )
815 {
816  SCIP_BRANCHRULE* branchrule;
817 
818  assert(scip != NULL);
819 
820  /* find branching rule */
821  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
822  assert(branchrule != NULL);
823 
824  /* select branching variable */
825  SCIP_CALL( selectBranchVar(scip, branchrule, branchcands, branchcandssol, branchcandsscore, nbranchcands, var, brpoint) );
826 
827  return SCIP_OKAY;
828 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36128
void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define BRANCHRULE_NAME
Definition: branch_pscost.c:30
SCIP_RETCODE SCIPrandomCreate(SCIP_RANDNUMGEN **randnumgen, BMS_BLKMEM *blkmem, unsigned int initialseed)
Definition: misc.c:8693
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip.c:4445
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1774
static SCIP_RETCODE updateBestCandidate(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR **bestvar, SCIP_Real *bestbrpoint, SCIP_Real *bestscore, SCIP_Real *bestrndscore, SCIP_VAR *cand, SCIP_Real candscoremin, SCIP_Real candscoremax, SCIP_Real candscoresum, SCIP_Real candrndscore, SCIP_Real candsol)
Definition: branch_pscost.c:75
#define BRANCHRULE_NCHILDREN_DEFAULT
Definition: branch_pscost.c:41
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:40453
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:16958
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
#define BRANCHRULE_NARYMAXDEPTH_DEFAULT
Definition: branch_pscost.c:42
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip.c:25593
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:16946
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip.c:36631
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip.c:9086
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:12561
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12654
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46138
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:9054
static SCIP_DECL_BRANCHEXECEXT(branchExecextPscost)
#define FALSE
Definition: def.h:64
SCIP_Real SCIPadjustedVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real ub)
Definition: scip.c:21580
SCIP_RETCODE SCIPbranchVarValNary(SCIP *scip, SCIP_VAR *var, SCIP_Real val, int n, SCIP_Real minwidth, SCIP_Real widthfactor, int *nchildren)
Definition: scip.c:36876
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:9618
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:45888
#define TRUE
Definition: def.h:63
static SCIP_DECL_BRANCHCOPY(branchCopyPscost)
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:9038
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9184
#define BRANCHRULE_NARYMINWIDTH_DEFAULT
Definition: branch_pscost.c:43
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
static SCIP_DECL_BRANCHINIT(branchInitPscost)
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip.c:9001
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21933
#define BRANCHRULE_STRATEGY_DEFAULT
Definition: branch_pscost.c:37
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7153
SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: scip.c:36244
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip.c:21548
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, 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: scip.c:4202
#define WEIGHTEDSCORING(data, min, max, sum)
Definition: branch_pscost.c:48
SCIP_Real SCIPcomputeVarLbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:23412
SCIP_Real SCIPgetVarPseudocostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition: scip.c:25882
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9136
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip.c:36583
static SCIP_DECL_BRANCHEXECLP(branchExeclpPscost)
SCIP_RETCODE SCIPselectBranchVarPscost(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsscore, int nbranchcands, SCIP_VAR **var, SCIP_Real *brpoint)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11524
void SCIPrandomFree(SCIP_RANDNUMGEN **randnumgen)
Definition: misc.c:8710
#define BRANCHRULE_STRATEGIES
Definition: branch_pscost.c:36
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:36737
#define SCIPerrorMessage
Definition: pub_message.h:45
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
static SCIP_DECL_BRANCHFREE(branchFreePscost)
#define NULL
Definition: lpi_spx1.cpp:137
#define REALABS(x)
Definition: def.h:159
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45985
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Real SCIPcomputeVarUbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:23433
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46112
#define BRANCHRULE_PRIORITY
Definition: branch_pscost.c:32
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
Definition: scip.c:45839
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
static SCIP_RETCODE selectBranchVar(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **cands, SCIP_Real *candssol, SCIP_Real *candsscore, int ncands, SCIP_VAR **brvar, SCIP_Real *brpoint)
public data structures and miscellaneous methods
pseudo costs branching rule
SCIP_Bool SCIPisSumGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46024
#define BRANCHRULE_RANDSEED_DEFAULT
Definition: branch_pscost.c:45
#define SCIP_Bool
Definition: def.h:61
#define BRANCHRULE_MAXDEPTH
Definition: branch_pscost.c:33
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1784
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11249
unsigned int SCIPinitializeRandomSeed(SCIP *scip, int initialseedvalue)
Definition: scip.c:25467
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip.c:9152
static SCIP_DECL_BRANCHEXIT(branchExitPscost)
#define BRANCHRULE_SCORESUMWEIGHT_DEFAULT
Definition: branch_pscost.c:40
#define BRANCHRULE_SCOREMAXWEIGHT_DEFAULT
Definition: branch_pscost.c:39
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:16934
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:8745
#define SCIP_REAL_MAX
Definition: def.h:136
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:45900
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4286
#define BRANCHRULE_MAXBOUNDDIST
Definition: branch_pscost.c:34
#define BRANCHRULE_DESC
Definition: branch_pscost.c:31
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16671
#define SCIP_Real
Definition: def.h:135
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1896
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip.c:9070
#define SCIP_INVALID
Definition: def.h:155
#define BRANCHRULE_NARYWIDTHFAC_DEFAULT
Definition: branch_pscost.c:44
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16717
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_RETCODE SCIPincludeBranchrulePscost(SCIP *scip)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:46187
#define BRANCHRULE_SCOREMINWEIGHT_DEFAULT
Definition: branch_pscost.c:38
#define SCIPABORT()
Definition: def.h:278
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, 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: scip.c:4258
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16839