Scippy

SCIP

Solving Constraint Integer Programs

scip_branch.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 scip_branch.c
17  * @ingroup OTHER_CFILES
18  * @brief public methods for branching rule plugins and branching
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Gerald Gamrath
22  * @author Leona Gottwald
23  * @author Stefan Heinz
24  * @author Gregor Hendel
25  * @author Thorsten Koch
26  * @author Alexander Martin
27  * @author Marc Pfetsch
28  * @author Michael Winkler
29  * @author Kati Wolter
30  *
31  * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include "scip/branch.h"
37 #include "scip/debug.h"
38 #include "scip/lp.h"
39 #include "scip/pub_message.h"
40 #include "scip/pub_var.h"
41 #include "scip/var.h"
42 #include "scip/scip_branch.h"
43 #include "scip/scip_numerics.h"
44 #include "scip/set.h"
45 #include "scip/struct_mem.h"
46 #include "scip/struct_primal.h"
47 #include "scip/struct_scip.h"
48 #include "scip/struct_set.h"
49 #include "scip/struct_var.h"
50 #include "scip/tree.h"
51 
52 
53 /** creates a branching rule and includes it in SCIP
54  *
55  * @note method has all branching rule callbacks as arguments and is thus changed every time a new
56  * callback is added in future releases; consider using SCIPincludeBranchruleBasic() and setter functions
57  * if you seek for a method which is less likely to change in future releases
58  */
60  SCIP* scip, /**< SCIP data structure */
61  const char* name, /**< name of branching rule */
62  const char* desc, /**< description of branching rule */
63  int priority, /**< priority of the branching rule */
64  int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
65  SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
66  * compared to best node's dual bound for applying branching rule
67  * (0.0: only on current best node, 1.0: on all nodes) */
68  SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
69  SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */
70  SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */
71  SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */
72  SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
73  SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
74  SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
75  SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external candidates */
76  SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
77  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
78  )
79 {
80  SCIP_BRANCHRULE* branchrule;
81 
82  SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBranchrule", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
83 
84  /* check whether branching rule is already present */
85  if( SCIPfindBranchrule(scip, name) != NULL )
86  {
87  SCIPerrorMessage("branching rule <%s> already included.\n", name);
88  return SCIP_INVALIDDATA;
89  }
90 
91  SCIP_CALL( SCIPbranchruleCreate(&branchrule, scip->set, scip->messagehdlr, scip->mem->setmem,
92  name, desc, priority, maxdepth,
93  maxbounddist, branchcopy, branchfree, branchinit, branchexit, branchinitsol, branchexitsol,
94  branchexeclp, branchexecext, branchexecps, branchruledata) );
95  SCIP_CALL( SCIPsetIncludeBranchrule(scip->set, branchrule) );
96 
97  return SCIP_OKAY;
98 }
99 
100 /** creates a branching rule and includes it in SCIP. All non-fundamental (or optional) callbacks will be set to NULL.
101  * Optional callbacks can be set via specific setter functions, see SCIPsetBranchruleInit(), SCIPsetBranchruleExit(),
102  * SCIPsetBranchruleCopy(), SCIPsetBranchruleFree(), SCIPsetBranchruleInitsol(), SCIPsetBranchruleExitsol(),
103  * SCIPsetBranchruleExecLp(), SCIPsetBranchruleExecExt(), and SCIPsetBranchruleExecPs().
104  *
105  * @note if you want to set all callbacks with a single method call, consider using SCIPincludeBranchrule() instead
106  */
108  SCIP* scip, /**< SCIP data structure */
109  SCIP_BRANCHRULE** branchruleptr, /**< pointer to branching rule, or NULL */
110  const char* name, /**< name of branching rule */
111  const char* desc, /**< description of branching rule */
112  int priority, /**< priority of the branching rule */
113  int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
114  SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
115  * compared to best node's dual bound for applying branching rule
116  * (0.0: only on current best node, 1.0: on all nodes) */
117  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
118  )
119 {
120  SCIP_BRANCHRULE* branchrule;
121 
122  SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeBranchruleBasic", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
123 
124  /* check whether branching rule is already present */
125  if( SCIPfindBranchrule(scip, name) != NULL )
126  {
127  SCIPerrorMessage("branching rule <%s> already included.\n", name);
128  return SCIP_INVALIDDATA;
129  }
130 
131  SCIP_CALL( SCIPbranchruleCreate(&branchrule, scip->set, scip->messagehdlr, scip->mem->setmem, name, desc, priority, maxdepth,
132  maxbounddist, NULL, NULL, NULL, NULL, NULL, NULL,
133  NULL, NULL, NULL, branchruledata) );
134 
135  SCIP_CALL( SCIPsetIncludeBranchrule(scip->set, branchrule) );
136 
137  if( branchruleptr != NULL )
138  *branchruleptr = branchrule;
139 
140  return SCIP_OKAY;
141 }
142 
143 /** sets copy method of branching rule */
145  SCIP* scip, /**< SCIP data structure */
146  SCIP_BRANCHRULE* branchrule, /**< branching rule */
147  SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
148  )
149 {
150  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleCopy", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
151 
152  assert(branchrule != NULL);
153 
154  SCIPbranchruleSetCopy(branchrule, branchcopy);
155 
156  return SCIP_OKAY;
157 }
158 
159 /** sets destructor method of branching rule */
161  SCIP* scip, /**< SCIP data structure */
162  SCIP_BRANCHRULE* branchrule, /**< branching rule */
163  SCIP_DECL_BRANCHFREE ((*branchfree)) /**< destructor of branching rule */
164  )
165 {
166  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleFree", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
167 
168  assert(branchrule != NULL);
169 
170  SCIPbranchruleSetFree(branchrule, branchfree);
171 
172  return SCIP_OKAY;
173 }
174 
175 /** sets initialization method of branching rule */
177  SCIP* scip, /**< SCIP data structure */
178  SCIP_BRANCHRULE* branchrule, /**< branching rule */
179  SCIP_DECL_BRANCHINIT ((*branchinit)) /**< initialize branching rule */
180  )
181 {
182  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleInit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
183 
184  assert(branchrule != NULL);
185 
186  SCIPbranchruleSetInit(branchrule, branchinit);
187 
188  return SCIP_OKAY;
189 }
190 
191 /** sets deinitialization method of branching rule */
193  SCIP* scip, /**< SCIP data structure */
194  SCIP_BRANCHRULE* branchrule, /**< branching rule */
195  SCIP_DECL_BRANCHEXIT ((*branchexit)) /**< deinitialize branching rule */
196  )
197 {
198  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExit", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
199 
200  assert(branchrule != NULL);
201 
202  SCIPbranchruleSetExit(branchrule, branchexit);
203 
204  return SCIP_OKAY;
205 }
206 
207 /** sets solving process initialization method of branching rule */
209  SCIP* scip, /**< SCIP data structure */
210  SCIP_BRANCHRULE* branchrule, /**< branching rule */
211  SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
212  )
213 {
214  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleInitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
215 
216  assert(branchrule != NULL);
217 
218  SCIPbranchruleSetInitsol(branchrule, branchinitsol);
219 
220  return SCIP_OKAY;
221 }
222 
223 /** sets solving process deinitialization method of branching rule */
225  SCIP* scip, /**< SCIP data structure */
226  SCIP_BRANCHRULE* branchrule, /**< branching rule */
227  SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
228  )
229 {
230  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExitsol", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
231 
232  assert(branchrule != NULL);
233 
234  SCIPbranchruleSetExitsol(branchrule, branchexitsol);
235 
236  return SCIP_OKAY;
237 }
238 
239 /** sets branching execution method for fractional LP solutions */
241  SCIP* scip, /**< SCIP data structure */
242  SCIP_BRANCHRULE* branchrule, /**< branching rule */
243  SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
244  )
245 {
246  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecLp", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
247 
248  assert(branchrule != NULL);
249 
250  SCIPbranchruleSetExecLp(branchrule, branchexeclp);
251 
252  return SCIP_OKAY;
253 }
254 
255 /** sets branching execution method for external candidates */
257  SCIP* scip, /**< SCIP data structure */
258  SCIP_BRANCHRULE* branchrule, /**< branching rule */
259  SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
260  )
261 {
262  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecExt", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
263 
264  assert(branchrule != NULL);
265 
266  SCIPbranchruleSetExecExt(branchrule, branchexecext);
267 
268  return SCIP_OKAY;
269 }
270 
271 /** sets branching execution method for not completely fixed pseudo solutions */
273  SCIP* scip, /**< SCIP data structure */
274  SCIP_BRANCHRULE* branchrule, /**< branching rule */
275  SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
276  )
277 {
278  SCIP_CALL( SCIPcheckStage(scip, "SCIPsetBranchruleExecPs", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE) );
279 
280  assert(branchrule != NULL);
281 
282  SCIPbranchruleSetExecPs(branchrule, branchexecps);
283 
284  return SCIP_OKAY;
285 }
286 
287 /** returns the branching rule of the given name, or NULL if not existing */
289  SCIP* scip, /**< SCIP data structure */
290  const char* name /**< name of branching rule */
291  )
292 {
293  assert(scip != NULL);
294  assert(scip->set != NULL);
295  assert(name != NULL);
296 
298 
299  return SCIPsetFindBranchrule(scip->set, name);
300 }
301 
302 /** returns the array of currently available branching rules */
304  SCIP* scip /**< SCIP data structure */
305  )
306 {
307  assert(scip != NULL);
308  assert(scip->set != NULL);
309 
310  return scip->set->branchrules;
311 }
312 
313 /** returns the number of currently available branching rules */
315  SCIP* scip /**< SCIP data structure */
316  )
317 {
318  assert(scip != NULL);
319  assert(scip->set != NULL);
320 
321  return scip->set->nbranchrules;
322 }
323 
324 /** sets the priority of a branching rule */
326  SCIP* scip, /**< SCIP data structure */
327  SCIP_BRANCHRULE* branchrule, /**< branching rule */
328  int priority /**< new priority of the branching rule */
329  )
330 {
331  assert(scip != NULL);
332  assert(scip->set != NULL);
333 
334  SCIPbranchruleSetPriority(branchrule, scip->set, priority);
335 
336  return SCIP_OKAY;
337 }
338 
339 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
341  SCIP* scip, /**< SCIP data structure */
342  SCIP_BRANCHRULE* branchrule, /**< branching rule */
343  int maxdepth /**< new maxdepth of the branching rule */
344  )
345 {
346  assert(scip != NULL);
347  assert(scip->set != NULL);
348 
349  SCIPbranchruleSetMaxdepth(branchrule, maxdepth);
350 
351  return SCIP_OKAY;
352 }
353 
354 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
356  SCIP* scip, /**< SCIP data structure */
357  SCIP_BRANCHRULE* branchrule, /**< branching rule */
358  SCIP_Real maxbounddist /**< new maxbounddist of the branching rule */
359  )
360 {
361  assert(scip != NULL);
362  assert(scip->set != NULL);
363 
364  SCIPbranchruleSetMaxbounddist(branchrule, maxbounddist);
365 
366  return SCIP_OKAY;
367 }
368 
369 /** gets branching candidates for LP solution branching (fractional variables) along with solution values,
370  * fractionalities, and number of branching candidates; The number of branching candidates does NOT
371  * account for fractional implicit integer variables which should not be used for branching decisions.
372  *
373  * Fractional implicit integer variables are stored at the positions *nlpcands to *nlpcands + *nfracimplvars - 1
374  *
375  * branching rules should always select the branching candidate among the first npriolpcands of the candidate
376  * list
377  *
378  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
379  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
380  *
381  * @pre This method can be called if @p scip is in one of the following stages:
382  * - \ref SCIP_STAGE_SOLVING
383  *
384  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
385  */
387  SCIP* scip, /**< SCIP data structure */
388  SCIP_VAR*** lpcands, /**< pointer to store the array of LP branching candidates, or NULL */
389  SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */
390  SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */
391  int* nlpcands, /**< pointer to store the number of LP branching candidates, or NULL */
392  int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */
393  int* nfracimplvars /**< pointer to store the number of fractional implicit integer variables, or NULL */
394  )
395 {
396  SCIP_CALL( SCIPcheckStage(scip, "SCIPgetLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
397 
399  {
400  SCIPerrorMessage("LP not solved to optimality - solstat=%d\n", SCIPlpGetSolstat(scip->lp));
401  return SCIP_INVALIDDATA;
402  }
403 
404  SCIP_CALL( SCIPbranchcandGetLPCands(scip->branchcand, scip->set, scip->stat, scip->lp,
405  lpcands, lpcandssol, lpcandsfrac, nlpcands, npriolpcands, nfracimplvars) );
406 
407  return SCIP_OKAY;
408 }
409 
410 /** gets number of branching candidates for LP solution branching (number of fractional variables)
411  *
412  * @return the number of branching candidates for LP solution branching (number of fractional variables).
413  *
414  * @pre This method can be called if @p scip is in one of the following stages:
415  * - \ref SCIP_STAGE_SOLVING
416  *
417  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
418  */
420  SCIP* scip /**< SCIP data structure */
421  )
422 {
423  SCIP_RETCODE retcode;
424  int nlpcands;
425 
426  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
427 
429  {
430  SCIPerrorMessage("LP not solved to optimality\n");
431  SCIPABORT();
432  return 0; /*lint !e527*/
433  }
434 
435  retcode = SCIPbranchcandGetLPCands(scip->branchcand, scip->set, scip->stat, scip->lp,
436  NULL, NULL, NULL, &nlpcands, NULL, NULL);
437 
438  if( retcode != SCIP_OKAY )
439  {
440  SCIPerrorMessage("Error <%u> during computation of the number of LP branching candidates\n", retcode);
441  SCIPABORT();
442  return 0; /*lint !e527*/
443  }
444 
445  return nlpcands;
446 }
447 
448 /** gets number of branching candidates with maximal priority for LP solution branching
449  *
450  * @return the number of branching candidates with maximal priority for LP solution branching.
451  *
452  * @pre This method can be called if @p scip is in one of the following stages:
453  * - \ref SCIP_STAGE_SOLVING
454  *
455  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
456  */
458  SCIP* scip /**< SCIP data structure */
459  )
460 {
461  SCIP_RETCODE retcode;
462  int npriolpcands;
463 
464  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioLPBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
465 
467  {
468  SCIPerrorMessage("LP not solved to optimality\n");
469  SCIPABORT();
470  return 0; /*lint !e527*/
471  }
472 
473  retcode = SCIPbranchcandGetLPCands(scip->branchcand, scip->set, scip->stat, scip->lp,
474  NULL, NULL, NULL, NULL, &npriolpcands, NULL);
475 
476  if( retcode != SCIP_OKAY )
477  {
478  SCIPerrorMessage("Error <%u> during computation of the number of LP branching candidates with maximal priority\n", retcode);
479  SCIPABORT();
480  return 0; /*lint !e527*/
481  }
482 
483  return npriolpcands;
484 }
485 
486 /** gets external branching candidates along with solution values, scores, and number of branching candidates;
487  * these branching candidates can be used by relaxations or nonlinear constraint handlers;
488  * branching rules should always select the branching candidate among the first nprioexterncands of the candidate
489  * list
490  *
491  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
492  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
493  *
494  * @pre This method can be called if @p scip is in one of the following stages:
495  * - \ref SCIP_STAGE_SOLVING
496  *
497  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
498  *
499  * @note Candidate variables with maximal priority are ordered: binaries first, then integers, implicit integers and
500  * continuous last.
501  */
503  SCIP* scip, /**< SCIP data structure */
504  SCIP_VAR*** externcands, /**< pointer to store the array of extern branching candidates, or NULL */
505  SCIP_Real** externcandssol, /**< pointer to store the array of extern candidate solution values, or NULL */
506  SCIP_Real** externcandsscore, /**< pointer to store the array of extern candidate scores, or NULL */
507  int* nexterncands, /**< pointer to store the number of extern branching candidates, or NULL */
508  int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */
509  int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */
510  int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */
511  int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority,
512  * or NULL */
513  )
514 {
515  assert(scip != NULL);
516 
517  SCIP_CALL( SCIPcheckStage(scip, "SCIPgetExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
518 
519  SCIP_CALL( SCIPbranchcandGetExternCands(scip->branchcand, externcands, externcandssol, externcandsscore, nexterncands,
520  nprioexterncands, nprioexternbins, nprioexternints, nprioexternimpls) );
521 
522  return SCIP_OKAY;
523 }
524 
525 /** gets number of external branching candidates
526  *
527  * @return the number of external branching candidates.
528  *
529  * @pre This method can be called if @p scip is in one of the following stages:
530  * - \ref SCIP_STAGE_SOLVING
531  *
532  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
533  */
535  SCIP* scip /**< SCIP data structure */
536  )
537 {
538  assert(scip != NULL);
539 
540  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
541 
543 }
544 
545 /** gets number of external branching candidates with maximal branch priority
546  *
547  * @return the number of external branching candidates with maximal branch priority.
548  *
549  * @pre This method can be called if @p scip is in one of the following stages:
550  * - \ref SCIP_STAGE_SOLVING
551  *
552  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
553  */
555  SCIP* scip /**< SCIP data structure */
556  )
557 {
558  assert(scip != NULL);
559 
560  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
561 
563 }
564 
565 /** gets number of binary external branching candidates with maximal branch priority
566  *
567  * @return the number of binary external branching candidates with maximal branch priority.
568  *
569  * @pre This method can be called if @p scip is in one of the following stages:
570  * - \ref SCIP_STAGE_SOLVING
571  *
572  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
573  */
575  SCIP* scip /**< SCIP data structure */
576  )
577 {
578  assert(scip != NULL);
579 
580  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchBins", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
581 
583 }
584 
585 /** gets number of integer external branching candidates with maximal branch priority
586  *
587  * @return the number of integer external branching candidates with maximal branch priority.
588  *
589  * @pre This method can be called if @p scip is in one of the following stages:
590  * - \ref SCIP_STAGE_SOLVING
591  *
592  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
593  */
595  SCIP* scip /**< SCIP data structure */
596  )
597 {
598  assert(scip != NULL);
599 
600  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchInts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
601 
603 }
604 
605 /** gets number of implicit integer external branching candidates with maximal branch priority
606  *
607  * @return the number of implicit integer external branching candidates with maximal branch priority.
608  *
609  * @pre This method can be called if @p scip is in one of the following stages:
610  * - \ref SCIP_STAGE_SOLVING
611  *
612  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
613  */
615  SCIP* scip /**< SCIP data structure */
616  )
617 {
618  assert(scip != NULL);
619 
620  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchImpls", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
621 
623 }
624 
625 /** gets number of continuous external branching candidates with maximal branch priority
626  *
627  * @return the number of continuous external branching candidates with maximal branch priority.
628  *
629  * @pre This method can be called if @p scip is in one of the following stages:
630  * - \ref SCIP_STAGE_SOLVING
631  *
632  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
633  */
635  SCIP* scip /**< SCIP data structure */
636  )
637 {
638  assert(scip != NULL);
639 
640  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioExternBranchConts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
641 
643 }
644 
645 /** insert variable, its score and its solution value into the external branching candidate storage
646  * the relative difference of the current lower and upper bounds of a continuous variable must be at least epsilon
647  *
648  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
649  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
650  *
651  * @pre This method can be called if @p scip is in one of the following stages:
652  * - \ref SCIP_STAGE_SOLVING
653  *
654  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
655  */
657  SCIP* scip, /**< SCIP data structure */
658  SCIP_VAR* var, /**< variable to insert */
659  SCIP_Real score, /**< score of external candidate, e.g. infeasibility */
660  SCIP_Real solval /**< value of the variable in the current solution */
661  )
662 {
663  assert(scip != NULL);
664  assert(var->scip == scip);
665 
666  SCIP_CALL( SCIPcheckStage(scip, "SCIPaddExternBranchCand", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
667 
668  SCIP_CALL( SCIPbranchcandAddExternCand(scip->branchcand, scip->set, var, score, solval) );
669 
670  return SCIP_OKAY;
671 }
672 
673 /** removes all external candidates from the storage for external branching
674  *
675  * @pre This method can be called if @p scip is in one of the following stages:
676  * - \ref SCIP_STAGE_SOLVING
677  *
678  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
679  */
681  SCIP* scip /**< SCIP data structure */
682  )
683 {
684  assert(scip != NULL);
685 
686  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPclearExternBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
687 
689 }
690 
691 /** checks whether the given variable is contained in the candidate storage for external branching
692  *
693  * @return whether the given variable is contained in the candidate storage for external branching.
694  *
695  * @pre This method can be called if @p scip is in one of the following stages:
696  * - \ref SCIP_STAGE_SOLVING
697  *
698  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
699  */
701  SCIP* scip, /**< SCIP data structure */
702  SCIP_VAR* var /**< variable to look for */
703  )
704 {
705  assert(scip != NULL);
706  assert(var->scip == scip);
707 
708  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcontainsExternBranchCand", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
709 
710  return SCIPbranchcandContainsExternCand(scip->branchcand, var);
711 }
712 
713 /** gets branching candidates for pseudo solution branching (non-fixed variables) along with the number of candidates
714  *
715  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
716  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
717  *
718  * @pre This method can be called if @p scip is in one of the following stages:
719  * - \ref SCIP_STAGE_PRESOLVING
720  * - \ref SCIP_STAGE_SOLVING
721  *
722  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
723  */
725  SCIP* scip, /**< SCIP data structure */
726  SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
727  int* npseudocands, /**< pointer to store the number of pseudo branching candidates, or NULL */
728  int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
729  )
730 {
731  SCIP_CALL( SCIPcheckStage(scip, "SCIPgetPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
732 
734  pseudocands, npseudocands, npriopseudocands) );
735 
736  return SCIP_OKAY;
737 }
738 
739 /** gets number of branching candidates for pseudo solution branching (non-fixed variables)
740  *
741  * @return the number branching candidates for pseudo solution branching (non-fixed variables).
742  *
743  * @pre This method can be called if @p scip is in one of the following stages:
744  * - \ref SCIP_STAGE_PRESOLVING
745  * - \ref SCIP_STAGE_SOLVING
746  *
747  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
748  */
750  SCIP* scip /**< SCIP data structure */
751  )
752 {
753  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
754 
756 }
757 
758 /** gets number of branching candidates with maximal branch priority for pseudo solution branching
759  *
760  * @return the number of branching candidates with maximal branch priority for pseudo solution branching.
761  *
762  * @pre This method can be called if @p scip is in one of the following stages:
763  * - \ref SCIP_STAGE_PRESOLVING
764  * - \ref SCIP_STAGE_SOLVING
765  *
766  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
767  */
769  SCIP* scip /**< SCIP data structure */
770  )
771 {
772  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchCands", FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
773 
775 }
776 
777 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching
778  *
779  * @return the number of binary branching candidates with maximal branch priority for pseudo solution branching.
780  *
781  * @pre This method can be called if @p scip is in one of the following stages:
782  * - \ref SCIP_STAGE_SOLVING
783  *
784  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
785  */
787  SCIP* scip /**< SCIP data structure */
788  )
789 {
790  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchBins", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
791 
793 }
794 
795 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching
796  *
797  * @return the number of integer branching candidates with maximal branch priority for pseudo solution branching.
798  *
799  * @pre This method can be called if @p scip is in one of the following stages:
800  * - \ref SCIP_STAGE_SOLVING
801  *
802  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
803  */
805  SCIP* scip /**< SCIP data structure */
806  )
807 {
808  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchInts", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
809 
811 }
812 
813 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching
814  *
815  * @return the number of implicit integer branching candidates with maximal branch priority for pseudo solution branching.
816  *
817  * @pre This method can be called if @p scip is in one of the following stages:
818  * - \ref SCIP_STAGE_SOLVING
819  *
820  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
821  */
823  SCIP* scip /**< SCIP data structure */
824  )
825 {
826  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetNPrioPseudoBranchImpls", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
827 
829 }
830 
831 /** calculates the branching score out of the gain predictions for a binary branching
832  *
833  * @return the branching score out of the gain predictions for a binary branching.
834  *
835  * @pre This method can be called if @p scip is in one of the following stages:
836  * - \ref SCIP_STAGE_SOLVING
837  *
838  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
839  */
841  SCIP* scip, /**< SCIP data structure */
842  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
843  SCIP_Real downgain, /**< prediction of objective gain for rounding downwards */
844  SCIP_Real upgain /**< prediction of objective gain for rounding upwards */
845  )
846 {
847  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchScore", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
848 
849  assert( var == NULL || var->scip == scip );
850 
851  return SCIPbranchGetScore(scip->set, var, downgain, upgain);
852 }
853 
854 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children
855  *
856  * @return the branching score out of the gain predictions for a branching with arbitrary many children.
857  *
858  * @pre This method can be called if @p scip is in one of the following stages:
859  * - \ref SCIP_STAGE_SOLVING
860  *
861  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
862  */
864  SCIP* scip, /**< SCIP data structure */
865  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
866  int nchildren, /**< number of children that the branching will create */
867  SCIP_Real* gains /**< prediction of objective gain for each child */
868  )
869 {
870  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchScoreMultiple", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
871 
872  assert( var->scip == scip );
873 
874  return SCIPbranchGetScoreMultiple(scip->set, var, nchildren, gains);
875 }
876 
877 /** computes a branching point for a continuous or discrete variable
878  *
879  * @see SCIPbranchGetBranchingPoint
880  *
881  * @return the branching point for a continuous or discrete variable.
882  *
883  * @pre This method can be called if @p scip is in one of the following stages:
884  * - \ref SCIP_STAGE_SOLVING
885  *
886  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
887  */
889  SCIP* scip, /**< SCIP data structure */
890  SCIP_VAR* var, /**< variable, of which the branching point should be computed */
891  SCIP_Real suggestion /**< suggestion for branching point, or SCIP_INVALID if no suggestion */
892  )
893 {
894  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPgetBranchingPoint", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
895 
896  assert( var->scip == scip );
897 
898  return SCIPbranchGetBranchingPoint(scip->set, scip->tree, var, suggestion);
899 }
900 
901 /** calculates the node selection priority for moving the given variable's LP value to the given target value;
902  * this node selection priority can be given to the SCIPcreateChild() call
903  *
904  * @return the node selection priority for moving the given variable's LP value to the given target value.
905  *
906  * @pre This method can be called if @p scip is in one of the following stages:
907  * - \ref SCIP_STAGE_SOLVING
908  *
909  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
910  */
912  SCIP* scip, /**< SCIP data structure */
913  SCIP_VAR* var, /**< variable on which the branching is applied */
914  SCIP_BRANCHDIR branchdir, /**< type of branching that was performed: upwards, downwards, or fixed;
915  * fixed should only be used, when both bounds changed
916  */
917  SCIP_Real targetvalue /**< new value of the variable in the child node */
918  )
919 {
920  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcalcNodeselPriority", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
921 
922  assert( var->scip == scip );
923 
924  return SCIPtreeCalcNodeselPriority(scip->tree, scip->set, scip->stat, var, branchdir, targetvalue);
925 }
926 
927 /** calculates an estimate for the objective of the best feasible solution contained in the subtree after applying the given
928  * branching; this estimate can be given to the SCIPcreateChild() call
929  *
930  * @return the estimate for the objective of the best feasible solution contained in the subtree after applying the given
931  * branching.
932  *
933  * @pre This method can be called if @p scip is in one of the following stages:
934  * - \ref SCIP_STAGE_SOLVING
935  *
936  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
937  */
939  SCIP* scip, /**< SCIP data structure */
940  SCIP_VAR* var, /**< variable on which the branching is applied */
941  SCIP_Real targetvalue /**< new value of the variable in the child node */
942  )
943 {
944  SCIP_CALL_ABORT( SCIPcheckStage(scip, "SCIPcalcChildEstimate", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
945 
946  assert( var->scip == scip );
947 
948  return SCIPtreeCalcChildEstimate(scip->tree, scip->set, scip->stat, var, targetvalue);
949 }
950 
951 /** calculates the increase of the estimate for the objective of the best feasible solution contained in the subtree
952  * after applying the given branching
953  *
954  * @return the increase of the estimate for the objective of the best feasible solution contained in the subtree after
955  * applying the given branching.
956  *
957  * @pre This method can be called if @p scip is in one of the following stages:
958  * - \ref SCIP_STAGE_SOLVING
959  *
960  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
961  */
963  SCIP* scip, /**< SCIP data structure */
964  SCIP_VAR* var, /**< variable on which the branching is applied */
965  SCIP_Real varsol, /**< solution value of variable */
966  SCIP_Real targetvalue /**< new value of the variable in the child node */
967  )
968 {
969  SCIP_Real estimateinc;
970 
971  assert(scip != NULL);
972  assert(var != NULL);
973 
974  /* compute increase above parent node's (i.e., focus node's) estimate value */
976  estimateinc = SCIPvarGetPseudocost(var, scip->stat, targetvalue - varsol);
977  else
978  {
979  SCIP_Real pscdown;
980  SCIP_Real pscup;
981 
982  /* calculate estimate based on pseudo costs:
983  * estimate = lowerbound + sum(min{f_j * pscdown_j, (1-f_j) * pscup_j})
984  * = parentestimate - min{f_b * pscdown_b, (1-f_b) * pscup_b} + (targetvalue-oldvalue)*{pscdown_b or pscup_b}
985  */
986  pscdown = SCIPvarGetPseudocost(var, scip->stat, SCIPsetFeasFloor(scip->set, varsol) - varsol);
987  pscup = SCIPvarGetPseudocost(var, scip->stat, SCIPsetFeasCeil(scip->set, varsol) - varsol);
988  estimateinc = SCIPvarGetPseudocost(var, scip->stat, targetvalue - varsol) - MIN(pscdown, pscup);
989  }
990 
991  /* due to rounding errors estimateinc might be slightly negative */
992  if( estimateinc > 0.0 )
993  estimateinc = 0.0;
994 
995  return estimateinc;
996 }
997 
998 /** creates a child node of the focus node
999  *
1000  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1001  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1002  *
1003  * @pre This method can be called if @p scip is in one of the following stages:
1004  * - \ref SCIP_STAGE_SOLVING
1005  *
1006  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1007  */
1009  SCIP* scip, /**< SCIP data structure */
1010  SCIP_NODE** node, /**< pointer to node data structure */
1011  SCIP_Real nodeselprio, /**< node selection priority of new node */
1012  SCIP_Real estimate /**< estimate for(transformed) objective value of best feasible solution in subtree */
1013  )
1014 {
1015  assert(node != NULL);
1016 
1017  SCIP_CALL( SCIPcheckStage(scip, "SCIPcreateChild", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1018 
1019  SCIP_CALL( SCIPnodeCreateChild(node, scip->mem->probmem, scip->set, scip->stat, scip->tree, nodeselprio, estimate) );
1020 
1021  return SCIP_OKAY;
1022 }
1023 
1024 /** branches on a non-continuous variable v using the current LP or pseudo solution;
1025  * if solution value x' is fractional, two child nodes will be created
1026  * (x <= floor(x'), x >= ceil(x')),
1027  * if solution value is integral, the x' is equal to lower or upper bound of the branching
1028  * variable and the bounds of v are finite, then two child nodes will be created
1029  * (x <= x'', x >= x''+1 with x'' = floor((lb + ub)/2)),
1030  * otherwise (up to) three child nodes will be created
1031  * (x <= x'-1, x == x', x >= x'+1)
1032  *
1033  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1034  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1035  *
1036  * @pre This method can be called if @p scip is in one of the following stages:
1037  * - \ref SCIP_STAGE_SOLVING
1038  *
1039  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1040  */
1042  SCIP* scip, /**< SCIP data structure */
1043  SCIP_VAR* var, /**< variable to branch on */
1044  SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
1045  SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
1046  SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
1047  )
1048 {
1049  SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVar", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1050 
1051  assert( var->scip == scip );
1052 
1054  {
1055  SCIPerrorMessage("cannot branch on continuous variable <%s>\n", SCIPvarGetName(var));
1056  return SCIP_INVALIDDATA;
1057  }
1058 
1059  if( SCIPsetIsEQ(scip->set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
1060  {
1061  SCIPerrorMessage("cannot branch on variable <%s> with fixed domain [%.15g,%.15g]\n",
1063  return SCIP_INVALIDDATA;
1064  }
1065 
1066  SCIP_CALL( SCIPtreeBranchVar(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1067  scip->lp, scip->branchcand, scip->eventqueue, var, SCIP_INVALID, downchild, eqchild, upchild) );
1068 
1069  return SCIP_OKAY;
1070 }
1071 
1072 /** branches a variable x using a given domain hole; two child nodes (x <= left, x >= right) are created
1073  *
1074  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1075  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1076  *
1077  * @pre This method can be called if @p scip is in one of the following stages:
1078  * - \ref SCIP_STAGE_SOLVING
1079  *
1080  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1081  */
1083  SCIP* scip, /**< SCIP data structure */
1084  SCIP_VAR* var, /**< variable to branch on */
1085  SCIP_Real left, /**< left side of the domain hole */
1086  SCIP_Real right, /**< right side of the domain hole */
1087  SCIP_NODE** downchild, /**< pointer to return the left child (x <= left), or NULL */
1088  SCIP_NODE** upchild /**< pointer to return the right child (x >= right), or NULL */
1089  )
1090 {
1091  SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarHole", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1092 
1093  assert( var->scip == scip );
1094 
1095  SCIP_CALL( SCIPtreeBranchVarHole(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
1096  scip->origprob, scip->lp, scip->branchcand, scip->eventqueue, var, left, right, downchild, upchild) );
1097 
1098  return SCIP_OKAY;
1099 }
1100 
1101 /** branches on a variable x using a given value x';
1102  * for continuous variables with relative domain width larger epsilon, x' must not be one of the bounds;
1103  * two child nodes (x <= x', x >= x') are created;
1104  * for integer variables, if solution value x' is fractional, two child nodes are created
1105  * (x <= floor(x'), x >= ceil(x')),
1106  * if x' is integral, three child nodes are created
1107  * (x <= x'-1, x == x', x >= x'+1)
1108  *
1109  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1110  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1111  *
1112  * @pre This method can be called if @p scip is in one of the following stages:
1113  * - \ref SCIP_STAGE_SOLVING
1114  *
1115  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1116  */
1118  SCIP* scip, /**< SCIP data structure */
1119  SCIP_VAR* var, /**< variable to branch on */
1120  SCIP_Real val, /**< value to branch on */
1121  SCIP_NODE** downchild, /**< pointer to return the left child with variable rounded down, or NULL */
1122  SCIP_NODE** eqchild, /**< pointer to return the middle child with variable fixed, or NULL */
1123  SCIP_NODE** upchild /**< pointer to return the right child with variable rounded up, or NULL */
1124  )
1125 {
1126  SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarVal", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1127 
1128  assert( var->scip == scip );
1129 
1130  /* A continuous variable will be fixed if SCIPisRelEQ(lb,ub) is true. Otherwise, the given branching value should be
1131  * such that its value is not equal to one of the bounds. We assert this by requiring that it is at least eps/2 away
1132  * from each bound. The 2.1 is there, because ub-lb may be in (eps, 2*eps], in which case there is no way to choose a
1133  * branching value that is at least eps away from both bounds. However, if the variable bounds are below/above
1134  * -/+infinity * 2.1, then SCIPisLT will give an assert, so we omit the check in this case.
1135  */
1136  assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ||
1137  SCIPisRelEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ||
1138  SCIPisInfinity(scip, -2.1*SCIPvarGetLbLocal(var)) || SCIPisInfinity(scip, 2.1*SCIPvarGetUbLocal(var)) ||
1139  (SCIPisLT(scip, 2.1*SCIPvarGetLbLocal(var), 2.1*val) && SCIPisLT(scip, 2.1*val, 2.1*SCIPvarGetUbLocal(var)) ) );
1140 
1141  if( SCIPsetIsEQ(scip->set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
1142  {
1143  SCIPerrorMessage("cannot branch on variable <%s> with fixed domain [%.15g,%.15g]\n",
1145  return SCIP_INVALIDDATA;
1146  }
1147 
1148  SCIP_CALL( SCIPtreeBranchVar(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1149  scip->lp, scip->branchcand, scip->eventqueue, var, val, downchild, eqchild, upchild) );
1150 
1151  return SCIP_OKAY;
1152 }
1153 
1154 /** n-ary branching on a variable x using a given value
1155  *
1156  * Branches on variable x such that up to n/2 children are created on each side of the usual branching value.
1157  * The branching value is selected as in SCIPbranchVarVal().
1158  * The parameters minwidth and widthfactor determine the domain width of the branching variable in the child nodes.
1159  * If n is odd, one child with domain width 'width' and having the branching value in the middle is created.
1160  * Otherwise, two children with domain width 'width' and being left and right of the branching value are created.
1161  * Next further nodes to the left and right are created, where width is multiplied by widthfactor with increasing distance
1162  * from the first nodes.
1163  * The initial width is calculated such that n/2 nodes are created to the left and to the right of the branching value.
1164  * If this value is below minwidth, the initial width is set to minwidth, which may result in creating less than n nodes.
1165  *
1166  * Giving a large value for widthfactor results in creating children with small domain when close to the branching value
1167  * and large domain when closer to the current variable bounds. That is, setting widthfactor to a very large value and n to 3
1168  * results in a ternary branching where the branching variable is mostly fixed in the middle child.
1169  * Setting widthfactor to 1.0 results in children where the branching variable always has the same domain width
1170  * (except for one child if the branching value is not in the middle).
1171  *
1172  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1173  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1174  *
1175  * @pre This method can be called if @p scip is in one of the following stages:
1176  * - \ref SCIP_STAGE_SOLVING
1177  *
1178  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1179  */
1181  SCIP* scip, /**< SCIP data structure */
1182  SCIP_VAR* var, /**< variable to branch on */
1183  SCIP_Real val, /**< value to branch on */
1184  int n, /**< attempted number of children to be created, must be >= 2 */
1185  SCIP_Real minwidth, /**< minimal domain width in children */
1186  SCIP_Real widthfactor, /**< multiplier for children domain width with increasing distance from val, must be >= 1.0 */
1187  int* nchildren /**< pointer to store number of created children, or NULL */
1188  )
1189 {
1190  SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchVarValNary", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1191 
1192  assert( var->scip == scip );
1193 
1194  /* see comment in SCIPbranchVarVal */
1195  assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS ||
1196  SCIPisRelEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) ||
1197  SCIPisInfinity(scip, -2.1*SCIPvarGetLbLocal(var)) || SCIPisInfinity(scip, 2.1*SCIPvarGetUbLocal(var)) ||
1198  (SCIPisLT(scip, 2.1*SCIPvarGetLbLocal(var), 2.1*val) && SCIPisLT(scip, 2.1*val, 2.1*SCIPvarGetUbLocal(var)) ) );
1199 
1200  if( SCIPsetIsEQ(scip->set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
1201  {
1202  SCIPerrorMessage("cannot branch on variable <%s> with fixed domain [%.15g,%.15g]\n",
1204  return SCIP_INVALIDDATA;
1205  }
1206 
1207  SCIP_CALL( SCIPtreeBranchVarNary(scip->tree, scip->reopt, scip->mem->probmem, scip->set, scip->stat, scip->transprob,
1208  scip->origprob, scip->lp, scip->branchcand, scip->eventqueue, var, val, n, minwidth, widthfactor, nchildren) );
1209 
1210  return SCIP_OKAY;
1211 }
1212 
1213 /** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN;
1214  * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional
1215  * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority
1216  *
1217  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1218  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1219  *
1220  * @pre This method can be called if @p scip is in one of the following stages:
1221  * - \ref SCIP_STAGE_SOLVING
1222  *
1223  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1224  */
1226  SCIP* scip, /**< SCIP data structure */
1227  SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
1228  )
1229 {
1230  SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchLP", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1231 
1232  SCIP_CALL( SCIPbranchExecLP(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1233  scip->tree, scip->reopt, scip->lp, scip->sepastore, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound,
1234  TRUE, result) );
1235 
1236  return SCIP_OKAY;
1237 }
1238 
1239 /** calls branching rules to branch on a external candidates; if no such candidates exist, the result is SCIP_DIDNOTRUN
1240  *
1241  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1242  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1243  *
1244  * @pre This method can be called if @p scip is in one of the following stages:
1245  * - \ref SCIP_STAGE_SOLVING
1246  *
1247  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1248  */
1250  SCIP* scip, /**< SCIP data structure */
1251  SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
1252  )
1253 {
1254  SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchExtern", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1255 
1256  SCIP_CALL( SCIPbranchExecExtern(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1257  scip->tree, scip->reopt, scip->lp, scip->sepastore, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound,
1258  TRUE, result) );
1259 
1260  return SCIP_OKAY;
1261 }
1262 
1263 /** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN
1264  *
1265  * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
1266  * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
1267  *
1268  * @pre This method can be called if @p scip is in one of the following stages:
1269  * - \ref SCIP_STAGE_SOLVING
1270  *
1271  * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
1272  */
1274  SCIP* scip, /**< SCIP data structure */
1275  SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
1276  )
1277 {
1278  SCIP_CALL( SCIPcheckStage(scip, "SCIPbranchPseudo", FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE) );
1279 
1280  SCIP_CALL( SCIPbranchExecPseudo(scip->mem->probmem, scip->set, scip->stat, scip->transprob, scip->origprob,
1281  scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue, scip->primal->cutoffbound, TRUE, result) );
1282 
1283  return SCIP_OKAY;
1284 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIP_Real cutoffbound
Definition: struct_primal.h:46
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
SCIP_RETCODE SCIPsetBranchrulePriority(SCIP *scip, SCIP_BRANCHRULE *branchrule, int priority)
Definition: scip_branch.c:325
SCIP_STAT * stat
Definition: struct_scip.h:70
int SCIPbranchcandGetNPrioExternBins(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:527
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPbranchruleCreate(SCIP_BRANCHRULE **branchrule, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_DECL_BRANCHCOPY((*branchcopy)), SCIP_DECL_BRANCHFREE((*branchfree)), SCIP_DECL_BRANCHINIT((*branchinit)), SCIP_DECL_BRANCHEXIT((*branchexit)), SCIP_DECL_BRANCHINITSOL((*branchinitsol)), SCIP_DECL_BRANCHEXITSOL((*branchexitsol)), SCIP_DECL_BRANCHEXECLP((*branchexeclp)), SCIP_DECL_BRANCHEXECEXT((*branchexecext)), SCIP_DECL_BRANCHEXECPS((*branchexecps)), SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1349
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
SCIP_RETCODE SCIPnodeCreateChild(SCIP_NODE **node, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: tree.c:984
SCIP_RETCODE SCIPtreeBranchVar(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: tree.c:5417
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip_branch.c:656
void SCIPbranchruleSetCopy(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: branch.c:1870
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
int SCIPgetNPrioExternBranchCands(SCIP *scip)
Definition: scip_branch.c:554
internal methods for branch and bound tree
SCIP_Bool SCIPcontainsExternBranchCand(SCIP *scip, SCIP_VAR *var)
Definition: scip_branch.c:700
SCIP_Real SCIPtreeCalcChildEstimate(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: tree.c:5358
SCIP_RETCODE SCIPtreeBranchVarHole(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild)
Definition: tree.c:5748
SCIP_RETCODE SCIPsetBranchruleMaxdepth(SCIP *scip, SCIP_BRANCHRULE *branchrule, int maxdepth)
Definition: scip_branch.c:340
#define SCIP_DECL_BRANCHEXECPS(x)
Definition: type_branch.h:167
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:888
int SCIPbranchcandGetNPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:852
SCIP_RETCODE SCIPbranchPseudo(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1273
void SCIPbranchruleSetFree(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: branch.c:1881
SCIP_EVENTQUEUE * eventqueue
Definition: struct_scip.h:80
int SCIPgetNPrioExternBranchConts(SCIP *scip)
Definition: scip_branch.c:634
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:48
SCIP_PRIMAL * primal
Definition: struct_scip.h:85
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:419
int SCIPbranchcandGetNPrioExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:517
SCIP_Real SCIPbranchGetScore(SCIP_SET *set, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: branch.c:2190
#define SCIP_DECL_BRANCHFREE(x)
Definition: type_branch.h:66
SCIP_BRANCHCAND * branchcand
Definition: struct_scip.h:81
#define FALSE
Definition: def.h:73
SCIP_RETCODE SCIPbranchExtern(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1249
SCIP_RETCODE SCIPbranchExecPseudo(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:2747
int SCIPbranchcandGetNPrioPseudoImpls(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:892
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
int SCIPgetNPrioPseudoBranchInts(SCIP *scip)
Definition: scip_branch.c:804
SCIP_EXPORT SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17182
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPbranchVarValNary(SCIP *scip, SCIP_VAR *var, SCIP_Real val, int n, SCIP_Real minwidth, SCIP_Real widthfactor, int *nchildren)
Definition: scip_branch.c:1180
internal methods for branching rules and branching candidate storage
void SCIPbranchcandClearExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:697
public methods for problem variables
#define SCIP_DECL_BRANCHEXECEXT(x)
Definition: type_branch.h:146
SCIP_RETCODE SCIPincludeBranchrule(SCIP *scip, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_DECL_BRANCHCOPY((*branchcopy)), SCIP_DECL_BRANCHFREE((*branchfree)), SCIP_DECL_BRANCHINIT((*branchinit)), SCIP_DECL_BRANCHEXIT((*branchexit)), SCIP_DECL_BRANCHINITSOL((*branchinitsol)), SCIP_DECL_BRANCHEXITSOL((*branchexitsol)), SCIP_DECL_BRANCHEXECLP((*branchexeclp)), SCIP_DECL_BRANCHEXECEXT((*branchexecext)), SCIP_DECL_BRANCHEXECPS((*branchexecps)), SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:59
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
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_PROB * transprob
Definition: struct_scip.h:89
#define SCIP_DECL_BRANCHEXITSOL(x)
Definition: type_branch.h:104
SCIP_BRANCHRULE ** SCIPgetBranchrules(SCIP *scip)
Definition: scip_branch.c:303
int SCIPbranchcandGetNPrioExternInts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:537
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:13047
internal methods for LP management
int SCIPbranchcandGetNPrioPseudoCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:862
int nbranchrules
Definition: struct_set.h:122
SCIP_PROB * origprob
Definition: struct_scip.h:71
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
SCIP_RETCODE SCIPbranchExecLP(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:2514
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:724
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:39
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:749
int SCIPbranchcandGetNExternCands(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:507
SCIP_RETCODE SCIPbranchcandAddExternCand(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: branch.c:569
SCIP_Real SCIPtreeCalcNodeselPriority(SCIP_TREE *tree, SCIP_SET *set, SCIP_STAT *stat, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: tree.c:5208
#define SCIP_DECL_BRANCHINIT(x)
Definition: type_branch.h:74
SCIP_MEM * mem
Definition: struct_scip.h:62
SCIP_Real SCIPcalcChildEstimateIncrease(SCIP *scip, SCIP_VAR *var, SCIP_Real varsol, SCIP_Real targetvalue)
Definition: scip_branch.c:962
SCIP_Real SCIPvarGetPseudocost(SCIP_VAR *var, SCIP_STAT *stat, SCIP_Real solvaldelta)
Definition: var.c:14242
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
#define SCIP_DECL_BRANCHCOPY(x)
Definition: type_branch.h:58
SCIP_RETCODE SCIPbranchcandGetExternCands(SCIP_BRANCHCAND *branchcand, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: branch.c:440
#define SCIPerrorMessage
Definition: pub_message.h:55
int SCIPgetNExternBranchCands(SCIP *scip)
Definition: scip_branch.c:534
SCIP_Real SCIPbranchGetBranchingPoint(SCIP_SET *set, SCIP_TREE *tree, SCIP_VAR *var, SCIP_Real suggestion)
Definition: branch.c:2288
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
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2025
#define SCIP_DECL_BRANCHINITSOL(x)
Definition: type_branch.h:93
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip_branch.c:911
#define SCIP_DECL_BRANCHEXECLP(x)
Definition: type_branch.h:125
SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: scip_branch.c:502
SCIP_RETCODE SCIPbranchcandGetPseudoCands(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_PROB *prob, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: branch.c:788
SCIP_REOPT * reopt
Definition: struct_scip.h:76
SCIP_Real SCIPsetFeasCeil(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6563
void SCIPbranchruleSetInit(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: branch.c:1892
SCIP_RETCODE SCIPbranchcandGetLPCands(SCIP_BRANCHCAND *branchcand, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: branch.c:405
#define NULL
Definition: lpi_spx1.cpp:155
int SCIPgetNPrioPseudoBranchImpls(SCIP *scip)
Definition: scip_branch.c:822
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:364
SCIP main data structure.
BMS_BLKMEM * setmem
Definition: struct_mem.h:39
SCIP_RETCODE SCIPbranchVarHole(SCIP *scip, SCIP_VAR *var, SCIP_Real left, SCIP_Real right, SCIP_NODE **downchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1082
SCIP_Bool SCIPsetIsEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6009
SCIP_Bool SCIPbranchcandContainsExternCand(SCIP_BRANCHCAND *branchcand, SCIP_VAR *var)
Definition: branch.c:712
SCIP_Real SCIPgetBranchScoreMultiple(SCIP *scip, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: scip_branch.c:863
SCIP_BRANCHRULE ** branchrules
Definition: struct_set.h:85
void SCIPbranchruleSetMaxdepth(SCIP_BRANCHRULE *branchrule, int maxdepth)
Definition: branch.c:2025
internal methods for problem variables
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1041
void SCIPbranchruleSetExecLp(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: branch.c:1938
void SCIPbranchruleSetPriority(SCIP_BRANCHRULE *branchrule, SCIP_SET *set, int priority)
Definition: branch.c:2001
SCIP_SEPASTORE * sepastore
Definition: struct_scip.h:93
#define SCIP_Bool
Definition: def.h:70
int SCIPbranchcandGetNPrioExternConts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:557
int SCIPgetNPrioExternBranchImpls(SCIP *scip)
Definition: scip_branch.c:614
int SCIPgetNPrioExternBranchInts(SCIP *scip)
Definition: scip_branch.c:594
methods for debugging
datastructures for block memory pools and memory buffers
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:176
SCIP_RETCODE SCIPsetBranchruleInitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: scip_branch.c:208
SCIP_Real SCIPbranchGetScoreMultiple(SCIP_SET *set, SCIP_VAR *var, int nchildren, SCIP_Real *gains)
Definition: branch.c:2250
int SCIPgetNPrioPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:768
void SCIPbranchruleSetExecPs(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: branch.c:1960
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:256
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
SCIP * scip
Definition: struct_var.h:278
void SCIPclearExternBranchCands(SCIP *scip)
Definition: scip_branch.c:680
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:938
void SCIPbranchruleSetInitsol(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINITSOL((*branchinitsol)))
Definition: branch.c:1914
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
SCIP_Real SCIPsetFeasFloor(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6552
public methods for branching rule plugins and branching
void SCIPbranchruleSetExecExt(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: branch.c:1949
void SCIPsetSortBranchrules(SCIP_SET *set)
Definition: set.c:4819
SCIP_RETCODE SCIPtreeBranchVarNary(SCIP_TREE *tree, SCIP_REOPT *reopt, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *var, SCIP_Real val, int n, SCIP_Real minwidth, SCIP_Real widthfactor, int *nchildren)
Definition: tree.c:5890
BMS_BLKMEM * probmem
Definition: struct_mem.h:40
void SCIPbranchruleSetExitsol(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: branch.c:1925
SCIP_RETCODE SCIPsetIncludeBranchrule(SCIP_SET *set, SCIP_BRANCHRULE *branchrule)
Definition: set.c:4775
int SCIPbranchcandGetNPrioPseudoBins(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:872
SCIP_SET * set
Definition: struct_scip.h:63
public methods for message output
datastructures for problem variables
int SCIPgetNPrioLPBranchCands(SCIP *scip)
Definition: scip_branch.c:457
SCIP_MESSAGEHDLR * messagehdlr
Definition: struct_scip.h:66
#define SCIP_Real
Definition: def.h:163
SCIP_BRANCHRULE * SCIPsetFindBranchrule(SCIP_SET *set, const char *name)
Definition: set.c:4799
SCIP_RETCODE SCIPsetBranchruleExitsol(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXITSOL((*branchexitsol)))
Definition: scip_branch.c:224
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
datastructures for collecting primal CIP solutions and primal informations
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
#define SCIP_INVALID
Definition: def.h:183
void SCIPbranchruleSetMaxbounddist(SCIP_BRANCHRULE *branchrule, SCIP_Real maxbounddist)
Definition: branch.c:2047
void SCIPbranchruleSetExit(SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: branch.c:1903
SCIP_TREE * tree
Definition: struct_scip.h:86
int SCIPgetNPrioExternBranchBins(SCIP *scip)
Definition: scip_branch.c:574
SCIP_RETCODE SCIPbranchLP(SCIP *scip, SCIP_RESULT *result)
Definition: scip_branch.c:1225
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:192
int SCIPbranchcandGetNPrioPseudoInts(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:882
int SCIPgetNPrioPseudoBranchBins(SCIP *scip)
Definition: scip_branch.c:786
SCIP_Real SCIPgetBranchScore(SCIP *scip, SCIP_VAR *var, SCIP_Real downgain, SCIP_Real upgain)
Definition: scip_branch.c:840
#define SCIP_CALL_ABORT(x)
Definition: def.h:343
SCIP_LP * lp
Definition: struct_scip.h:82
SCIP_RETCODE SCIPbranchExecExtern(BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_BRANCHCAND *branchcand, SCIP_EVENTQUEUE *eventqueue, SCIP_Real cutoffbound, SCIP_Bool allowaddcons, SCIP_RESULT *result)
Definition: branch.c:2616
#define SCIPABORT()
Definition: def.h:336
int SCIPgetNBranchrules(SCIP *scip)
Definition: scip_branch.c:314
datastructures for global SCIP settings
#define SCIP_DECL_BRANCHEXIT(x)
Definition: type_branch.h:82
SCIP_RETCODE SCIPsetBranchruleMaxbounddist(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_Real maxbounddist)
Definition: scip_branch.c:355
int SCIPbranchcandGetNPrioExternImpls(SCIP_BRANCHCAND *branchcand)
Definition: branch.c:547