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