Scippy

SCIP

Solving Constraint Integer Programs

branch.h
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-2014 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch.h
17  * @brief internal methods for branching rules and branching candidate storage
18  * @author Tobias Achterberg
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #ifndef __SCIP_BRANCH_H__
24 #define __SCIP_BRANCH_H__
25 
26 
27 #include "scip/def.h"
28 #include "blockmemshell/memory.h"
29 #include "scip/type_retcode.h"
30 #include "scip/type_result.h"
31 #include "scip/type_set.h"
32 #include "scip/type_stat.h"
33 #include "scip/type_misc.h"
34 #include "scip/type_event.h"
35 #include "scip/type_lp.h"
36 #include "scip/type_var.h"
37 #include "scip/type_prob.h"
38 #include "scip/type_tree.h"
39 #include "scip/type_sepastore.h"
40 #include "scip/type_branch.h"
41 #include "scip/pub_branch.h"
42 
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46 
47 /*
48  * branching candidate storage methods
49  */
50 
51 /** creates a branching candidate storage */
52 extern
53 SCIP_RETCODE SCIPbranchcandCreate(
54  SCIP_BRANCHCAND** branchcand /**< pointer to store branching candidate storage */
55  );
56 
57 /** frees branching candidate storage */
58 extern
59 SCIP_RETCODE SCIPbranchcandFree(
60  SCIP_BRANCHCAND** branchcand /**< pointer to store branching candidate storage */
61  );
62 
63 /** gets branching candidates for LP solution branching (fractional variables) */
64 extern
65 SCIP_RETCODE SCIPbranchcandGetLPCands(
66  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
67  SCIP_SET* set, /**< global SCIP settings */
68  SCIP_STAT* stat, /**< problem statistics */
69  SCIP_LP* lp, /**< current LP data */
70  SCIP_VAR*** lpcands, /**< pointer to store the array of LP branching candidates, or NULL */
71  SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */
72  SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */
73  int* nlpcands, /**< pointer to store the number of LP branching candidates, or NULL */
74  int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */
75  int* nfracimplvars /**< pointer to store the number of implicit fractional variables, or NULL */
76  );
77 
78 
79 /** gets external branching candidates */
80 extern
81 SCIP_RETCODE SCIPbranchcandGetExternCands(
82  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
83  SCIP_VAR*** externcands, /**< pointer to store the array of external branching candidates, or NULL */
84  SCIP_Real** externcandssol, /**< pointer to store the array of external candidate solution values, or NULL */
85  SCIP_Real** externcandsscore, /**< pointer to store the array of external candidate scores, or NULL */
86  int* nexterncands, /**< pointer to store the number of external branching candidates, or NULL */
87  int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */
88  int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */
89  int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */
90  int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority,
91  * or NULL */
92  );
93 
94 /** gets number of external branching candidates */
95 extern
96 int SCIPbranchcandGetNExternCands(
97  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
98  );
99 
100 /** gets number of external branching candidates with maximal branch priority */
101 extern
102 int SCIPbranchcandGetNPrioExternCands(
103  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
104  );
105 
106 /** gets number of binary external branching candidates with maximal branch priority */
107 extern
108 int SCIPbranchcandGetNPrioExternBins(
109  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
110  );
111 
112 /** gets number of integer external branching candidates with maximal branch priority */
113 extern
114 int SCIPbranchcandGetNPrioExternInts(
115  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
116  );
117 
118 /** gets number of implicit integer external branching candidates with maximal branch priority */
119 extern
120 int SCIPbranchcandGetNPrioExternImpls(
121  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
122  );
123 
124 /** gets number of continuous external branching candidates with maximal branch priority */
125 extern
126 int SCIPbranchcandGetNPrioExternConts(
127  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
128  );
129 
130 /** insert variable, its score and its solution value into the external branching candidate storage
131  * the absolute difference of the current lower and upper bounds of the variable must be at least epsilon
132  */
133 extern
134 SCIP_RETCODE SCIPbranchcandAddExternCand(
135  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
136  SCIP_SET* set, /**< global SCIP settings */
137  SCIP_VAR* var, /**< variable to insert */
138  SCIP_Real score, /**< score of external candidate, e.g. infeasibility */
139  SCIP_Real solval /**< value of the variable in the current solution */
140  );
141 
142 /** removes all external candidates from the storage for external branching */
143 extern
144 void SCIPbranchcandClearExternCands(
145  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
146  );
147 
148 /** checks whether the given variable is contained in the candidate storage for external branching */
149 extern
150 SCIP_Bool SCIPbranchcandContainsExternCand(
151  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
152  SCIP_VAR* var /**< variable to look for */
153  );
154 
155 /** gets branching candidates for pseudo solution branching (non-fixed variables) */
156 extern
157 SCIP_RETCODE SCIPbranchcandGetPseudoCands(
158  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
159  SCIP_SET* set, /**< global SCIP settings */
160  SCIP_PROB* prob, /**< problem data */
161  SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
162  int* npseudocands, /**< pointer to store the number of pseudo branching candidates, or NULL */
163  int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
164  );
165 
166 /** gets number of branching candidates for pseudo solution branching (non-fixed variables) */
167 extern
168 int SCIPbranchcandGetNPseudoCands(
169  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
170  );
171 
172 /** gets number of branching candidates with maximal branch priority for pseudo solution branching */
173 extern
174 int SCIPbranchcandGetNPrioPseudoCands(
175  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
176  );
177 
178 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching */
179 extern
180 int SCIPbranchcandGetNPrioPseudoBins(
181  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
182  );
183 
184 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching */
185 extern
186 int SCIPbranchcandGetNPrioPseudoInts(
187  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
188  );
189 
190 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching */
191 extern
192 int SCIPbranchcandGetNPrioPseudoImpls(
193  SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
194  );
195 
196 /** removes variable from branching candidate list */
197 extern
198 SCIP_RETCODE SCIPbranchcandRemoveVar(
199  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
200  SCIP_VAR* var /**< variable that changed its bounds */
201  );
202 
203 /** updates branching candidate list for a given variable */
204 extern
205 SCIP_RETCODE SCIPbranchcandUpdateVar(
206  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
207  SCIP_SET* set, /**< global SCIP settings */
208  SCIP_VAR* var /**< variable that changed its bounds */
209  );
210 
211 /** updates branching priority of the given variable and update the pseude candidate array if needed */
212 extern
213 SCIP_RETCODE SCIPbranchcandUpdateVarBranchPriority(
214  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
215  SCIP_SET* set, /**< global SCIP settings */
216  SCIP_VAR* var, /**< variable that changed its bounds */
217  int branchpriority /**< branch priority of the variable */
218  );
219 
220 
221 
222 
223 /*
224  * branching rules
225  */
226 
227 /** copies the given branchrule to a new scip */
228 extern
229 SCIP_RETCODE SCIPbranchruleCopyInclude(
230  SCIP_BRANCHRULE* branchrule, /**< branchrule */
231  SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
232  );
233 
234 /** creates a branching rule */
235 extern
236 SCIP_RETCODE SCIPbranchruleCreate(
237  SCIP_BRANCHRULE** branchrule, /**< pointer to store branching rule */
238  SCIP_SET* set, /**< global SCIP settings */
239  SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
240  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
241  const char* name, /**< name of branching rule */
242  const char* desc, /**< description of branching rule */
243  int priority, /**< priority of the branching rule */
244  int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
245  SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
246  * compared to best node's dual bound for applying branching rule
247  * (0.0: only on current best node, 1.0: on all nodes) */
248  SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule */
249  SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */
250  SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */
251  SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */
252  SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
253  SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
254  SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
255  SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */
256  SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
257  SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
258  );
259 
260 /** frees memory of branching rule */
261 extern
262 SCIP_RETCODE SCIPbranchruleFree(
263  SCIP_BRANCHRULE** branchrule, /**< pointer to branching rule data structure */
264  SCIP_SET* set /**< global SCIP settings */
265  );
266 
267 /** initializes branching rule */
268 extern
269 SCIP_RETCODE SCIPbranchruleInit(
270  SCIP_BRANCHRULE* branchrule, /**< branching rule */
271  SCIP_SET* set /**< global SCIP settings */
272  );
273 
274 /** deinitializes branching rule */
275 extern
276 SCIP_RETCODE SCIPbranchruleExit(
277  SCIP_BRANCHRULE* branchrule, /**< branching rule */
278  SCIP_SET* set /**< global SCIP settings */
279  );
280 
281 /** informs branching rule that the branch and bound process is being started */
282 extern
283 SCIP_RETCODE SCIPbranchruleInitsol(
284  SCIP_BRANCHRULE* branchrule, /**< branching rule */
285  SCIP_SET* set /**< global SCIP settings */
286  );
287 
288 /** informs branching rule that the branch and bound process data is being freed */
289 extern
290 SCIP_RETCODE SCIPbranchruleExitsol(
291  SCIP_BRANCHRULE* branchrule, /**< branching rule */
292  SCIP_SET* set /**< global SCIP settings */
293  );
294 
295 /** executes branching rule for fractional LP solution */
296 extern
297 SCIP_RETCODE SCIPbranchruleExecLPSol(
298  SCIP_BRANCHRULE* branchrule, /**< branching rule */
299  SCIP_SET* set, /**< global SCIP settings */
300  SCIP_STAT* stat, /**< problem statistics */
301  SCIP_TREE* tree, /**< branch and bound tree */
302  SCIP_SEPASTORE* sepastore, /**< separation storage */
303  SCIP_Real cutoffbound, /**< global upper cutoff bound */
304  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
305  SCIP_RESULT* result /**< pointer to store the result of the callback method */
306  );
307 
308 /** executes branching rule for external branching candidates */
309 extern
310 SCIP_RETCODE SCIPbranchruleExecExternSol(
311  SCIP_BRANCHRULE* branchrule, /**< branching rule */
312  SCIP_SET* set, /**< global SCIP settings */
313  SCIP_STAT* stat, /**< problem statistics */
314  SCIP_TREE* tree, /**< branch and bound tree */
315  SCIP_SEPASTORE* sepastore, /**< separation storage */
316  SCIP_Real cutoffbound, /**< global upper cutoff bound */
317  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
318  SCIP_RESULT* result /**< pointer to store the result of the callback method */
319  );
320 
321 /** executes branching rule for not completely fixed pseudo solution */
322 extern
323 SCIP_RETCODE SCIPbranchruleExecPseudoSol(
324  SCIP_BRANCHRULE* branchrule, /**< branching rule */
325  SCIP_SET* set, /**< global SCIP settings */
326  SCIP_STAT* stat, /**< problem statistics */
327  SCIP_TREE* tree, /**< branch and bound tree */
328  SCIP_Real cutoffbound, /**< global upper cutoff bound */
329  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
330  SCIP_RESULT* result /**< pointer to store the result of the callback method */
331  );
332 
333 /** sets priority of branching rule */
334 extern
335 void SCIPbranchruleSetPriority(
336  SCIP_BRANCHRULE* branchrule, /**< branching rule */
337  SCIP_SET* set, /**< global SCIP settings */
338  int priority /**< new priority of the branching rule */
339  );
340 
341 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
342 extern
343 void SCIPbranchruleSetMaxdepth(
344  SCIP_BRANCHRULE* branchrule, /**< branching rule */
345  int maxdepth /**< new maxdepth of the branching rule */
346  );
347 
348 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
349 extern
350 void SCIPbranchruleSetMaxbounddist(
351  SCIP_BRANCHRULE* branchrule, /**< branching rule */
352  SCIP_Real maxbounddist /**< new maxbounddist of the branching rule */
353  );
354 
355 /** sets copy method of branching rule */
356 extern
357 void SCIPbranchruleSetCopy(
358  SCIP_BRANCHRULE* branchrule, /**< branching rule */
359  SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
360  );
361 
362 /** sets destructor method of branching rule */
363 extern
364 void SCIPbranchruleSetFree(
365  SCIP_BRANCHRULE* branchrule, /**< branching rule */
366  SCIP_DECL_BRANCHFREE ((*branchfree)) /**< destructor of branching rule */
367  );
368 
369 /** sets initialization method of branching rule */
370 extern
371 void SCIPbranchruleSetInit(
372  SCIP_BRANCHRULE* branchrule, /**< branching rule */
373  SCIP_DECL_BRANCHINIT ((*branchinit)) /**< initialize branching rule */
374  );
375 
376 /** sets deinitialization method of branching rule */
377 extern
378 void SCIPbranchruleSetExit(
379  SCIP_BRANCHRULE* branchrule, /**< branching rule */
380  SCIP_DECL_BRANCHEXIT ((*branchexit)) /**< deinitialize branching rule */
381  );
382 
383 /** sets solving process initialization method of branching rule */
384 extern
385 void SCIPbranchruleSetInitsol(
386  SCIP_BRANCHRULE* branchrule, /**< branching rule */
387  SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
388  );
389 
390 /** sets solving process deinitialization method of branching rule */
391 extern
392 void SCIPbranchruleSetExitsol(
393  SCIP_BRANCHRULE* branchrule, /**< branching rule */
394  SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
395  );
396 
397 /** sets branching execution method for fractional LP solutions */
398 extern
399 void SCIPbranchruleSetExecLp(
400  SCIP_BRANCHRULE* branchrule, /**< branching rule */
401  SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
402  );
403 
404 /** sets branching execution method for external candidates */
405 extern
406 void SCIPbranchruleSetExecExt(
407  SCIP_BRANCHRULE* branchrule, /**< branching rule */
408  SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
409  );
410 
411 /** sets branching execution method for not completely fixed pseudo solutions */
412 extern
413 void SCIPbranchruleSetExecPs(
414  SCIP_BRANCHRULE* branchrule, /**< branching rule */
415  SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
416  );
417 
418 /*
419  * branching methods
420  */
421 
422 /** calculates the branching score out of the gain predictions for a binary branching */
423 extern
424 SCIP_Real SCIPbranchGetScore(
425  SCIP_SET* set, /**< global SCIP settings */
426  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
427  SCIP_Real downgain, /**< prediction of objective gain for rounding downwards */
428  SCIP_Real upgain /**< prediction of objective gain for rounding upwards */
429  );
430 
431 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children */
432 extern
433 SCIP_Real SCIPbranchGetScoreMultiple(
434  SCIP_SET* set, /**< global SCIP settings */
435  SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
436  int nchildren, /**< number of children that the branching will create */
437  SCIP_Real* gains /**< prediction of objective gain for each child */
438  );
439 
440 /** computes a branching point for a (not necessarily discrete) variable
441  * a suggested branching point is first projected onto the box
442  * if no point is suggested, then the value in the current LP or pseudo solution is used
443  * if this value is at infinity, then 0.0 projected onto the bounds and then moved inside the interval is used
444  * for a discrete variable, it is ensured that the returned value is fractional
445  * for a continuous variable, the parameter branching/clamp defines how far a branching point need to be from the bounds of a variable
446  * the latter is only applied if no point has been suggested, or the suggested point is not inside the variable's interval
447  */
448 extern
449 SCIP_Real SCIPbranchGetBranchingPoint(
450  SCIP_SET* set, /**< global SCIP settings */
451  SCIP_TREE* tree, /**< branch and bound tree */
452  SCIP_VAR* var, /**< variable, of which the branching point should be computed */
453  SCIP_Real suggestion /**< suggestion for branching point, or SCIP_INVALID if no suggestion */
454  );
455 
456 /** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN;
457  * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional
458  * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority
459  */
460 extern
461 SCIP_RETCODE SCIPbranchExecLP(
462  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
463  SCIP_SET* set, /**< global SCIP settings */
464  SCIP_STAT* stat, /**< problem statistics */
465  SCIP_PROB* transprob, /**< transformed problem after presolve */
466  SCIP_PROB* origprob, /**< original problem */
467  SCIP_TREE* tree, /**< branch and bound tree */
468  SCIP_LP* lp, /**< current LP data */
469  SCIP_SEPASTORE* sepastore, /**< separation storage */
470  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
471  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
472  SCIP_Real cutoffbound, /**< global upper cutoff bound */
473  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
474  SCIP_RESULT* result /**< pointer to store the result of the branching */
475  );
476 
477 /** calls branching rules to branch on an external solution; if no external branching candidates exist, the result is SCIP_DIDNOTRUN */
478 extern
479 SCIP_RETCODE SCIPbranchExecExtern(
480  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
481  SCIP_SET* set, /**< global SCIP settings */
482  SCIP_STAT* stat, /**< problem statistics */
483  SCIP_PROB* transprob, /**< transformed problem after presolve */
484  SCIP_PROB* origprob, /**< original problem */
485  SCIP_TREE* tree, /**< branch and bound tree */
486  SCIP_LP* lp, /**< current LP data */
487  SCIP_SEPASTORE* sepastore, /**< separation storage */
488  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
489  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
490  SCIP_Real cutoffbound, /**< global upper cutoff bound */
491  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
492  SCIP_RESULT* result /**< pointer to store the result of the branching */
493  );
494 
495 /** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN */
496 extern
497 SCIP_RETCODE SCIPbranchExecPseudo(
498  BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
499  SCIP_SET* set, /**< global SCIP settings */
500  SCIP_STAT* stat, /**< problem statistics */
501  SCIP_PROB* transprob, /**< transformed problem after presolve */
502  SCIP_PROB* origprob, /**< original problem */
503  SCIP_TREE* tree, /**< branch and bound tree */
504  SCIP_LP* lp, /**< current LP data */
505  SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
506  SCIP_EVENTQUEUE* eventqueue, /**< event queue */
507  SCIP_Real cutoffbound, /**< global upper cutoff bound */
508  SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
509  SCIP_RESULT* result /**< pointer to store the result of the branching */
510  );
511 
512 #ifdef __cplusplus
513 }
514 #endif
515 
516 #endif
517