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