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