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-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch_pscost.c
17  * @brief pseudo costs branching rule
18  * @author Tobias Achterberg
19  * @author Stefan Vigerske
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/branch_pscost.h"
28 
29 #define BRANCHRULE_NAME "pscost"
30 #define BRANCHRULE_DESC "branching on pseudo cost values"
31 #define BRANCHRULE_PRIORITY 2000
32 #define BRANCHRULE_MAXDEPTH -1
33 #define BRANCHRULE_MAXBOUNDDIST 1.0
34 
35 #define BRANCHRULE_STRATEGIES "cdsu" /**< possible pseudo cost multiplication strategies for branching on external candidates */
36 #define BRANCHRULE_STRATEGY_DEFAULT 'u' /**< default pseudo cost multiplication strategy */
37 #define BRANCHRULE_SCOREMINWEIGHT_DEFAULT 0.8 /**< default weight for minimum of scores of a branching candidate */
38 #define BRANCHRULE_SCOREMAXWEIGHT_DEFAULT 1.3 /**< default weight for maximum of scores of a branching candidate */
39 #define BRANCHRULE_SCORESUMWEIGHT_DEFAULT 0.1 /**< default weight for sum of scores of a branching candidate */
40 #define BRANCHRULE_NCHILDREN_DEFAULT 2 /**< default number of children in n-ary branching */
41 #define BRANCHRULE_NARYMAXDEPTH_DEFAULT -1 /**< default maximal depth where to do n-ary branching */
42 #define BRANCHRULE_NARYMINWIDTH_DEFAULT 0.001 /**< default minimal domain width in children when doing n-ary branching */
43 #define BRANCHRULE_NARYWIDTHFAC_DEFAULT 2.0 /**< default factor of domain width in n-ary branching */
44 
45 #define WEIGHTEDSCORING(data, min, max, sum) \
46  ((data)->scoreminweight * (min) + (data)->scoremaxweight * (max) + (data)->scoresumweight * (sum))
47 
48 /** branching rule data */
49 struct SCIP_BranchruleData
50 {
51  char strategy; /**< strategy for computing score of external candidates */
52  SCIP_Real scoreminweight; /**< weight for minimum of scores of a branching candidate */
53  SCIP_Real scoremaxweight; /**< weight for maximum of scores of a branching candidate */
54  SCIP_Real scoresumweight; /**< weight for sum of scores of a branching candidate */
55 
56  char updatestrategy; /**< strategy used to update pseudo costs of continuous variables */
57 
58  int nchildren; /**< targeted number of children in n-ary branching */
59  int narymaxdepth; /**< maximal depth where to do n-ary branching, -1 to turn off */
60  SCIP_Real naryminwidth; /**< minimal domain width in children when doing n-ary branching, relative to global bounds */
61  SCIP_Real narywidthfactor; /**< factor of domain width in n-ary branching */
62 };
63 
64 /*
65  * Local methods
66  */
67 
68 /** checks if a given branching candidate is better than a previous one and updates the best branching candidate accordingly */
69 static
70 SCIP_RETCODE updateBestCandidate(
71  SCIP* scip, /**< SCIP data structure */
72  SCIP_BRANCHRULEDATA* branchruledata, /**< branching rule data */
73  SCIP_VAR** bestvar, /**< best branching candidate */
74  SCIP_Real* bestbrpoint, /**< branching point for best branching candidate */
75  SCIP_Real* bestscore, /**< score of best branching candidate */
76  SCIP_VAR* cand, /**< branching candidate to consider */
77  SCIP_Real candscoremin, /**< minimal score of branching candidate */
78  SCIP_Real candscoremax, /**< maximal score of branching candidate */
79  SCIP_Real candscoresum, /**< sum of scores of branching candidate */
80  SCIP_Real candsol /**< proposed branching point of branching candidate */
81 )
82 {
83  SCIP_Real candbrpoint;
84  SCIP_Real branchscore;
85 
86  SCIP_Real deltaminus;
87  SCIP_Real deltaplus;
88 
89  SCIP_Real pscostdown;
90  SCIP_Real pscostup;
91 
92  char strategy;
93 
94  assert(scip != NULL);
95  assert(branchruledata != NULL);
96  assert(bestvar != NULL);
97  assert(bestbrpoint != NULL);
98  assert(bestscore != NULL);
99  assert(cand != NULL);
100 
101  /* a branching variable candidate should either be an active problem variable or a multi-aggregated variable */
102  assert(SCIPvarIsActive(SCIPvarGetProbvar(cand)) ||
103  SCIPvarGetStatus(SCIPvarGetProbvar(cand)) == SCIP_VARSTATUS_MULTAGGR);
104 
105  if( SCIPvarGetStatus(SCIPvarGetProbvar(cand)) == SCIP_VARSTATUS_MULTAGGR )
106  {
107  /* for a multi-aggregated variable, we call updateBestCandidate function recursively with all variables in the multi-aggregation */
108  SCIP_VAR** multvars;
109  int nmultvars;
110  int i;
111  SCIP_Bool success;
112  SCIP_Real multvarlb;
113  SCIP_Real multvarub;
114 
115  cand = SCIPvarGetProbvar(cand);
116  multvars = SCIPvarGetMultaggrVars(cand);
117  nmultvars = SCIPvarGetMultaggrNVars(cand);
118 
119  /* if we have a candidate branching point, then first register only aggregation variables
120  * for which we can compute a corresponding branching point too (see also comments below)
121  * if this fails, then register all (unfixed) aggregation variables, thereby forgetting about candsol
122  */
123  success = FALSE;
124  if( candsol != SCIP_INVALID ) /*lint !e777*/
125  {
126  SCIP_Real* multscalars;
127  SCIP_Real minact;
128  SCIP_Real maxact;
129  SCIP_Real aggrvarsol;
130  SCIP_Real aggrvarsol1;
131  SCIP_Real aggrvarsol2;
132 
133  multscalars = SCIPvarGetMultaggrScalars(cand);
134 
135  /* for computing the branching point, we need the current bounds of the multi-aggregated variable */
136  minact = SCIPcomputeVarLbLocal(scip, cand);
137  maxact = SCIPcomputeVarUbLocal(scip, cand);
138 
139  for( i = 0; i < nmultvars; ++i )
140  {
141  /* skip fixed variables */
142  multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]);
143  multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]);
144  if( SCIPisEQ(scip, multvarlb, multvarub) )
145  continue;
146 
147  assert(multscalars != NULL);
148  assert(multscalars[i] != 0.0);
149 
150  /* we cannot ensure that both the upper bound in the left node and the lower bound in the right node
151  * will be candsol by a clever choice for the branching point of multvars[i],
152  * but we can try to ensure that at least one of them will be at candsol
153  */
154  if( multscalars[i] > 0.0 )
155  {
156  /* cand >= candsol
157  * if multvars[i] >= (candsol - (maxact - multscalars[i] * ub(multvars[i]))) / multscalars[i]
158  * = (candsol - maxact) / multscalars[i] + ub(multvars[i])
159  */
160  aggrvarsol1 = (candsol - maxact) / multscalars[i] + multvarub;
161 
162  /* cand <= candsol
163  * if multvars[i] <= (candsol - (minact - multscalar[i] * lb(multvars[i]))) / multscalars[i]
164  * = (candsol - minact) / multscalars[i] + lb(multvars[i])
165  */
166  aggrvarsol2 = (candsol - minact) / multscalars[i] + multvarlb;
167  }
168  else
169  {
170  /* cand >= candsol
171  * if multvars[i] <= (candsol - (maxact - multscalars[i] * lb(multvars[i]))) / multscalars[i]
172  * = (candsol - maxact) / multscalars[i] + lb(multvars[i])
173  */
174  aggrvarsol2 = (candsol - maxact) / multscalars[i] + multvarlb;
175 
176  /* cand <= candsol
177  * if multvars[i] >= (candsol - (minact - multscalar[i] * ub(multvars[i]))) / multscalars[i]
178  * = (candsol - minact) / multscalars[i] + ub(multvars[i])
179  */
180  aggrvarsol1 = (candsol - minact) / multscalars[i] + multvarub;
181  }
182 
183  /* by the above choice, aggrvarsol1 <= ub(multvars[i]) and aggrvarsol2 >= lb(multvars[i])
184  * if aggrvarsol1 <= lb(multvars[i]) or aggrvarsol2 >= ub(multvars[i]), then choose the other one
185  * if both are out of bounds, then give up
186  * if both are inside bounds, then choose the one closer to 0.0 (someone has better idea???)
187  */
188  if( SCIPisFeasLE(scip, aggrvarsol1, multvarlb) )
189  {
190  if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) )
191  continue;
192  else
193  aggrvarsol = aggrvarsol2;
194  }
195  else
196  {
197  if( SCIPisFeasGE(scip, aggrvarsol2, multvarub) )
198  aggrvarsol = aggrvarsol1;
199  else
200  aggrvarsol = REALABS(aggrvarsol1) < REALABS(aggrvarsol2) ? aggrvarsol1 : aggrvarsol2;
201  }
202  success = TRUE;
203 
204  SCIP_CALL( updateBestCandidate(scip, branchruledata, bestvar, bestbrpoint, bestscore,
205  multvars[i], candscoremin, candscoremax, candscoresum, aggrvarsol) );
206  }
207  }
208 
209  if( !success )
210  for( i = 0; i < nmultvars; ++i )
211  {
212  /* skip fixed variables */
213  multvarlb = SCIPcomputeVarLbLocal(scip, multvars[i]);
214  multvarub = SCIPcomputeVarUbLocal(scip, multvars[i]);
215  if( SCIPisEQ(scip, multvarlb, multvarub) )
216  continue;
217 
218  SCIP_CALL( updateBestCandidate(scip, branchruledata, bestvar, bestbrpoint, bestscore,
219  multvars[i], candscoremin, candscoremax, candscoresum, SCIP_INVALID) );
220  }
221 
222  assert(*bestvar != NULL); /* if all variables were fixed, something is strange */
223 
224  return SCIP_OKAY;
225  }
226 
227  /* select branching point for this variable */
228  candbrpoint = SCIPgetBranchingPoint(scip, cand, candsol);
229  assert(candbrpoint >= SCIPvarGetLbLocal(cand));
230  assert(candbrpoint <= SCIPvarGetUbLocal(cand));
231 
232  /* we cannot branch on a huge value for a discrete variable, because we simply cannot enumerate such huge integer values in floating point
233  * arithmetics
234  */
235  if( SCIPvarGetType(cand) != SCIP_VARTYPE_CONTINUOUS && (SCIPisHugeValue(scip, candbrpoint) || SCIPisHugeValue(scip, -candbrpoint)) )
236  return SCIP_OKAY;
237 
238  assert(SCIPvarGetType(cand) == SCIP_VARTYPE_CONTINUOUS || !SCIPisIntegral(scip, candbrpoint));
239 
240  if( SCIPvarGetType(cand) == SCIP_VARTYPE_CONTINUOUS )
241  strategy = (branchruledata->strategy == 'u' ? branchruledata->updatestrategy : branchruledata->strategy);
242  else
243  strategy = (branchruledata->strategy == 'u' ? 'l' : branchruledata->strategy);
244 
245  switch( strategy )
246  {
247  case 'l':
248  if( SCIPisInfinity(scip, SCIPgetSolVal(scip, NULL, cand)) || SCIPgetSolVal(scip, NULL, cand) <= SCIPadjustedVarUb(scip, cand, candbrpoint) )
249  deltaminus = 0.0;
250  else
251  deltaminus = SCIPgetSolVal(scip, NULL, cand) - SCIPadjustedVarUb(scip, cand, candbrpoint);
252  if( SCIPisInfinity(scip, -SCIPgetSolVal(scip, NULL, cand)) || SCIPgetSolVal(scip, NULL, cand) >= SCIPadjustedVarLb(scip, cand, candbrpoint) )
253  deltaplus = 0.0;
254  else
255  deltaplus = SCIPadjustedVarLb(scip, cand, candbrpoint) - SCIPgetSolVal(scip, NULL, cand);
256  break;
257 
258  case 'd':
259  if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(cand)) )
260  deltaminus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
261  else
262  deltaminus = SCIPadjustedVarUb(scip, cand, candbrpoint) - SCIPvarGetLbLocal(cand);
263 
264  if( SCIPisInfinity(scip, SCIPvarGetUbLocal(cand)) )
265  deltaplus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
266  else
267  deltaplus = SCIPvarGetUbLocal(cand) - SCIPadjustedVarLb(scip, cand, candbrpoint);
268  break;
269 
270  case 's':
271  if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(cand)) )
272  deltaplus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
273  else
274  deltaplus = SCIPadjustedVarUb(scip, cand, candbrpoint) - SCIPvarGetLbLocal(cand);
275 
276  if( SCIPisInfinity(scip, SCIPvarGetUbLocal(cand)) )
277  deltaminus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
278  else
279  deltaminus = SCIPvarGetUbLocal(cand) - SCIPadjustedVarLb(scip, cand, candbrpoint);
280  break;
281 
282  case 'v':
283  deltaplus = SCIPisInfinity(scip, candscoremax) ? SCIPinfinity(scip) : WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum);
284  deltaminus = deltaplus;
285  break;
286 
287  default :
288  SCIPerrorMessage("branching strategy %c unknown\n", strategy);
289  SCIPABORT();
290  return SCIP_INVALIDDATA; /*lint !e527*/
291  }
292 
293  if( SCIPisInfinity(scip, deltaminus) || SCIPisInfinity(scip, deltaplus) )
294  {
295  branchscore = SCIPinfinity(scip);
296  }
297  else
298  {
299  pscostdown = SCIPgetVarPseudocostVal(scip, cand, -deltaminus);
300  pscostup = SCIPgetVarPseudocostVal(scip, cand, deltaplus);
301  branchscore = SCIPgetBranchScore(scip, cand, pscostdown, pscostup);
302  assert(!SCIPisNegative(scip, branchscore));
303  }
304  SCIPdebugMessage("branching score variable <%s>[%g,%g] = %g; wscore = %g; type=%d bestbrscore=%g\n",
305  SCIPvarGetName(cand), SCIPvarGetLbLocal(cand), SCIPvarGetUbLocal(cand), branchscore, WEIGHTEDSCORING(branchruledata, candscoremin, candscoremax, candscoresum),
306  SCIPvarGetType(cand), *bestscore);
307 
308  if( SCIPisInfinity(scip, branchscore) )
309  branchscore = 0.9*SCIPinfinity(scip);
310 
311  if( SCIPisSumGT(scip, branchscore, *bestscore) )
312  {
313  (*bestscore) = branchscore;
314  (*bestvar) = cand;
315  (*bestbrpoint) = candbrpoint;
316  }
317  else if( SCIPisSumEQ(scip, branchscore, *bestscore)
318  && !(SCIPisInfinity(scip, -SCIPvarGetLbLocal(*bestvar)) && SCIPisInfinity(scip, SCIPvarGetUbLocal(*bestvar))) )
319  {
320  /* if best candidate so far is not unbounded to both sides, maybe take new candidate */
321  if( (SCIPisInfinity(scip, -SCIPvarGetLbLocal(cand)) || SCIPisInfinity(scip, SCIPvarGetUbLocal(cand))) &&
322  (SCIPisInfinity(scip, -SCIPvarGetLbLocal(*bestvar)) || SCIPisInfinity(scip, SCIPvarGetUbLocal(*bestvar))) )
323  {
324  /* if both variables are unbounded but one of them is bounded on one side, take the one with the larger bound on this side (hope that this avoids branching on always the same variable) */
325  if( SCIPvarGetUbLocal(cand) > SCIPvarGetUbLocal(*bestvar) || SCIPvarGetLbLocal(cand) < SCIPvarGetLbLocal(*bestvar) )
326  {
327  (*bestscore) = branchscore;
328  (*bestvar) = cand;
329  (*bestbrpoint) = candbrpoint;
330  }
331  }
332  else if( SCIPvarGetType(*bestvar) == SCIPvarGetType(cand) )
333  {
334  /* if both have the same type, take the one with larger diameter */
335  if( SCIPvarGetUbLocal(*bestvar) - SCIPvarGetLbLocal(*bestvar) < SCIPvarGetUbLocal(cand) - SCIPvarGetLbLocal(cand) )
336  {
337  (*bestscore) = branchscore;
338  (*bestvar) = cand;
339  (*bestbrpoint) = candbrpoint;
340  }
341  }
342  else if( SCIPvarGetType(*bestvar) > SCIPvarGetType(cand) )
343  {
344  /* take the one with better type ("more discrete") */
345  (*bestscore) = branchscore;
346  (*bestvar) = cand;
347  (*bestbrpoint) = candbrpoint;
348  }
349  }
350 
351  return SCIP_OKAY;
352 }
353 
354 /** selects the branching variable from given candidate array */
355 static
356 SCIP_RETCODE selectBranchVar(
357  SCIP* scip, /**< SCIP data structure */
358  SCIP_BRANCHRULE* branchrule, /**< branching rule */
359  SCIP_VAR** cands, /**< array of branching candidates */
360  SCIP_Real* candssol, /**< array of candidate solution values */
361  SCIP_Real* candsscore, /**< array of candidate scores */
362  int ncands, /**< the number of candidates */
363  SCIP_VAR** brvar, /**< pointer to store the selected branching candidate or NULL if none */
364  SCIP_Real* brpoint /**< pointer to store branching point of selected branching variable */
365  )
366 { /*lint --e{850}*/
367  SCIP_BRANCHRULEDATA* branchruledata;
368 
369  SCIP_VAR* cand;
370  SCIP_Real candsol;
371 
372  SCIP_Real bestbranchscore;
373 
374  SCIP_Real scoremin;
375  SCIP_Real scoresum;
376  SCIP_Real scoremax;
377 
378  SCIP_VAR** candssorted;
379  int* candsorigidx;
380 
381  int i;
382  int j;
383 
384  assert(brvar != NULL);
385  assert(brpoint != NULL);
386 
387  (*brvar) = NULL;
388  (*brpoint) = SCIP_INVALID;
389 
390  if( ncands == 0 )
391  return SCIP_OKAY;
392 
393  branchruledata = SCIPbranchruleGetData(branchrule);
394  assert(branchruledata != NULL);
395 
396  /* sort branching candidates (in a copy), such that same variables are on consecutive positions */
397  SCIP_CALL( SCIPduplicateBufferArray(scip, &candssorted, cands, ncands) );
398  SCIP_CALL( SCIPallocBufferArray(scip, &candsorigidx, ncands) );
399  for( i = 0; i < ncands; ++i )
400  candsorigidx[i] = i;
401 
402  SCIPsortPtrInt((void**)candssorted, candsorigidx, SCIPvarComp, ncands);
403 
404  bestbranchscore = -1.0;
405 
406  for( i = 0; i < ncands; ++i )
407  {
408  cand = candssorted[i];
409 
410  /* there should be no fixed branching candidates */
411  assert(!SCIPisEQ(scip, SCIPvarGetLbLocal(cand), SCIPvarGetUbLocal(cand)));
412 
413  /* compute min, sum, and max of all registered scores for this variables
414  * set candsol to a valid value, if someone registered one */
415  scoremin = candsscore[candsorigidx[i]];
416  scoresum = scoremin;
417  scoremax = scoremin;
418  candsol = candssol[candsorigidx[i]];
419  for( j = i+1 ; j < ncands && SCIPvarCompare(candssorted[j], cand) == 0; ++j )
420  {
421  assert(candsscore[candsorigidx[j]] >= 0.0);
422  scoresum += candsscore[candsorigidx[j]];
423  if( candsscore[candsorigidx[j]] < scoremin )
424  scoremin = candsscore[candsorigidx[j]];
425  else if( candsscore[candsorigidx[j]] > scoremax )
426  scoremax = candsscore[candsorigidx[j]];
427 
428  /* @todo if there are two valid externcandssol available for the same variable, should we take the one closer to the middle of the domain? */
429  if( SCIPisInfinity(scip, REALABS(candsol)) )
430  candsol = candssol[candsorigidx[j]];
431  }
432  /* set i to last occurrence of cand in candssorted (instead of first one as before), so in next round we look at another variable */
433  i = j-1;
434  assert(candssorted[i] == cand);
435 
436  /* check if new candidate is better than previous candidate (if any) */
437  SCIP_CALL( updateBestCandidate(scip, branchruledata, brvar, brpoint, &bestbranchscore, cand, scoremin, scoremax, scoresum, candsol) );
438  }
439 
440  /* there were candidates, but no variable was selected; this can only happen if the branching points are huge values
441  * for all variables on which we cannot branch
442  * @todo delay the node?
443  */
444  if( (*brvar) == NULL )
445  {
446  SCIPerrorMessage("no branching could be created: all external candidates have huge bounds\n");
447  SCIPABORT();
448  return SCIP_BRANCHERROR; /*lint !e527*/
449  }
450 
451  /* free buffer arrays */
452  SCIPfreeBufferArray(scip, &candssorted);
453  SCIPfreeBufferArray(scip, &candsorigidx);
454 
455  return SCIP_OKAY;
456 }
457 
458 /*
459  * Callback methods
460  */
461 
462 /** copy method for branchrule plugins (called when SCIP copies plugins) */
463 static
464 SCIP_DECL_BRANCHCOPY(branchCopyPscost)
465 { /*lint --e{715}*/
466  assert(scip != NULL);
467  assert(branchrule != NULL);
468  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
469 
470  /* call inclusion method of branchrule */
471  SCIP_CALL( SCIPincludeBranchrulePscost(scip) );
472 
473  return SCIP_OKAY;
474 }
475 
476 /** destructor of branching rule to free user data (called when SCIP is exiting) */
477 static
478 SCIP_DECL_BRANCHFREE(branchFreePscost)
479 { /*lint --e{715}*/
480  SCIP_BRANCHRULEDATA* branchruledata;
481 
482  /* free branching rule data */
483  branchruledata = SCIPbranchruleGetData(branchrule);
484  SCIPfreeMemory(scip, &branchruledata);
485  SCIPbranchruleSetData(branchrule, NULL);
486 
487  return SCIP_OKAY;
488 }
489 
490 
491 /** branching execution method for fractional LP solutions */
492 static
493 SCIP_DECL_BRANCHEXECLP(branchExeclpPscost)
494 { /*lint --e{715}*/
495  SCIP_VAR** lpcands;
496  SCIP_Real* lpcandssol;
497  SCIP_Real bestscore;
498  SCIP_Real bestrootdiff;
499  int nlpcands;
500  int bestcand;
501  int c;
502 
503  assert(branchrule != NULL);
504  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
505  assert(scip != NULL);
506  assert(result != NULL);
507 
508  SCIPdebugMessage("Execlp method of pscost branching\n");
509 
510  /* get branching candidates */
511  SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, NULL, &nlpcands, NULL) );
512  assert(nlpcands > 0);
513 
514  bestcand = -1;
515  bestscore = -SCIPinfinity(scip);
516  bestrootdiff = 0.0;
517  for( c = 0; c < nlpcands; ++c )
518  {
519  SCIP_Real score;
520  SCIP_Real rootsolval;
521  SCIP_Real rootdiff;
522 
523  score = SCIPgetVarPseudocostScore(scip, lpcands[c], lpcandssol[c]);
524  rootsolval = SCIPvarGetRootSol(lpcands[c]);
525  rootdiff = REALABS(lpcandssol[c] - rootsolval);
526  if( SCIPisSumGT(scip, score, bestscore) || (SCIPisSumEQ(scip, score, bestscore) && rootdiff > bestrootdiff) )
527  {
528  bestcand = c;
529  bestscore = score;
530  bestrootdiff = rootdiff;
531  }
532  }
533  assert(0 <= bestcand && bestcand < nlpcands);
534  assert(!SCIPisFeasIntegral(scip, lpcandssol[bestcand]));
535 
536  /* perform the branching */
537  SCIPdebugMessage(" -> %d cands, selected cand %d: variable <%s> (solval=%g, score=%g)\n",
538  nlpcands, bestcand, SCIPvarGetName(lpcands[bestcand]), lpcandssol[bestcand], bestscore);
539 
540  /* perform the branching */
541  SCIP_CALL( SCIPbranchVar(scip, lpcands[bestcand], NULL, NULL, NULL) );
542  *result = SCIP_BRANCHED;
543 
544  return SCIP_OKAY;
545 }
546 
547 
548 /** branching execution method for external candidates */
549 static
550 SCIP_DECL_BRANCHEXECEXT(branchExecextPscost)
551 { /*lint --e{715}*/
552  SCIP_BRANCHRULEDATA* branchruledata;
553  SCIP_VAR** externcands;
554  SCIP_Real* externcandssol;
555  SCIP_Real* externcandsscore;
556  int nprioexterncands;
557  SCIP_VAR* brvar;
558  SCIP_Real brpoint;
559  int nchildren;
560 
561  assert(branchrule != NULL);
562  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
563  assert(scip != NULL);
564  assert(result != NULL);
565 
566  branchruledata = SCIPbranchruleGetData(branchrule);
567  assert(branchruledata != NULL);
568 
569  SCIPdebugMessage("Execext method of pscost branching\n");
570 
571  /* get branching candidates */
572  SCIP_CALL( SCIPgetExternBranchCands(scip, &externcands, &externcandssol, &externcandsscore, NULL, &nprioexterncands, NULL, NULL, NULL) );
573  assert(nprioexterncands > 0);
574 
575  /* get current update strategy for pseudo costs, if our multiplier rule is 'u' */
576  if( branchruledata->strategy == 'u' )
577  {
578  SCIP_CALL( SCIPgetCharParam(scip, "branching/lpgainnormalize", &branchruledata->updatestrategy) );
579  }
580 
581  /* select branching variable */
582  SCIP_CALL( selectBranchVar(scip, branchrule, externcands, externcandssol, externcandsscore, nprioexterncands, &brvar, &brpoint) );
583 
584  if( brvar == NULL )
585  {
586  SCIPerrorMessage("branchExecextPscost failed to select a branching variable from %d candidates\n", nprioexterncands);
587  *result = SCIP_DIDNOTRUN;
588  return SCIP_OKAY;
589  }
590 
591  assert(SCIPvarIsActive(SCIPvarGetProbvar(brvar)));
592 
593  SCIPdebugMessage("branching on variable <%s>: new intervals: [%g, %g] and [%g, %g]\n",
594  SCIPvarGetName(brvar), SCIPvarGetLbLocal(brvar), SCIPadjustedVarUb(scip, brvar, brpoint), SCIPadjustedVarLb(scip, brvar, brpoint), SCIPvarGetUbLocal(brvar));
595 
596  if( branchruledata->nchildren > 2 && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) <= branchruledata->narymaxdepth )
597  {
598  /* do n-ary branching */
599  SCIP_Real minwidth;
600 
601  minwidth = 0.0;
602  if( !SCIPisInfinity(scip, -SCIPvarGetLbGlobal(brvar)) && !SCIPisInfinity(scip, SCIPvarGetUbGlobal(brvar)) )
603  minwidth = branchruledata->naryminwidth * (SCIPvarGetUbGlobal(brvar) - SCIPvarGetLbGlobal(brvar));
604 
605  SCIP_CALL( SCIPbranchVarValNary(scip, brvar, brpoint, branchruledata->nchildren, minwidth, branchruledata->narywidthfactor, &nchildren) );
606  }
607  else
608  {
609  /* do binary branching */
610  SCIP_CALL( SCIPbranchVarValNary(scip, brvar, brpoint, 2, 0.0, 1.0, &nchildren) );
611  }
612 
613  if( nchildren > 1 )
614  {
615  *result = SCIP_BRANCHED;
616  }
617  else
618  {
619  /* if there are no children, then variable should have been fixed by SCIPbranchVarVal */
620  assert(SCIPisEQ(scip, SCIPvarGetLbLocal(brvar), SCIPvarGetUbLocal(brvar)));
621  *result = SCIP_REDUCEDDOM;
622  }
623 
624  return SCIP_OKAY;
625 }
626 
627 
628 /*
629  * branching specific interface methods
630  */
631 
632 /** creates the pseudo cost branching rule and includes it in SCIP */
633 SCIP_RETCODE SCIPincludeBranchrulePscost(
634  SCIP* scip /**< SCIP data structure */
635  )
636 {
637  SCIP_BRANCHRULEDATA* branchruledata;
638  SCIP_BRANCHRULE* branchrule;
639 
640  /* create pscost branching rule data */
641  SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
642 
643  /* include allfullstrong branching rule */
644  SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
645  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
646 
647  assert(branchrule != NULL);
648 
649  /* set non-fundamental callbacks via specific setter functions*/
650  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyPscost) );
651  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreePscost) );
652  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpPscost) );
653  SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextPscost) );
654 
655  SCIP_CALL( SCIPaddCharParam(scip, "branching/"BRANCHRULE_NAME"/strategy",
656  "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)",
657  &branchruledata->strategy, FALSE, BRANCHRULE_STRATEGY_DEFAULT, BRANCHRULE_STRATEGIES, NULL, NULL) );
658 
659  SCIP_CALL( SCIPaddRealParam(scip, "branching/"BRANCHRULE_NAME"/minscoreweight",
660  "weight for minimum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
661  &branchruledata->scoreminweight, TRUE, BRANCHRULE_SCOREMINWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
662 
663  SCIP_CALL( SCIPaddRealParam(scip, "branching/"BRANCHRULE_NAME"/maxscoreweight",
664  "weight for maximum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
665  &branchruledata->scoremaxweight, TRUE, BRANCHRULE_SCOREMAXWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
666 
667  SCIP_CALL( SCIPaddRealParam(scip, "branching/"BRANCHRULE_NAME"/sumscoreweight",
668  "weight for sum of scores of a branching candidate when building weighted sum of min/max/sum of scores",
669  &branchruledata->scoresumweight, TRUE, BRANCHRULE_SCORESUMWEIGHT_DEFAULT, -SCIPinfinity(scip), SCIPinfinity(scip), NULL, NULL) );
670 
671  SCIP_CALL( SCIPaddIntParam(scip, "branching/"BRANCHRULE_NAME"/nchildren",
672  "number of children to create in n-ary branching",
673  &branchruledata->nchildren, FALSE, BRANCHRULE_NCHILDREN_DEFAULT, 2, INT_MAX, NULL, NULL) );
674 
675  SCIP_CALL( SCIPaddIntParam(scip, "branching/"BRANCHRULE_NAME"/narymaxdepth",
676  "maximal depth where to do n-ary branching, -1 to turn off",
677  &branchruledata->narymaxdepth, FALSE, BRANCHRULE_NARYMAXDEPTH_DEFAULT, -1, INT_MAX, NULL, NULL) );
678 
679  SCIP_CALL( SCIPaddRealParam(scip, "branching/"BRANCHRULE_NAME"/naryminwidth",
680  "minimal domain width in children when doing n-ary branching, relative to global bounds",
681  &branchruledata->naryminwidth, FALSE, BRANCHRULE_NARYMINWIDTH_DEFAULT, 0.0, 1.0, NULL, NULL) );
682 
683  SCIP_CALL( SCIPaddRealParam(scip, "branching/"BRANCHRULE_NAME"/narywidthfactor",
684  "factor of domain width in n-ary branching when creating nodes with increasing distance from branching value",
685  &branchruledata->narywidthfactor, FALSE, BRANCHRULE_NARYWIDTHFAC_DEFAULT, 1.0, SCIP_REAL_MAX, NULL, NULL) );
686 
687  return SCIP_OKAY;
688 }
689 
690 /** selects a branching variable, due to pseudo cost, from the given candidate array and returns this variable together
691  * with a branching point */
692 SCIP_RETCODE SCIPselectBranchVarPscost(
693  SCIP* scip, /**< SCIP data structure */
694  SCIP_VAR** branchcands, /**< branching candidates */
695  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
696  SCIP_Real* branchcandsscore, /**< array of candidate scores */
697  int nbranchcands, /**< number of branching candidates */
698  SCIP_VAR** var, /**< pointer to store the variable to branch on, or NULL if none */
699  SCIP_Real* brpoint /**< pointer to store the branching point for the branching variable, will be fractional for a discrete variable */
700  )
701 {
702  SCIP_BRANCHRULE* branchrule;
703 
704  assert(scip != NULL);
705 
706  /* find branching rule */
707  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
708  assert(branchrule != NULL);
709 
710  /* select branching variable */
711  SCIP_CALL( selectBranchVar(scip, branchrule, branchcands, branchcandssol, branchcandsscore, nbranchcands, var, brpoint) );
712 
713  return SCIP_OKAY;
714 }
715