Scippy

SCIP

Solving Constraint Integer Programs

branch_vanillafullstrong.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-2024 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_vanillafullstrong.c
26  * @ingroup DEFPLUGINS_BRANCH
27  * @brief vanilla full strong LP branching rule
28  * @author Tobias Achterberg
29  * @author Maxime Gasse
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include "blockmemshell/memory.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 "vanillafullstrong"
55 #define BRANCHRULE_DESC "vanilla full strong branching"
56 #define BRANCHRULE_PRIORITY -2000
57 #define BRANCHRULE_MAXDEPTH -1
58 #define BRANCHRULE_MAXBOUNDDIST 1.0
59 
60 #define DEFAULT_INTEGRALCANDS FALSE /**< should integral variables in the current LP solution be considered as
61  * branching candidates ? */
62 #define DEFAULT_SCOREALL FALSE /**< should strong branching scores be computed for all candidates, or can
63  * we early stop when a variable has infinite score ? */
64 #define DEFAULT_IDEMPOTENT FALSE /**< should strong branching side-effects be prevented (e.g., domain
65  * changes, stat updates etc.) ? */
66 #define DEFAULT_COLLECTSCORES FALSE /**< should strong branching scores be collected ? */
67 #define DEFAULT_DONOTBRANCH FALSE /**< should branching be done ? */
68 
69 
70 /** branching rule data */
71 struct SCIP_BranchruleData
72 {
73  SCIP_Bool integralcands; /**< should integral variables in the current LP solution be considered
74  * as branching candidates ? */
75  SCIP_Bool scoreall; /**< should strong branching scores be computed for all candidates, or
76  * can we early stop when a node is detected infeasible ? */
77  SCIP_Bool idempotent; /**< should strong branching side-effects be prevented (e.g., domain
78  * changes, stat updates etc.) ? */
79  SCIP_Bool collectscores; /**< should strong branching scores be collected ? */
80  SCIP_Bool donotbranch; /**< should branching be done ? */
81  SCIP_VAR** cands; /**< candidate variables */
82  SCIP_Real* candscores; /**< candidate scores */
83  int ncands; /**< number of candidates */
84  int npriocands; /**< number of priority candidates */
85  int bestcand; /**< best branching candidate */
86  int candcapacity; /**< capacity of candidate arrays */
87 };
88 
89 
90 /*
91  * local methods
92  */
93 
94 
95 /** selects a variable from a set of candidates by strong branching */
96 static
98  SCIP* scip, /**< SCIP data structure */
99  SCIP_VAR** cands, /**< branching candidates */
100  int ncands, /**< number of branching candidates */
101  int npriocands, /**< number of branching candidates with highest priority */
102  SCIP_Bool scoreall, /**< should strong branching scores be computed for all candidates, or can
103  * we early stop when a node is detected infeasible ? */
104  SCIP_Bool idempotent, /**< should strong branching side-effects be prevented (e.g., domain
105  * changes, stat updates etc.) ? */
106  SCIP_Real* scores, /**< candidate scores */
107  int* bestcand, /**< best candidate for branching */
108  SCIP_Real* bestdown, /**< objective value of the down branch for bestcand */
109  SCIP_Real* bestup, /**< objective value of the up branch for bestcand */
110  SCIP_Real* bestscore, /**< score for bestcand */
111  SCIP_Bool* bestdownvalid, /**< is bestdown a valid dual bound for the down branch? */
112  SCIP_Bool* bestupvalid, /**< is bestup a valid dual bound for the up branch? */
113  SCIP_Real* provedbound /**< proved dual bound for current subtree */
114  )
115 { /*lint --e{715}*/
116  SCIP_Real lpobjval;
117  int nsbcalls;
118  int c;
119 
120  assert(scip != NULL);
121  assert(cands != NULL);
122  assert(bestcand != NULL);
123  assert(bestdown != NULL);
124  assert(bestup != NULL);
125  assert(bestscore != NULL);
126  assert(bestdownvalid != NULL);
127  assert(bestupvalid != NULL);
128  assert(provedbound != NULL);
129  assert(ncands > 0);
130 
131  /* get current LP objective bound of the local sub problem and global cutoff bound */
132  lpobjval = SCIPgetLPObjval(scip);
133  *provedbound = lpobjval;
134 
135  *bestcand = 0;
136  *bestdown = lpobjval;
137  *bestup = lpobjval;
138  *bestdownvalid = TRUE;
139  *bestupvalid = TRUE;
140  *bestscore = -SCIPinfinity(scip);
141 
142  if( scores != NULL )
143  for( c = 0; c < ncands; ++c )
144  scores[c] = -SCIPinfinity(scip);
145 
146  /* if only one candidate exists, choose this one without applying strong branching; also, when SCIP is about to be
147  * stopped, all strongbranching evaluations will be aborted anyway, thus we can return immediately
148  */
149  if( (!scoreall && ncands == 1) || SCIPisStopped(scip) )
150  return SCIP_OKAY;
151 
152  /* this assert may not hold if SCIP is stopped, thus we only check it here */
153  assert(SCIPgetLPSolstat(scip) == SCIP_LPSOLSTAT_OPTIMAL);
154 
155  /* initialize strong branching without propagation */
157 
158  /* compute strong branching scores */
159  nsbcalls = 0;
160  for( c = 0; c < ncands ; ++c )
161  {
162  SCIP_VAR* var;
163  SCIP_Real val;
164  SCIP_Bool integral;
165  SCIP_Real down, up;
166  SCIP_Real downgain, upgain;
167  SCIP_Bool downvalid, upvalid;
168  SCIP_Bool downinf, upinf;
169  SCIP_Bool downconflict, upconflict;
170  SCIP_Bool lperror;
171  SCIP_Real gains[3];
172  SCIP_Real score;
173 
174  var = cands[c];
175  assert(var != NULL);
176 
177  val = SCIPvarGetLPSol(var);
178  integral = SCIPisFeasIntegral(scip, val);
179 
180  up = -SCIPinfinity(scip);
181  down = -SCIPinfinity(scip);
182 
183  SCIPdebugMsg(scip, "applying vanilla strong branching on variable <%s> with solution %g\n",
184  SCIPvarGetName(var), val);
185 
186  /* apply strong branching */
187  if( integral )
188  {
189  SCIP_CALL( SCIPgetVarStrongbranchInt(scip, cands[c], INT_MAX, idempotent,
190  &down, &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
191  }
192  else
193  {
194  SCIP_CALL( SCIPgetVarStrongbranchFrac(scip, cands[c], INT_MAX, idempotent,
195  &down, &up, &downvalid, &upvalid, &downinf, &upinf, &downconflict, &upconflict, &lperror) );
196  }
197  nsbcalls++;
198 
199  /* check for an error in strong branching */
200  if( lperror )
201  {
203  "(node %" SCIP_LONGINT_FORMAT ") error in strong branching call for variable <%s> with solution %g\n",
204  SCIPgetNNodes(scip), SCIPvarGetName(var), val);
205  break;
206  }
207 
208  /* evaluate strong branching */
209  down = MAX(down, lpobjval);
210  up = MAX(up, lpobjval);
211  downgain = down - lpobjval;
212  upgain = up - lpobjval;
213 
214  assert(!SCIPallColsInLP(scip) || SCIPisExactSolve(scip) || !downvalid || downinf == SCIPisGE(scip, down, SCIPgetCutoffbound(scip)));
215  assert(!SCIPallColsInLP(scip) || SCIPisExactSolve(scip) || !upvalid || upinf == SCIPisGE(scip, up, SCIPgetCutoffbound(scip)));
216  assert(downinf || !downconflict);
217  assert(upinf || !upconflict);
218 
219  if( !idempotent )
220  {
221  /* display node information line */
222  if( SCIPgetDepth(scip) == 0 && nsbcalls % 100 == 0 )
223  {
225  }
226  /* update variable pseudo cost values */
227  if( !downinf && downvalid )
228  {
229  SCIP_CALL( SCIPupdateVarPseudocost(scip, var, integral ? -1.0 : 0.0 - SCIPfrac(scip, val), downgain, 1.0) );
230  }
231  if( !upinf && upvalid )
232  {
233  SCIP_CALL( SCIPupdateVarPseudocost(scip, var, integral ? +1.0 : 1.0 - SCIPfrac(scip, val), upgain, 1.0) );
234  }
235  }
236 
237  /* compute strong branching score */
238  gains[0] = downgain;
239  gains[1] = upgain;
240  gains[2] = 0.0;
241  score = SCIPgetBranchScoreMultiple(scip, var, integral ? 3 : 2, gains);
242 
243  /* collect scores if requested */
244  if( scores != NULL )
245  scores[c] = score;
246 
247  /* check for a better score */
248  if( score > *bestscore )
249  {
250  *bestcand = c;
251  *bestdown = down;
252  *bestup = up;
253  *bestdownvalid = downvalid;
254  *bestupvalid = upvalid;
255  *bestscore = score;
256  }
257 
258  SCIPdebugMsg(scip, " -> cand %d/%d (prio:%d) var <%s> (solval=%g, downgain=%g, upgain=%g, score=%g) -- best: <%s> (%g)\n",
259  c, ncands, npriocands, SCIPvarGetName(var), val, downgain, upgain, score,
260  SCIPvarGetName(cands[*bestcand]), *bestscore);
261 
262  /* node is infeasible -> early stopping (highest score) */
263  if( !integral && !scoreall && downinf && upinf )
264  {
265  /* we should only detect infeasibility if the LP is a valid relaxation */
266  assert(SCIPallColsInLP(scip));
267  assert(!SCIPisExactSolve(scip));
268 
269  SCIPdebugMsg(scip, " -> variable <%s> is infeasible in both directions\n", SCIPvarGetName(var));
270  break;
271  }
272  }
273 
274  /* end strong branching */
276 
277  return SCIP_OKAY;
278 }
279 
280 /*
281  * Callback methods
282  */
283 
284 /** copy method for branchrule plugins (called when SCIP copies plugins) */
285 static
286 SCIP_DECL_BRANCHCOPY(branchCopyVanillafullstrong)
287 { /*lint --e{715}*/
288  assert(scip != NULL);
289  assert(branchrule != NULL);
290  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
291 
292  /* call inclusion method of branchrule */
294 
295  return SCIP_OKAY;
296 }
297 
298 /** destructor of branching rule to free user data (called when SCIP is exiting) */
299 static
300 SCIP_DECL_BRANCHFREE(branchFreeVanillafullstrong)
301 { /*lint --e{715}*/
302  SCIP_BRANCHRULEDATA* branchruledata;
304  /* free branching rule data */
305  branchruledata = SCIPbranchruleGetData(branchrule);
306  assert(branchruledata != NULL);
307 
308  SCIPfreeBlockMemoryNull(scip, &branchruledata);
309 
310  return SCIP_OKAY;
311 }
312 
313 /** initialization method of branching rule (called after problem was transformed) */
314 static
315 SCIP_DECL_BRANCHINIT(branchInitVanillafullstrong)
316 { /*lint --e{715}*/
317 #ifndef NDEBUG
318  SCIP_BRANCHRULEDATA* branchruledata;
319 
320  /* initialize branching rule data */
321  branchruledata = SCIPbranchruleGetData(branchrule);
322 #endif
323  assert(branchruledata != NULL);
324  assert(branchruledata->candscores == NULL);
325  assert(branchruledata->cands == NULL);
326 
327  return SCIP_OKAY;
328 }
329 
330 /** deinitialization method of branching rule (called before transformed problem is freed) */
331 static
332 SCIP_DECL_BRANCHEXIT(branchExitVanillafullstrong)
333 { /*lint --e{715}*/
334  SCIP_BRANCHRULEDATA* branchruledata;
336  /* initialize branching rule data */
337  branchruledata = SCIPbranchruleGetData(branchrule);
338  assert(branchruledata != NULL);
339 
340  /* free candidate arrays if any */
341  if( branchruledata->candscores != NULL )
342  {
343  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->candscores, branchruledata->candcapacity);
344  }
345  if( branchruledata->cands != NULL )
346  {
347  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->cands, branchruledata->candcapacity);
348  }
349 
350  branchruledata->candcapacity = -1;
351  branchruledata->ncands = -1;
352  branchruledata->npriocands = -1;
353  branchruledata->bestcand = -1;
354 
355  return SCIP_OKAY;
356 }
357 
358 /** branching execution method */
359 static
360 SCIP_DECL_BRANCHEXECLP(branchExeclpVanillafullstrong)
361 { /*lint --e{715}*/
362  SCIP_BRANCHRULEDATA* branchruledata;
363  SCIP_Real bestdown;
364  SCIP_Real bestup;
365  SCIP_Real bestscore;
366  SCIP_Real provedbound;
367  SCIP_Bool bestdownvalid;
368  SCIP_Bool bestupvalid;
369  SCIP_VAR** cands;
370  int ncands;
371  int npriocands;
372  int i;
373 
374  assert(branchrule != NULL);
375  assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
376  assert(scip != NULL);
377  assert(result != NULL);
378 
379  SCIPdebugMsg(scip, "Execlp method of vanilla fullstrong branching\n");
380 
381  *result = SCIP_DIDNOTRUN;
382 
383  /* get branching rule data */
384  branchruledata = SCIPbranchruleGetData(branchrule);
385  assert(branchruledata != NULL);
386 
387  /* get branching candidates, either all non-fixed variables or only the
388  * fractional ones */
389  if( branchruledata->integralcands )
390  {
391  SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, &ncands, &npriocands) );
392  }
393  else
394  {
395  SCIP_CALL( SCIPgetLPBranchCands(scip, &cands, NULL, NULL, &ncands, &npriocands, NULL) );
396  }
397 
398  assert(ncands > 0);
399  assert(npriocands > 0);
400 
401  /* increase candidate arrays capacity if needed */
402  if( ncands > branchruledata->candcapacity )
403  {
404  /* free previously allocated arrays if any */
405  if( branchruledata->candscores != NULL)
406  {
407  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->candscores, branchruledata->candcapacity);
408  branchruledata->candscores = NULL;
409  }
410  if( branchruledata->cands != NULL)
411  {
412  SCIPfreeBlockMemoryArrayNull(scip, &branchruledata->cands, branchruledata->candcapacity);
413  branchruledata->cands = NULL;
414  }
415 
416  /* update capacity */
417  branchruledata->candcapacity = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip);
418  }
419  assert(branchruledata->candcapacity >= ncands);
420 
421  /* allocate new candidate arrays if needed */
422  if( branchruledata->cands == NULL )
423  {
424  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->cands, branchruledata->candcapacity) );
425  }
426  if( branchruledata->candscores == NULL && branchruledata->collectscores )
427  {
428  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->candscores, branchruledata->candcapacity) );
429  }
430 
431  /* copy candidates */
432  branchruledata->ncands = ncands;
433  branchruledata->npriocands = npriocands;
434 
435  for( i = 0; i < ncands; i++ )
436  branchruledata->cands[i] = cands[i];
437 
438  SCIP_CALL( runVanillaStrongBranching(scip, branchruledata->cands, branchruledata->ncands, branchruledata->npriocands,
439  branchruledata->scoreall, branchruledata->idempotent, branchruledata->candscores,
440  &branchruledata->bestcand, &bestdown, &bestup, &bestscore, &bestdownvalid,
441  &bestupvalid, &provedbound) );
442 
443  if( !branchruledata->donotbranch )
444  {
445  SCIP_VAR* var;
446  SCIP_Real val;
447  SCIP_NODE* downchild;
448  SCIP_NODE* eqchild;
449  SCIP_NODE* upchild;
450  SCIP_Bool allcolsinlp;
451  SCIP_Bool exactsolve;
452 
453  assert(0 <= branchruledata->bestcand && branchruledata->bestcand < branchruledata->ncands);
454  assert(SCIPisLT(scip, provedbound, SCIPgetCutoffbound(scip)));
455 
456  var = branchruledata->cands[branchruledata->bestcand];
457  val = SCIPvarGetLPSol(var);
458 
459  /* perform the branching */
460  SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s>[%g,%g] (solval=%g, down=%g, up=%g, score=%g)\n",
461  branchruledata->ncands, branchruledata->bestcand, SCIPvarGetName(var), SCIPvarGetLbLocal(var),
462  SCIPvarGetUbLocal(var), val, bestdown, bestup, bestscore);
463  SCIP_CALL( SCIPbranchVarVal(scip, var, val, &downchild, &eqchild, &upchild) );
464 
465  /* check, if we want to solve the problem exactly, meaning that strong branching information is not useful
466  * for cutting off sub problems and improving lower bounds of children
467  */
468  exactsolve = SCIPisExactSolve(scip);
469 
470  /* check, if all existing columns are in LP, and thus the strong branching results give lower bounds */
471  allcolsinlp = SCIPallColsInLP(scip);
472 
473  /* update the lower bounds in the children */
474  if( !branchruledata->idempotent && allcolsinlp && !exactsolve )
475  {
476  if( downchild != NULL )
477  {
478  SCIP_CALL( SCIPupdateNodeLowerbound(scip, downchild, bestdownvalid ? MAX(bestdown, provedbound) : provedbound) );
479  SCIPdebugMsg(scip, " -> down child's lowerbound: %g\n", SCIPnodeGetLowerbound(downchild));
480  }
481  if( eqchild != NULL )
482  {
483  SCIP_CALL( SCIPupdateNodeLowerbound(scip, eqchild, provedbound) );
484  SCIPdebugMsg(scip, " -> eq child's lowerbound: %g\n", SCIPnodeGetLowerbound(eqchild));
485  }
486  if( upchild != NULL )
487  {
488  SCIP_CALL( SCIPupdateNodeLowerbound(scip, upchild, bestupvalid ? MAX(bestup, provedbound) : provedbound) );
489  SCIPdebugMsg(scip, " -> up child's lowerbound: %g\n", SCIPnodeGetLowerbound(upchild));
490  }
491  }
492 
493  *result = SCIP_BRANCHED;
494  }
495 
496  return SCIP_OKAY;
497 }
498 
499 
500 /*
501  * branching specific interface methods
502  */
503 
504 /** creates the vanilla full strong LP branching rule and includes it in SCIP */
506  SCIP* scip /**< SCIP data structure */
507  )
508 {
509  SCIP_BRANCHRULEDATA* branchruledata;
510  SCIP_BRANCHRULE* branchrule;
511 
512  /* create fullstrong branching rule data */
513  SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
514  branchruledata->cands = NULL;
515  branchruledata->candscores = NULL;
516  branchruledata->candcapacity = -1;
517  branchruledata->ncands = -1;
518  branchruledata->npriocands = -1;
519  branchruledata->bestcand = -1;
520 
521  /* include branching rule */
523  BRANCHRULE_MAXDEPTH, BRANCHRULE_MAXBOUNDDIST, branchruledata) );
524 
525  assert(branchrule != NULL);
526 
527  /* set non-fundamental callbacks via specific setter functions*/
528  SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyVanillafullstrong) );
529  SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeVanillafullstrong) );
530  SCIP_CALL( SCIPsetBranchruleInit(scip, branchrule, branchInitVanillafullstrong) );
531  SCIP_CALL( SCIPsetBranchruleExit(scip, branchrule, branchExitVanillafullstrong) );
532  SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpVanillafullstrong) );
533 
534  /* fullstrong branching rule parameters */
536  "branching/vanillafullstrong/integralcands",
537  "should integral variables in the current LP solution be considered as branching candidates?",
538  &branchruledata->integralcands, FALSE, DEFAULT_INTEGRALCANDS, NULL, NULL) );
540  "branching/vanillafullstrong/idempotent",
541  "should strong branching side-effects be prevented (e.g., domain changes, stat updates etc.)?",
542  &branchruledata->idempotent, FALSE, DEFAULT_IDEMPOTENT, NULL, NULL) );
544  "branching/vanillafullstrong/scoreall",
545  "should strong branching scores be computed for all candidates, or can we early stop when a variable has infinite score?",
546  &branchruledata->scoreall, TRUE, DEFAULT_SCOREALL, NULL, NULL) );
548  "branching/vanillafullstrong/collectscores",
549  "should strong branching scores be collected?",
550  &branchruledata->collectscores, TRUE, DEFAULT_COLLECTSCORES, NULL, NULL) );
552  "branching/vanillafullstrong/donotbranch",
553  "should candidates only be scored, but no branching be performed?",
554  &branchruledata->donotbranch, TRUE, DEFAULT_DONOTBRANCH, NULL, NULL) );
555 
556  return SCIP_OKAY;
557 }
558 
559 
560 /** recovers candidate variables and their scores from last vanilla full strong branching call */
562  SCIP* scip, /**< SCIP data structure */
563  SCIP_VAR*** cands, /**< pointer to store candidate variables; or NULL */
564  SCIP_Real** candscores, /**< pointer to store candidate scores; or NULL */
565  int* ncands, /**< pointer to store number of candidates; or NULL */
566  int* npriocands, /**< pointer to store number of priority candidates; or NULL */
567  int* bestcand /**< pointer to store best branching candidate; or NULL */
568  )
569 {
570  SCIP_BRANCHRULEDATA* branchruledata;
571  SCIP_BRANCHRULE* branchrule;
572 
573  assert(scip != NULL);
574 
575  branchrule = SCIPfindBranchrule(scip, BRANCHRULE_NAME);
576  assert( branchrule != NULL );
577  branchruledata = SCIPbranchruleGetData(branchrule);
578  assert( branchruledata != NULL );
579 
580  if( cands )
581  {
582  *cands = branchruledata->cands;
583  }
584  if( candscores && branchruledata->collectscores )
585  {
586  *candscores = branchruledata->candscores;
587  }
588  if( ncands )
589  {
590  *ncands = branchruledata->ncands;
591  }
592  if( npriocands )
593  {
594  *npriocands = branchruledata->npriocands;
595  }
596  if( bestcand )
597  {
598  *bestcand = branchruledata->bestcand;
599  }
600 
601  return SCIP_OKAY;
602 }
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
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
static SCIP_DECL_BRANCHEXIT(branchExitVanillafullstrong)
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:7464
#define DEFAULT_SCOREALL
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
static SCIP_RETCODE runVanillaStrongBranching(SCIP *scip, SCIP_VAR **cands, int ncands, int npriocands, SCIP_Bool scoreall, SCIP_Bool idempotent, SCIP_Real *scores, int *bestcand, SCIP_Real *bestdown, SCIP_Real *bestup, SCIP_Real *bestscore, SCIP_Bool *bestdownvalid, SCIP_Bool *bestupvalid, SCIP_Real *provedbound)
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:94
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.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
SCIP_Real SCIPgetBranchScoreMultiple(SCIP *scip, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: scip_branch.c:872
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:297
public methods for problem variables
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 SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
public methods for SCIP variables
#define SCIPdebugMsg
Definition: scip_message.h:78
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:3664
public methods for numerical tolerances
#define BRANCHRULE_PRIORITY
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
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:8782
public methods for the branch-and-bound tree
#define BRANCHRULE_DESC
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define DEFAULT_COLLECTSCORES
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
static SCIP_DECL_BRANCHINIT(branchInitVanillafullstrong)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18453
#define SCIP_CALL(x)
Definition: def.h:380
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
static SCIP_DECL_BRANCHCOPY(branchCopyVanillafullstrong)
#define SCIPfreeBlockMemoryNull(scip, ptr)
Definition: scip_mem.h:109
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
SCIP_RETCODE SCIPstartStrongbranch(SCIP *scip, SCIP_Bool enablepropagation)
Definition: scip_var.c:2688
#define SCIP_Bool
Definition: def.h:91
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_RETCODE SCIPupdateNodeLowerbound(SCIP *scip, SCIP_NODE *node, SCIP_Real newbound)
Definition: scip_prob.c:3757
static SCIP_DECL_BRANCHEXECLP(branchExeclpVanillafullstrong)
SCIP_RETCODE SCIPincludeBranchruleVanillafullstrong(SCIP *scip)
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:2921
#define BRANCHRULE_MAXBOUNDDIST
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
public methods for the LP relaxation, rows and columns
static SCIP_DECL_BRANCHFREE(branchFreeVanillafullstrong)
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
SCIP_RETCODE SCIPgetVanillafullstrongData(SCIP *scip, SCIP_VAR ***cands, SCIP_Real **candscores, int *ncands, int *npriocands, int *bestcand)
public methods for branching rule plugins and branching
general public methods
#define MAX(x, y)
Definition: def.h:239
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition: scip_lp.c:247
SCIP_RETCODE SCIPendStrongbranch(SCIP *scip)
Definition: scip_var.c:2746
public methods for message output
#define SCIP_Real
Definition: def.h:173
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:718
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:185
public methods for message handling
#define DEFAULT_INTEGRALCANDS
SCIP_Bool SCIPallColsInLP(SCIP *scip)
Definition: scip_lp.c:649
SCIP_Real SCIPfrac(SCIP *scip, SCIP_Real val)
vanilla full strong LP branching rule
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
#define DEFAULT_IDEMPOTENT
SCIP_Longint SCIPgetNNodes(SCIP *scip)
public methods for global and local (sub)problems
#define BRANCHRULE_NAME
#define BRANCHRULE_MAXDEPTH
#define DEFAULT_DONOTBRANCH
SCIP_Bool SCIPisExactSolve(SCIP *scip)
Definition: scip_general.c:605
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