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