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