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