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