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