Scippy

SCIP

Solving Constraint Integer Programs

branch_allfullstrong.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-2016 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch_allfullstrong.c
17  * @brief all variables full strong LP branching rule
18  * @author Tobias Achterberg
19  *
20  * The all variables full strong branching rule applies strong branching to every non-fixed variable
21  * at the current node of the branch-and-bound search. The rule selects the candidate
22  * which will cause the highest gain of the dual bound in the created sub-tree among all branching variables.
23  *
24  * For calculating the gain, a look-ahead is performed by solving the child node LPs which will result
25  * from branching on a variable.
26  *
27  * For a more mathematical description and a comparison between the strong branching rule and other branching rules
28  * in SCIP, we refer to
29  *
30  * @par
31  * Tobias Achterberg@n
32  * Constraint Integer Programming@n
33  * PhD Thesis, Technische Universität Berlin, 2007@n
34  *
35  */
36 
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38 
39 #include <assert.h>
40 #include <string.h>
41 
43 
44 
45 #define BRANCHRULE_NAME "allfullstrong"
46 #define BRANCHRULE_DESC "all variables full strong branching"
47 #define BRANCHRULE_PRIORITY -1000
48 #define BRANCHRULE_MAXDEPTH -1
49 #define BRANCHRULE_MAXBOUNDDIST 1.0
50 
51 
52 /** branching rule data */
53 struct SCIP_BranchruleData
54 {
55  int lastcand; /**< last evaluated candidate of last branching rule execution */
56  SCIP_Bool* skipdown;
57  SCIP_Bool* skipup;
58 };
59 
60 
61 /** performs the all fullstrong branching */
62 static
64  SCIP* scip, /**< SCIP data structure */
65  SCIP_BRANCHRULE* branchrule, /**< branching rule */
66  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
67  SCIP_RESULT* result /**< pointer to store the result of the callback method */
68  )
69 {
70  SCIP_BRANCHRULEDATA* branchruledata;
71  SCIP_VAR** pseudocands;
72  SCIP_Real bestdown;
73  SCIP_Real bestup;
74  SCIP_Real bestscore;
75  SCIP_Real provedbound;
76  SCIP_Bool exactsolve;
77  SCIP_Bool allcolsinlp;
78  SCIP_Bool bestdownvalid;
79  SCIP_Bool bestupvalid;
80  int npseudocands;
81  int npriopseudocands;
82  int bestpseudocand;
83 #ifndef NDEBUG
84  SCIP_Real cutoffbound;
85  cutoffbound = SCIPgetCutoffbound(scip);
86 #endif
87 
88  assert(branchrule != NULL);
89  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
90  assert(scip != NULL);
91  assert(result != NULL);
92 
93  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
94  allcolsinlp = SCIPallColsInLP(scip);
95 
96  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
97  * for cutting off sub problems and improving lower bounds of children
98  */
99  exactsolve = SCIPisExactSolve(scip);
100 
101  /* get branching rule data */
102  branchruledata = SCIPbranchruleGetData(branchrule);
103  assert(branchruledata != NULL);
104 
105  if( branchruledata->skipdown == NULL )
106  {
107  int nvars;
108  nvars = SCIPgetNVars(scip);
109 
110  assert(branchruledata->skipup == NULL);
111 
112  SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->skipdown, nvars) );
113  SCIP_CALL( SCIPallocMemoryArray(scip, &branchruledata->skipup, nvars) );
114  BMSclearMemoryArray(branchruledata->skipdown, nvars);
115  BMSclearMemoryArray(branchruledata->skipup, nvars);
116  }
117 
118  /* get all non-fixed variables (not only the fractional ones) */
119  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &pseudocands, &npseudocands, &npriopseudocands) );
120  assert(npseudocands > 0);
121  assert(npriopseudocands > 0);
122 
123  SCIP_CALL( SCIPselectVarPseudoStrongBranching(scip, pseudocands, branchruledata->skipdown, branchruledata->skipup, npseudocands, npriopseudocands,
124  allowaddcons, &bestpseudocand, &bestdown, &bestup, &bestscore, &bestdownvalid, &bestupvalid, &provedbound, result) );
125 
126  if( *result != SCIP_CUTOFF && *result != SCIP_REDUCEDDOM && *result != SCIP_CONSADDED )
127  {
128  SCIP_NODE* downchild;
129  SCIP_NODE* eqchild;
130  SCIP_NODE* upchild;
131  SCIP_VAR* var;
132 
133  assert(*result == SCIP_DIDNOTRUN);
134  assert(0 <= bestpseudocand && bestpseudocand < npseudocands);
135  assert(SCIPisLT(scip, provedbound, cutoffbound));
136 
137  var = pseudocands[bestpseudocand];
138 
139  /* perform the branching */
140  SCIPdebugMessage(" -> %d candidates, selected candidate %d: variable <%s>[%g,%g] (solval=%g, down=%g, up=%g, score=%g)\n",
141  npseudocands, bestpseudocand, SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLPSol(var),
142  bestdown, bestup, bestscore);
143  SCIP_CALL( SCIPbranchVarVal(scip, var, SCIPvarGetLPSol(var), &downchild, &eqchild, &upchild) );
144 
145  /* update the lower bounds in the children */
146  if( allcolsinlp && !exactsolve )
147  {
148  if( downchild != NULL )
149  {
150  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
151  SCIPdebugMessage(" -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
152  }
153  if( eqchild != NULL )
154  {
155  SCIP_CALL( SCIPupdateNodeLowerbound(scip, eqchild, provedbound) );
156  SCIPdebugMessage(" -> eq child's lowerbound: %g\n", SCIPnodeGetLowerbound(eqchild));
157  }
158  if( upchild != NULL )
159  {
160  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
161  SCIPdebugMessage(" -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
162  }
163  }
164 
165  *result = SCIP_BRANCHED;
166  }
167 
168  return SCIP_OKAY;
169 }
170 
171 
172 /*
173  * Callback methods
174  */
175 
176 /** copy method for branchrule plugins (called when SCIP copies plugins) */
177 static
178 SCIP_DECL_BRANCHCOPY(branchCopyAllfullstrong)
179 { /*lint --e{715}*/
180  assert(scip != NULL);
181  assert(branchrule != NULL);
182  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
183 
184  /* call inclusion method of branchrule */
186 
187  return SCIP_OKAY;
188 }
189 
190 /** destructor of branching rule to free user data (called when SCIP is exiting) */
191 static
192 SCIP_DECL_BRANCHFREE(branchFreeAllfullstrong)
193 { /*lint --e{715}*/
194  SCIP_BRANCHRULEDATA* branchruledata;
195 
196  /* free branching rule data */
197  branchruledata = SCIPbranchruleGetData(branchrule);
198  SCIPfreeMemoryArrayNull(scip, &branchruledata->skipdown);
199  SCIPfreeMemoryArrayNull(scip, &branchruledata->skipup);
200 
201  SCIPfreeMemory(scip, &branchruledata);
202  SCIPbranchruleSetData(branchrule, NULL);
203 
204  return SCIP_OKAY;
205 }
206 
207 
208 /** initialization method of branching rule (called after problem was transformed) */
209 static
210 SCIP_DECL_BRANCHINIT(branchInitAllfullstrong)
211 { /*lint --e{715}*/
212  SCIP_BRANCHRULEDATA* branchruledata;
213 
214  /* initialize branching rule data */
215  branchruledata = SCIPbranchruleGetData(branchrule);
216  branchruledata->lastcand = 0;
217 
218  return SCIP_OKAY;
219 }
220 
221 
222 /** branching execution method for fractional LP solutions */
223 static
224 SCIP_DECL_BRANCHEXECLP(branchExeclpAllfullstrong)
225 { /*lint --e{715}*/
226  assert(result != NULL);
227 
228  SCIPdebugMessage("Execlp method of allfullstrong branching\n");
229 
230  *result = SCIP_DIDNOTRUN;
231 
232  SCIP_CALL( branch(scip, branchrule, allowaddcons, result) );
233 
234  return SCIP_OKAY;
235 }
236 
237 
238 /** branching execution method for not completely fixed pseudo solutions */
239 static
240 SCIP_DECL_BRANCHEXECPS(branchExecpsAllfullstrong)
241 { /*lint --e{715}*/
242  assert(result != NULL);
243 
244  SCIPdebugMessage("Execps method of allfullstrong branching\n");
245 
246  *result = SCIP_DIDNOTRUN;
247 
249  {
250  SCIP_CALL( branch(scip, branchrule, allowaddcons, result) );
251  }
252 
253  return SCIP_OKAY;
254 }
255 
256 
257 /*
258  * branching specific interface methods
259  */
260 /**
261  * Selects a variable from a set of candidates by strong branching
262  *
263  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
264  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
265  *
266  * @note The variables in the lpcands array must have a fractional value in the current LP solution
267  */
269  SCIP* scip, /**< original SCIP data structure */
270  SCIP_VAR** pseudocands, /**< branching candidates */
271  SCIP_Bool* skipdown, /**< should down branchings be skipped? */
272  SCIP_Bool* skipup, /**< should up branchings be skipped? */
273  int npseudocands, /**< number of branching candidates */
274  int npriopseudocands, /**< number of priority branching candidates */
275  SCIP_Bool allowaddcons, /**< is the branching rule allowed to add constraints? */
276  int* bestpseudocand, /**< best candidate for branching */
277  SCIP_Real* bestdown, /**< objective value of the down branch for bestcand */
278  SCIP_Real* bestup, /**< objective value of the up branch for bestcand */
279  SCIP_Real* bestscore, /**< score for bestcand */
280  SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */
281  SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */
282  SCIP_Real* provedbound, /**< proved dual bound for current subtree */
283  SCIP_RESULT* result /**< result pointer */
284  )
285 {
286  SCIP_Real lpobjval;
287  SCIP_Bool allcolsinlp;
288  SCIP_Bool exactsolve;
289 #ifndef NDEBUG
290  SCIP_Real cutoffbound;
291  cutoffbound = SCIPgetCutoffbound(scip);
292 #endif
293 
294 
295  assert(scip != NULL);
296  assert(pseudocands != NULL);
297  assert(bestpseudocand != NULL);
298  assert(skipdown != NULL);
299  assert(skipup != NULL);
300  assert(bestdown != NULL);
301  assert(bestup != NULL);
302  assert(bestscore != NULL);
303  assert(bestdownvalid != NULL);
304  assert(bestupvalid != NULL);
305  assert(provedbound != NULL);
306  assert(result != NULL);
307  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
308 
309  /* get current LP objective bound of the local sub problem and global cutoff bound */
310  lpobjval = SCIPgetLPObjval(scip);
311 
312  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
313  * for cutting off sub problems and improving lower bounds of children
314  */
315  exactsolve = SCIPisExactSolve(scip);
316 
317  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
318  allcolsinlp = SCIPallColsInLP(scip);
319 
320  /* if only one candidate exists, choose this one without applying strong branching */
321  *bestpseudocand = 0;
322  *bestdown = lpobjval;
323  *bestup = lpobjval;
324  *bestdownvalid = TRUE;
325  *bestupvalid = TRUE;
326  *bestscore = -SCIPinfinity(scip);
327  *provedbound = lpobjval;
328  if( npseudocands > 1 )
329  {
330  SCIP_BRANCHRULE* branchrule;
331  SCIP_BRANCHRULEDATA* branchruledata;
332 
333  SCIP_Real solval;
334  SCIP_Real down;
335  SCIP_Real up;
336  SCIP_Real downgain;
337  SCIP_Real upgain;
338  SCIP_Real score;
339  SCIP_Bool integral;
340  SCIP_Bool lperror;
341  SCIP_Bool downvalid;
342  SCIP_Bool upvalid;
343  SCIP_Bool downinf;
344  SCIP_Bool upinf;
345  SCIP_Bool downconflict;
346  SCIP_Bool upconflict;
347  int nsbcalls;
348  int i;
349  int c;
350 
351  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
352  assert(branchrule != NULL);
353 
354  /* get branching rule data */
355  branchruledata = SCIPbranchruleGetData(branchrule);
356  assert(branchruledata != NULL);
357 
358 
359  /* initialize strong branching */
361 
362  /* search the full strong candidate:
363  * cycle through the candidates, starting with the position evaluated in the last run
364  */
365  nsbcalls = 0;
366  for( i = 0, c = branchruledata->lastcand; i < npseudocands; ++i, ++c )
367  {
368  c = c % npseudocands;
369  assert(pseudocands[c] != NULL);
370 
371  /* we can only apply strong branching on COLUMN variables that are in the current LP */
372  if( !SCIPvarIsInLP(pseudocands[c]) )
373  continue;
374 
375  solval = SCIPvarGetLPSol(pseudocands[c]);
376  integral = SCIPisFeasIntegral(scip, solval);
377 
378  SCIPdebugMessage("applying strong branching on %s variable <%s>[%g,%g] with solution %g\n",
379  integral ? "integral" : "fractional", SCIPvarGetName(pseudocands[c]), SCIPvarGetLbLocal(pseudocands[c]),
380  SCIPvarGetUbLocal(pseudocands[c]), solval);
381 
382  up = -SCIPinfinity(scip);
383  down = -SCIPinfinity(scip);
384 
385  if( integral )
386  {
387  SCIP_CALL( SCIPgetVarStrongbranchInt(scip, pseudocands[c], INT_MAX,
388  skipdown[c] ? NULL : &down, skipup[c] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
389  }
390  else
391  {
392  SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, pseudocands[c], INT_MAX,
393  skipdown[c] ? NULL : &down, skipup[c] ? NULL : &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
394  }
395  nsbcalls++;
396 
397  /* display node information line in root node */
398  if( SCIPgetDepth(scip) == 0 && nsbcalls % 100 == 0 )
399  {
401  }
402 
403  /* check for an error in strong branching */
404  if( lperror )
405  {
407  "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call for variable <%s> with solution %g\n",
408  SCIPgetNNodes(scip), SCIPvarGetName(pseudocands[c]), solval);
409  break;
410  }
411 
412  /* evaluate strong branching */
413  down = MAX(down, lpobjval);
414  up = MAX(up, lpobjval);
415  downgain = down - lpobjval;
416  upgain = up - lpobjval;
417  assert(!allcolsinlp || exactsolve || !downvalid || downinf == SCIPisGE(scip, down, cutoffbound));
418  assert(!allcolsinlp || exactsolve || !upvalid || upinf == SCIPisGE(scip, up, cutoffbound));
419  assert(downinf || !downconflict);
420  assert(upinf || !upconflict);
421 
422  /* check if there are infeasible roundings */
423  if( downinf || upinf )
424  {
425  assert(allcolsinlp);
426  assert(!exactsolve);
427 
428  /* if for both infeasibilities, a conflict constraint was created, we don't need to fix the variable by hand,
429  * but better wait for the next propagation round to fix them as an inference, and potentially produce a
430  * cutoff that can be analyzed
431  */
432  if( allowaddcons && downinf == downconflict && upinf == upconflict )
433  {
434  *result = SCIP_CONSADDED;
435  break; /* terminate initialization loop, because constraint was added */
436  }
437  else if( downinf && upinf )
438  {
439  if( integral )
440  {
441  SCIP_Bool infeasible;
442  SCIP_Bool fixed;
443 
444  /* both bound changes are infeasible: variable can be fixed to its current value */
445  SCIP_CALL( SCIPfixVar(scip, pseudocands[c], solval, &infeasible, &fixed) );
446  assert(!infeasible);
447  assert(fixed);
448  *result = SCIP_REDUCEDDOM;
449  SCIPdebugMessage(" -> integral variable <%s> is infeasible in both directions\n",
450  SCIPvarGetName(pseudocands[c]));
451  break; /* terminate initialization loop, because LP was changed */
452  }
453  else
454  {
455  /* both roundings are infeasible: the node is infeasible */
456  *result = SCIP_CUTOFF;
457  SCIPdebugMessage(" -> fractional variable <%s> is infeasible in both directions\n",
458  SCIPvarGetName(pseudocands[c]));
459  break; /* terminate initialization loop, because node is infeasible */
460  }
461  }
462  else if( downinf )
463  {
464  SCIP_Real newlb;
465 
466  /* downwards rounding is infeasible -> change lower bound of variable to upward rounding */
467  newlb = SCIPfeasCeil(scip, solval);
468  if( SCIPvarGetLbLocal(pseudocands[c]) < newlb - 0.5 )
469  {
470  SCIP_CALL( SCIPchgVarLb(scip, pseudocands[c], newlb) );
471  *result = SCIP_REDUCEDDOM;
472  SCIPdebugMessage(" -> variable <%s> is infeasible in downward branch\n", SCIPvarGetName(pseudocands[c]));
473  break; /* terminate initialization loop, because LP was changed */
474  }
475  }
476  else
477  {
478  SCIP_Real newub;
479 
480  /* upwards rounding is infeasible -> change upper bound of variable to downward rounding */
481  assert(upinf);
482  newub = SCIPfeasFloor(scip, solval);
483  if( SCIPvarGetUbLocal(pseudocands[c]) > newub + 0.5 )
484  {
485  SCIP_CALL( SCIPchgVarUb(scip, pseudocands[c], newub) );
486  *result = SCIP_REDUCEDDOM;
487  SCIPdebugMessage(" -> variable <%s> is infeasible in upward branch\n", SCIPvarGetName(pseudocands[c]));
488  break; /* terminate initialization loop, because LP was changed */
489  }
490  }
491  }
492  else if( allcolsinlp && !exactsolve && downvalid && upvalid )
493  {
494  SCIP_Real minbound;
495 
496  /* the minimal lower bound of both children is a proved lower bound of the current subtree */
497  minbound = MIN(down, up);
498  *provedbound = MAX(*provedbound, minbound);
499  }
500 
501  /* check for a better score, if we are within the maximum priority candidates */
502  if( c < npriopseudocands )
503  {
504  if( integral )
505  {
506 
507  if( skipdown[c] )
508  {
509  downgain = 0.0;
510  score = SCIPgetBranchScore(scip, pseudocands[c], downgain, upgain);
511  }
512  else if( skipup[c] )
513  {
514  upgain = 0.0;
515  score = SCIPgetBranchScore(scip, pseudocands[c], downgain, upgain);
516  }
517  else
518  {
519  SCIP_Real gains[3];
520 
521  gains[0] = downgain;
522  gains[1] = 0.0;
523  gains[2] = upgain;
524  score = SCIPgetBranchScoreMultiple(scip, pseudocands[c], 3, gains);
525  }
526  }
527  else
528  score = SCIPgetBranchScore(scip, pseudocands[c], downgain, upgain);
529 
530  if( score > *bestscore )
531  {
532  *bestpseudocand = c;
533  *bestdown = down;
534  *bestup = up;
535  *bestdownvalid = downvalid;
536  *bestupvalid = upvalid;
537  *bestscore = score;
538  }
539  }
540  else
541  score = 0.0;
542 
543  /* update pseudo cost values */
544  if( !downinf )
545  {
546  SCIP_CALL( SCIPupdateVarPseudocost(scip, pseudocands[c],
547  solval-SCIPfeasCeil(scip, solval-1.0), downgain, 1.0) );
548  }
549  if( !upinf )
550  {
551  SCIP_CALL( SCIPupdateVarPseudocost(scip, pseudocands[c],
552  solval-SCIPfeasFloor(scip, solval+1.0), upgain, 1.0) );
553  }
554 
555  SCIPdebugMessage(" -> var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
556  SCIPvarGetName(pseudocands[c]), solval, downgain, upgain, score,
557  SCIPvarGetName(pseudocands[*bestpseudocand]), *bestscore);
558  }
559 
560  /* remember last evaluated candidate */
561  branchruledata->lastcand = c;
562 
563  /* end strong branching */
565  }
566 
567  return SCIP_OKAY;
568 }
569 
570 /** creates the all variables full strong LP branching rule and includes it in SCIP */
572  SCIP* scip /**< SCIP data structure */
573  )
574 {
575  SCIP_BRANCHRULEDATA* branchruledata;
576  SCIP_BRANCHRULE* branchrule;
577 
578  /* create allfullstrong branching rule data */
579  SCIP_CALL( SCIPallocMemory(scip, &branchruledata) );
580  branchruledata->lastcand = 0;
581  branchruledata->skipup = NULL;
582  branchruledata->skipdown = NULL;
583 
584  /* include allfullstrong branching rule */
586  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
587 
588  assert(branchrule != NULL);
589 
590  /* set non-fundamental callbacks via specific setter functions*/
591  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyAllfullstrong) );
592  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeAllfullstrong) );
593  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitAllfullstrong) );
594  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpAllfullstrong) );
595  SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsAllfullstrong) );
596 
597  return SCIP_OKAY;
598 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:51
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:22777
SCIP_RETCODE SCIPprintDisplayLine(SCIP *scip, FILE *file, SCIP_VERBLEVEL verblevel, SCIP_Bool endline)
Definition: scip.c:40623
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:10698
#define SCIPallocMemory(scip, ptr)
Definition: scip.h:20526
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16443
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:19748
#define BRANCHRULE_MAXBOUNDDIST
static SCIP_DECL_BRANCHEXECPS(branchExecpsAllfullstrong)
#define BRANCHRULE_MAXDEPTH
#define NULL
Definition: lpi_spx.cpp:130
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17113
SCIP_RETCODE SCIPgetVarStrongbranchInt(SCIP *scip, SCIP_VAR *var, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror)
Definition: scip.c:18943
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:42032
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip.c:8322
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:43
static SCIP_DECL_BRANCHINIT(branchInitAllfullstrong)
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip.h:20528
#define FALSE
Definition: def.h:56
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip.c:17963
#define TRUE
Definition: def.h:55
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition: scip.c:23184
#define SCIP_CALL(x)
Definition: def.h:266
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1877
#define BRANCHRULE_NAME
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip.c:42008
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
Definition: scip.c:38561
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip.c:26439
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip.c:8290
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_RETCODE SCIPgetVarStrongbranchFrac(SCIP *scip, SCIP_VAR *var, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, SCIP_Bool *downinf, SCIP_Bool *upinf, SCIP_Bool *downconflict, SCIP_Bool *upconflict, SCIP_Bool *lperror)
Definition: scip.c:18191
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip.c:8306
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
Definition: var.c:16782
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip.c:8420
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip.c:26482
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
Definition: scip.c:42044
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip.c:26829
SCIP_RETCODE SCIPincludeBranchruleAllfullstrong(SCIP *scip)
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip.c:12363
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip.c:8388
#define SCIPfreeMemory(scip, ptr)
Definition: scip.h:20542
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41585
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip.c:8253
static SCIP_DECL_BRANCHFREE(branchFreeAllfullstrong)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1765
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip.c:33464
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:41637
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition: scip.c:26354
static SCIP_DECL_BRANCHEXECLP(branchExeclpAllfullstrong)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17123
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:19828
#define SCIP_Bool
Definition: def.h:53
#define MAX(x, y)
Definition: tclique_def.h:75
SCIP_RETCODE SCIPselectVarPseudoStrongBranching(SCIP *scip, SCIP_VAR **pseudocands, SCIP_Bool *skipdown, SCIP_Bool *skipup, int npseudocands, int npriopseudocands, SCIP_Bool allowaddcons, int *bestpseudocand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound, SCIP_RESULT *result)
#define BRANCHRULE_PRIORITY
#define BRANCHRULE_DESC
static SCIP_RETCODE branch(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Bool allowaddcons, SCIP_RESULT *result)
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:38140
static SCIP_DECL_BRANCHCOPY(branchCopyAllfullstrong)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1298
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41624
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:17431
all variables full strong LP branching rule
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1755
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip.h:20545
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip.c:33580
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip.c:8436
#define SCIP_Real
Definition: def.h:127
#define MIN(x, y)
Definition: memory.c:67
SCIP_Real SCIPgetBranchScoreMultiple(SCIP *scip, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: scip.c:33603
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
Definition: scip.c:18019
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7036
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip.c:33810
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:37372
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip.c:1012