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-2018 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not 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 non-continuous 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  return SCIP_BRANCHERROR; /*lint !e527*/
524  }
525 
526  /* free buffer arrays */
527  SCIPfreeBufferArray(scip, &candssorted);
528  SCIPfreeBufferArray(scip, &candsorigidx);
529 
530  return SCIP_OKAY;
531 }
532 
533 /*
534  * Callback methods
535  */
536 
537 /** copy method for branchrule plugins (called when SCIP copies plugins) */
538 static
539 SCIP_DECL_BRANCHCOPY(branchCopyPscost)
540 { /*lint --e{715}*/
541  assert(scip != NULL);
542  assert(branchrule != NULL);
543  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
544 
545  /* call inclusion method of branchrule */
547 
548  return SCIP_OKAY;
549 }
550 
551 /** destructor of branching rule to free user data (called when SCIP is exiting) */
552 static
553 SCIP_DECL_BRANCHFREE(branchFreePscost)
554 { /*lint --e{715}*/
555  SCIP_BRANCHRULEDATA* branchruledata;
556 
557  /* get branching rule data */
558  branchruledata = SCIPbranchruleGetData(branchrule);
559  assert(branchruledata != NULL);
560 
561  /* free random number generator */
562  SCIPfreeRandom(scip, &branchruledata->randnumgen);
563 
564  /* free branching rule data */
565  SCIPfreeBlockMemory(scip, &branchruledata);
566  SCIPbranchruleSetData(branchrule, NULL);
567 
568  return SCIP_OKAY;
569 }
570 
571 /** initialization method of branching rule (called after problem was transformed) */
572 static
573 SCIP_DECL_BRANCHINIT(branchInitPscost)
574 { /*lint --e{715}*/
575  SCIP_BRANCHRULEDATA* branchruledata;
576 
577  /* initialize branching rule data */
578  branchruledata = SCIPbranchruleGetData(branchrule);
579  assert(branchruledata != NULL);
580 
581  SCIPsetRandomSeed(scip, branchruledata->randnumgen, BRANCHRULE_RANDSEED_DEFAULT);
582 
583  return SCIP_OKAY;
584 }
585 
586 /** branching execution method for fractional LP solutions */
587 static
588 SCIP_DECL_BRANCHEXECLP(branchExeclpPscost)
589 { /*lint --e{715}*/
590  SCIP_VAR** lpcands;
591  SCIP_Real* lpcandssol;
592  SCIP_Real bestscore;
593  SCIP_Real bestrootdiff;
594  int nlpcands;
595  int bestcand;
596  int c;
597 
598  assert(branchrule != NULL);
599  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
600  assert(scip != NULL);
601  assert(result != NULL);
602 
603  SCIPdebugMsg(scip, "Execlp method of pscost branching\n");
604 
605  /* get branching candidates */
606  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, NULL, &nlpcands, NULL) );
607  assert(nlpcands > 0);
608 
609  bestcand = -1;
610  bestscore = -SCIPinfinity(scip);
611  bestrootdiff = 0.0;
612  for( c = 0; c < nlpcands; ++c )
613  {
614  SCIP_Real score;
615  SCIP_Real rootsolval;
616  SCIP_Real rootdiff;
617 
618  score = SCIPgetVarPseudocostScore(scip, lpcands[c], lpcandssol[c]);
619  rootsolval = SCIPvarGetRootSol(lpcands[c]);
620  rootdiff = REALABS(lpcandssol[c] - rootsolval);
621  if( SCIPisSumGT(scip, score, bestscore) || (SCIPisSumEQ(scip, score, bestscore) && rootdiff > bestrootdiff) )
622  {
623  bestcand = c;
624  bestscore = score;
625  bestrootdiff = rootdiff;
626  }
627  }
628  assert(0 <= bestcand && bestcand < nlpcands);
629  assert(!SCIPisFeasIntegral(scip, lpcandssol[bestcand]));
630  assert(!SCIPisFeasIntegral(scip, SCIPvarGetSol(lpcands[bestcand], TRUE)));
631 
632  /* perform the branching */
633  SCIPdebugMsg(scip, " -> %d cands, selected cand %d: variable <%s> (solval=%g, score=%g)\n",
634  nlpcands, bestcand, SCIPvarGetName(lpcands[bestcand]), lpcandssol[bestcand], bestscore);
635 
636  /* perform the branching */
637  SCIP_CALL( SCIPbranchVar(scip, lpcands[bestcand], NULL, NULL, NULL) );
638  *result = SCIP_BRANCHED;
639 
640  return SCIP_OKAY;
641 }
642 
643 
644 /** branching execution method for external candidates */
645 static
646 SCIP_DECL_BRANCHEXECEXT(branchExecextPscost)
647 { /*lint --e{715}*/
648  SCIP_BRANCHRULEDATA* branchruledata;
649  SCIP_VAR** externcands;
650  SCIP_Real* externcandssol;
651  SCIP_Real* externcandsscore;
652  int nprioexterncands;
653  SCIP_VAR* brvar;
654  SCIP_Real brpoint;
655  int nchildren;
656 
657  assert(branchrule != NULL);
658  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
659  assert(scip != NULL);
660  assert(result != NULL);
661 
662  branchruledata = SCIPbranchruleGetData(branchrule);
663  assert(branchruledata != NULL);
664 
665  SCIPdebugMsg(scip, "Execext method of pscost branching\n");
666 
667  /* get branching candidates */
668  SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, &externcandsscore, NULL, &nprioexterncands, NULL, NULL, NULL) );
669  assert(nprioexterncands > 0);
670 
671  /* get current update strategy for pseudo costs, if our multiplier rule is 'u' */
672  if( branchruledata->strategy == 'u' )
673  {
674  SCIP_CALL( SCIPgetCharParam(scip, "branching/lpgainnormalize", &branchruledata->updatestrategy) );
675  }
676 
677  /* select branching variable */
678  SCIP_CALL( selectBranchVar(scip, branchrule, externcands, externcandssol, externcandsscore, nprioexterncands, &brvar, &brpoint) );
679 
680  if( brvar == NULL )
681  {
682  /* can happen if all candidates were non-continous variables with huge bounds */
683  *result = SCIP_DIDNOTFIND;
684  return SCIP_OKAY;
685  }
686 
687  assert(SCIPvarIsActive(SCIPvarGetProbvar(brvar)));
688 
689  SCIPdebugMsg(scip, "branching on variable <%s>: new intervals: [%g, %g] and [%g, %g]\n",
690  SCIPvarGetName(brvar), SCIPvarGetLbLocal(brvar), SCIPadjustedVarUb(scip, brvar, brpoint), SCIPadjustedVarLb(scip, brvar, brpoint), SCIPvarGetUbLocal(brvar));
691 
692  if( branchruledata->nchildren > 2 && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) <= branchruledata->narymaxdepth )
693  {
694  /* do n-ary branching */
695  SCIP_Real minwidth;
696 
697  minwidth = 0.0;
699  minwidth = branchruledata->naryminwidth * (SCIPvarGetUbGlobal(brvar) - SCIPvarGetLbGlobal(brvar));
700 
701  SCIP_CALL( SCIPbranchVarValNary(scip, brvar, brpoint, branchruledata->nchildren, minwidth, branchruledata->narywidthfactor, &nchildren) );
702  }
703  else
704  {
705  /* do binary branching */
706  SCIP_CALL( SCIPbranchVarValNary(scip, brvar, brpoint, 2, 0.0, 1.0, &nchildren) );
707  }
708 
709  if( nchildren > 1 )
710  {
711  *result = SCIP_BRANCHED;
712  }
713  else
714  {
715  /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
716  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(brvar), SCIPvarGetUbLocal(brvar)));
717  *result = SCIP_REDUCEDDOM;
718  }
719 
720  return SCIP_OKAY;
721 }
722 
723 
724 /*
725  * branching specific interface methods
726  */
727 
728 /** creates the pseudo cost branching rule and includes it in SCIP */
730  SCIP* scip /**< SCIP data structure */
731  )
732 {
733  SCIP_BRANCHRULEDATA* branchruledata;
734  SCIP_BRANCHRULE* branchrule;
735 
736  /* create pscost branching rule data */
737  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
738 
739  /* include allfullstrong branching rule */
741  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
742 
743  assert(branchrule != NULL);
744  /* create a random number generator */
745  SCIP_CALL( SCIPcreateRandom(scip, &branchruledata->randnumgen,
747 
748  /* set non-fundamental callbacks via specific setter functions*/
749  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyPscost) );
750  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreePscost) );
751  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitPscost) );
752  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpPscost) );
753  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextPscost) );
754 
755  SCIP_CALL( SCIPaddCharParam(scip, "branching/" BRANCHRULE_NAME "/strategy",
756  "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)",
757  &branchruledata->strategy, FALSE, BRANCHRULE_STRATEGY_DEFAULT, BRANCHRULE_STRATEGIES, NULL, NULL) );
758 
759  SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/minscoreweight",
760  "weight for minimum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
761  &branchruledata->scoreminweight, TRUE, BRANCHRULE_SCOREMINWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
762 
763  SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/maxscoreweight",
764  "weight for maximum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
765  &branchruledata->scoremaxweight, TRUE, BRANCHRULE_SCOREMAXWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
766 
767  SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/sumscoreweight",
768  "weight for sum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
769  &branchruledata->scoresumweight, TRUE, BRANCHRULE_SCORESUMWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
770 
771  SCIP_CALL( SCIPaddIntParam(scip, "branching/" BRANCHRULE_NAME "/nchildren",
772  "number of children to create in n-ary branching",
773  &branchruledata->nchildren, FALSE, BRANCHRULE_NCHILDREN_DEFAULT, 2, INT_MAX, NULL, NULL) );
774 
775  SCIP_CALL( SCIPaddIntParam(scip, "branching/" BRANCHRULE_NAME "/narymaxdepth",
776  "maximal depth where to do n-ary branching, -1 to turn off",
777  &branchruledata->narymaxdepth, FALSE, BRANCHRULE_NARYMAXDEPTH_DEFAULT, -1, INT_MAX, NULL, NULL) );
778 
779  SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/naryminwidth",
780  "minimal domain width in children when doing n-ary branching, relative to global bounds",
781  &branchruledata->naryminwidth, FALSE, BRANCHRULE_NARYMINWIDTH_DEFAULT, 0.0, 1.0, NULL, NULL) );
782 
783  SCIP_CALL( SCIPaddRealParam(scip, "branching/" BRANCHRULE_NAME "/narywidthfactor",
784  "factor of domain width in n-ary branching when creating nodes with increasing distance from branching value",
785  &branchruledata->narywidthfactor, FALSE, BRANCHRULE_NARYWIDTHFAC_DEFAULT, 1.0, SCIP_REAL_MAX, NULL, NULL) );
786 
787  return SCIP_OKAY;
788 }
789 
790 /** selects a branching variable, due to pseudo cost, from the given candidate array and returns this variable together
791  * with a branching point */
793  SCIP* scip, /**< SCIP data structure */
794  SCIP_VAR** branchcands, /**< branching candidates */
795  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
796  SCIP_Real* branchcandsscore, /**< array of candidate scores */
797  int nbranchcands, /**< number of branching candidates */
798  SCIP_VAR** var, /**< pointer to store the variable to branch on, or NULL if none */
799  SCIP_Real* brpoint /**< pointer to store the branching point for the branching variable, will be fractional for a discrete variable */
800  )
801 {
802  SCIP_BRANCHRULE* branchrule;
803 
804  assert(scip != NULL);
805 
806  /* find branching rule */
807  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
808  assert(branchrule != NULL);
809 
810  /* select branching variable */
811  SCIP_CALL( selectBranchVar(scip, branchrule, branchcands, branchcandssol, branchcandsscore, nbranchcands, var, brpoint) );
812 
813  return SCIP_OKAY;
814 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:37001
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
Definition: scip.c:48626
void SCIPsortPtrInt(void **ptrarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define BRANCHRULE_NAME
Definition: branch_pscost.c:30
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip.c:4508
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1810
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:41404
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:17068
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17276
#define BRANCHRULE_NARYMAXDEPTH_DEFAULT
Definition: branch_pscost.c:42
SCIP_Real SCIPgetVarPseudocostVal(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta)
Definition: scip.c:26031
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed)
Definition: scip.c:48608
void SCIPsetRandomSeed(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, unsigned int seed)
Definition: scip.c:48641
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:17056
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip.c:37504
SCIP_Real SCIPvarGetSol(SCIP_VAR *var, SCIP_Bool getlpval)
Definition: var.c:12665
SCIP_Real SCIPvarGetRootSol(SCIP_VAR *var)
Definition: var.c:12758
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47350
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:9139
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:21985
SCIP_RETCODE SCIPbranchVarValNary(SCIP *scip, SCIP_VAR *var, SCIP_Real val, int n, SCIP_Real minwidth, SCIP_Real widthfactor, int *nchildren)
Definition: scip.c:37749
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:10289
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47028
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:47100
#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:9123
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9269
#define BRANCHRULE_NARYMINWIDTH_DEFAULT
Definition: branch_pscost.c:43
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
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:9086
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:22628
#define BRANCHRULE_STRATEGY_DEFAULT
Definition: branch_pscost.c:37
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46963
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7352
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:37117
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
SCIP_Real SCIPadjustedVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real lb)
Definition: scip.c:21953
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
#define SCIPdebugMsg
Definition: scip.h:455
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:4265
#define WEIGHTEDSCORING(data, min, max, sum)
Definition: branch_pscost.c:48
SCIP_Real SCIPcomputeVarLbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:23819
SCIP_Real SCIPgetVarPseudocostScore(SCIP *scip, SCIP_VAR *var, SCIP_Real solval)
Definition: scip.c:26320
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9221
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip.c:37456
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:17286
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:11628
#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:37610
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
static SCIP_DECL_BRANCHFREE(branchFreePscost)
#define REALABS(x)
Definition: def.h:173
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47197
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_Real SCIPcomputeVarUbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:23840
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47324
#define BRANCHRULE_PRIORITY
Definition: branch_pscost.c:32
SCIP_Bool SCIPisHugeValue(SCIP *scip, SCIP_Real val)
Definition: scip.c:47051
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
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:47236
#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:1820
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11353
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip.c:9237
#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:17044
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:47039
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:9388
#define SCIP_REAL_MAX
Definition: def.h:150
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47112
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:4349
#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:16781
#define SCIP_Real
Definition: def.h:149
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1932
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip.c:9155
#define SCIP_INVALID
Definition: def.h:169
#define BRANCHRULE_NARYWIDTHFAC_DEFAULT
Definition: branch_pscost.c:44
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16827
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
SCIP_RETCODE SCIPincludeBranchrulePscost(SCIP *scip)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:47399
#define BRANCHRULE_SCOREMINWEIGHT_DEFAULT
Definition: branch_pscost.c:38
#define SCIPABORT()
Definition: def.h:322
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38911
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:4321
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:16949