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