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  SCIP_Bool allowaddcons, /**< is the branching rule allowed to add constraints? */
158  int maxproprounds, /**< maximum number of propagation rounds to be performed during strong
159  * branching before solving the LP (-1: no limit, -2: parameter settings) */
160  SCIP_Bool probingbounds, /**< should valid bounds be identified in a probing-like fashion during
161  * strong branching (only with propagation)? */
162  SCIP_Bool forcestrongbranch, /**< should strong branching be applied even if there is just a single candidate? */
163  int* bestcand, /**< best candidate for branching */
164  SCIP_Real* bestdown, /**< objective value of the down branch for bestcand */
165  SCIP_Real* bestup, /**< objective value of the up branch for bestcand */
166  SCIP_Real* bestscore, /**< score for bestcand */
167  SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */
168  SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */
169  SCIP_Real* provedbound, /**< proved dual bound for current subtree */
170  SCIP_RESULT* result /**< result pointer */
171  )
172 {
173  SCIP_VAR** vars = NULL;
174  SCIP_Real* newlbs = NULL;
175  SCIP_Real* newubs = NULL;
176  SCIP_BRANCHRULE* branchrule;
177  SCIP_BRANCHRULEDATA* branchruledata;
178  SCIP_Longint reevalage;
179  SCIP_Longint nodenum;
180  SCIP_Real down;
181  SCIP_Real up;
182  SCIP_Real downgain;
183  SCIP_Real upgain;
184  SCIP_Real score;
185  SCIP_Real lpobjval;
186  SCIP_Bool exactsolve;
187  SCIP_Bool lperror;
188  SCIP_Bool allcolsinlp;
189  SCIP_Bool downvalid;
190  SCIP_Bool upvalid;
191  SCIP_Bool downinf;
192  SCIP_Bool upinf;
193  SCIP_Bool downconflict;
194  SCIP_Bool upconflict;
195  SCIP_Bool bothgains;
196  SCIP_Bool propagate;
197  int nvars = 0;
198  int nsbcalls;
199  int i;
200  int c;
201 
202  assert(scip != NULL);
203  assert(lpcands != NULL);
204  assert(lpcandssol != NULL);
205  assert(lpcandsfrac != NULL);
206  assert(bestcand != NULL);
207  assert(skipdown != NULL);
208  assert(skipup != NULL);
209  assert(bestdown != NULL);
210  assert(bestup != NULL);
211  assert(bestscore != NULL);
212  assert(bestdownvalid != NULL);
213  assert(bestupvalid != NULL);
214  assert(provedbound != NULL);
215  assert(result != NULL);
216  assert(nlpcands > 0);
217 
218  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
219  * for cutting off sub problems and improving lower bounds of children
220  */
221  exactsolve = SCIPisExactSolve(scip);
222 
223  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
224  allcolsinlp = SCIPallColsInLP(scip);
225 
226  /* get current node number */
227  nodenum = SCIPgetNNodes(scip);
228 
229  /* get current LP objective bound of the local sub problem and global cutoff bound */
230  lpobjval = SCIPgetLPObjval(scip);
231  *provedbound = lpobjval;
232 
233  *bestcand = 0;
234  *bestdown = lpobjval;
235  *bestup = lpobjval;
236  *bestdownvalid = TRUE;
237  *bestupvalid = TRUE;
238  *bestscore = -SCIPinfinity(scip);
239 
240  /* if only one candidate exists, choose this one without applying strong branching; also, when SCIP is about to be
241  * stopped, all strongbranching evaluations will be aborted anyway, thus we can return immediately
242  */
243  if( (!forcestrongbranch && nlpcands == 1) || SCIPisStopped(scip) )
244  return SCIP_OKAY;
245 
246  /* this assert may not hold if SCIP is stopped, thus we only check it here */
247  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
248 
249  /* get branching rule */
250  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
251  assert(branchrule != NULL);
252 
253  /* get branching rule data */
254  branchruledata = SCIPbranchruleGetData(branchrule);
255  assert(branchruledata != NULL);
256 
257  /* auto-setting for reevalage */
258  reevalage = branchruledata->reevalage;
259 
260  /* check whether propagation should be performed */
261  propagate = (maxproprounds != 0);
262 
263  /* if we don't do propagation, we cannot identify valid bounds in a probing-like fashion */
264  if( !propagate )
265  probingbounds = FALSE;
266 
267  /* create arrays for probing-like bound tightening */
268  if( probingbounds )
269  {
270  vars = SCIPgetVars(scip);
271  nvars = SCIPgetNVars(scip);
272 
273  SCIP_CALL( SCIPallocBufferArray(scip, &newlbs, nvars) );
274  SCIP_CALL( SCIPallocBufferArray(scip, &newubs, nvars) );
275  }
276 
277  /* initialize strong branching */
278  SCIP_CALL( SCIPstartStrongbranch(scip, propagate) );
279 
280  /* search the full strong candidate
281  * cycle through the candidates, starting with the position evaluated in the last run
282  */
283  nsbcalls = 0;
284  bothgains = TRUE;
285  for( i = 0, c = *start; i < nlpcands && (!bothgains || i < ncomplete); ++i, ++c )
286  {
287  c = c % nlpcands;
288  assert(lpcands[c] != NULL);
289 
290  /* don't use strong branching on variables that have already been initialized at the current node,
291  * and that were evaluated not too long ago
292  */
293  if( SCIPgetVarStrongbranchNode(scip, lpcands[c]) == nodenum
294  && SCIPgetVarStrongbranchLPAge(scip, lpcands[c]) < reevalage )
295  {
296  SCIP_Real lastlpobjval;
297 
298  /* use the score of the strong branching call at the current node */
299  SCIP_CALL( SCIPgetVarStrongbranchLast(scip, lpcands[c], &down, &up, NULL, NULL, NULL, &lastlpobjval) );
300  downgain = MAX(down - lastlpobjval, 0.0);
301  upgain = MAX(up - lastlpobjval, 0.0);
302  downvalid = FALSE;
303  upvalid = FALSE;
304  downinf = FALSE;
305  upinf = FALSE;
306  downconflict = FALSE;
307  upconflict = FALSE;
308  lperror = FALSE;
309  SCIPdebugMsg(scip, "strong branching on variable <%s> already performed (lpage=%" SCIP_LONGINT_FORMAT ", down=%g (%+g), up=%g (%+g))\n",
310  SCIPvarGetName(lpcands[c]), SCIPgetVarStrongbranchLPAge(scip, lpcands[c]), down, downgain, up, upgain);
311  }
312  else
313  {
314  SCIPdebugMsg(scip, "applying strong branching%s on variable <%s> with solution %g\n",
315  propagate ? "with propagation" : "", SCIPvarGetName(lpcands[c]), lpcandssol[c]);
316  assert(i >= ncomplete || (!skipdown[i] && !skipup[i]));
317 
318  /* apply strong branching */
319  up = -SCIPinfinity(scip);
320  down = -SCIPinfinity(scip);
321 
322  if( propagate )
323  {
324  SCIP_CALL( SCIPgetVarStrongbranchWithPropagation(scip, lpcands[c], lpcandssol[c], lpobjval, INT_MAX,
325  maxproprounds, skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid,
326  &upvalid, NULL, NULL, &downinf, &upinf, &downconflict, &upconflict, &lperror, newlbs, newubs) );
327 
328  SCIPdebugMsg(scip, "-> down=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u), up=%.9g (gain=%.9g, valid=%u, inf=%u, conflict=%u)\n",
329  down, down - lpobjval, downvalid, downinf, downconflict, up, up - lpobjval, upvalid, upinf, upconflict);
330  }
331  else
332  {
333  SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, lpcands[c], INT_MAX,
334  skipdown[i] ? NULL : &down, skipup[i] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf,
335  &downconflict, &upconflict, &lperror) );
336  }
337  nsbcalls++;
338 
339  /* display node information line */
340  if( SCIPgetDepth(scip) == 0 && nsbcalls % 100 == 0 )
341  {
343  }
344 
345  /* check for an error in strong branching */
346  if( lperror )
347  {
349  "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call%s for variable <%s> with solution %g\n",
350  SCIPgetNNodes(scip), propagate ? " with propagation" : "", SCIPvarGetName(lpcands[c]), lpcandssol[c]);
351  break;
352  }
353 
354  /* evaluate strong branching */
355  down = MAX(down, lpobjval);
356  up = MAX(up, lpobjval);
357  downgain = down - lpobjval;
358  upgain = up - lpobjval;
359  if( !SCIPisFeasZero(scip,downgain) && !SCIPisFeasZero(scip,upgain) )
360  bothgains = TRUE;
361 
362  assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
363  assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
364  assert(downinf || !downconflict);
365  assert(upinf || !upconflict);
366 
367  /* check if there are infeasible roundings */
368  if( downinf || upinf )
369  {
370  /* if we didn't do propagation, we can only detect infeasibility if the LP is a valid relaxation */
371  assert(allcolsinlp || propagate);
372  assert(!exactsolve);
373 
374  /* if for both infeasibilities, a conflict constraint was created, we don't need to fix the variable by
375  * hand, but better wait for the next propagation round to fix them as an inference, and potentially
376  * produce a cutoff that can be analyzed
377  */
378  if( allowaddcons && downinf == downconflict && upinf == upconflict )
379  {
380  *result = SCIP_CONSADDED;
381  break; /* terminate initialization loop, because constraint was added */
382  }
383  else if( downinf && upinf )
384  {
385  /* both roundings are infeasible -> node is infeasible */
386  *result = SCIP_CUTOFF;
387  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions\n", SCIPvarGetName(lpcands[c]));
388  break; /* terminate initialization loop, because node is infeasible */
389  }
390  else if( downinf )
391  {
392  SCIP_Bool infeasible;
393  SCIP_Bool tightened;
394 
395  /* downwards rounding is infeasible -> change lower bound of variable to upward rounding */
396  SCIP_CALL( SCIPtightenVarLb(scip, lpcands[c], SCIPfeasCeil(scip, lpcandssol[c]), TRUE, &infeasible, &tightened) );
397  assert(!infeasible);
398 
399  /* if we did propagation, the bound change might already have been added */
400  assert(tightened || propagate);
401 
402  *result = SCIP_REDUCEDDOM;
403  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in downward branch\n", SCIPvarGetName(lpcands[c]));
404  break; /* terminate initialization loop, because LP was changed */
405  }
406  else
407  {
408  SCIP_Bool infeasible;
409  SCIP_Bool tightened;
410 
411  /* upwards rounding is infeasible -> change upper bound of variable to downward rounding */
412  assert(upinf);
413  SCIP_CALL( SCIPtightenVarUb(scip, lpcands[c], SCIPfeasFloor(scip, lpcandssol[c]), TRUE, &infeasible, &tightened) );
414  assert(!infeasible);
415 
416  /* if we did propagation, the bound change might already have been added */
417  assert(tightened || propagate);
418 
419  *result = SCIP_REDUCEDDOM;
420  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in upward branch\n", SCIPvarGetName(lpcands[c]));
421  break; /* terminate initialization loop, because LP was changed */
422  }
423  }
424  else if( allcolsinlp && !exactsolve && downvalid && upvalid )
425  {
426  SCIP_Real minbound;
427 
428  /* the minimal lower bound of both children is a proved lower bound of the current subtree */
429  minbound = MIN(down, up);
430  *provedbound = MAX(*provedbound, minbound);
431 
432  /* apply probing-like bounds detected during strong branching */
433  if( probingbounds )
434  {
435  int nboundchgs;
436  int v;
437 
438  assert(vars != NULL);
439  assert(nvars > 0);
440  assert(newlbs != NULL);
441  assert(newubs != NULL);
442 
443  nboundchgs = 0;
444 
445  for( v = 0; v < nvars; ++v )
446  {
447  if( SCIPisGT(scip, newlbs[v], SCIPvarGetLbLocal(vars[v])) )
448  {
449  SCIPdebugMsg(scip, "better lower bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
450  SCIPvarGetName(vars[v]), SCIPvarGetLbLocal(vars[v]), newlbs[v], SCIPvarGetName(lpcands[c]));
451 
452  SCIP_CALL( SCIPchgVarLb(scip, vars[v], newlbs[v]) );
453  ++nboundchgs;
454  }
455  if( SCIPisLT(scip, newubs[v], SCIPvarGetUbLocal(vars[v])) )
456  {
457  SCIPdebugMsg(scip, "better upper bound for variable <%s>: %.9g -> %.9g (strongbranching on var <%s>\n",
458  SCIPvarGetName(vars[v]), SCIPvarGetUbLocal(vars[v]), newubs[v], SCIPvarGetName(lpcands[c]));
459 
460  SCIP_CALL( SCIPchgVarUb(scip, vars[v], newubs[v]) );
461  ++nboundchgs;
462  }
463  }
464 
465  if( nboundchgs > 0 )
466  {
467  *result = SCIP_REDUCEDDOM;
468  SCIPdebugMsg(scip, " -> strong branching with propagation on variable <%s> led to %d bound changes\n",
469  SCIPvarGetName(lpcands[c]), nboundchgs);
470  break; /* terminate initialization loop, because LP was changed */
471  }
472  }
473  }
474 
475  /* update pseudo cost values */
476  assert(!downinf); /* otherwise, we would have terminated the initialization loop */
477  assert(!upinf);
478  SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[c], 0.0-lpcandsfrac[c], downgain, 1.0) );
479  SCIP_CALL( SCIPupdateVarPseudocost(scip, lpcands[c], 1.0-lpcandsfrac[c], upgain, 1.0) );
480  }
481 
482  /* check for a better score, if we are within the maximum priority candidates */
483  if( c < npriolpcands )
484  {
485  score = SCIPgetBranchScore(scip, lpcands[c], downgain, upgain);
486  if( score > *bestscore )
487  {
488  *bestcand = c;
489  *bestdown = down;
490  *bestup = up;
491  *bestdownvalid = downvalid;
492  *bestupvalid = upvalid;
493  *bestscore = score;
494  }
495  }
496  else
497  {
498  SCIPdebug(score = 0.0;)
499  }
500 
501  SCIPdebugMsg(scip, " -> cand %d/%d (prio:%d) var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
502  c, nlpcands, npriolpcands, SCIPvarGetName(lpcands[c]), lpcandssol[c], downgain, upgain, score,
503  SCIPvarGetName(lpcands[*bestcand]), *bestscore);
504  }
505 
506  /* end strong branching */
508 
509  *start = c;
510 
511  if( probingbounds )
512  {
513  assert(newlbs != NULL);
514  assert(newubs != NULL);
515 
516  SCIPfreeBufferArray(scip, &newlbs);
517  SCIPfreeBufferArray(scip, &newubs);
518  }
519 
520  return SCIP_OKAY;
521 }
522 
523 /** branching execution method for fractional LP solutions */
524 static
525 SCIP_DECL_BRANCHEXECLP(branchExeclpFullstrong)
526 { /*lint --e{715}*/
527  SCIP_BRANCHRULEDATA* branchruledata;
528  SCIP_VAR** tmplpcands;
529  SCIP_VAR** lpcands;
530  SCIP_Real* tmplpcandssol;
531  SCIP_Real* lpcandssol;
532  SCIP_Real* tmplpcandsfrac;
533  SCIP_Real* lpcandsfrac;
534  SCIP_Real bestdown;
535  SCIP_Real bestup;
536  SCIP_Real bestscore;
537  SCIP_Real provedbound;
538  SCIP_Bool bestdownvalid;
539  SCIP_Bool bestupvalid;
540  int nlpcands;
541  int npriolpcands;
542  int bestcand;
543 
544  assert(branchrule != NULL);
545  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
546  assert(scip != NULL);
547  assert(result != NULL);
548 
549  SCIPdebugMsg(scip, "Execlp method of fullstrong branching\n");
550 
551  *result = SCIP_DIDNOTRUN;
552 
553  /* get branching rule data */
554  branchruledata = SCIPbranchruleGetData(branchrule);
555  assert(branchruledata != NULL);
556 
557  /* get branching candidates */
558  SCIP_CALL( SCIPgetLPBranchCands(scip, &tmplpcands, &tmplpcandssol, &tmplpcandsfrac, &nlpcands, &npriolpcands, NULL) );
559  assert(nlpcands > 0);
560  assert(npriolpcands > 0);
561 
562  /* copy LP banching candidates and solution values, because they will be updated w.r.t. the strong branching LP
563  * solution
564  */
565  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcands, tmplpcands, nlpcands) );
566  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandssol, tmplpcandssol, nlpcands) );
567  SCIP_CALL( SCIPduplicateBufferArray(scip, &lpcandsfrac, tmplpcandsfrac, nlpcands) );
568 
569  if( branchruledata->skipdown == NULL )
570  {
571  assert(branchruledata->skipup == NULL);
572 
573  branchruledata->skipsize = SCIPgetNVars(scip);
574  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipdown, branchruledata->skipsize) );
575  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->skipup, branchruledata->skipsize) );
576  BMSclearMemoryArray(branchruledata->skipdown, branchruledata->skipsize);
577  BMSclearMemoryArray(branchruledata->skipup, branchruledata->skipsize);
578  }
579 
580  SCIP_CALL( SCIPselectVarStrongBranching(scip, lpcands, lpcandssol, lpcandsfrac, branchruledata->skipdown,
581  branchruledata->skipup, nlpcands, npriolpcands, nlpcands, &branchruledata->lastcand, allowaddcons,
582  branchruledata->maxproprounds, branchruledata->probingbounds, branchruledata->forcestrongbranch, &bestcand,
583  &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
584 
585  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
586  {
587  SCIP_NODE* downchild;
588  SCIP_NODE* upchild;
589  SCIP_VAR* var;
590  SCIP_Real val;
591  SCIP_Bool allcolsinlp;
592  SCIP_Bool exactsolve;
593 
594  assert(*result == SCIP_DIDNOTRUN);
595  assert(0 <= bestcand && bestcand < nlpcands);
596  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
597 
598  var = lpcands[bestcand];
599  val = lpcandssol[bestcand];
600 
601  /* perform the branching */
602  SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (solval=%g, down=%g, up=%g, score=%g)\n",
603  nlpcands, bestcand, SCIPvarGetName(var), lpcandssol[bestcand], bestdown, bestup, bestscore);
604  SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, NULL, &upchild) );
605  assert(downchild != NULL);
606  assert(upchild != NULL);
607 
608  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
609  * for cutting off sub problems and improving lower bounds of children
610  */
611  exactsolve = SCIPisExactSolve(scip);
612 
613  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
614  allcolsinlp = SCIPallColsInLP(scip);
615 
616  /* update the lower bounds in the children */
617  if( allcolsinlp && !exactsolve )
618  {
619  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
620  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
621  }
622  SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
623  SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
624 
625  *result = SCIP_BRANCHED;
626  }
627 
628  SCIPfreeBufferArray(scip, &lpcandsfrac);
629  SCIPfreeBufferArray(scip, &lpcandssol);
630  SCIPfreeBufferArray(scip, &lpcands);
631 
632  return SCIP_OKAY;
633 }
634 
635 
636 /*
637  * branching specific interface methods
638  */
639 
640 /** creates the full strong LP branching rule and includes it in SCIP */
642  SCIP* scip /**< SCIP data structure */
643  )
644 {
645  SCIP_BRANCHRULEDATA* branchruledata;
646  SCIP_BRANCHRULE* branchrule;
647 
648  /* create fullstrong branching rule data */
649  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
650  branchruledata->lastcand = 0;
651  branchruledata->skipsize = 0;
652  branchruledata->skipup = NULL;
653  branchruledata->skipdown = NULL;
654 
655  /* include branching rule */
657  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
658 
659  assert(branchrule != NULL);
660 
661  /* set non-fundamental callbacks via specific setter functions*/
662  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyFullstrong) );
663  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeFullstrong) );
664  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitFullstrong) );
665  SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitFullstrong) );
666  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpFullstrong) );
667 
668  /* fullstrong branching rule parameters */
670  "branching/fullstrong/reevalage",
671  "number of intermediate LPs solved to trigger reevaluation of strong branching value for a variable that was already evaluated at the current node",
672  &branchruledata->reevalage, TRUE, DEFAULT_REEVALAGE, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
674  "branching/fullstrong/maxproprounds",
675  "maximum number of propagation rounds to be performed during strong branching before solving the LP (-1: no limit, -2: parameter settings)",
676  &branchruledata->maxproprounds, TRUE, DEFAULT_MAXPROPROUNDS, -2, INT_MAX, NULL, NULL) );
678  "branching/fullstrong/probingbounds",
679  "should valid bounds be identified in a probing-like fashion during strong branching (only with propagation)?",
680  &branchruledata->probingbounds, TRUE, DEFAULT_PROBINGBOUNDS, NULL, NULL) );
682  "branching/fullstrong/forcestrongbranch",
683  "should strong branching be applied even if there is just a single candidate?",
684  &branchruledata->forcestrongbranch, TRUE, DEFAULT_FORCESTRONGBRANCH, NULL, NULL) );
685 
686  return SCIP_OKAY;
687 }
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:36128
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21909
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46151
static SCIP_DECL_BRANCHFREE(branchFreeFullstrong)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1774
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21892
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22118
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:42499
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7163
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
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:21112
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45803
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:9086
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:9054
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
Definition: scip.c:44712
#define FALSE
Definition: def.h:64
#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:4230
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
#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:9038
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:21156
static SCIP_DECL_BRANCHINIT(branchInitFullstrong)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:9184
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22234
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
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:9001
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21933
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21611
#define SCIP_LONGINT_MAX
Definition: def.h:121
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
#define SCIPdebugMsg
Definition: scip.h:451
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:4202
#define BRANCHRULE_MAXDEPTH
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:46223
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:46211
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:9136
#define DEFAULT_MAXPROPROUNDS
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip.c:25559
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip.c:36583
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45764
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21701
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
#define NULL
Definition: lpi_spx1.cpp:137
#define BRANCHRULE_DESC
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:36813
SCIP_Longint SCIPgetVarStrongbranchLPAge(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:21190
#define DEFAULT_REEVALAGE
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1353
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip.c:19781
full strong LP branching rule
#define SCIP_Bool
Definition: def.h:61
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:28854
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip.c:13394
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1784
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:20465
#define MAX(x, y)
Definition: tclique_def.h:75
#define DEFAULT_FORCESTRONGBRANCH
#define BRANCHRULE_NAME
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
#define BRANCHRULE_MAXBOUNDDIST
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:28897
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
static SCIP_DECL_BRANCHEXIT(branchExitFullstrong)
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
Definition: scip.c:19840
SCIP_RETCODE SCIPincludeBranchruleFullstrong(SCIP *scip)
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, SCIP_Bool allowaddcons, 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)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11586
#define SCIP_Real
Definition: def.h:135
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1896
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip.c:9070
static SCIP_DECL_BRANCHEXECLP(branchExeclpFullstrong)
#define SCIP_Longint
Definition: def.h:120
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:29244
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip.h:21910
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
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:20012
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182
#define DEFAULT_PROBINGBOUNDS
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip.c:1025
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:4176