Scippy

SCIP

Solving Constraint Integer Programs

branch_relpscost.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_relpscost.c
17  * @brief reliable pseudo costs branching rule
18  * @author Tobias Achterberg
19  * @author Timo Berthold
20  * @author Gerald Gamrath
21  */
22 
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24 
25 #include <assert.h>
26 #include <string.h>
27 
28 #include "scip/branch_relpscost.h"
29 
30 
31 #define BRANCHRULE_NAME "relpscost"
32 #define BRANCHRULE_DESC "reliability branching on pseudo cost values"
33 #define BRANCHRULE_PRIORITY 10000
34 #define BRANCHRULE_MAXDEPTH -1
35 #define BRANCHRULE_MAXBOUNDDIST 1.0
36 
37 #define DEFAULT_CONFLICTWEIGHT 0.01 /**< weight in score calculations for conflict score */
38 #define DEFAULT_CONFLENGTHWEIGHT 0.0 /**< weight in score calculations for conflict length score*/
39 #define DEFAULT_INFERENCEWEIGHT 0.0001 /**< weight in score calculations for inference score */
40 #define DEFAULT_CUTOFFWEIGHT 0.0001 /**< weight in score calculations for cutoff score */
41 #define DEFAULT_PSCOSTWEIGHT 1.0 /**< weight in score calculations for pseudo cost score */
42 #define DEFAULT_MINRELIABLE 1.0 /**< minimal value for minimum pseudo cost size to regard pseudo cost value as reliable */
43 #define DEFAULT_MAXRELIABLE 5.0 /**< maximal value for minimum pseudo cost size to regard pseudo cost value as reliable */
44 #define DEFAULT_SBITERQUOT 0.5 /**< maximal fraction of strong branching LP iterations compared to normal iterations */
45 #define DEFAULT_SBITEROFS 100000 /**< additional number of allowed strong branching LP iterations */
46 #define DEFAULT_MAXLOOKAHEAD 9 /**< maximal number of further variables evaluated without better score */
47 #define DEFAULT_INITCAND 100 /**< maximal number of candidates initialized with strong branching per node */
48 #define DEFAULT_INITITER 0 /**< iteration limit for strong branching initialization of pseudo cost entries (0: auto) */
49 #define DEFAULT_MAXBDCHGS 5 /**< maximal number of bound tightenings before the node is reevaluated (-1: unlimited) */
50 #define DEFAULT_MAXPROPROUNDS -2 /**< maximum number of propagation rounds to be performed during strong branching
51  * before solving the LP (-1: no limit, -2: parameter settings) */
52 #define DEFAULT_PROBINGBOUNDS TRUE /**< should valid bounds be identified in a probing-like fashion during strong
53  * branching (only with propagation)? */
54 
55 
56 /** branching rule data */
57 struct SCIP_BranchruleData
58 {
59  SCIP_Real conflictweight; /**< weight in score calculations for conflict score */
60  SCIP_Real conflengthweight; /**< weight in score calculations for conflict length score */
61  SCIP_Real inferenceweight; /**< weight in score calculations for inference score */
62  SCIP_Real cutoffweight; /**< weight in score calculations for cutoff score */
63  SCIP_Real pscostweight; /**< weight in score calculations for pseudo cost score */
64  SCIP_Real minreliable; /**< minimal value for minimum pseudo cost size to regard pseudo cost value as reliable */
65  SCIP_Real maxreliable; /**< maximal value for minimum pseudo cost size to regard pseudo cost value as reliable */
66  SCIP_Real sbiterquot; /**< maximal fraction of strong branching LP iterations compared to normal iterations */
67  int sbiterofs; /**< additional number of allowed strong branching LP iterations */
68  int maxlookahead; /**< maximal number of further variables evaluated without better score */
69  int initcand; /**< maximal number of candidates initialized with strong branching per node */
70  int inititer; /**< iteration limit for strong branching initialization of pseudo cost entries (0: auto) */
71  int maxbdchgs; /**< maximal number of bound tightenings before the node is reevaluated (-1: unlimited) */
72  int maxproprounds; /**< maximum number of propagation rounds to be performed during strong branching
73  * before solving the LP (-1: no limit, -2: parameter settings) */
74  SCIP_Bool probingbounds; /**< should valid bounds be identified in a probing-like fashion during strong
75  * branching (only with propagation)? */
76 };
77 
78 
79 /*
80  * local methods
81  */
82 
83 /** calculates an overall score value for the given individual score values */
84 static
85 SCIP_Real calcScore(
86  SCIP* scip, /**< SCIP data structure */
87  SCIP_BRANCHRULEDATA* branchruledata, /**< branching rule data */
88  SCIP_Real conflictscore, /**< conflict score of current variable */
89  SCIP_Real avgconflictscore, /**< average conflict score */
90  SCIP_Real conflengthscore, /**< conflict length score of current variable */
91  SCIP_Real avgconflengthscore, /**< average conflict length score */
92  SCIP_Real inferencescore, /**< inference score of current variable */
93  SCIP_Real avginferencescore, /**< average inference score */
94  SCIP_Real cutoffscore, /**< cutoff score of current variable */
95  SCIP_Real avgcutoffscore, /**< average cutoff score */
96  SCIP_Real pscostscore, /**< pscost score of current variable */
97  SCIP_Real avgpscostscore, /**< average pscost score */
98  SCIP_Real frac /**< fractional value of variable in current solution */
99  )
100 {
101  SCIP_Real score;
102 
103  assert(branchruledata != NULL);
104  assert(0.0 < frac && frac < 1.0);
105 
106  score = branchruledata->conflictweight * (1.0 - 1.0/(1.0+conflictscore/avgconflictscore))
107  + branchruledata->conflengthweight * (1.0 - 1.0/(1.0+conflengthscore/avgconflengthscore))
108  + branchruledata->inferenceweight * (1.0 - 1.0/(1.0+inferencescore/avginferencescore))
109  + branchruledata->cutoffweight * (1.0 - 1.0/(1.0+cutoffscore/avgcutoffscore))
110  + branchruledata->pscostweight * (1.0 - 1.0/(1.0+pscostscore/avgpscostscore));
111 
112  /* avoid close to integral variables */
113  if( MIN(frac, 1.0 - frac) < 10.0*SCIPfeastol(scip) )
114  score *= 1e-6;
115 
116  return score;
117 }
118 
119 /** adds given index and direction to bound change arrays */
120 static
121 SCIP_RETCODE addBdchg(
122  SCIP* scip, /**< SCIP data structure */
123  int** bdchginds, /**< pointer to bound change index array */
124  SCIP_BOUNDTYPE** bdchgtypes, /**< pointer to bound change types array */
125  SCIP_Real** bdchgbounds, /**< pointer to bound change new bounds array */
126  int* nbdchgs, /**< pointer to number of bound changes */
127  int ind, /**< index to store in bound change index array */
128  SCIP_BOUNDTYPE type, /**< type of the bound change to store in bound change type array */
129  SCIP_Real bound /**< new bound to store in bound change new bounds array */
130  )
131 {
132  assert(bdchginds != NULL);
133  assert(bdchgtypes != NULL);
134  assert(bdchgbounds != NULL);
135  assert(nbdchgs != NULL);
136 
137  SCIP_CALL( SCIPreallocBufferArray(scip, bdchginds, (*nbdchgs) + 1) );
138  SCIP_CALL( SCIPreallocBufferArray(scip, bdchgtypes, (*nbdchgs) + 1) );
139  SCIP_CALL( SCIPreallocBufferArray(scip, bdchgbounds, (*nbdchgs) + 1) );
140  assert(*bdchginds != NULL);
141  assert(*bdchgtypes != NULL);
142  assert(*bdchgbounds != NULL);
143 
144  (*bdchginds)[*nbdchgs] = ind;
145  (*bdchgtypes)[*nbdchgs] = type;
146  (*bdchgbounds)[*nbdchgs] = bound;
147  (*nbdchgs)++;
148 
149  return SCIP_OKAY;
150 }
151 
152 /** frees bound change arrays */
153 static
154 void freeBdchgs(
155  SCIP* scip, /**< SCIP data structure */
156  int** bdchginds, /**< pointer to bound change index array */
157  SCIP_BOUNDTYPE** bdchgtypes, /**< pointer to bound change types array */
158  SCIP_Real** bdchgbounds, /**< pointer to bound change new bounds array */
159  int* nbdchgs /**< pointer to number of bound changes */
160  )
161 {
162  assert(bdchginds != NULL);
163  assert(bdchgtypes != NULL);
164  assert(bdchgbounds != NULL);
165  assert(nbdchgs != NULL);
166 
167  SCIPfreeBufferArrayNull(scip, bdchgbounds);
168  SCIPfreeBufferArrayNull(scip, bdchgtypes);
169  SCIPfreeBufferArrayNull(scip, bdchginds);
170  *nbdchgs = 0;
171 }
172 
173 /** applies bound changes stored in bound change arrays */
174 static
175 SCIP_RETCODE applyBdchgs(
176  SCIP* scip, /**< SCIP data structure */
177  SCIP_VAR** vars, /**< problem variables */
178  int* bdchginds, /**< bound change index array */
179  SCIP_BOUNDTYPE* bdchgtypes, /**< bound change types array */
180  SCIP_Real* bdchgbounds, /**< bound change new bound array */
181  int nbdchgs, /**< number of bound changes */
182  SCIP_RESULT* result /**< result pointer */
183  )
184 {
185 #ifndef NDEBUG
186  SCIP_BRANCHRULE* branchrule;
187  SCIP_BRANCHRULEDATA* branchruledata;
188 #endif
189  SCIP_Bool infeasible;
190  SCIP_Bool tightened;
191  int i;
192 
193  assert(vars != NULL);
194 
195 #ifndef NDEBUG
196  /* find branching rule */
197  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
198  assert(branchrule != NULL);
199 
200  /* get branching rule data */
201  branchruledata = SCIPbranchruleGetData(branchrule);
202  assert(branchruledata != NULL);
203 #endif
204 
205  SCIPdebugMessage("applying %d bound changes\n", nbdchgs);
206 
207  for( i = 0; i < nbdchgs; ++i )
208  {
209  int v;
210 
211  v = bdchginds[i];
212 
213  SCIPdebugMessage(" -> <%s> [%g,%g]\n",
214  SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v]));
215 
216  if( bdchgtypes[i] == SCIP_BOUNDTYPE_LOWER )
217  {
218  /* change lower bound of variable to given bound */
219  SCIP_CALL( SCIPtightenVarLb(scip, vars[v], bdchgbounds[i], TRUE, &infeasible, &tightened) );
220  if( infeasible )
221  {
222  *result = SCIP_CUTOFF;
223  return SCIP_OKAY;
224  }
225 
226  /* if we did propagation, the bound change might already have been added */
227  assert(tightened || (branchruledata->maxproprounds != 0));
228  }
229  else
230  {
231  assert(bdchgtypes[i] == SCIP_BOUNDTYPE_UPPER);
232 
233  /* change upper bound of variable to given bound */
234  SCIP_CALL( SCIPtightenVarUb(scip, vars[v], bdchgbounds[i], TRUE, &infeasible, &tightened) );
235  if( infeasible )
236  {
237  *result = SCIP_CUTOFF;
238  return SCIP_OKAY;
239  }
240 
241  /* if we did propagation, the bound change might already have been added */
242  assert(tightened || (branchruledata->maxproprounds != 0));
243  }
244  SCIPdebugMessage(" -> [%g,%g]\n", SCIPvarGetLbLocal(vars[v]), SCIPvarGetUbLocal(vars[v]));
245  }
246 
247  return SCIP_OKAY;
248 }
249 
250 /** execute reliability pseudo cost branching */
251 static
252 SCIP_RETCODE execRelpscost(
253  SCIP* scip, /**< SCIP data structure */
254  SCIP_BRANCHRULE* branchrule, /**< branching rule */
255  SCIP_Bool allowaddcons, /**< is the branching rule allowed to add constraints to the current node
256  * in order to cut off the current solution instead of creating a branching? */
257  SCIP_VAR** branchcands, /**< branching candidates */
258  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
259  SCIP_Real* branchcandsfrac, /**< fractional part of the branching candidates */
260  int nbranchcands, /**< number of branching candidates */
261  SCIP_RESULT* result /**< pointer to the result of the execution */
262  )
263 {
264  SCIP_BRANCHRULEDATA* branchruledata;
265  SCIP_Real lpobjval;
266  SCIP_Real bestsbdown;
267  SCIP_Real bestsbup;
268  SCIP_Real provedbound;
269  SCIP_Bool bestsbdownvalid;
270  SCIP_Bool bestsbupvalid;
271  SCIP_Bool bestsbdowncutoff;
272  SCIP_Bool bestsbupcutoff;
273  SCIP_Bool bestisstrongbranch;
274  SCIP_Bool allcolsinlp;
275  SCIP_Bool exactsolve;
276  int ninitcands;
277  int bestcand;
278 
279  *result = SCIP_DIDNOTRUN;
280 
281  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
282 
283  /* get branching rule data */
284  branchruledata = SCIPbranchruleGetData(branchrule);
285  assert(branchruledata != NULL);
286 
287  /* get current LP objective bound of the local sub problem and global cutoff bound */
288  lpobjval = SCIPgetLPObjval(scip);
289 
290  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
291  * for cutting off sub problems and improving lower bounds of children
292  */
293  exactsolve = SCIPisExactSolve(scip);
294 
295  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
296  allcolsinlp = SCIPallColsInLP(scip);
297 
298  bestcand = -1;
299  bestisstrongbranch = FALSE;
300  bestsbdown = SCIP_INVALID;
301  bestsbup = SCIP_INVALID;
302  bestsbdownvalid = FALSE;
303  bestsbupvalid = FALSE;
304  bestsbdowncutoff = FALSE;
305  bestsbupcutoff = FALSE;
306  provedbound = lpobjval;
307 
308  if( nbranchcands == 1 )
309  {
310  /* only one candidate: nothing has to be done */
311  bestcand = 0;
312  ninitcands = 0;
313  }
314  else
315  {
316  SCIP_SOL* bestsol;
317  SCIP_VAR** vars;
318  int* initcands;
319  SCIP_Real* initcandscores;
320  SCIP_Real* newlbs = NULL;
321  SCIP_Real* newubs = NULL;
322  int* bdchginds;
323  SCIP_BOUNDTYPE* bdchgtypes;
324  SCIP_Real* bdchgbounds;
325  int maxninitcands;
326  int nuninitcands;
327  int nbdchgs;
328  int nbdconflicts;
329  SCIP_Real avgconflictscore;
330  SCIP_Real avgconflengthscore;
331  SCIP_Real avginferencescore;
332  SCIP_Real avgcutoffscore;
333  SCIP_Real avgpscostscore;
334  SCIP_Real bestpsscore;
335  SCIP_Real bestpsfracscore;
336  SCIP_Real bestpsdomainscore;
337  SCIP_Real bestsbscore;
338  SCIP_Real bestuninitsbscore;
339  SCIP_Real bestsbfracscore;
340  SCIP_Real bestsbdomainscore;
341  SCIP_Real prio;
342  SCIP_Real reliable;
343  SCIP_Real maxlookahead;
344  SCIP_Real lookahead;
345  SCIP_Bool initstrongbranching;
346  SCIP_Bool propagate;
347  SCIP_Bool probingbounds;
348  SCIP_Longint nodenum;
349  SCIP_Longint nlpiterationsquot;
350  SCIP_Longint nsblpiterations;
351  SCIP_Longint maxnsblpiterations;
352  int maxbdchgs;
353  int bestpscand;
354  int bestsbcand;
355  int inititer;
356  int nvars;
357  int i;
358  int c;
359 
360  vars = SCIPgetVars(scip);
361  nvars = SCIPgetNVars(scip);
362 
363  bestsol = SCIPgetBestSol(scip);
364 
365  /* get average conflict, inference, and pseudocost scores */
366  avgconflictscore = SCIPgetAvgConflictScore(scip);
367  avgconflictscore = MAX(avgconflictscore, 0.1);
368  avgconflengthscore = SCIPgetAvgConflictlengthScore(scip);
369  avgconflengthscore = MAX(avgconflengthscore, 0.1);
370  avginferencescore = SCIPgetAvgInferenceScore(scip);
371  avginferencescore = MAX(avginferencescore, 0.1);
372  avgcutoffscore = SCIPgetAvgCutoffScore(scip);
373  avgcutoffscore = MAX(avgcutoffscore, 0.1);
374  avgpscostscore = SCIPgetAvgPseudocostScore(scip);
375  avgpscostscore = MAX(avgpscostscore, 0.1);
376 
377  initstrongbranching = FALSE;
378 
379  /* check whether propagation should be performed */
380  propagate = (branchruledata->maxproprounds != 0);
381 
382  /* check whether valid bounds should be identified in probing-like fashion */
383  probingbounds = propagate && branchruledata->probingbounds;
384 
385  /* get maximal number of candidates to initialize with strong branching; if the current solutions is not basic,
386  * we cannot warmstart the simplex algorithm and therefore don't initialize any candidates
387  */
388  maxninitcands = MIN(nbranchcands, branchruledata->initcand);
389  if( !SCIPisLPSolBasic(scip) )
390  maxninitcands = 0;
391 
392  /* calculate maximal number of strong branching LP iterations; if we used too many, don't apply strong branching
393  * any more
394  */
395  nlpiterationsquot = (SCIP_Longint)(branchruledata->sbiterquot * SCIPgetNNodeLPIterations(scip));
396  maxnsblpiterations = nlpiterationsquot + branchruledata->sbiterofs + SCIPgetNRootStrongbranchLPIterations(scip);
397  nsblpiterations = SCIPgetNStrongbranchLPIterations(scip);
398  if( nsblpiterations > maxnsblpiterations )
399  maxninitcands = 0;
400 
401  /* get buffer for storing the unreliable candidates */
402  SCIP_CALL( SCIPallocBufferArray(scip, &initcands, maxninitcands+1) ); /* allocate one additional slot for convenience */
403  SCIP_CALL( SCIPallocBufferArray(scip, &initcandscores, maxninitcands+1) );
404  ninitcands = 0;
405 
406  /* get current node number */
407  nodenum = SCIPgetNNodes(scip);
408 
409  /* initialize bound change arrays */
410  bdchginds = NULL;
411  bdchgtypes = NULL;
412  bdchgbounds = NULL;
413  nbdchgs = 0;
414  nbdconflicts = 0;
415  maxbdchgs = branchruledata->maxbdchgs;
416  if( maxbdchgs == -1 )
417  maxbdchgs = INT_MAX;
418 
419  /* calculate value used as reliability */
420  prio = (maxnsblpiterations - nsblpiterations)/(nsblpiterations + 1.0);
421  prio = MIN(prio, 1.0);
422  prio = MAX(prio, (nlpiterationsquot - nsblpiterations)/(nsblpiterations + 1.0));
423  reliable = (1.0-prio) * branchruledata->minreliable + prio * branchruledata->maxreliable;
424 
425  /* search for the best pseudo cost candidate, while remembering unreliable candidates in a sorted buffer */
426  nuninitcands = 0;
427  bestpscand = -1;
428  bestpsscore = -SCIPinfinity(scip);
429  bestpsfracscore = -SCIPinfinity(scip);
430  bestpsdomainscore = -SCIPinfinity(scip);
431  for( c = 0; c < nbranchcands; ++c )
432  {
433  SCIP_Real conflictscore;
434  SCIP_Real conflengthscore;
435  SCIP_Real inferencescore;
436  SCIP_Real cutoffscore;
437  SCIP_Real pscostscore;
438  SCIP_Real score;
439  SCIP_Bool usesb;
440 
441  assert(branchcands[c] != NULL);
442  assert(!SCIPisFeasIntegral(scip, branchcandssol[c]));
443 
444  /* get conflict, inference, cutoff, and pseudo cost scores for candidate */
445  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
446  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
447  inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
448  cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
449  pscostscore = SCIPgetVarPseudocostScore(scip, branchcands[c], branchcandssol[c]);
450  usesb = FALSE;
451 
452  /* don't use strong branching on variables that have already been initialized at the current node;
453  * instead replace the pseudo cost score with the already calculated one;
454  * @todo: use old data for strong branching with propagation?
455  */
456  if( SCIPgetVarStrongbranchNode(scip, branchcands[c]) == nodenum )
457  {
458  SCIP_Real down;
459  SCIP_Real up;
460  SCIP_Real lastlpobjval;
461  SCIP_Real downgain;
462  SCIP_Real upgain;
463 
464  /* use the score of the strong branching call at the current node */
465  SCIP_CALL( SCIPgetVarStrongbranchLast(scip, branchcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
466  downgain = MAX(down - lastlpobjval, 0.0);
467  upgain = MAX(up - lastlpobjval, 0.0);
468  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
469 
470  SCIPdebugMessage(" -> strong branching on variable <%s> already performed (down=%g (%+g), up=%g (%+g), pscostscore=%g)\n",
471  SCIPvarGetName(branchcands[c]), down, downgain, up, upgain, pscostscore);
472  }
473  else if( maxninitcands > 0 )
474  {
475  SCIP_Real downsize;
476  SCIP_Real upsize;
477  SCIP_Real size;
478 
479  /* check, if the pseudo cost score of the variable is reliable */
480  downsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_DOWNWARDS);
481  upsize = SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_UPWARDS);
482  size = MIN(downsize, upsize);
483 
484  /* use strong branching on variables with unreliable pseudo cost scores */
485  usesb = (size < reliable);
486 
487  /* count the number of variables that are completely uninitialized */
488  if( size < 0.1 )
489  nuninitcands++;
490  }
491 
492  /* combine the four score values */
493  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
494  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, branchcandsfrac[c]);
495 
496  if( usesb )
497  {
498  int j;
499 
500  /* pseudo cost of variable is not reliable: insert candidate in initcands buffer */
501  for( j = ninitcands; j > 0 && score > initcandscores[j-1]; --j )
502  {
503  initcands[j] = initcands[j-1];
504  initcandscores[j] = initcandscores[j-1];
505  }
506  initcands[j] = c;
507  initcandscores[j] = score;
508  ninitcands++;
509  ninitcands = MIN(ninitcands, maxninitcands);
510  }
511  else
512  {
513  /* variable will keep it's pseudo cost value: check for better score of candidate */
514  if( SCIPisSumGE(scip, score, bestpsscore) )
515  {
516  SCIP_Real fracscore;
517  SCIP_Real domainscore;
518 
519  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
520  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
521  if( SCIPisSumGT(scip, score, bestpsscore)
522  || SCIPisSumGT(scip, fracscore, bestpsfracscore)
523  || (SCIPisSumGE(scip, fracscore, bestpsfracscore) && domainscore > bestpsdomainscore) )
524  {
525  bestpscand = c;
526  bestpsscore = score;
527  bestpsfracscore = fracscore;
528  bestpsdomainscore = domainscore;
529  }
530  }
531  }
532  }
533 
534  /* initialize unreliable candidates with strong branching until maxlookahead is reached,
535  * search best strong branching candidate
536  */
537  maxlookahead = (SCIP_Real)branchruledata->maxlookahead * (1.0 + (SCIP_Real)nuninitcands/(SCIP_Real)nbranchcands);
538  inititer = branchruledata->inititer;
539  if( inititer == 0 )
540  {
541  SCIP_Longint nlpiterations;
542  SCIP_Longint nlps;
543 
544  /* iteration limit is set to twice the average number of iterations spent to resolve a dual feasible SCIP_LP;
545  * at the first few nodes, this average is not very exact, so we better increase the iteration limit on
546  * these very important nodes
547  */
548  nlpiterations = SCIPgetNDualResolveLPIterations(scip);
549  nlps = SCIPgetNDualResolveLPs(scip);
550  if( nlps == 0 )
551  {
552  nlpiterations = SCIPgetNNodeInitLPIterations(scip);
553  nlps = SCIPgetNNodeInitLPs(scip);
554  if( nlps == 0 )
555  {
556  nlpiterations = 1000;
557  nlps = 1;
558  }
559  }
560  assert(nlps >= 1);
561  inititer = (int)(2*nlpiterations / nlps);
562  inititer = (int)((SCIP_Real)inititer * (1.0 + 20.0/nodenum));
563  inititer = MAX(inititer, 10);
564  inititer = MIN(inititer, 500);
565  }
566 
567  SCIPdebugMessage("strong branching (reliable=%g, %d/%d cands, %d uninit, maxcands=%d, maxlookahead=%g, maxbdchgs=%d, inititer=%d, iterations:%"SCIP_LONGINT_FORMAT"/%"SCIP_LONGINT_FORMAT", basic:%u)\n",
568  reliable, ninitcands, nbranchcands, nuninitcands, maxninitcands, maxlookahead, maxbdchgs, inititer,
569  SCIPgetNStrongbranchLPIterations(scip), maxnsblpiterations, SCIPisLPSolBasic(scip));
570 
571  bestsbcand = -1;
572  bestsbscore = -SCIPinfinity(scip);
573  bestsbfracscore = -SCIPinfinity(scip);
574  bestsbdomainscore = -SCIPinfinity(scip);
575  lookahead = 0.0;
576  for( i = 0; i < ninitcands && lookahead < maxlookahead && nbdchgs + nbdconflicts < maxbdchgs
577  && (i < (int) maxlookahead || SCIPgetNStrongbranchLPIterations(scip) < maxnsblpiterations); ++i )
578  {
579  SCIP_Real down;
580  SCIP_Real up;
581  SCIP_Real downgain;
582  SCIP_Real upgain;
583  SCIP_Bool downvalid;
584  SCIP_Bool upvalid;
585  SCIP_Bool lperror;
586  SCIP_Bool downinf;
587  SCIP_Bool upinf;
588  SCIP_Bool downconflict;
589  SCIP_Bool upconflict;
590 
591  /* get candidate number to initialize */
592  c = initcands[i];
593  assert(!SCIPisFeasIntegral(scip, branchcandssol[c]));
594 
595  SCIPdebugMessage("init pseudo cost (%g/%g) of <%s> at %g (score:%g) with strong branching (%d iterations) -- %"SCIP_LONGINT_FORMAT"/%"SCIP_LONGINT_FORMAT" iterations\n",
596  SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_DOWNWARDS),
597  SCIPgetVarPseudocostCountCurrentRun(scip, branchcands[c], SCIP_BRANCHDIR_UPWARDS),
598  SCIPvarGetName(branchcands[c]), branchcandssol[c], initcandscores[i],
599  inititer, SCIPgetNStrongbranchLPIterations(scip), maxnsblpiterations);
600 
601  /* use strong branching on candidate */
602  if( !initstrongbranching )
603  {
604  initstrongbranching = TRUE;
605 
606  SCIP_CALL( SCIPstartStrongbranch(scip, propagate) );
607 
608  /* create arrays for probing-like bound tightening */
609  if( probingbounds )
610  {
611  SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
612  SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
613  }
614  }
615 
616  if( propagate )
617  {
618  /* apply strong branching */
619  SCIP_CALL( SCIPgetVarStrongbranchWithPropagation(scip, branchcands[c], branchcandssol[c], lpobjval, inititer,
620  branchruledata->maxproprounds, &down, &up, &downvalid, &upvalid, &downinf, &upinf,
621  &downconflict, &upconflict, &lperror, newlbs, newubs) );
622  }
623  else
624  {
625  /* apply strong branching */
626  SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, branchcands[c], inititer,
627  &down, &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
628  }
629 
630  /* check for an error in strong branching */
631  if( lperror )
632  {
633  if( !SCIPisStopped(scip) )
634  {
635  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
636  "(node %"SCIP_LONGINT_FORMAT") error in strong branching call for variable <%s> with solution %g\n",
637  SCIPgetNNodes(scip), SCIPvarGetName(branchcands[c]), branchcandssol[c]);
638  }
639  break;
640  }
641 
642  /* evaluate strong branching */
643  down = MAX(down, lpobjval);
644  up = MAX(up, lpobjval);
645  downgain = down - lpobjval;
646  upgain = up - lpobjval;
647  assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
648  assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
649  assert(downinf || !downconflict);
650  assert(upinf || !upconflict);
651 
652  /* Strong branching might have found a new primal solution which updated the cutoff bound. In this case, the
653  * provedbound computed before can be higher than the cutoffbound and the current node can be cut off.
654  * Additionally, also if the value for the current best candidate is valid and exceeds the new cutoff bound,
655  * we want to change the domain of this variable rather than branching on it.
656  */
657  if( SCIPgetBestSol(scip) != bestsol )
658  {
659  bestsol = SCIPgetBestSol(scip);
660 
661  SCIPdebugMessage(" -> strong branching on variable <%s> lead to a new incumbent\n",
662  SCIPvarGetName(branchcands[c]));
663 
664  /* proved bound for current node is larger than new cutoff bound -> cut off current node */
665  if( SCIPisGE(scip, provedbound, SCIPgetCutoffbound(scip)) )
666  {
667  SCIPdebugMessage(" -> node can be cut off (provedbound=%g, cutoff=%g)\n", provedbound, SCIPgetCutoffbound(scip));
668 
669  *result = SCIP_CUTOFF;
670  break; /* terminate initialization loop, because node is infeasible */
671  }
672  /* proved bound for down child of best candidate is larger than cutoff bound -> increase lower bound of best candidate */
673  else if( bestsbcand != -1 )
674  {
675  if( !bestsbdowncutoff && bestsbdownvalid && SCIPisGE(scip, bestsbdown, SCIPgetCutoffbound(scip)) )
676  {
677  bestsbdowncutoff = TRUE;
678 
679  SCIPdebugMessage(" -> valid dual bound for down child of best candidate <%s> is higher than new cutoff bound (valid=%u, bestsbdown=%g, cutoff=%g)\n",
680  SCIPvarGetName(branchcands[bestsbcand]), bestsbdownvalid, bestsbdown, SCIPgetCutoffbound(scip));
681 
682  SCIPdebugMessage(" -> increase lower bound of best candidate <%s> to %g\n",
683  SCIPvarGetName(branchcands[bestsbcand]), SCIPfeasCeil(scip, branchcandssol[bestsbcand]));
684 
685  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[bestsbcand]),
686  SCIP_BOUNDTYPE_LOWER, SCIPfeasCeil(scip, branchcandssol[bestsbcand])) );
687  }
688  /* proved bound for up child of best candidate is larger than cutoff bound -> decrease upper bound of best candidate */
689  else if( !bestsbupcutoff && bestsbupvalid && SCIPisGE(scip, bestsbup, SCIPgetCutoffbound(scip)) )
690  {
691  bestsbupcutoff = TRUE;
692 
693  SCIPdebugMessage(" -> valid dual bound for up child of best candidate <%s> is higher than new cutoff bound (valid=%u, bestsbup=%g, cutoff=%g)\n",
694  SCIPvarGetName(branchcands[bestsbcand]), bestsbupvalid, bestsbup, SCIPgetCutoffbound(scip));
695 
696  SCIPdebugMessage(" -> decrease upper bound of best candidate <%s> to %g\n",
697  SCIPvarGetName(branchcands[bestsbcand]), SCIPfeasFloor(scip, branchcandssol[bestsbcand]));
698 
699  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[bestsbcand]),
700  SCIP_BOUNDTYPE_UPPER, SCIPfeasFloor(scip, branchcandssol[bestsbcand])) );
701  }
702  }
703  }
704 
705  /* @todo: store pseudo cost only for valid bounds? and also if the other sb child was infeasible? */
706  if( !downinf && !upinf )
707  {
708  /* update pseudo cost values */
709  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchcands[c], 0.0-branchcandsfrac[c], downgain, 1.0) );
710  SCIP_CALL( SCIPupdateVarPseudocost(scip, branchcands[c], 1.0-branchcandsfrac[c], upgain, 1.0) );
711  }
712 
713  /* the minimal lower bound of both children is a proved lower bound of the current subtree */
714  if( allcolsinlp && !exactsolve && downvalid && upvalid )
715  {
716  SCIP_Real minbound;
717 
718  minbound = MIN(down, up);
719  provedbound = MAX(provedbound, minbound);
720  assert((downinf && upinf) || SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
721 
722  /* save probing-like bounds detected during strong branching */
723  if( probingbounds )
724  {
725  int v;
726 
727  assert(newlbs != NULL);
728  assert(newubs != NULL);
729 
730  for( v = 0; v < nvars; ++v )
731  {
732  if( SCIPisGT(scip, newlbs[v], SCIPvarGetLbLocal(vars[v])) )
733  {
734  SCIPdebugMessage("better lower bound for variable <%s>: %.9g -> %.9g (by strongbranching on <%s>)\n",
735  SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), newlbs[v], SCIPvarGetName(branchcands[c]));
736 
737  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, v,
738  SCIP_BOUNDTYPE_LOWER, newlbs[v]) );
739  }
740  if( SCIPisLT(scip, newubs[v], SCIPvarGetUbLocal(vars[v])) )
741  {
742  SCIPdebugMessage("better upper bound for variable <%s>: %.9g -> %.9g (by strongbranching on <%s>)\n",
743  SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), newubs[v], SCIPvarGetName(branchcands[c]));
744 
745  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, v,
746  SCIP_BOUNDTYPE_UPPER, newubs[v]) );
747  }
748  }
749 
750  if( nbdchgs + nbdconflicts >= maxbdchgs )
751  break; /* terminate initialization loop, because enough bound changes are performed */
752  }
753  }
754 
755  /* check if there are infeasible roundings */
756  if( downinf || upinf )
757  {
758  assert(allcolsinlp || propagate);
759  assert(!exactsolve);
760 
761  /* if for both infeasibilities, a conflict constraint was created, we don't need to fix the variable by hand,
762  * but better wait for the next propagation round to fix them as an inference, and potentially produce a
763  * cutoff that can be analyzed
764  */
765  if( allowaddcons && downinf == downconflict && upinf == upconflict )
766  {
767  SCIPdebugMessage(" -> variable <%s> is infeasible in %s: conflict constraint added\n",
768  SCIPvarGetName(branchcands[c]),
769  downinf && upinf ? "both directions" : (downinf ? "downward branch" : "upward branch"));
770  *result = SCIP_CONSADDED;
771  nbdconflicts++;
772  if( (downinf && upinf) || (nbdchgs + nbdconflicts >= maxbdchgs) )
773  break; /* terminate initialization loop, because enough roundings are performed or a cutoff was found */
774  }
775  else if( downinf && upinf )
776  {
777  /* both roundings are infeasible -> node is infeasible */
778  SCIPdebugMessage(" -> variable <%s> is infeasible in both directions (conflict: %u/%u)\n",
779  SCIPvarGetName(branchcands[c]), downconflict, upconflict);
780  *result = SCIP_CUTOFF;
781  break; /* terminate initialization loop, because node is infeasible */
782  }
783  else
784  {
785  /* rounding is infeasible in one direction -> round variable in other direction */
786  SCIPdebugMessage(" -> variable <%s> is infeasible in %s branch (conflict: %u/%u)\n",
787  SCIPvarGetName(branchcands[c]), downinf ? "downward" : "upward", downconflict, upconflict);
788  SCIP_CALL( addBdchg(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs, SCIPvarGetProbindex(branchcands[c]),
789  (downinf ? SCIP_BOUNDTYPE_LOWER : SCIP_BOUNDTYPE_UPPER),
790  (downinf ? SCIPfeasCeil(scip, branchcandssol[c]) : SCIPfeasFloor(scip, branchcandssol[c]))) );
791  if( nbdchgs + nbdconflicts >= maxbdchgs )
792  break; /* terminate initialization loop, because enough roundings are performed */
793  }
794  }
795  else
796  {
797  SCIP_Real conflictscore;
798  SCIP_Real conflengthscore;
799  SCIP_Real inferencescore;
800  SCIP_Real cutoffscore;
801  SCIP_Real pscostscore;
802  SCIP_Real score;
803 
804  /* check for a better score */
805  conflictscore = SCIPgetVarConflictScore(scip, branchcands[c]);
806  conflengthscore = SCIPgetVarConflictlengthScore(scip, branchcands[c]);
807  inferencescore = SCIPgetVarAvgInferenceScore(scip, branchcands[c]);
808  cutoffscore = SCIPgetVarAvgCutoffScore(scip, branchcands[c]);
809  pscostscore = SCIPgetBranchScore(scip, branchcands[c], downgain, upgain);
810  score = calcScore(scip, branchruledata, conflictscore, avgconflictscore, conflengthscore, avgconflengthscore,
811  inferencescore, avginferencescore, cutoffscore, avgcutoffscore, pscostscore, avgpscostscore, branchcandsfrac[c]);
812 
813  if( SCIPisSumGE(scip, score, bestsbscore) )
814  {
815  SCIP_Real fracscore;
816  SCIP_Real domainscore;
817 
818  fracscore = MIN(branchcandsfrac[c], 1.0 - branchcandsfrac[c]);
819  domainscore = -(SCIPvarGetUbLocal(branchcands[c]) - SCIPvarGetLbLocal(branchcands[c]));
820  if( SCIPisSumGT(scip, score, bestsbscore)
821  || SCIPisSumGT(scip, fracscore, bestsbfracscore)
822  || (SCIPisSumGE(scip, fracscore, bestsbfracscore) && domainscore > bestsbdomainscore) )
823  {
824  bestsbcand = c;
825  bestsbscore = score;
826  bestsbdown = down;
827  bestsbup = up;
828  bestsbdownvalid = downvalid;
829  bestsbupvalid = upvalid;
830  bestsbdowncutoff = FALSE;
831  bestsbupcutoff = FALSE;
832  bestsbfracscore = fracscore;
833  bestsbdomainscore = domainscore;
834  lookahead = 0.0;
835  }
836  else
837  lookahead += 0.5;
838  }
839  else
840  lookahead += 1.0;
841 
842  SCIPdebugMessage(" -> variable <%s> (solval=%g, down=%g (%+g,valid=%u), up=%g (%+g,valid=%u), score=%g/ %g/%g %g/%g -> %g)\n",
843  SCIPvarGetName(branchcands[c]), branchcandssol[c], down, downgain, downvalid, up, upgain, upvalid,
844  pscostscore, conflictscore, conflengthscore, inferencescore, cutoffscore, score);
845  }
846  }
847 #ifdef SCIP_DEBUG
848  if( bestsbcand >= 0 )
849  {
850  SCIPdebugMessage(" -> best: <%s> (%g / %g / %g), lookahead=%g/%g\n",
851  SCIPvarGetName(branchcands[bestsbcand]), bestsbscore, bestsbfracscore, bestsbdomainscore,
852  lookahead, maxlookahead);
853  }
854 #endif
855 
856  if( initstrongbranching )
857  {
858  if( probingbounds )
859  {
860  assert(newlbs != NULL);
861  assert(newubs != NULL);
862 
863  SCIPfreeBufferArray(scip, &newubs);
864  SCIPfreeBufferArray(scip, &newlbs);
865  }
866 
867  SCIP_CALL( SCIPendStrongbranch(scip) );
868  }
869 
870  /* get the score of the best uninitialized strong branching candidate */
871  if( i < ninitcands )
872  bestuninitsbscore = initcandscores[i];
873  else
874  bestuninitsbscore = -SCIPinfinity(scip);
875 
876  /* if the best pseudo cost candidate is better than the best uninitialized strong branching candidate,
877  * compare it to the best initialized strong branching candidate
878  */
879  if( bestpsscore > bestuninitsbscore && SCIPisSumGT(scip, bestpsscore, bestsbscore) )
880  {
881  bestcand = bestpscand;
882  bestisstrongbranch = FALSE;
883  }
884  else if( bestsbcand >= 0 )
885  {
886  bestcand = bestsbcand;
887  bestisstrongbranch = TRUE;
888  }
889  else
890  {
891  /* no candidate was initialized, and the best score is the one of the first candidate in the initialization
892  * queue
893  */
894  assert(ninitcands >= 1);
895  bestcand = initcands[0];
896  bestisstrongbranch = FALSE;
897  }
898 
899  /* apply domain reductions */
900  if( nbdchgs > 0 )
901  {
902  if( *result != SCIP_CUTOFF )
903  {
904  SCIP_CALL( applyBdchgs(scip, vars, bdchginds, bdchgtypes, bdchgbounds, nbdchgs, result) );
905  if( *result != SCIP_CUTOFF )
906  *result = SCIP_REDUCEDDOM;
907  }
908  freeBdchgs(scip, &bdchginds, &bdchgtypes, &bdchgbounds, &nbdchgs);
909  }
910 
911  /* free buffer for the unreliable candidates */
912  SCIPfreeBufferArray(scip, &initcandscores);
913  SCIPfreeBufferArray(scip, &initcands);
914  }
915 
916  /* if no domain could be reduced, create the branching */
917  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
918  {
919  SCIP_NODE* downchild;
920  SCIP_NODE* upchild;
921  SCIP_VAR* var;
922  SCIP_Real proveddown;
923  SCIP_Real provedup;
924 
925  assert(*result == SCIP_DIDNOTRUN);
926  assert(0 <= bestcand && bestcand < nbranchcands);
927  assert(!SCIPisFeasIntegral(scip, branchcandssol[bestcand]));
928  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
929  assert(!bestsbdowncutoff && !bestsbupcutoff);
930 
931  var = branchcands[bestcand];
932 
933  /* perform the branching */
934  SCIPdebugMessage(" -> %d (%d) cands, sel cand %d: var <%s> (sol=%g, down=%g (%+g), up=%g (%+g), sb=%u, psc=%g/%g [%g])\n",
935  nbranchcands, ninitcands, bestcand, SCIPvarGetName(var), branchcandssol[bestcand],
936  bestsbdown, bestsbdown - lpobjval, bestsbup, bestsbup - lpobjval, bestisstrongbranch,
937  SCIPgetVarPseudocostCurrentRun(scip, var, SCIP_BRANCHDIR_DOWNWARDS),
938  SCIPgetVarPseudocostCurrentRun(scip, var, SCIP_BRANCHDIR_UPWARDS),
939  SCIPgetVarPseudocostScoreCurrentRun(scip, var, branchcandssol[bestcand]));
940  SCIP_CALL( SCIPbranchVar(scip, var, &downchild, NULL, &upchild) );
941  assert(downchild != NULL);
942  assert(upchild != NULL);
943 
944  /* calculate proved lower bounds for children */
945  proveddown = provedbound;
946  provedup = provedbound;
947  if( bestisstrongbranch )
948  {
949  if( bestsbdownvalid )
950  proveddown = MAX(provedbound, bestsbdown);
951  if( bestsbupvalid )
952  provedup = MAX(provedbound, bestsbup);
953  }
954 
955  /* update the lower bounds in the children */
956  if( allcolsinlp && !exactsolve )
957  {
958  assert(SCIPisLT(scip, proveddown, SCIPgetCutoffbound(scip)));
959  assert(SCIPisLT(scip, provedup, SCIPgetCutoffbound(scip)));
960  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, proveddown) );
961  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, provedup) );
962  }
963  SCIPdebugMessage(" -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
964  SCIPdebugMessage(" -> up child's lowerbound : %g\n", SCIPnodeGetLowerbound(upchild));
965 
966  *result = SCIP_BRANCHED;
967  }
968  return SCIP_OKAY;
969 }
970 
971 
972 /*
973  * Callback methods
974  */
975 
976 /** copy method for branchrule plugins (called when SCIP copies plugins) */
977 static
978 SCIP_DECL_BRANCHCOPY(branchCopyRelpscost)
979 { /*lint --e{715}*/
980  assert(scip != NULL);
981  assert(branchrule != NULL);
982  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
983 
984  /* call inclusion method of branchrule */
985  SCIP_CALL( SCIPincludeBranchruleRelpscost(scip) );
986 
987  return SCIP_OKAY;
988 }
989 
990 /** destructor of branching rule to free user data (called when SCIP is exiting) */
991 static
992 SCIP_DECL_BRANCHFREE(branchFreeRelpscost)
993 { /*lint --e{715}*/
994  SCIP_BRANCHRULEDATA* branchruledata;
995 
996  /* free branching rule data */
997  branchruledata = SCIPbranchruleGetData(branchrule);
998  SCIPfreeMemory(scip, &branchruledata);
999  SCIPbranchruleSetData(branchrule, NULL);
1000 
1001  return SCIP_OKAY;
1002 }
1003 
1004 
1005 /** branching execution method for fractional LP solutions */
1006 static
1007 SCIP_DECL_BRANCHEXECLP(branchExeclpRelpscost)
1008 { /*lint --e{715}*/
1009  SCIP_VAR** tmplpcands;
1010  SCIP_VAR** lpcands;
1011  SCIP_Real* tmplpcandssol;
1012  SCIP_Real* lpcandssol;
1013  SCIP_Real* tmplpcandsfrac;
1014  SCIP_Real* lpcandsfrac;
1015  int nlpcands;
1016 
1017  assert(branchrule != NULL);
1018  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
1019  assert(scip != NULL);
1020  assert(result != NULL);
1021 
1022  SCIPdebugMessage("Execlp method of relpscost branching\n");
1023 
1024  /* get branching candidates */
1025  SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, NULL, &nlpcands, NULL) );
1026  assert(nlpcands > 0);
1027 
1028  /* copy LP banching candidates and solution values, because they will be updated w.r.t. the strong branching LP
1029  * solution
1030  */
1031  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) );
1032  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) );
1033  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) );
1034 
1035  /* execute branching rule */
1036  SCIP_CALL( execRelpscost(scip, branchrule, allowaddcons, lpcands, lpcandssol, lpcandsfrac, nlpcands, result) );
1037 
1038  SCIPfreeBufferArray(scip, &lpcandsfrac);
1039  SCIPfreeBufferArray(scip, &lpcandssol);
1040  SCIPfreeBufferArray(scip, &lpcands);
1041 
1042  return SCIP_OKAY;
1043 }
1044 
1045 
1046 /*
1047  * branching specific interface methods
1048  */
1049 
1050 /** creates the reliable pseudo cost branching rule and includes it in SCIP */
1051 SCIP_RETCODE SCIPincludeBranchruleRelpscost(
1052  SCIP* scip /**< SCIP data structure */
1053  )
1054 {
1055  SCIP_BRANCHRULEDATA* branchruledata;
1056  SCIP_BRANCHRULE* branchrule;
1057 
1058  /* create relpscost branching rule data */
1059  SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
1060 
1061  /* include branching rule */
1062  SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
1063  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
1064 
1065  assert(branchrule != NULL);
1066 
1067  /* set non-fundamental callbacks via specific setter functions*/
1068  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyRelpscost) );
1069  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeRelpscost) );
1070  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpRelpscost) );
1071 
1072  /* relpscost branching rule parameters */
1073  SCIP_CALL( SCIPaddRealParam(scip,
1074  "branching/relpscost/conflictweight",
1075  "weight in score calculations for conflict score",
1076  &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1077  SCIP_CALL( SCIPaddRealParam(scip,
1078  "branching/relpscost/conflictlengthweight",
1079  "weight in score calculations for conflict length score",
1080  &branchruledata->conflengthweight, TRUE, DEFAULT_CONFLENGTHWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1081  SCIP_CALL( SCIPaddRealParam(scip,
1082  "branching/relpscost/inferenceweight",
1083  "weight in score calculations for inference score",
1084  &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1085  SCIP_CALL( SCIPaddRealParam(scip,
1086  "branching/relpscost/cutoffweight",
1087  "weight in score calculations for cutoff score",
1088  &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1089  SCIP_CALL( SCIPaddRealParam(scip,
1090  "branching/relpscost/pscostweight",
1091  "weight in score calculations for pseudo cost score",
1092  &branchruledata->pscostweight, TRUE, DEFAULT_PSCOSTWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
1093  SCIP_CALL( SCIPaddRealParam(scip,
1094  "branching/relpscost/minreliable",
1095  "minimal value for minimum pseudo cost size to regard pseudo cost value as reliable",
1096  &branchruledata->minreliable, TRUE, DEFAULT_MINRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1097  SCIP_CALL( SCIPaddRealParam(scip,
1098  "branching/relpscost/maxreliable",
1099  "maximal value for minimum pseudo cost size to regard pseudo cost value as reliable",
1100  &branchruledata->maxreliable, TRUE, DEFAULT_MAXRELIABLE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1101  SCIP_CALL( SCIPaddRealParam(scip,
1102  "branching/relpscost/sbiterquot",
1103  "maximal fraction of strong branching LP iterations compared to node relaxation LP iterations",
1104  &branchruledata->sbiterquot, FALSE, DEFAULT_SBITERQUOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1105  SCIP_CALL( SCIPaddIntParam(scip,
1106  "branching/relpscost/sbiterofs",
1107  "additional number of allowed strong branching LP iterations",
1108  &branchruledata->sbiterofs, FALSE, DEFAULT_SBITEROFS, 0, INT_MAX, NULL, NULL) );
1109  SCIP_CALL( SCIPaddIntParam(scip,
1110  "branching/relpscost/maxlookahead",
1111  "maximal number of further variables evaluated without better score",
1112  &branchruledata->maxlookahead, TRUE, DEFAULT_MAXLOOKAHEAD, 1, INT_MAX, NULL, NULL) );
1113  SCIP_CALL( SCIPaddIntParam(scip,
1114  "branching/relpscost/initcand",
1115  "maximal number of candidates initialized with strong branching per node",
1116  &branchruledata->initcand, FALSE, DEFAULT_INITCAND, 0, INT_MAX, NULL, NULL) );
1117  SCIP_CALL( SCIPaddIntParam(scip,
1118  "branching/relpscost/inititer",
1119  "iteration limit for strong branching initializations of pseudo cost entries (0: auto)",
1120  &branchruledata->inititer, FALSE, DEFAULT_INITITER, 0, INT_MAX, NULL, NULL) );
1121  SCIP_CALL( SCIPaddIntParam(scip,
1122  "branching/relpscost/maxbdchgs",
1123  "maximal number of bound tightenings before the node is reevaluated (-1: unlimited)",
1124  &branchruledata->maxbdchgs, TRUE, DEFAULT_MAXBDCHGS, -1, INT_MAX, NULL, NULL) );
1125  SCIP_CALL( SCIPaddIntParam(scip,
1126  "branching/relpscost/maxproprounds",
1127  "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
1128  &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
1129  SCIP_CALL( SCIPaddBoolParam(scip,
1130  "branching/relpscost/probingbounds",
1131  "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
1132  &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
1133 
1134 
1135  return SCIP_OKAY;
1136 }
1137 
1138 /** execution reliability pseudo cost branching with the given branching candidates */
1139 SCIP_RETCODE SCIPexecRelpscostBranching(
1140  SCIP* scip, /**< SCIP data structure */
1141  SCIP_Bool allowaddcons, /**< is the branching rule allowed to add constraints to the current node
1142  * in order to cut off the current solution instead of creating a branching? */
1143  SCIP_VAR** branchcands, /**< branching candidates */
1144  SCIP_Real* branchcandssol, /**< solution value for the branching candidates */
1145  SCIP_Real* branchcandsfrac, /**< fractional part of the branching candidates */
1146  int nbranchcands, /**< number of branching candidates */
1147  SCIP_RESULT* result /**< pointer to the result of the execution */
1148  )
1149 {
1150  SCIP_BRANCHRULE* branchrule;
1151 
1152  assert(scip != NULL);
1153  assert(result != NULL);
1154 
1155  /* find branching rule */
1156  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
1157  assert(branchrule != NULL);
1158 
1159  /* execute branching rule */
1160  SCIP_CALL( execRelpscost(scip, branchrule, allowaddcons, branchcands, branchcandssol, branchcandsfrac, nbranchcands, result) );
1161 
1162  return SCIP_OKAY;
1163 }
1164