Scippy

SCIP

Solving Constraint Integer Programs

branch_fullstrong.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-2017 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_fullstrong.c
17  * @brief full strong LP branching rule
18  * @author Tobias Achterberg
19  * @author Gerald Gamrath
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_fullstrong.h"
28 
29 
30 #define BRANCHRULE_NAME "fullstrong"
31 #define BRANCHRULE_DESC "full strong branching"
32 #define BRANCHRULE_PRIORITY 0
33 #define BRANCHRULE_MAXDEPTH -1
34 #define BRANCHRULE_MAXBOUNDDIST 1.0
35 
36 #define DEFAULT_REEVALAGE 10LL /**< number of intermediate LPs solved to trigger reevaluation of strong branching
37  * value for a variable that was already evaluated at the current node */
38 #define DEFAULT_MAXPROPROUNDS -2 /**< maximum number of propagation rounds to be performed during strong branching
39  * before solving the LP (-1: no limit, -2: parameter settings) */
40 #define DEFAULT_PROBINGBOUNDS TRUE /**< should valid bounds be identified in a probing-like fashion during strong
41  * branching (only with propagation)? */
42 #define DEFAULT_FORCESTRONGBRANCH FALSE /**< should strong branching be applied even if there is just a single candidate? */
43 
44 
45 /** branching rule data */
46 struct SCIP_BranchruleData
47 {
48  SCIP_Longint reevalage; /**< number of intermediate LPs solved to trigger reevaluation of strong branching
49  * value for a variable that was already evaluated at the current node */
50  int maxproprounds; /**< maximum number of propagation rounds to be performed during strong branching
51  * before solving the LP (-1: no limit, -2: parameter settings) */
52  SCIP_Bool probingbounds; /**< should valid bounds be identified in a probing-like fashion during strong
53  * branching (only with propagation)? */
54  SCIP_Bool forcestrongbranch; /**< should strong branching be applied even if there is just a single candidate? */
55  int lastcand; /**< last evaluated candidate of last branching rule execution */
56  int skipsize; /**< size of skipdown and skipup array */
57  SCIP_Bool* skipdown; /**< should be branching on down child be skipped? */
58  SCIP_Bool* skipup; /**< should be branching on up child be skipped? */
59 };
60 
61 
62 /*
63  * Callback methods
64  */
65 
66 /** copy method for branchrule plugins (called when SCIP copies plugins) */
67 static
68 SCIP_DECL_BRANCHCOPY(branchCopyFullstrong)
69 { /*lint --e{715}*/
70  assert(scip != NULL);
71  assert(branchrule != NULL);
72  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
73 
74  /* call inclusion method of branchrule */
76 
77  return SCIP_OKAY;
78 }
79 
80 /** destructor of branching rule to free user data (called when SCIP is exiting) */
81 static
82 SCIP_DECL_BRANCHFREE(branchFreeFullstrong)
83 { /*lint --e{715}*/
84  SCIP_BRANCHRULEDATA* branchruledata;
85 
86  /* free branching rule data */
87  branchruledata = SCIPbranchruleGetData(branchrule);
88  assert(branchruledata != NULL);
89 
90  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipdown, branchruledata->skipsize);
91  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->skipup, branchruledata->skipsize);
92 
93  SCIPfreeBlockMemory(scip, &branchruledata);
94  SCIPbranchruleSetData(branchrule, NULL);
95 
96  return SCIP_OKAY;
97 }
98 
99 
100 /** initialization method of branching rule (called after problem was transformed) */
101 static
102 SCIP_DECL_BRANCHINIT(branchInitFullstrong)
103 { /*lint --e{715}*/
104  SCIP_BRANCHRULEDATA* branchruledata;
106  /* initialize branching rule data */
107  branchruledata = SCIPbranchruleGetData(branchrule);
108  assert(branchruledata != NULL);
109 
110  branchruledata->lastcand = 0;
111 
112  return SCIP_OKAY;
113 }
114 
115 /** deinitialization method of branching rule (called before transformed problem is freed) */
116 static
117 SCIP_DECL_BRANCHEXIT(branchExitFullstrong)
118 { /*lint --e{715}*/
119  SCIP_BRANCHRULEDATA* branchruledata;
121  /* initialize branching rule data */
122  branchruledata = SCIPbranchruleGetData(branchrule);
123  assert(branchruledata != NULL);
124  assert((branchruledata->skipdown != NULL) == (branchruledata->skipup != NULL));
125 
126  if( branchruledata->skipdown != NULL )
127  {
128  SCIPfreeBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize);
129  SCIPfreeBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize);
130  branchruledata->skipdown = NULL;
131  branchruledata->skipup = NULL;
132  branchruledata->skipsize = 0;
133  }
134 
135  return SCIP_OKAY;
136 }
137 
138 /**
139  * Selects a variable from a set of candidates by strong branching
140  *
141  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
142  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
143  *
144  * @note The variables in the lpcands array must have a fractional value in the current LP solution
145  */
147  SCIP* scip, /**< original SCIP data structure */
148  SCIP_VAR** lpcands, /**< branching candidates */
149  SCIP_Real* lpcandssol, /**< solution values of the branching candidates */
150  SCIP_Real* lpcandsfrac, /**< fractional values of the branching candidates */
151  SCIP_Bool* skipdown, /**< should down branchings be skipped? */
152  SCIP_Bool* skipup, /**< should up branchings be skipped? */
153  int nlpcands, /**< number of branching candidates */
154  int npriolpcands, /**< number of priority branching candidates */
155  int ncomplete, /**< number of branching candidates without skip */
156  int* start, /**< starting index in lpcands */
157  int maxproprounds, /**< maximum number of propagation rounds to be performed during strong
158  * branching before solving the LP (-1: no limit, -2: parameter settings) */
159  SCIP_Bool probingbounds, /**< should valid bounds be identified in a probing-like fashion during
160  * strong branching (only with propagation)? */
161  SCIP_Bool forcestrongbranch, /**< should strong branching be applied even if there is just a single candidate? */
162  int* bestcand, /**< best candidate for branching */
163  SCIP_Real* bestdown, /**< objective value of the down branch for bestcand */
164  SCIP_Real* bestup, /**< objective value of the up branch for bestcand */
165  SCIP_Real* bestscore, /**< score for bestcand */
166  SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */
167  SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */
168  SCIP_Real* provedbound, /**< proved dual bound for current subtree */
169  SCIP_RESULT* result /**< result pointer */
170  )
171 { /*lint --e{715}*/
172  SCIP_VAR** vars = NULL;
173  SCIP_Real* newlbs = NULL;
174  SCIP_Real* newubs = NULL;
175  SCIP_BRANCHRULE* branchrule;
176  SCIP_BRANCHRULEDATA* branchruledata;
177  SCIP_Longint reevalage;
178  SCIP_Longint nodenum;
179  SCIP_Real down;
180  SCIP_Real up;
181  SCIP_Real downgain;
182  SCIP_Real upgain;
183  SCIP_Real score;
184  SCIP_Real lpobjval;
185  SCIP_Bool exactsolve;
186  SCIP_Bool lperror;
187  SCIP_Bool allcolsinlp;
188  SCIP_Bool downvalid;
189  SCIP_Bool upvalid;
190  SCIP_Bool downinf;
191  SCIP_Bool upinf;
192  SCIP_Bool downconflict;
193  SCIP_Bool upconflict;
194  SCIP_Bool bothgains;
195  SCIP_Bool propagate;
196  int nvars = 0;
197  int nsbcalls;
198  int i;
199  int c;
200 
201  assert(scip != NULL);
202  assert(lpcands != NULL);
203  assert(lpcandssol != NULL);
204  assert(lpcandsfrac != NULL);
205  assert(bestcand != NULL);
206  assert(skipdown != NULL);
207  assert(skipup != NULL);
208  assert(bestdown != NULL);
209  assert(bestup != NULL);
210  assert(bestscore != NULL);
211  assert(bestdownvalid != NULL);
212  assert(bestupvalid != NULL);
213  assert(provedbound != NULL);
214  assert(result != NULL);
215  assert(nlpcands > 0);
216 
217  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
218  * for cutting off sub problems and improving lower bounds of children
219  */
220  exactsolve = SCIPisExactSolve(scip);
221 
222  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
223  allcolsinlp = SCIPallColsInLP(scip);
224 
225  /* get current node number */
226  nodenum = SCIPgetNNodes(scip);
227 
228  /* get current LP objective bound of the local sub problem and global cutoff bound */
229  lpobjval = SCIPgetLPObjval(scip);
230  *provedbound = lpobjval;
231 
232  *bestcand = 0;
233  *bestdown = lpobjval;
234  *bestup = lpobjval;
235  *bestdownvalid = TRUE;
236  *bestupvalid = TRUE;
237  *bestscore = -SCIPinfinity(scip);
238 
239  /* if only one candidate exists, choose this one without applying strong branching; also, when SCIP is about to be
240  * stopped, all strongbranching evaluations will be aborted anyway, thus we can return immediately
241  */
242  if( (!forcestrongbranch && nlpcands == 1) || SCIPisStopped(scip) )
243  return SCIP_OKAY;
244 
245  /* this assert may not hold if SCIP is stopped, thus we only check it here */
246  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
247 
248  /* get branching rule */
249  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
250  assert(branchrule != NULL);
251 
252  /* get branching rule data */
253  branchruledata = SCIPbranchruleGetData(branchrule);
254  assert(branchruledata != NULL);
255 
256  /* auto-setting for reevalage */
257  reevalage = branchruledata->reevalage;
258 
259  /* check whether propagation should be performed */
260  propagate = (maxproprounds != 0);
261 
262  /* if we don't do propagation, we cannot identify valid bounds in a probing-like fashion */
263  if( !propagate )
264  probingbounds = FALSE;
265 
266  /* create arrays for probing-like bound tightening */
267  if( probingbounds )
268  {
269  vars = SCIPgetVars(scip);
270  nvars = SCIPgetNVars(scip);
271 
272  SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
273  SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
274  }
275 
276  /* initialize strong branching */
277  SCIP_CALL( SCIPstartStrongbranch(scip, propagate) );
278 
279  /* search the full strong candidate
280  * cycle through the candidates, starting with the position evaluated in the last run
281  */
282  nsbcalls = 0;
283  bothgains = TRUE;
284  for( i = 0, c = *start; i < nlpcands && (!bothgains || i < ncomplete); ++i, ++c )
285  {
286  c = c % nlpcands;
287  assert(lpcands[c] != NULL);
288 
289  /* don't use strong branching on variables that have already been initialized at the current node,
290  * and that were evaluated not too long ago
291  */
292  if( SCIPgetVarStrongbranchNode(scip, lpcands[c]) == nodenum
293  && SCIPgetVarStrongbranchLPAge(scip, lpcands[c]) < reevalage )
294  {
295  SCIP_Real lastlpobjval;
296 
297  /* use the score of the strong branching call at the current node */
298  SCIP_CALL( SCIPgetVarStrongbranchLast(scip, lpcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
299  downgain = MAX(down - lastlpobjval, 0.0);
300  upgain = MAX(up - lastlpobjval, 0.0);
301  downvalid = FALSE;
302  upvalid = FALSE;
303  downinf = FALSE;
304  upinf = FALSE;
305  downconflict = FALSE;
306  upconflict = FALSE;
307  lperror = FALSE;
308  SCIPdebugMsg(scip, "strong branching on variable <%s> already performed (lpage=%" SCIP_LONGINT_FORMAT ", down=%g (%+g), up=%g (%+g))\n",
309  SCIPvarGetName(lpcands[c]), SCIPgetVarStrongbranchLPAge(scip, lpcands[c]), down, downgain, up, upgain);
310  }
311  else
312  {
313  SCIPdebugMsg(scip, "applying strong branching%s on variable <%s> with solution %g\n",
314  propagate ? "with propagation" : "", SCIPvarGetName(lpcands[c]), lpcandssol[c]);
315  assert(i >= ncomplete || (!skipdown[i] && !skipup[i]));
316 
317  /* apply strong branching */
318  up = -SCIPinfinity(scip);
319  down = -SCIPinfinity(scip);
320 
321  if( propagate )
322  {
323  SCIP_CALL( SCIPgetVarStrongbranchWithPropagation(scip, lpcands[c], lpcandssol[c], lpobjval, INT_MAX,
324  maxproprounds, skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid,
325  &upvalid, NULL, NULL, &downinf, &upinf, &downconflict, &upconflict, &lperror, newlbs, newubs) );
326 
327  SCIPdebugMsg(scip, "-> down=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u), up=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u)\n",
328  down, down - lpobjval, downvalid, downinf, downconflict, up, up - lpobjval, upvalid, upinf, upconflict);
329  }
330  else
331  {
332  SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, lpcands[c], INT_MAX,
333  skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf,
334  &downconflict, &upconflict, &lperror) );
335  }
336  nsbcalls++;
337 
338  /* display node information line */
339  if( SCIPgetDepth(scip) == 0 && nsbcalls % 100 == 0 )
340  {
342  }
343 
344  /* check for an error in strong branching */
345  if( lperror )
346  {
348  "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call%s for variable <%s> with solution %g\n",
349  SCIPgetNNodes(scip), propagate ? " with propagation" : "", SCIPvarGetName(lpcands[c]), lpcandssol[c]);
350  break;
351  }
352 
353  /* evaluate strong branching */
354  down = MAX(down, lpobjval);
355  up = MAX(up, lpobjval);
356  downgain = down - lpobjval;
357  upgain = up - lpobjval;
358  if( !SCIPisFeasZero(scip,downgain) && !SCIPisFeasZero(scip,upgain) )
359  bothgains = TRUE;
360 
361  assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
362  assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
363  assert(downinf || !downconflict);
364  assert(upinf || !upconflict);
365 
366  /* check if there are infeasible roundings */
367  if( downinf || upinf )
368  {
369  /* if we didn't do propagation, we can only detect infeasibility if the LP is a valid relaxation */
370  assert(allcolsinlp || propagate);
371  assert(!exactsolve);
372 
373  if( downinf && upinf )
374  {
375  /* both roundings are infeasible -> node is infeasible */
376  *result = SCIP_CUTOFF;
377  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions\n", SCIPvarGetName(lpcands[c]));
378  break; /* terminate initialization loop, because node is infeasible */
379  }
380  else if( downinf )
381  {
382  SCIP_Bool infeasible;
383  SCIP_Bool tightened;
384 
385  /* downwards rounding is infeasible -> change lower bound of variable to upward rounding */
386  SCIP_CALL( SCIPtightenVarLb(scip, lpcands[c], SCIPfeasCeil(scip, lpcandssol[c]), TRUE, &infeasible, &tightened) );
387  assert(!infeasible);
388 
389  /* if we did propagation, the bound change might already have been added */
390  assert(tightened || propagate);
391 
392  *result = SCIP_REDUCEDDOM;
393  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in downward branch\n", SCIPvarGetName(lpcands[c]));
394  break; /* terminate initialization loop, because LP was changed */
395  }
396  else
397  {
398  SCIP_Bool infeasible;
399  SCIP_Bool tightened;
400 
401  /* upwards rounding is infeasible -> change upper bound of variable to downward rounding */
402  assert(upinf);
403  SCIP_CALL( SCIPtightenVarUb(scip, lpcands[c], SCIPfeasFloor(scip, lpcandssol[c]), TRUE, &infeasible, &tightened) );
404  assert(!infeasible);
405 
406  /* if we did propagation, the bound change might already have been added */
407  assert(tightened || propagate);
408 
409  *result = SCIP_REDUCEDDOM;
410  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in upward branch\n", SCIPvarGetName(lpcands[c]));
411  break; /* terminate initialization loop, because LP was changed */
412  }
413  }
414  else if( allcolsinlp && !exactsolve && downvalid && upvalid )
415  {
416  SCIP_Real minbound;
417 
418  /* the minimal lower bound of both children is a proved lower bound of the current subtree */
419  minbound = MIN(down, up);
420  *provedbound = MAX(*provedbound, minbound);
421 
422  /* apply probing-like bounds detected during strong branching */
423  if( probingbounds )
424  {
425  int nboundchgs;
426  int v;
427 
428  assert(vars != NULL);
429  assert(nvars > 0);
430  assert(newlbs != NULL);
431  assert(newubs != NULL);
432 
433  nboundchgs = 0;
434 
435  for( v = 0; v < nvars; ++v )
436  {
437  if( SCIPisGT(scip, newlbs[v], SCIPvarGetLbLocal(vars[v])) )
438  {
439  SCIPdebugMsg(scip, "better lower bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
440  SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), newlbs[v], SCIPvarGetName(lpcands[c]));
441 
442  SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlbs[v]) );
443  ++nboundchgs;
444  }
445  if( SCIPisLT(scip, newubs[v], SCIPvarGetUbLocal(vars[v])) )
446  {
447  SCIPdebugMsg(scip, "better upper bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
448  SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), newubs[v], SCIPvarGetName(lpcands[c]));
449 
450  SCIP_CALL( SCIPchgVarUb(scip, vars[v], newubs[v]) );
451  ++nboundchgs;
452  }
453  }
454 
455  if( nboundchgs > 0 )
456  {
457  *result = SCIP_REDUCEDDOM;
458  SCIPdebugMsg(scip, " -> strong branching with propagation on variable <%s> led to %d bound changes\n",
459  SCIPvarGetName(lpcands[c]), nboundchgs);
460  break; /* terminate initialization loop, because LP was changed */
461  }
462  }
463  }
464 
465  /* update pseudo cost values */
466  assert(!downinf); /* otherwise, we would have terminated the initialization loop */
467  assert(!upinf);
468  SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[c], 0.0-lpcandsfrac[c], downgain, 1.0) );
469  SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[c], 1.0-lpcandsfrac[c], upgain, 1.0) );
470  }
471 
472  /* check for a better score, if we are within the maximum priority candidates */
473  if( c < npriolpcands )
474  {
475  score = SCIPgetBranchScore(scip, lpcands[c], downgain, upgain);
476  if( score > *bestscore )
477  {
478  *bestcand = c;
479  *bestdown = down;
480  *bestup = up;
481  *bestdownvalid = downvalid;
482  *bestupvalid = upvalid;
483  *bestscore = score;
484  }
485  }
486  else
487  {
488  SCIPdebug(score = 0.0;)
489  }
490 
491  SCIPdebugMsg(scip, " -> cand %d/%d (prio:%d) var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
492  c, nlpcands, npriolpcands, SCIPvarGetName(lpcands[c]), lpcandssol[c], downgain, upgain, score,
493  SCIPvarGetName(lpcands[*bestcand]), *bestscore);
494  }
495 
496  /* end strong branching */
498 
499  *start = c;
500 
501  if( probingbounds )
502  {
503  assert(newlbs != NULL);
504  assert(newubs != NULL);
505 
506  SCIPfreeBufferArray(scip, &newlbs);
507  SCIPfreeBufferArray(scip, &newubs);
508  }
509 
510  return SCIP_OKAY;
511 }
512 
513 /** branching execution method for fractional LP solutions */
514 static
515 SCIP_DECL_BRANCHEXECLP(branchExeclpFullstrong)
516 { /*lint --e{715}*/
517  SCIP_BRANCHRULEDATA* branchruledata;
518  SCIP_VAR** tmplpcands;
519  SCIP_VAR** lpcands;
520  SCIP_Real* tmplpcandssol;
521  SCIP_Real* lpcandssol;
522  SCIP_Real* tmplpcandsfrac;
523  SCIP_Real* lpcandsfrac;
524  SCIP_Real bestdown;
525  SCIP_Real bestup;
526  SCIP_Real bestscore;
527  SCIP_Real provedbound;
528  SCIP_Bool bestdownvalid;
529  SCIP_Bool bestupvalid;
530  int nlpcands;
531  int npriolpcands;
532  int bestcand;
533 
534  assert(branchrule != NULL);
535  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
536  assert(scip != NULL);
537  assert(result != NULL);
538 
539  SCIPdebugMsg(scip, "Execlp method of fullstrong branching\n");
540 
541  *result = SCIP_DIDNOTRUN;
542 
543  /* get branching rule data */
544  branchruledata = SCIPbranchruleGetData(branchrule);
545  assert(branchruledata != NULL);
546 
547  /* get branching candidates */
548  SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, &nlpcands, &npriolpcands, NULL) );
549  assert(nlpcands > 0);
550  assert(npriolpcands > 0);
551 
552  /* copy LP banching candidates and solution values, because they will be updated w.r.t. the strong branching LP
553  * solution
554  */
555  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) );
556  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) );
557  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) );
558 
559  if( branchruledata->skipdown == NULL )
560  {
561  assert(branchruledata->skipup == NULL);
562 
563  branchruledata->skipsize = SCIPgetNVars(scip);
564  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
565  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
566  BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
567  BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
568  }
569 
570  SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcands, lpcandssol, lpcandsfrac, branchruledata->skipdown,
571  branchruledata->skipup, nlpcands, npriolpcands, nlpcands, &branchruledata->lastcand,
572  branchruledata->maxproprounds, branchruledata->probingbounds, branchruledata->forcestrongbranch, &bestcand,
573  &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
574 
575  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
576  {
577  SCIP_NODE* downchild;
578  SCIP_NODE* upchild;
579  SCIP_VAR* var;
580  SCIP_Real val;
581  SCIP_Bool allcolsinlp;
582  SCIP_Bool exactsolve;
583 
584  assert(*result == SCIP_DIDNOTRUN);
585  assert(0 <= bestcand && bestcand < nlpcands);
586  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
587 
588  var = lpcands[bestcand];
589  val = lpcandssol[bestcand];
590 
591  /* perform the branching */
592  SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
593  nlpcands, bestcand, SCIPvarGetName(var), lpcandssol[bestcand], bestdown, bestup, bestscore);
594  SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, NULL, &upchild) );
595  assert(downchild != NULL);
596  assert(upchild != NULL);
597 
598  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
599  * for cutting off sub problems and improving lower bounds of children
600  */
601  exactsolve = SCIPisExactSolve(scip);
602 
603  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
604  allcolsinlp = SCIPallColsInLP(scip);
605 
606  /* update the lower bounds in the children */
607  if( allcolsinlp && !exactsolve )
608  {
609  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
610  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
611  }
612  SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
613  SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
614 
615  *result = SCIP_BRANCHED;
616  }
617 
618  SCIPfreeBufferArray(scip, &lpcandsfrac);
619  SCIPfreeBufferArray(scip, &lpcandssol);
620  SCIPfreeBufferArray(scip, &lpcands);
621 
622  return SCIP_OKAY;
623 }
624 
625 
626 /*
627  * branching specific interface methods
628  */
629 
630 /** creates the full strong LP branching rule and includes it in SCIP */
632  SCIP* scip /**< SCIP data structure */
633  )
634 {
635  SCIP_BRANCHRULEDATA* branchruledata;
636  SCIP_BRANCHRULE* branchrule;
637 
638  /* create fullstrong branching rule data */
639  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
640  branchruledata->lastcand = 0;
641  branchruledata->skipsize = 0;
642  branchruledata->skipup = NULL;
643  branchruledata->skipdown = NULL;
644 
645  /* include branching rule */
647  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
648 
649  assert(branchrule != NULL);
650 
651  /* set non-fundamental callbacks via specific setter functions*/
652  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyFullstrong) );
653  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeFullstrong) );
654  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitFullstrong) );
655  SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitFullstrong) );
656  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpFullstrong) );
657 
658  /* fullstrong branching rule parameters */
660  "branching/fullstrong/reevalage",
661  "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node",
662  &branchruledata->reevalage, TRUE, DEFAULT_REEVALAGE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
664  "branching/fullstrong/maxproprounds",
665  "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
666  &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
668  "branching/fullstrong/probingbounds",
669  "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
670  &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
672  "branching/fullstrong/forcestrongbranch",
673  "should strong branching be applied even if there is just a single candidate?",
674  &branchruledata->forcestrongbranch, TRUE, DEFAULT_FORCESTRONGBRANCH, NULL, NULL) );
675 
676  return SCIP_OKAY;
677 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip.c:36995
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:47357
static SCIP_DECL_BRANCHFREE(branchFreeFullstrong)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1810
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22517
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:43447
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7360
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17332
SCIP_RETCODE SCIPgetVarStrongbranchLast(SCIP *scip, SCIP_VAR *var, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Real *solval, SCIP_Real *lpobjval)
Definition: scip.c:21511
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:47009
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip.c:9171
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:9139
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
Definition: scip.c:45875
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPselectVarStrongBranching(SCIP *scip, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Bool *skipdown, SCIP_Bool *skipup, int nlpcands, int npriolpcands, int ncomplete, int *start, int maxproprounds, SCIP_Bool probingbounds, SCIP_Bool forcestrongbranch, int *bestcand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
#define BRANCHRULE_PRIORITY
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4293
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:47022
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:9123
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_DECL_BRANCHCOPY(branchCopyFullstrong)
SCIP_Longint SCIPgetVarStrongbranchNode(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21555
static SCIP_DECL_BRANCHINIT(branchInitFullstrong)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9269
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22633
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:22602
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.c:9086
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:22628
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:22010
#define SCIP_LONGINT_MAX
Definition: def.h:135
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:22585
#define SCIPdebugMsg
Definition: scip.h:455
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.c:4265
#define BRANCHRULE_MAXDEPTH
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:47429
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:47417
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9221
#define DEFAULT_MAXPROPROUNDS
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip.c:25991
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip.c:37450
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46970
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:22100
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16662
#define BRANCHRULE_DESC
#define SCIP_CALL(x)
Definition: def.h:350
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:37680
SCIP_Longint SCIPgetVarStrongbranchLPAge(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21589
#define DEFAULT_REEVALAGE
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1360
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip.c:20169
full strong LP branching rule
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:29287
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:43039
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip.c:13574
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1820
SCIP_RETCODE SCIPgetVarStrongbranchWithPropagation(SCIP *scip, SCIP_VAR *var, SCIP_Real solval, SCIP_Real lpobjval, int itlim, int maxproprounds, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Longint *ndomredsdown, SCIP_Longint *ndomredsup, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror, SCIP_Real *newlbs, SCIP_Real *newubs)
Definition: scip.c:20856
#define MAX(x, y)
Definition: tclique_def.h:75
#define DEFAULT_FORCESTRONGBRANCH
#define BRANCHRULE_NAME
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11806
#define BRANCHRULE_MAXBOUNDDIST
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:29366
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46996
static SCIP_DECL_BRANCHEXIT(branchExitFullstrong)
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
Definition: scip.c:20228
SCIP_RETCODE SCIPincludeBranchruleFullstrong(SCIP *scip)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11761
#define SCIP_Real
Definition: def.h:149
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1932
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1145
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip.c:9155
static SCIP_DECL_BRANCHEXECLP(branchExeclpFullstrong)
#define SCIP_Longint
Definition: def.h:134
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:29713
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17342
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:22605
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:112
SCIP_RETCODE SCIPgetVarStrongbranchFrac(SCIP *scip, SCIP_VAR *var, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror)
Definition: scip.c:20403
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:42127
#define DEFAULT_PROBINGBOUNDS
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip.c:1032
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4239