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