1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file branch.c
17 * @ingroup OTHER_CFILES
18 * @brief methods for branching rules and branching candidate storage
19 * @author Tobias Achterberg
20 * @author Timo Berthold
21 * @author Gerald Gamrath
22 * @author Stefan Heinz
23 * @author Michael Winkler
24 * @author Stefan Vigerske
25 */
26
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28
29 #include <assert.h>
30 #include <string.h>
31
32 #include "scip/def.h"
33 #include "blockmemshell/memory.h"
34 #include "scip/set.h"
35 #include "scip/stat.h"
36 #include "scip/clock.h"
37 #include "scip/paramset.h"
38 #include "scip/event.h"
39 #include "scip/lp.h"
40 #include "scip/var.h"
41 #include "scip/prob.h"
42 #include "scip/tree.h"
43 #include "scip/sepastore.h"
44 #include "scip/scip.h"
45 #include "scip/branch.h"
46 #include "scip/solve.h"
47
48 #include "scip/struct_branch.h"
49
50 /*
51 * memory growing methods for dynamically allocated arrays
52 */
53
54 /** ensures, that lpcands array can store at least num entries */
55 static
ensureLpcandsSize(SCIP_BRANCHCAND * branchcand,SCIP_SET * set,int num)56 SCIP_RETCODE ensureLpcandsSize(
57 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
58 SCIP_SET* set, /**< global SCIP settings */
59 int num /**< minimum number of entries to store */
60 )
61 {
62 assert(branchcand->nlpcands <= branchcand->lpcandssize);
63
64 if( num > branchcand->lpcandssize )
65 {
66 int newsize;
67
68 newsize = SCIPsetCalcMemGrowSize(set, num);
69 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcands, newsize) );
70 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcandssol, newsize) );
71 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->lpcandsfrac, newsize) );
72 branchcand->lpcandssize = newsize;
73 }
74 assert(num <= branchcand->lpcandssize);
75
76 return SCIP_OKAY;
77 }
78
79 /** ensures, that pseudocands array can store at least num entries */
80 static
ensurePseudocandsSize(SCIP_BRANCHCAND * branchcand,SCIP_SET * set,int num)81 SCIP_RETCODE ensurePseudocandsSize(
82 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
83 SCIP_SET* set, /**< global SCIP settings */
84 int num /**< minimum number of entries to store */
85 )
86 {
87 assert(branchcand->npseudocands <= branchcand->pseudocandssize);
88
89 if( num > branchcand->pseudocandssize )
90 {
91 int newsize;
92
93 newsize = SCIPsetCalcMemGrowSize(set, num);
94 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->pseudocands, newsize) );
95 branchcand->pseudocandssize = newsize;
96 }
97 assert(num <= branchcand->pseudocandssize);
98
99 return SCIP_OKAY;
100 }
101
102 /** ensures, that externcands array can store at least num entries */
103 static
ensureExterncandsSize(SCIP_BRANCHCAND * branchcand,SCIP_SET * set,int num)104 SCIP_RETCODE ensureExterncandsSize(
105 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
106 SCIP_SET* set, /**< global SCIP settings */
107 int num /**< minimum number of entries to store */
108 )
109 {
110 assert(branchcand->nexterncands <= branchcand->externcandssize);
111
112 if( num > branchcand->externcandssize )
113 {
114 int newsize;
115
116 newsize = SCIPsetCalcMemGrowSize(set, num);
117 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcands, newsize) );
118 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcandsscore, newsize) );
119 SCIP_ALLOC( BMSreallocMemoryArray(&branchcand->externcandssol, newsize) );
120 branchcand->externcandssize = newsize;
121 }
122 assert(num <= branchcand->externcandssize);
123
124 return SCIP_OKAY;
125 }
126
127
128
129 /*
130 * branching candidate storage methods
131 */
132
133 /** creates a branching candidate storage */
SCIPbranchcandCreate(SCIP_BRANCHCAND ** branchcand)134 SCIP_RETCODE SCIPbranchcandCreate(
135 SCIP_BRANCHCAND** branchcand /**< pointer to store branching candidate storage */
136 )
137 {
138 assert(branchcand != NULL);
139
140 SCIP_ALLOC( BMSallocMemory(branchcand) );
141 (*branchcand)->lpcands = NULL;
142 (*branchcand)->lpcandssol = NULL;
143 (*branchcand)->lpcandsfrac = NULL;
144 (*branchcand)->externcands = NULL;
145 (*branchcand)->externcandssol = NULL;
146 (*branchcand)->externcandsscore = NULL;
147 (*branchcand)->pseudocands = NULL;
148 (*branchcand)->lpcandssize = 0;
149 (*branchcand)->nlpcands = 0;
150 (*branchcand)->nimpllpfracs = 0;
151 (*branchcand)->npriolpcands = 0;
152 (*branchcand)->npriolpbins = 0;
153 (*branchcand)->lpmaxpriority = INT_MIN;
154 (*branchcand)->externcandssize = 0;
155 (*branchcand)->nexterncands = 0;
156 (*branchcand)->nprioexterncands = 0;
157 (*branchcand)->nprioexternbins = 0;
158 (*branchcand)->nprioexternints = 0;
159 (*branchcand)->nprioexternimpls = 0;
160 (*branchcand)->externmaxpriority = INT_MIN;
161 (*branchcand)->pseudocandssize = 0;
162 (*branchcand)->npseudocands = 0;
163 (*branchcand)->npriopseudocands = 0;
164 (*branchcand)->npriopseudobins = 0;
165 (*branchcand)->npriopseudoints = 0;
166 (*branchcand)->pseudomaxpriority = INT_MIN;
167
168 SCIPbranchcandInvalidate(*branchcand);
169
170 return SCIP_OKAY;
171 }
172
173 /** frees branching candidate storage */
SCIPbranchcandFree(SCIP_BRANCHCAND ** branchcand)174 SCIP_RETCODE SCIPbranchcandFree(
175 SCIP_BRANCHCAND** branchcand /**< pointer to store branching candidate storage */
176 )
177 {
178 assert(branchcand != NULL);
179
180 BMSfreeMemoryArrayNull(&(*branchcand)->lpcands);
181 BMSfreeMemoryArrayNull(&(*branchcand)->lpcandssol);
182 BMSfreeMemoryArrayNull(&(*branchcand)->lpcandsfrac);
183 BMSfreeMemoryArrayNull(&(*branchcand)->pseudocands);
184 BMSfreeMemoryArrayNull(&(*branchcand)->externcands);
185 BMSfreeMemoryArrayNull(&(*branchcand)->externcandsscore);
186 BMSfreeMemoryArrayNull(&(*branchcand)->externcandssol);
187 BMSfreeMemory(branchcand);
188
189 return SCIP_OKAY;
190 }
191
192 /** resets branching candidates storage */
SCIPbranchcandInvalidate(SCIP_BRANCHCAND * branchcand)193 void SCIPbranchcandInvalidate(
194 SCIP_BRANCHCAND* branchcand /**< pointer to store branching candidate storage */
195 )
196 {
197 assert(branchcand != NULL);
198
199 branchcand->validlpcandslp = -1;
200 }
201
202 /** calculates branching candidates for LP solution branching (fractional variables) */
203 static
branchcandCalcLPCands(SCIP_BRANCHCAND * branchcand,SCIP_SET * set,SCIP_STAT * stat,SCIP_LP * lp)204 SCIP_RETCODE branchcandCalcLPCands(
205 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
206 SCIP_SET* set, /**< global SCIP settings */
207 SCIP_STAT* stat, /**< problem statistics */
208 SCIP_LP* lp /**< current LP data */
209 )
210 {
211 assert(branchcand != NULL);
212 assert(stat != NULL);
213 assert(branchcand->validlpcandslp <= stat->lpcount);
214 assert(lp != NULL);
215 assert(lp->solved);
216 assert(SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_OPTIMAL || SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY);
217
218 SCIPsetDebugMsg(set, "calculating LP branching candidates: validlp=%" SCIP_LONGINT_FORMAT ", lpcount=%" SCIP_LONGINT_FORMAT "\n",
219 branchcand->validlpcandslp, stat->lpcount);
220
221 if( SCIPlpGetSolstat(lp) == SCIP_LPSOLSTAT_UNBOUNDEDRAY )
222 {
223 branchcand->lpmaxpriority = INT_MIN / 2;
224 branchcand->nlpcands = 0;
225 branchcand->npriolpcands = 0;
226 branchcand->npriolpbins = 0;
227 branchcand->nimpllpfracs = 0;
228 branchcand->validlpcandslp = stat->lpcount;
229
230 SCIPsetDebugMsg(set, " LP is unbounded -> no branching candidates\n");
231 return SCIP_OKAY;
232 }
233
234 /* check, if the current LP branching candidate array is invalid */
235 if( branchcand->validlpcandslp < stat->lpcount )
236 {
237 SCIP_COL** cols;
238 SCIP_VAR* var;
239 SCIP_COL* col;
240 SCIP_Real primsol;
241 SCIP_Real frac;
242 SCIP_VARTYPE vartype;
243 int branchpriority;
244 int ncols;
245 int c;
246 int insertpos;
247
248 SCIPsetDebugMsg(set, " -> recalculating LP branching candidates\n");
249
250 cols = SCIPlpGetCols(lp);
251 ncols = SCIPlpGetNCols(lp);
252
253 /* construct the LP branching candidate set, moving the candidates with maximal priority to the front */
254 SCIP_CALL( ensureLpcandsSize(branchcand, set, ncols) );
255
256 branchcand->lpmaxpriority = INT_MIN / 2;
257 branchcand->nlpcands = 0;
258 branchcand->nimpllpfracs = 0;
259 branchcand->npriolpcands = 0;
260 branchcand->npriolpbins = 0;
261 for( c = 0; c < ncols; ++c )
262 {
263 col = cols[c];
264 assert(col != NULL);
265 assert(col->lppos == c);
266 assert(col->lpipos >= 0);
267
268 primsol = SCIPcolGetPrimsol(col);
269 assert(primsol < SCIP_INVALID);
270 assert(SCIPsetIsInfinity(set, -col->lb) || SCIPsetIsFeasGE(set, primsol, col->lb));
271 assert(SCIPsetIsInfinity(set, col->ub) || SCIPsetIsFeasLE(set, primsol, col->ub));
272
273 var = col->var;
274 assert(var != NULL);
275 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
276 assert(SCIPvarGetCol(var) == col);
277
278 /* LP branching candidates are fractional binary and integer variables; implicit variables are kept at the end
279 * of the candidates array for some rounding heuristics
280 */
281 vartype = SCIPvarGetType(var);
282 if( vartype == SCIP_VARTYPE_CONTINUOUS )
283 continue;
284
285 /* ignore fixed variables (due to numerics, it is possible, that the LP solution of a fixed integer variable
286 * (with large fixed value) is fractional in terms of absolute feasibility measure)
287 */
288 if( SCIPvarGetLbLocal(var) >= SCIPvarGetUbLocal(var) - 0.5 )
289 continue;
290
291 /* check, if the LP solution value is fractional */
292 frac = SCIPsetFeasFrac(set, primsol);
293
294 /* The fractionality should not be smaller than -feastol, however, if the primsol is large enough
295 * and close to an integer, fixed precision floating point arithmetic might give us values slightly
296 * smaller than -feastol. Originally, the "frac >= -feastol"-check was within SCIPsetIsFeasFracIntegral(),
297 * however, we relaxed it to "frac >= -2*feastol" and have the stricter check here for small-enough primsols.
298 */
299 assert(SCIPsetIsGE(set, frac, -SCIPsetFeastol(set)) || (primsol > 1e14 * SCIPsetFeastol(set)));
300
301 if( SCIPsetIsFeasFracIntegral(set, frac) )
302 continue;
303
304 /* insert candidate in candidate list */
305 branchpriority = SCIPvarGetBranchPriority(var);
306 insertpos = branchcand->nlpcands + branchcand->nimpllpfracs;
307 assert(insertpos < branchcand->lpcandssize);
308
309 if( vartype == SCIP_VARTYPE_IMPLINT )
310 branchpriority = INT_MIN;
311
312 assert(vartype == SCIP_VARTYPE_IMPLINT || branchpriority >= INT_MIN/2);
313 /* ensure that implicit variables are stored at the end of the array */
314 if( vartype != SCIP_VARTYPE_IMPLINT && branchcand->nimpllpfracs > 0 )
315 {
316 assert(branchcand->lpcands[branchcand->nlpcands] != NULL
317 && SCIPvarGetType(branchcand->lpcands[branchcand->nlpcands]) == SCIP_VARTYPE_IMPLINT );
318
319 branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->nlpcands];
320 branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->nlpcands];
321 branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->nlpcands];
322
323 insertpos = branchcand->nlpcands;
324 }
325
326 if( branchpriority > branchcand->lpmaxpriority )
327 {
328 /* candidate has higher priority than the current maximum:
329 * move it to the front and declare it to be the single best candidate
330 */
331 if( insertpos != 0 )
332 {
333 branchcand->lpcands[insertpos] = branchcand->lpcands[0];
334 branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[0];
335 branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[0];
336 insertpos = 0;
337 }
338 branchcand->npriolpcands = 1;
339 branchcand->npriolpbins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0);
340 branchcand->lpmaxpriority = branchpriority;
341 }
342 else if( branchpriority == branchcand->lpmaxpriority )
343 {
344 /* candidate has equal priority as the current maximum:
345 * move away the first non-maximal priority candidate, move the current candidate to the correct
346 * slot (binaries first) and increase the number of maximal priority candidates
347 */
348 if( insertpos != branchcand->npriolpcands )
349 {
350 branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->npriolpcands];
351 branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->npriolpcands];
352 branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->npriolpcands];
353 insertpos = branchcand->npriolpcands;
354 }
355 branchcand->npriolpcands++;
356 if( vartype == SCIP_VARTYPE_BINARY )
357 {
358 if( insertpos != branchcand->npriolpbins )
359 {
360 branchcand->lpcands[insertpos] = branchcand->lpcands[branchcand->npriolpbins];
361 branchcand->lpcandssol[insertpos] = branchcand->lpcandssol[branchcand->npriolpbins];
362 branchcand->lpcandsfrac[insertpos] = branchcand->lpcandsfrac[branchcand->npriolpbins];
363 insertpos = branchcand->npriolpbins;
364 }
365 branchcand->npriolpbins++;
366 }
367 }
368 /* insert variable at the correct position of the candidates storage */
369 branchcand->lpcands[insertpos] = var;
370 branchcand->lpcandssol[insertpos] = primsol;
371 branchcand->lpcandsfrac[insertpos] = frac;
372
373 /* increase the counter depending on the variable type */
374 if( vartype != SCIP_VARTYPE_IMPLINT )
375 branchcand->nlpcands++;
376 else
377 branchcand->nimpllpfracs++;
378
379 SCIPsetDebugMsg(set, " -> candidate %d: var=<%s>, sol=%g, frac=%g, prio=%d (max: %d) -> pos %d\n",
380 branchcand->nlpcands, SCIPvarGetName(var), primsol, frac, branchpriority, branchcand->lpmaxpriority,
381 insertpos);
382 }
383
384 #ifndef NDEBUG
385 /* in debug mode we assert that the variables are positioned correctly (binaries and integers first,
386 * implicit integers last)
387 */
388 for( c = 0; c < branchcand->nlpcands + branchcand->nimpllpfracs; ++c )
389 {
390 assert(c >= branchcand->nlpcands || SCIPvarGetType(branchcand->lpcands[c]) != SCIP_VARTYPE_IMPLINT);
391 assert(c < branchcand->nlpcands || SCIPvarGetType(branchcand->lpcands[c]) == SCIP_VARTYPE_IMPLINT);
392 }
393 #endif
394
395 branchcand->validlpcandslp = stat->lpcount;
396 }
397 assert(0 <= branchcand->npriolpcands && branchcand->npriolpcands <= branchcand->nlpcands);
398
399 SCIPsetDebugMsg(set, " -> %d fractional variables (%d of maximal priority)\n", branchcand->nlpcands, branchcand->npriolpcands);
400
401 return SCIP_OKAY;
402 }
403
404 /** gets branching candidates for LP solution branching (fractional variables) */
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)405 SCIP_RETCODE SCIPbranchcandGetLPCands(
406 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
407 SCIP_SET* set, /**< global SCIP settings */
408 SCIP_STAT* stat, /**< problem statistics */
409 SCIP_LP* lp, /**< current LP data */
410 SCIP_VAR*** lpcands, /**< pointer to store the array of LP branching candidates, or NULL */
411 SCIP_Real** lpcandssol, /**< pointer to store the array of LP candidate solution values, or NULL */
412 SCIP_Real** lpcandsfrac, /**< pointer to store the array of LP candidate fractionalities, or NULL */
413 int* nlpcands, /**< pointer to store the number of LP branching candidates, or NULL */
414 int* npriolpcands, /**< pointer to store the number of candidates with maximal priority, or NULL */
415 int* nfracimplvars /**< pointer to store the number of implicit fractional variables, or NULL */
416 )
417 {
418 /* calculate branching candidates */
419 SCIP_CALL( branchcandCalcLPCands(branchcand, set, stat, lp) );
420
421 /* assign return values */
422 if( lpcands != NULL )
423 *lpcands = branchcand->lpcands;
424 if( lpcandssol != NULL )
425 *lpcandssol = branchcand->lpcandssol;
426 if( lpcandsfrac != NULL )
427 *lpcandsfrac = branchcand->lpcandsfrac;
428 if( nlpcands != NULL )
429 *nlpcands = branchcand->nlpcands;
430 if( npriolpcands != NULL )
431 *npriolpcands = (set->branch_preferbinary && branchcand->npriolpbins > 0 ? branchcand->npriolpbins
432 : branchcand->npriolpcands);
433 if( nfracimplvars != NULL )
434 *nfracimplvars = branchcand->nimpllpfracs;
435
436 return SCIP_OKAY;
437 }
438
439 /** gets external branching candidates */
SCIPbranchcandGetExternCands(SCIP_BRANCHCAND * branchcand,SCIP_VAR *** externcands,SCIP_Real ** externcandssol,SCIP_Real ** externcandsscore,int * nexterncands,int * nprioexterncands,int * nprioexternbins,int * nprioexternints,int * nprioexternimpls)440 SCIP_RETCODE SCIPbranchcandGetExternCands(
441 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
442 SCIP_VAR*** externcands, /**< pointer to store the array of external branching candidates, or NULL */
443 SCIP_Real** externcandssol, /**< pointer to store the array of external candidate solution values, or NULL */
444 SCIP_Real** externcandsscore, /**< pointer to store the array of external candidate scores, or NULL */
445 int* nexterncands, /**< pointer to store the number of external branching candidates, or NULL */
446 int* nprioexterncands, /**< pointer to store the number of candidates with maximal priority, or NULL */
447 int* nprioexternbins, /**< pointer to store the number of binary candidates with maximal priority, or NULL */
448 int* nprioexternints, /**< pointer to store the number of integer candidates with maximal priority, or NULL */
449 int* nprioexternimpls /**< pointer to store the number of implicit integer candidates with maximal priority,
450 * or NULL */
451 )
452 {
453 assert(branchcand != NULL);
454
455 /* assign return values */
456 if( externcands != NULL )
457 *externcands = branchcand->externcands;
458 if( externcandssol != NULL )
459 *externcandssol = branchcand->externcandssol;
460 if( externcandsscore != NULL )
461 *externcandsscore = branchcand->externcandsscore;
462 if( nexterncands != NULL )
463 *nexterncands = branchcand->nexterncands;
464 if( nprioexterncands != NULL )
465 *nprioexterncands = branchcand->nprioexterncands;
466 if( nprioexternbins != NULL )
467 *nprioexternbins = branchcand->nprioexternbins;
468 if( nprioexternints != NULL )
469 *nprioexternints = branchcand->nprioexternints;
470 if( nprioexternimpls != NULL )
471 *nprioexternimpls = branchcand->nprioexternimpls;
472
473 return SCIP_OKAY;
474 }
475
476 /** gets maximal branching priority of LP branching candidates */
SCIPbranchcandGetLPMaxPrio(SCIP_BRANCHCAND * branchcand)477 int SCIPbranchcandGetLPMaxPrio(
478 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
479 )
480 {
481 assert(branchcand != NULL);
482
483 return branchcand->lpmaxpriority;
484 }
485
486 /** gets number of LP branching candidates with maximal branch priority */
SCIPbranchcandGetNPrioLPCands(SCIP_BRANCHCAND * branchcand)487 int SCIPbranchcandGetNPrioLPCands(
488 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
489 )
490 {
491 assert(branchcand != NULL);
492
493 return branchcand->npriolpcands;
494 }
495
496 /** gets maximal branching priority of external branching candidates */
SCIPbranchcandGetExternMaxPrio(SCIP_BRANCHCAND * branchcand)497 int SCIPbranchcandGetExternMaxPrio(
498 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
499 )
500 {
501 assert(branchcand != NULL);
502
503 return branchcand->externmaxpriority;
504 }
505
506 /** gets number of external branching candidates */
SCIPbranchcandGetNExternCands(SCIP_BRANCHCAND * branchcand)507 int SCIPbranchcandGetNExternCands(
508 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
509 )
510 {
511 assert(branchcand != NULL);
512
513 return branchcand->nexterncands;
514 }
515
516 /** gets number of external branching candidates with maximal branch priority */
SCIPbranchcandGetNPrioExternCands(SCIP_BRANCHCAND * branchcand)517 int SCIPbranchcandGetNPrioExternCands(
518 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
519 )
520 {
521 assert(branchcand != NULL);
522
523 return branchcand->nprioexterncands;
524 }
525
526 /** gets number of binary external branching candidates with maximal branch priority */
SCIPbranchcandGetNPrioExternBins(SCIP_BRANCHCAND * branchcand)527 int SCIPbranchcandGetNPrioExternBins(
528 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
529 )
530 {
531 assert(branchcand != NULL);
532
533 return branchcand->nprioexternbins;
534 }
535
536 /** gets number of integer external branching candidates with maximal branch priority */
SCIPbranchcandGetNPrioExternInts(SCIP_BRANCHCAND * branchcand)537 int SCIPbranchcandGetNPrioExternInts(
538 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
539 )
540 {
541 assert(branchcand != NULL);
542
543 return branchcand->nprioexternints;
544 }
545
546 /** gets number of implicit integer external branching candidates with maximal branch priority */
SCIPbranchcandGetNPrioExternImpls(SCIP_BRANCHCAND * branchcand)547 int SCIPbranchcandGetNPrioExternImpls(
548 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
549 )
550 {
551 assert(branchcand != NULL);
552
553 return branchcand->nprioexternimpls;
554 }
555
556 /** gets number of continuous external branching candidates with maximal branch priority */
SCIPbranchcandGetNPrioExternConts(SCIP_BRANCHCAND * branchcand)557 int SCIPbranchcandGetNPrioExternConts(
558 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
559 )
560 {
561 assert(branchcand != NULL);
562
563 return branchcand->nprioexterncands - branchcand->nprioexternbins - branchcand->nprioexternints - branchcand->nprioexternimpls;
564 }
565
566 /** insert variable, its score and its solution value into the external branching candidate storage
567 * the absolute difference of the current lower and upper bounds of the variable must be at least epsilon
568 */
SCIPbranchcandAddExternCand(SCIP_BRANCHCAND * branchcand,SCIP_SET * set,SCIP_VAR * var,SCIP_Real score,SCIP_Real solval)569 SCIP_RETCODE SCIPbranchcandAddExternCand(
570 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
571 SCIP_SET* set, /**< global SCIP settings */
572 SCIP_VAR* var, /**< variable to insert */
573 SCIP_Real score, /**< score of external candidate, e.g. infeasibility */
574 SCIP_Real solval /**< value of the variable in the current solution */
575 )
576 {
577 SCIP_VARTYPE vartype;
578 int branchpriority;
579 int insertpos;
580
581 assert(branchcand != NULL);
582 assert(var != NULL);
583 assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var))); /* the variable should not be fixed yet */
584 assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || !SCIPsetIsEQ(set, SCIPsetCeil(set, SCIPvarGetLbLocal(var)), SCIPsetFloor(set, SCIPvarGetUbLocal(var)))); /* a discrete variable should also not be fixed, even after rounding bounds to integral values */
585 assert(SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR || !SCIPsetIsEQ(set, SCIPvarGetMultaggrLbLocal(var, set), SCIPvarGetMultaggrUbLocal(var, set))); /* also the current bounds of a multi-aggregated variable should not be fixed yet */
586 assert(branchcand->nprioexterncands <= branchcand->nexterncands);
587 assert(branchcand->nexterncands <= branchcand->externcandssize);
588
589 vartype = SCIPvarGetType(var);
590 branchpriority = SCIPvarGetBranchPriority(var);
591 insertpos = branchcand->nexterncands;
592
593 SCIP_CALL( ensureExterncandsSize(branchcand, set, branchcand->nexterncands+1) );
594
595 SCIPsetDebugMsg(set, "inserting external candidate <%s> of type %d and priority %d into candidate set (maxprio: %d), score = %g, solval = %g\n",
596 SCIPvarGetName(var), vartype, branchpriority, branchcand->externmaxpriority, score, solval);
597
598 /* insert the variable into externcands, making sure, that the highest priority candidates are at the front
599 * and ordered binaries, integers, implicit integers, continuous
600 */
601 if( branchpriority > branchcand->externmaxpriority )
602 {
603 /* candidate has higher priority than the current maximum:
604 * move it to the front and declare it to be the single best candidate
605 */
606 branchcand->externcands[insertpos] = branchcand->externcands[0];
607 branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[0];
608 branchcand->externcandssol[insertpos] = branchcand->externcandssol[0];
609
610 insertpos = 0;
611
612 branchcand->nprioexterncands = 1;
613 branchcand->nprioexternbins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0);
614 branchcand->nprioexternints = (vartype == SCIP_VARTYPE_INTEGER ? 1 : 0);
615 branchcand->nprioexternimpls = (vartype == SCIP_VARTYPE_IMPLINT ? 1 : 0);
616 branchcand->externmaxpriority = branchpriority;
617 }
618 else if( branchpriority == branchcand->externmaxpriority )
619 {
620 /* candidate has equal priority as the current maximum:
621 * move away the first non-maximal priority candidate, move the current candidate to the correct
622 * slot (binaries first, integers next, implicit integers next, continuous last) and increase the number
623 * of maximal priority candidates
624 */
625 if( insertpos != branchcand->nprioexterncands )
626 {
627 branchcand->externcands[insertpos] = branchcand->externcands[branchcand->nprioexterncands];
628 branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[branchcand->nprioexterncands];
629 branchcand->externcandssol[insertpos] = branchcand->externcandssol[branchcand->nprioexterncands];
630
631 insertpos = branchcand->nprioexterncands;
632 }
633 branchcand->nprioexterncands++;
634 if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER || vartype == SCIP_VARTYPE_IMPLINT )
635 {
636 if( insertpos != branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls )
637 {
638 branchcand->externcands[insertpos] =
639 branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
640 branchcand->externcandsscore[insertpos] =
641 branchcand->externcandsscore[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
642 branchcand->externcandssol[insertpos] =
643 branchcand->externcandssol[branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls];
644
645 insertpos = branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls;
646 }
647 branchcand->nprioexternimpls++;
648
649 if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER )
650 {
651 if( insertpos != branchcand->nprioexternbins + branchcand->nprioexternints )
652 {
653 branchcand->externcands[insertpos] =
654 branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints];
655 branchcand->externcandsscore[insertpos] =
656 branchcand->externcandsscore[branchcand->nprioexternbins + branchcand->nprioexternints];
657 branchcand->externcandssol[insertpos] =
658 branchcand->externcandssol[branchcand->nprioexternbins + branchcand->nprioexternints];
659
660 insertpos = branchcand->nprioexternbins + branchcand->nprioexternints;
661 }
662 branchcand->nprioexternints++;
663 branchcand->nprioexternimpls--;
664
665 if( vartype == SCIP_VARTYPE_BINARY )
666 {
667 if( insertpos != branchcand->nprioexternbins )
668 {
669 branchcand->externcands[insertpos] = branchcand->externcands[branchcand->nprioexternbins];
670 branchcand->externcandsscore[insertpos] = branchcand->externcandsscore[branchcand->nprioexternbins];
671 branchcand->externcandssol[insertpos] = branchcand->externcandssol[branchcand->nprioexternbins];
672
673 insertpos = branchcand->nprioexternbins;
674 }
675 branchcand->nprioexternbins++;
676 branchcand->nprioexternints--;
677 }
678 }
679 }
680 }
681 branchcand->externcands[insertpos] = var;
682 branchcand->externcandsscore[insertpos] = score;
683 branchcand->externcandssol[insertpos] = solval;
684 branchcand->nexterncands++;
685
686 SCIPsetDebugMsg(set, " -> inserted at position %d (nprioexterncands=%d)\n", insertpos, branchcand->nprioexterncands);
687
688 assert(0 <= branchcand->nprioexterncands && branchcand->nprioexterncands <= branchcand->nexterncands);
689 assert(0 <= branchcand->nprioexternbins && branchcand->nprioexternbins <= branchcand->nprioexterncands);
690 assert(0 <= branchcand->nprioexternints && branchcand->nprioexternints <= branchcand->nprioexterncands);
691 assert(0 <= branchcand->nprioexternimpls && branchcand->nprioexternimpls <= branchcand->nprioexterncands);
692
693 return SCIP_OKAY;
694 }
695
696 /** removes all external candidates from the storage for external branching */
SCIPbranchcandClearExternCands(SCIP_BRANCHCAND * branchcand)697 void SCIPbranchcandClearExternCands(
698 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
699 )
700 {
701 assert(branchcand != NULL);
702
703 branchcand->nexterncands = 0;
704 branchcand->nprioexterncands = 0;
705 branchcand->nprioexternbins = 0;
706 branchcand->nprioexternints = 0;
707 branchcand->nprioexternimpls = 0;
708 branchcand->externmaxpriority = INT_MIN;
709 }
710
711 /** checks whether the given variable is contained in the candidate storage for external branching */
SCIPbranchcandContainsExternCand(SCIP_BRANCHCAND * branchcand,SCIP_VAR * var)712 SCIP_Bool SCIPbranchcandContainsExternCand(
713 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
714 SCIP_VAR* var /**< variable to look for */
715 )
716 {
717 int branchpriority;
718 int i;
719
720 assert(branchcand != NULL);
721 assert(var != NULL);
722 assert(branchcand->nprioexterncands <= branchcand->nexterncands);
723 assert(branchcand->nexterncands <= branchcand->externcandssize);
724
725 branchpriority = SCIPvarGetBranchPriority(var);
726
727 /* look for the variable in the externcands, using the fact, that the highest priority candidates are at the front
728 * and ordered binaries, integers, implicit integers, continuous
729 */
730 if( branchpriority > branchcand->externmaxpriority )
731 {
732 /* the branching priority of the variable is higher than the maximal priority contained in the array;
733 * the variable can thus not be contained */
734 return FALSE;
735 }
736 if( branchpriority == branchcand->externmaxpriority )
737 {
738 SCIP_VARTYPE vartype;
739
740 vartype = SCIPvarGetType(var);
741
742 /* variable has equal priority as the current maximum:
743 * look for it in the correct slot (binaries first, integers next, implicit integers next, continuous last)
744 */
745 if( vartype == SCIP_VARTYPE_BINARY )
746 {
747 /* the variable is binary, look at the first branchcand->nprioexternbins slots */
748 for( i = 0; i < branchcand->nprioexternbins; i++ )
749 if( branchcand->externcands[i] == var )
750 return TRUE;
751 return FALSE;
752 }
753 if( vartype == SCIP_VARTYPE_INTEGER )
754 {
755 /* the variable is integer, look at the slots containing integers */
756 for( i = 0; i < branchcand->nprioexternints; i++ )
757 if( branchcand->externcands[branchcand->nprioexternbins + i] == var )
758 return TRUE;
759 return FALSE;
760 }
761 if( vartype == SCIP_VARTYPE_IMPLINT )
762 {
763 /* the variable is implicit integer, look at the slots containing implicit integers */
764 for( i = 0; i < branchcand->nprioexternimpls; i++ )
765 if( branchcand->externcands[branchcand->nprioexternbins + branchcand->nprioexternints + i] == var )
766 return TRUE;
767 return FALSE;
768 }
769 /* the variable is continuous, look at the slots containing continuous variables */
770 assert(vartype == SCIP_VARTYPE_CONTINUOUS);
771 for( i = branchcand->nprioexternbins + branchcand->nprioexternints + branchcand->nprioexternimpls;
772 i < branchcand->nprioexterncands; i++ )
773 if( branchcand->externcands[i] == var )
774 return TRUE;
775 return FALSE;
776 }
777 /* the branching priority of the variable is lower than the maximal priority contained in the array;
778 * look for the variable in the candidates which do not have maximal priority */
779 assert(branchpriority < branchcand->externmaxpriority);
780
781 for( i = branchcand->nprioexterncands; i < branchcand->nexterncands; i++ )
782 if( branchcand->externcands[i] == var )
783 return TRUE;
784 return FALSE;
785 }
786
787 /** gets branching candidates for pseudo solution branching (non-fixed variables) */
SCIPbranchcandGetPseudoCands(SCIP_BRANCHCAND * branchcand,SCIP_SET * set,SCIP_PROB * prob,SCIP_VAR *** pseudocands,int * npseudocands,int * npriopseudocands)788 SCIP_RETCODE SCIPbranchcandGetPseudoCands(
789 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
790 SCIP_SET* set, /**< global SCIP settings */
791 SCIP_PROB* prob, /**< problem data */
792 SCIP_VAR*** pseudocands, /**< pointer to store the array of pseudo branching candidates, or NULL */
793 int* npseudocands, /**< pointer to store the number of pseudo branching candidates, or NULL */
794 int* npriopseudocands /**< pointer to store the number of candidates with maximal priority, or NULL */
795 )
796 {
797 assert(branchcand != NULL);
798
799 #ifndef NDEBUG
800 /* check, if the current pseudo branching candidate array is correct */
801 {
802 SCIP_VAR* var;
803 int npcs;
804 int v;
805
806 assert(prob != NULL);
807
808 /* pseudo branching candidates are non-fixed binary, integer, and implicit integer variables */
809 npcs = 0;
810 for( v = 0; v < prob->nbinvars + prob->nintvars + prob->nimplvars; ++v )
811 {
812 var = prob->vars[v];
813 assert(var != NULL);
814 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
815 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY
816 || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER
817 || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT);
818 assert(SCIPsetIsFeasIntegral(set, SCIPvarGetLbLocal(var)));
819 assert(SCIPsetIsFeasIntegral(set, SCIPvarGetUbLocal(var)));
820 assert(SCIPsetIsLE(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
821
822 if( SCIPsetIsLT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
823 {
824 assert(0 <= var->pseudocandindex && var->pseudocandindex < branchcand->npseudocands);
825 assert(branchcand->pseudocands[var->pseudocandindex] == var);
826 npcs++;
827 }
828 else
829 {
830 assert(var->pseudocandindex == -1);
831 }
832 }
833 assert(branchcand->npseudocands == npcs);
834 for (v = 0; v < branchcand->npriopseudocands; ++v)
835 assert( branchcand->pseudocands[v]->branchpriority == branchcand->pseudomaxpriority );
836 }
837 #endif
838
839 /* assign return values */
840 if( pseudocands != NULL )
841 *pseudocands = branchcand->pseudocands;
842 if( npseudocands != NULL )
843 *npseudocands = branchcand->npseudocands;
844 if( npriopseudocands != NULL )
845 *npriopseudocands = (set->branch_preferbinary && branchcand->npriopseudobins > 0 ? branchcand->npriopseudobins
846 : branchcand->npriopseudocands);
847
848 return SCIP_OKAY;
849 }
850
851 /** gets number of branching candidates for pseudo solution branching (non-fixed variables) */
SCIPbranchcandGetNPseudoCands(SCIP_BRANCHCAND * branchcand)852 int SCIPbranchcandGetNPseudoCands(
853 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
854 )
855 {
856 assert(branchcand != NULL);
857
858 return branchcand->npseudocands;
859 }
860
861 /** gets number of branching candidates with maximal branch priority for pseudo solution branching */
SCIPbranchcandGetNPrioPseudoCands(SCIP_BRANCHCAND * branchcand)862 int SCIPbranchcandGetNPrioPseudoCands(
863 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
864 )
865 {
866 assert(branchcand != NULL);
867
868 return branchcand->npriopseudocands;
869 }
870
871 /** gets number of binary branching candidates with maximal branch priority for pseudo solution branching */
SCIPbranchcandGetNPrioPseudoBins(SCIP_BRANCHCAND * branchcand)872 int SCIPbranchcandGetNPrioPseudoBins(
873 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
874 )
875 {
876 assert(branchcand != NULL);
877
878 return branchcand->npriopseudobins;
879 }
880
881 /** gets number of integer branching candidates with maximal branch priority for pseudo solution branching */
SCIPbranchcandGetNPrioPseudoInts(SCIP_BRANCHCAND * branchcand)882 int SCIPbranchcandGetNPrioPseudoInts(
883 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
884 )
885 {
886 assert(branchcand != NULL);
887
888 return branchcand->npriopseudoints;
889 }
890
891 /** gets number of implicit integer branching candidates with maximal branch priority for pseudo solution branching */
SCIPbranchcandGetNPrioPseudoImpls(SCIP_BRANCHCAND * branchcand)892 int SCIPbranchcandGetNPrioPseudoImpls(
893 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
894 )
895 {
896 assert(branchcand != NULL);
897
898 return branchcand->npriopseudocands - branchcand->npriopseudobins - branchcand->npriopseudoints;
899 }
900
901 /** insert pseudocand at given position, or to the first positions of the maximal priority candidates, using the
902 * given position as free slot for the other candidates
903 */
904 static
branchcandInsertPseudoCand(SCIP_BRANCHCAND * branchcand,SCIP_VAR * var,int insertpos)905 void branchcandInsertPseudoCand(
906 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
907 SCIP_VAR* var, /**< variable to insert */
908 int insertpos /**< free position to insert the variable */
909 )
910 {
911 SCIP_VARTYPE vartype;
912 int branchpriority;
913
914 assert(branchcand != NULL);
915 assert(var != NULL);
916 assert(branchcand->npriopseudocands <= insertpos && insertpos < branchcand->npseudocands);
917 assert(branchcand->npseudocands <= branchcand->pseudocandssize);
918
919 vartype = SCIPvarGetType(var);
920 branchpriority = SCIPvarGetBranchPriority(var);
921
922 SCIPdebugMessage("inserting pseudo candidate <%s> of type %d and priority %d into candidate set at position %d (maxprio: %d)\n",
923 SCIPvarGetName(var), vartype, branchpriority, insertpos, branchcand->pseudomaxpriority);
924
925 /* insert the variable into pseudocands, making sure, that the highest priority candidates are at the front
926 * and ordered binaries, integers, implicit integers
927 */
928 if( branchpriority > branchcand->pseudomaxpriority )
929 {
930 /* candidate has higher priority than the current maximum:
931 * move it to the front and declare it to be the single best candidate
932 */
933 if( insertpos != 0 )
934 {
935 branchcand->pseudocands[insertpos] = branchcand->pseudocands[0];
936 branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
937 insertpos = 0;
938 }
939 branchcand->npriopseudocands = 1;
940 branchcand->npriopseudobins = (vartype == SCIP_VARTYPE_BINARY ? 1 : 0);
941 branchcand->npriopseudoints = (vartype == SCIP_VARTYPE_INTEGER ? 1 : 0);
942 branchcand->pseudomaxpriority = branchpriority;
943 }
944 else if( branchpriority == branchcand->pseudomaxpriority )
945 {
946 /* candidate has equal priority as the current maximum:
947 * move away the first non-maximal priority candidate, move the current candidate to the correct
948 * slot (binaries first, integers next, implicit integers last) and increase the number of maximal priority candidates
949 */
950 if( insertpos != branchcand->npriopseudocands )
951 {
952 branchcand->pseudocands[insertpos] = branchcand->pseudocands[branchcand->npriopseudocands];
953 branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
954 insertpos = branchcand->npriopseudocands;
955 }
956 branchcand->npriopseudocands++;
957 if( vartype == SCIP_VARTYPE_BINARY || vartype == SCIP_VARTYPE_INTEGER )
958 {
959 if( insertpos != branchcand->npriopseudobins + branchcand->npriopseudoints )
960 {
961 branchcand->pseudocands[insertpos] =
962 branchcand->pseudocands[branchcand->npriopseudobins + branchcand->npriopseudoints];
963 branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
964 insertpos = branchcand->npriopseudobins + branchcand->npriopseudoints;
965 }
966 branchcand->npriopseudoints++;
967
968 if( vartype == SCIP_VARTYPE_BINARY )
969 {
970 if( insertpos != branchcand->npriopseudobins )
971 {
972 branchcand->pseudocands[insertpos] = branchcand->pseudocands[branchcand->npriopseudobins];
973 branchcand->pseudocands[insertpos]->pseudocandindex = insertpos;
974 insertpos = branchcand->npriopseudobins;
975 }
976 branchcand->npriopseudobins++;
977 branchcand->npriopseudoints--;
978 }
979 }
980 }
981 branchcand->pseudocands[insertpos] = var;
982 var->pseudocandindex = insertpos;
983
984 SCIPdebugMessage(" -> inserted at position %d (npriopseudocands=%d)\n", insertpos, branchcand->npriopseudocands);
985
986 assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
987 assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
988 assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
989 }
990
991 /** sorts the pseudo branching candidates, such that the candidates of maximal priority are at the front,
992 * ordered by binaries, integers, implicit integers
993 */
994 static
branchcandSortPseudoCands(SCIP_BRANCHCAND * branchcand)995 void branchcandSortPseudoCands(
996 SCIP_BRANCHCAND* branchcand /**< branching candidate storage */
997 )
998 {
999 SCIP_VAR* var;
1000 int i;
1001
1002 assert(branchcand != NULL);
1003 assert(branchcand->npriopseudocands == 0); /* is only be called after removal of last maximal candidate */
1004 assert(branchcand->npriopseudobins == 0);
1005 assert(branchcand->npriopseudoints == 0);
1006
1007 SCIPdebugMessage("resorting pseudo candidates\n");
1008
1009 branchcand->pseudomaxpriority = INT_MIN;
1010
1011 for( i = 0; i < branchcand->npseudocands; ++i )
1012 {
1013 var = branchcand->pseudocands[i];
1014 assert(var->pseudocandindex == i);
1015
1016 if( SCIPvarGetBranchPriority(var) >= branchcand->pseudomaxpriority )
1017 branchcandInsertPseudoCand(branchcand, var, i);
1018 }
1019
1020 assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
1021 assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
1022 assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
1023 #ifndef NDEBUG
1024 {
1025 for (i = 0; i < branchcand->npriopseudocands; ++i)
1026 assert( branchcand->pseudocands[i]->branchpriority == branchcand->pseudomaxpriority );
1027 }
1028 #endif
1029 }
1030
1031 /** removes pseudo candidate from pseudocands array
1032 */
1033 static
branchcandRemovePseudoCand(SCIP_BRANCHCAND * branchcand,SCIP_VAR * var)1034 void branchcandRemovePseudoCand(
1035 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1036 SCIP_VAR* var /**< variable to remove */
1037 )
1038 {
1039 int freepos;
1040
1041 assert(branchcand != NULL);
1042 assert(var != NULL);
1043 assert(var->pseudocandindex < branchcand->npseudocands);
1044 assert(branchcand->pseudocands[var->pseudocandindex] == var);
1045 assert(branchcand->pseudocands[branchcand->npseudocands-1] != NULL);
1046
1047 /* Note that the branching priority of the variable to be removed is not necessarily equal to pseudomaxpriority, since
1048 * the status of the variable might have changed, leading to a change in the branching priority. Moreover, if the
1049 * variable was part of an aggregation, even other variables might at this point have different priorities. */
1050 SCIPdebugMessage("removing pseudo candidate <%s> of type %d and priority %d at %d from candidate set (maxprio: %d)\n",
1051 SCIPvarGetName(var), SCIPvarGetType(var), SCIPvarGetBranchPriority(var), var->pseudocandindex,
1052 branchcand->pseudomaxpriority);
1053
1054 /* delete the variable from pseudocands, making sure, that the highest priority candidates are at the front
1055 * and ordered binaries, integers, implicit integers
1056 */
1057 freepos = var->pseudocandindex;
1058 var->pseudocandindex = -1;
1059 assert(0 <= freepos && freepos < branchcand->npseudocands);
1060
1061 if( freepos < branchcand->npriopseudobins )
1062 {
1063 /* a binary candidate of maximal priority was removed */
1064 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
1065 if( freepos != branchcand->npriopseudobins - 1 )
1066 {
1067 branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npriopseudobins - 1];
1068 branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1069 freepos = branchcand->npriopseudobins - 1;
1070 }
1071 branchcand->npriopseudobins--;
1072 branchcand->npriopseudoints++;
1073 }
1074
1075 if( freepos < branchcand->npriopseudobins + branchcand->npriopseudoints )
1076 {
1077 /* a binary or integer candidate of maximal priority was removed */
1078 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY || SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER);
1079 if( freepos != branchcand->npriopseudobins + branchcand->npriopseudoints - 1 )
1080 {
1081 branchcand->pseudocands[freepos] =
1082 branchcand->pseudocands[branchcand->npriopseudobins + branchcand->npriopseudoints - 1];
1083 branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1084 freepos = branchcand->npriopseudobins + branchcand->npriopseudoints - 1;
1085 }
1086 branchcand->npriopseudoints--;
1087 }
1088
1089 if( freepos < branchcand->npriopseudocands )
1090 {
1091 /* a candidate of maximal priority was removed */
1092 if( freepos != branchcand->npriopseudocands - 1 )
1093 {
1094 branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npriopseudocands - 1];
1095 branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1096 freepos = branchcand->npriopseudocands - 1;
1097 }
1098 branchcand->npriopseudocands--;
1099 }
1100 if( freepos != branchcand->npseudocands - 1 )
1101 {
1102 branchcand->pseudocands[freepos] = branchcand->pseudocands[branchcand->npseudocands - 1];
1103 branchcand->pseudocands[freepos]->pseudocandindex = freepos;
1104 }
1105 branchcand->npseudocands--;
1106
1107 assert(0 <= branchcand->npriopseudocands && branchcand->npriopseudocands <= branchcand->npseudocands);
1108 assert(0 <= branchcand->npriopseudobins && branchcand->npriopseudobins <= branchcand->npriopseudocands);
1109 assert(0 <= branchcand->npriopseudoints && branchcand->npriopseudoints <= branchcand->npriopseudocands);
1110
1111 /* if all maximal priority candidates were removed, resort the array s.t. the new maximal priority candidates
1112 * are at the front
1113 */
1114 if( branchcand->npriopseudocands == 0 )
1115 branchcandSortPseudoCands(branchcand);
1116 }
1117
1118 /** removes variable from branching candidate list */
SCIPbranchcandRemoveVar(SCIP_BRANCHCAND * branchcand,SCIP_VAR * var)1119 SCIP_RETCODE SCIPbranchcandRemoveVar(
1120 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1121 SCIP_VAR* var /**< variable that changed its bounds */
1122 )
1123 {
1124 assert(var != NULL);
1125
1126 /* make sure, variable is not member of the pseudo branching candidate list */
1127 if( var->pseudocandindex >= 0 )
1128 {
1129 branchcandRemovePseudoCand(branchcand, var);
1130 }
1131
1132 return SCIP_OKAY;
1133 }
1134
1135 /** updates branching candidate list for a given variable */
SCIPbranchcandUpdateVar(SCIP_BRANCHCAND * branchcand,SCIP_SET * set,SCIP_VAR * var)1136 SCIP_RETCODE SCIPbranchcandUpdateVar(
1137 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1138 SCIP_SET* set, /**< global SCIP settings */
1139 SCIP_VAR* var /**< variable that changed its bounds */
1140 )
1141 {
1142 assert(branchcand != NULL);
1143 assert(var != NULL);
1144
1145 if( (SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN)
1146 && SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS
1147 && SCIPsetIsLT(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)) )
1148 {
1149 /* variable is neither continuous nor fixed and has non-empty domain: make sure it is member of the pseudo branching candidate list */
1150 if( var->pseudocandindex == -1 )
1151 {
1152 SCIP_CALL( ensurePseudocandsSize(branchcand, set, branchcand->npseudocands+1) );
1153
1154 branchcand->npseudocands++;
1155 branchcandInsertPseudoCand(branchcand, var, branchcand->npseudocands-1);
1156 }
1157 }
1158 else
1159 {
1160 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_ORIGINAL
1161 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED
1162 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED
1163 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR
1164 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED
1165 || SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS
1166 || SCIPsetIsGE(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
1167
1168 /* variable is continuous or fixed or has empty domain: make sure it is not member of the pseudo branching candidate list */
1169 SCIP_CALL( SCIPbranchcandRemoveVar(branchcand, var) );
1170 }
1171
1172 return SCIP_OKAY;
1173 }
1174
1175 /** updates branching priority of the given variable and update the pseudo candidate array if needed */
SCIPbranchcandUpdateVarBranchPriority(SCIP_BRANCHCAND * branchcand,SCIP_SET * set,SCIP_VAR * var,int branchpriority)1176 SCIP_RETCODE SCIPbranchcandUpdateVarBranchPriority(
1177 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1178 SCIP_SET* set, /**< global SCIP settings */
1179 SCIP_VAR* var, /**< variable that changed its bounds */
1180 int branchpriority /**< branch priority of the variable */
1181 )
1182 {
1183 int oldbranchpriority;
1184 int pseudomaxpriority;
1185
1186 assert(branchcand != NULL);
1187
1188 oldbranchpriority = SCIPvarGetBranchPriority(var);
1189
1190 if( oldbranchpriority == branchpriority )
1191 return SCIP_OKAY;
1192
1193 pseudomaxpriority = branchcand->pseudomaxpriority;
1194
1195 /* if the variable currently belongs to the priority set or the new branching priority is larger than the current one,
1196 * remove it from the pseudo branch candidate array */
1197 if( oldbranchpriority == pseudomaxpriority || branchpriority > pseudomaxpriority )
1198 {
1199 SCIP_CALL( SCIPbranchcandRemoveVar(branchcand, var) );
1200 assert(var->pseudocandindex == -1);
1201 }
1202
1203 /* change the branching priority of the variable */
1204 SCIP_CALL( SCIPvarChgBranchPriority(var, branchpriority) );
1205
1206 /* if the variable is not part of the pseudo branching candidate array, check if it is a pseudo branching candidate
1207 * and add it if so */
1208 SCIP_CALL( SCIPbranchcandUpdateVar(branchcand, set, var) );
1209
1210 return SCIP_OKAY;
1211 }
1212
1213
1214
1215 /*
1216 * branching rule methods
1217 */
1218
1219 /** compares two branching rules w. r. to their priority */
SCIP_DECL_SORTPTRCOMP(SCIPbranchruleComp)1220 SCIP_DECL_SORTPTRCOMP(SCIPbranchruleComp)
1221 { /*lint --e{715}*/
1222 return ((SCIP_BRANCHRULE*)elem2)->priority - ((SCIP_BRANCHRULE*)elem1)->priority;
1223 }
1224
1225 /** comparison method for sorting branching rules w.r.t. to their name */
SCIP_DECL_SORTPTRCOMP(SCIPbranchruleCompName)1226 SCIP_DECL_SORTPTRCOMP(SCIPbranchruleCompName)
1227 {
1228 return strcmp(SCIPbranchruleGetName((SCIP_BRANCHRULE*)elem1), SCIPbranchruleGetName((SCIP_BRANCHRULE*)elem2));
1229 }
1230
1231 /** method to call, when the priority of a branching rule was changed */
1232 static
SCIP_DECL_PARAMCHGD(paramChgdBranchrulePriority)1233 SCIP_DECL_PARAMCHGD(paramChgdBranchrulePriority)
1234 { /*lint --e{715}*/
1235 SCIP_PARAMDATA* paramdata;
1236
1237 paramdata = SCIPparamGetData(param);
1238 assert(paramdata != NULL);
1239
1240 /* use SCIPsetBranchrulePriority() to mark the branchrules unsorted */
1241 SCIP_CALL( SCIPsetBranchrulePriority(scip, (SCIP_BRANCHRULE*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
1242
1243 return SCIP_OKAY;
1244 }
1245
1246 /** copies the given branchrule to a new scip */
SCIPbranchruleCopyInclude(SCIP_BRANCHRULE * branchrule,SCIP_SET * set)1247 SCIP_RETCODE SCIPbranchruleCopyInclude(
1248 SCIP_BRANCHRULE* branchrule, /**< branchrule */
1249 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
1250 )
1251 {
1252 assert(branchrule != NULL);
1253 assert(set != NULL);
1254 assert(set->scip != NULL);
1255
1256 if( branchrule->branchcopy != NULL )
1257 {
1258 SCIPsetDebugMsg(set, "including branching rule %s in subscip %p\n", SCIPbranchruleGetName(branchrule), (void*)set->scip);
1259 SCIP_CALL( branchrule->branchcopy(set->scip, branchrule) );
1260 }
1261
1262 return SCIP_OKAY;
1263 }
1264
1265 /** internal method for creating a branching rule */
1266 static
doBranchruleCreate(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)1267 SCIP_RETCODE doBranchruleCreate(
1268 SCIP_BRANCHRULE** branchrule, /**< pointer to store branching rule */
1269 SCIP_SET* set, /**< global SCIP settings */
1270 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1271 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
1272 const char* name, /**< name of branching rule */
1273 const char* desc, /**< description of branching rule */
1274 int priority, /**< priority of the branching rule */
1275 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
1276 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
1277 * compared to best node's dual bound for applying branching rule
1278 * (0.0: only on current best node, 1.0: on all nodes) */
1279 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule */
1280 SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */
1281 SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */
1282 SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */
1283 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
1284 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
1285 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
1286 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */
1287 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
1288 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
1289 )
1290 {
1291 char paramname[SCIP_MAXSTRLEN];
1292 char paramdesc[SCIP_MAXSTRLEN];
1293
1294 assert(branchrule != NULL);
1295 assert(name != NULL);
1296 assert(desc != NULL);
1297
1298 SCIP_ALLOC( BMSallocMemory(branchrule) );
1299 BMSclearMemory(*branchrule);
1300
1301 SCIP_ALLOC( BMSduplicateMemoryArray(&(*branchrule)->name, name, strlen(name)+1) );
1302 SCIP_ALLOC( BMSduplicateMemoryArray(&(*branchrule)->desc, desc, strlen(desc)+1) );
1303 (*branchrule)->priority = priority;
1304 (*branchrule)->maxdepth = maxdepth;
1305 (*branchrule)->maxbounddist = maxbounddist;
1306 (*branchrule)->branchcopy = branchcopy;
1307 (*branchrule)->branchfree = branchfree;
1308 (*branchrule)->branchinit = branchinit;
1309 (*branchrule)->branchexit = branchexit;
1310 (*branchrule)->branchinitsol = branchinitsol;
1311 (*branchrule)->branchexitsol = branchexitsol;
1312 (*branchrule)->branchexeclp = branchexeclp;
1313 (*branchrule)->branchexecext = branchexecext;
1314 (*branchrule)->branchexecps = branchexecps;
1315 (*branchrule)->branchruledata = branchruledata;
1316 SCIP_CALL( SCIPclockCreate(&(*branchrule)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
1317 SCIP_CALL( SCIPclockCreate(&(*branchrule)->branchclock, SCIP_CLOCKTYPE_DEFAULT) );
1318 (*branchrule)->nlpcalls = 0;
1319 (*branchrule)->nexterncalls = 0;
1320 (*branchrule)->npseudocalls = 0;
1321 (*branchrule)->ncutoffs = 0;
1322 (*branchrule)->ncutsfound = 0;
1323 (*branchrule)->nconssfound = 0;
1324 (*branchrule)->ndomredsfound = 0;
1325 (*branchrule)->nchildren = 0;
1326 (*branchrule)->initialized = FALSE;
1327
1328 /* add parameters */
1329 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/priority", name);
1330 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of branching rule <%s>", name);
1331 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
1332 &(*branchrule)->priority, FALSE, priority, INT_MIN/4, INT_MAX/4,
1333 paramChgdBranchrulePriority, (SCIP_PARAMDATA*)(*branchrule)) ); /*lint !e740*/
1334 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/maxdepth", name);
1335 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal depth level, up to which branching rule <%s> should be used (-1 for no limit)", name);
1336 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
1337 &(*branchrule)->maxdepth, FALSE, maxdepth, -1, SCIP_MAXTREEDEPTH,
1338 NULL, NULL) ); /*lint !e740*/
1339 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "branching/%s/maxbounddist", name);
1340 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "maximal relative distance from current node's dual bound to primal bound compared to best node's dual bound for applying branching rule (0.0: only on current best node, 1.0: on all nodes)");
1341 SCIP_CALL( SCIPsetAddRealParam(set, messagehdlr, blkmem, paramname, paramdesc,
1342 &(*branchrule)->maxbounddist, FALSE, maxbounddist, 0.0, 1.0,
1343 NULL, NULL) ); /*lint !e740*/
1344
1345 return SCIP_OKAY;
1346 }
1347
1348 /** creates a branching rule */
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)1349 SCIP_RETCODE SCIPbranchruleCreate(
1350 SCIP_BRANCHRULE** branchrule, /**< pointer to store branching rule */
1351 SCIP_SET* set, /**< global SCIP settings */
1352 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
1353 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
1354 const char* name, /**< name of branching rule */
1355 const char* desc, /**< description of branching rule */
1356 int priority, /**< priority of the branching rule */
1357 int maxdepth, /**< maximal depth level, up to which this branching rule should be used (or -1) */
1358 SCIP_Real maxbounddist, /**< maximal relative distance from current node's dual bound to primal bound
1359 * compared to best node's dual bound for applying branching rule
1360 * (0.0: only on current best node, 1.0: on all nodes) */
1361 SCIP_DECL_BRANCHCOPY ((*branchcopy)), /**< copy method of branching rule */
1362 SCIP_DECL_BRANCHFREE ((*branchfree)), /**< destructor of branching rule */
1363 SCIP_DECL_BRANCHINIT ((*branchinit)), /**< initialize branching rule */
1364 SCIP_DECL_BRANCHEXIT ((*branchexit)), /**< deinitialize branching rule */
1365 SCIP_DECL_BRANCHINITSOL((*branchinitsol)),/**< solving process initialization method of branching rule */
1366 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)),/**< solving process deinitialization method of branching rule */
1367 SCIP_DECL_BRANCHEXECLP((*branchexeclp)), /**< branching execution method for fractional LP solutions */
1368 SCIP_DECL_BRANCHEXECEXT((*branchexecext)),/**< branching execution method for external solutions */
1369 SCIP_DECL_BRANCHEXECPS((*branchexecps)), /**< branching execution method for not completely fixed pseudo solutions */
1370 SCIP_BRANCHRULEDATA* branchruledata /**< branching rule data */
1371 )
1372 {
1373 assert(branchrule != NULL);
1374 assert(name != NULL);
1375 assert(desc != NULL);
1376
1377 SCIP_CALL_FINALLY( doBranchruleCreate(branchrule, set, messagehdlr, blkmem, name, desc, priority, maxdepth,
1378 maxbounddist, branchcopy, branchfree, branchinit, branchexit, branchinitsol, branchexitsol, branchexeclp,
1379 branchexecext, branchexecps, branchruledata), (void) SCIPbranchruleFree(branchrule, set) );
1380
1381 return SCIP_OKAY;
1382 }
1383
1384 /** frees memory of branching rule */
SCIPbranchruleFree(SCIP_BRANCHRULE ** branchrule,SCIP_SET * set)1385 SCIP_RETCODE SCIPbranchruleFree(
1386 SCIP_BRANCHRULE** branchrule, /**< pointer to branching rule data structure */
1387 SCIP_SET* set /**< global SCIP settings */
1388 )
1389 {
1390 assert(branchrule != NULL);
1391 if( *branchrule == NULL )
1392 return SCIP_OKAY;
1393 assert(!(*branchrule)->initialized);
1394 assert(set != NULL);
1395
1396 /* call destructor of branching rule */
1397 if( (*branchrule)->branchfree != NULL )
1398 {
1399 SCIP_CALL( (*branchrule)->branchfree(set->scip, *branchrule) );
1400 }
1401
1402 SCIPclockFree(&(*branchrule)->branchclock);
1403 SCIPclockFree(&(*branchrule)->setuptime);
1404 BMSfreeMemoryArrayNull(&(*branchrule)->name);
1405 BMSfreeMemoryArrayNull(&(*branchrule)->desc);
1406 BMSfreeMemory(branchrule);
1407
1408 return SCIP_OKAY;
1409 }
1410
1411 /** initializes branching rule */
SCIPbranchruleInit(SCIP_BRANCHRULE * branchrule,SCIP_SET * set)1412 SCIP_RETCODE SCIPbranchruleInit(
1413 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1414 SCIP_SET* set /**< global SCIP settings */
1415 )
1416 {
1417 assert(branchrule != NULL);
1418 assert(set != NULL);
1419
1420 if( branchrule->initialized )
1421 {
1422 SCIPerrorMessage("branching rule <%s> already initialized\n", branchrule->name);
1423 return SCIP_INVALIDCALL;
1424 }
1425
1426 if( set->misc_resetstat )
1427 {
1428 SCIPclockReset(branchrule->setuptime);
1429 SCIPclockReset(branchrule->branchclock);
1430 branchrule->nlpcalls = 0;
1431 branchrule->nexterncalls = 0;
1432 branchrule->npseudocalls = 0;
1433 branchrule->ncutoffs = 0;
1434 branchrule->ncutsfound = 0;
1435 branchrule->nconssfound = 0;
1436 branchrule->ndomredsfound = 0;
1437 branchrule->nchildren = 0;
1438 }
1439
1440 if( branchrule->branchinit != NULL )
1441 {
1442 /* start timing */
1443 SCIPclockStart(branchrule->setuptime, set);
1444
1445 SCIP_CALL( branchrule->branchinit(set->scip, branchrule) );
1446
1447 /* stop timing */
1448 SCIPclockStop(branchrule->setuptime, set);
1449 }
1450 branchrule->initialized = TRUE;
1451
1452 return SCIP_OKAY;
1453 }
1454
1455 /** deinitializes branching rule */
SCIPbranchruleExit(SCIP_BRANCHRULE * branchrule,SCIP_SET * set)1456 SCIP_RETCODE SCIPbranchruleExit(
1457 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1458 SCIP_SET* set /**< global SCIP settings */
1459 )
1460 {
1461 assert(branchrule != NULL);
1462 assert(set != NULL);
1463
1464 if( !branchrule->initialized )
1465 {
1466 SCIPerrorMessage("branching rule <%s> not initialized\n", branchrule->name);
1467 return SCIP_INVALIDCALL;
1468 }
1469
1470 if( branchrule->branchexit != NULL )
1471 {
1472 /* start timing */
1473 SCIPclockStart(branchrule->setuptime, set);
1474
1475 SCIP_CALL( branchrule->branchexit(set->scip, branchrule) );
1476
1477 /* stop timing */
1478 SCIPclockStop(branchrule->setuptime, set);
1479 }
1480 branchrule->initialized = FALSE;
1481
1482 return SCIP_OKAY;
1483 }
1484
1485 /** informs branching rule that the branch and bound process is being started */
SCIPbranchruleInitsol(SCIP_BRANCHRULE * branchrule,SCIP_SET * set)1486 SCIP_RETCODE SCIPbranchruleInitsol(
1487 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1488 SCIP_SET* set /**< global SCIP settings */
1489 )
1490 {
1491 assert(branchrule != NULL);
1492 assert(set != NULL);
1493
1494 /* call solving process initialization method of branching rule */
1495 if( branchrule->branchinitsol != NULL )
1496 {
1497 /* start timing */
1498 SCIPclockStart(branchrule->setuptime, set);
1499
1500 SCIP_CALL( branchrule->branchinitsol(set->scip, branchrule) );
1501
1502 /* stop timing */
1503 SCIPclockStop(branchrule->setuptime, set);
1504 }
1505
1506 return SCIP_OKAY;
1507 }
1508
1509 /** informs branching rule that the branch and bound process data is being freed */
SCIPbranchruleExitsol(SCIP_BRANCHRULE * branchrule,SCIP_SET * set)1510 SCIP_RETCODE SCIPbranchruleExitsol(
1511 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1512 SCIP_SET* set /**< global SCIP settings */
1513 )
1514 {
1515 assert(branchrule != NULL);
1516 assert(set != NULL);
1517
1518 /* call solving process deinitialization method of branching rule */
1519 if( branchrule->branchexitsol != NULL )
1520 {
1521 /* start timing */
1522 SCIPclockStart(branchrule->setuptime, set);
1523
1524 SCIP_CALL( branchrule->branchexitsol(set->scip, branchrule) );
1525
1526 /* stop timing */
1527 SCIPclockStop(branchrule->setuptime, set);
1528 }
1529
1530 return SCIP_OKAY;
1531 }
1532
1533 /** executes branching rule for fractional LP solution */
SCIPbranchruleExecLPSol(SCIP_BRANCHRULE * branchrule,SCIP_SET * set,SCIP_STAT * stat,SCIP_TREE * tree,SCIP_SEPASTORE * sepastore,SCIP_Real cutoffbound,SCIP_Bool allowaddcons,SCIP_RESULT * result)1534 SCIP_RETCODE SCIPbranchruleExecLPSol(
1535 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1536 SCIP_SET* set, /**< global SCIP settings */
1537 SCIP_STAT* stat, /**< problem statistics */
1538 SCIP_TREE* tree, /**< branch and bound tree */
1539 SCIP_SEPASTORE* sepastore, /**< separation storage */
1540 SCIP_Real cutoffbound, /**< global upper cutoff bound */
1541 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
1542 SCIP_RESULT* result /**< pointer to store the result of the callback method */
1543 )
1544 {
1545 assert(branchrule != NULL);
1546 assert(set != NULL);
1547 assert(tree != NULL);
1548 assert(tree->focusnode != NULL);
1549 assert(tree->nchildren == 0);
1550 assert(result != NULL);
1551
1552 *result = SCIP_DIDNOTRUN;
1553 if( branchrule->branchexeclp != NULL
1554 && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) )
1555 {
1556 SCIP_Real loclowerbound;
1557 SCIP_Real glblowerbound;
1558 SCIP_Bool runbranchrule;
1559
1560 loclowerbound = SCIPnodeGetLowerbound(tree->focusnode);
1561 glblowerbound = SCIPtreeGetLowerbound(tree, set);
1562
1563 /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1564 if( SCIPsetIsInfinity(set, -glblowerbound) )
1565 runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1566 else
1567 {
1568 assert(!SCIPsetIsInfinity(set, -loclowerbound));
1569 runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1570 }
1571
1572 if( runbranchrule )
1573 {
1574 SCIP_Longint oldndomchgs;
1575 SCIP_Longint oldnprobdomchgs;
1576 SCIP_Longint oldnactiveconss;
1577 int oldncuts;
1578
1579 SCIPsetDebugMsg(set, "executing LP branching rule <%s>\n", branchrule->name);
1580
1581 oldndomchgs = stat->nboundchgs + stat->nholechgs;
1582 oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
1583 oldncuts = SCIPsepastoreGetNCuts(sepastore);
1584 oldnactiveconss = stat->nactiveconssadded;
1585
1586 /* start timing */
1587 SCIPclockStart(branchrule->branchclock, set);
1588
1589 /* call external method */
1590 SCIP_CALL( branchrule->branchexeclp(set->scip, branchrule, allowaddcons, result) );
1591
1592 /* stop timing */
1593 SCIPclockStop(branchrule->branchclock, set);
1594
1595 /* evaluate result */
1596 if( *result != SCIP_CUTOFF
1597 && *result != SCIP_CONSADDED
1598 && *result != SCIP_REDUCEDDOM
1599 && *result != SCIP_SEPARATED
1600 && *result != SCIP_BRANCHED
1601 && *result != SCIP_DIDNOTFIND
1602 && *result != SCIP_DIDNOTRUN )
1603 {
1604 SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from LP solution branching\n",
1605 branchrule->name, *result);
1606 return SCIP_INVALIDRESULT;
1607 }
1608 if( *result == SCIP_CONSADDED && !allowaddcons )
1609 {
1610 SCIPerrorMessage("branching rule <%s> added a constraint in LP solution branching without permission\n",
1611 branchrule->name);
1612 return SCIP_INVALIDRESULT;
1613 }
1614
1615 /* update statistics */
1616 if( *result != SCIP_DIDNOTRUN )
1617 branchrule->nlpcalls++;
1618 if( *result == SCIP_CUTOFF )
1619 branchrule->ncutoffs++;
1620 if( *result != SCIP_BRANCHED )
1621 {
1622 assert(tree->nchildren == 0);
1623
1624 /* update domain reductions; therefore remove the domain
1625 * reduction counts which were generated in probing mode */
1626 branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
1627 branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
1628
1629 branchrule->ncutsfound += SCIPsepastoreGetNCuts(sepastore) - oldncuts; /*lint !e776*/
1630 branchrule->nconssfound += stat->nactiveconssadded - oldnactiveconss; /*lint !e776*/
1631 }
1632 else
1633 branchrule->nchildren += tree->nchildren;
1634 }
1635 }
1636
1637 return SCIP_OKAY;
1638 }
1639
1640 /** executes branching rule for external branching candidates */
SCIPbranchruleExecExternSol(SCIP_BRANCHRULE * branchrule,SCIP_SET * set,SCIP_STAT * stat,SCIP_TREE * tree,SCIP_SEPASTORE * sepastore,SCIP_Real cutoffbound,SCIP_Bool allowaddcons,SCIP_RESULT * result)1641 SCIP_RETCODE SCIPbranchruleExecExternSol(
1642 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1643 SCIP_SET* set, /**< global SCIP settings */
1644 SCIP_STAT* stat, /**< problem statistics */
1645 SCIP_TREE* tree, /**< branch and bound tree */
1646 SCIP_SEPASTORE* sepastore, /**< separation storage */
1647 SCIP_Real cutoffbound, /**< global upper cutoff bound */
1648 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
1649 SCIP_RESULT* result /**< pointer to store the result of the callback method */
1650 )
1651 {
1652 assert(branchrule != NULL);
1653 assert(set != NULL);
1654 assert(tree != NULL);
1655 assert(tree->focusnode != NULL);
1656 assert(tree->nchildren == 0);
1657 assert(result != NULL);
1658
1659 *result = SCIP_DIDNOTRUN;
1660 if( branchrule->branchexecext != NULL
1661 && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) )
1662 {
1663 SCIP_Real loclowerbound;
1664 SCIP_Real glblowerbound;
1665 SCIP_Bool runbranchrule;
1666
1667 loclowerbound = SCIPnodeGetLowerbound(tree->focusnode);
1668 glblowerbound = SCIPtreeGetLowerbound(tree, set);
1669 assert(!SCIPsetIsInfinity(set, loclowerbound));
1670
1671 /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1672 if( SCIPsetIsInfinity(set, -glblowerbound) )
1673 runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1674 else
1675 {
1676 assert(!SCIPsetIsInfinity(set, -loclowerbound));
1677 runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1678 }
1679
1680 if( runbranchrule )
1681 {
1682 SCIP_Longint oldndomchgs;
1683 SCIP_Longint oldnprobdomchgs;
1684 int oldncuts;
1685 int oldnactiveconss;
1686
1687 SCIPsetDebugMsg(set, "executing external solution branching rule <%s>\n", branchrule->name);
1688
1689 oldndomchgs = stat->nboundchgs + stat->nholechgs;
1690 oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
1691 oldncuts = SCIPsepastoreGetNCuts(sepastore);
1692 oldnactiveconss = stat->nactiveconss;
1693
1694 /* start timing */
1695 SCIPclockStart(branchrule->branchclock, set);
1696
1697 /* call external method */
1698 SCIP_CALL( branchrule->branchexecext(set->scip, branchrule, allowaddcons, result) );
1699
1700 /* stop timing */
1701 SCIPclockStop(branchrule->branchclock, set);
1702
1703 /* evaluate result */
1704 if( *result != SCIP_CUTOFF
1705 && *result != SCIP_CONSADDED
1706 && *result != SCIP_REDUCEDDOM
1707 && *result != SCIP_SEPARATED
1708 && *result != SCIP_BRANCHED
1709 && *result != SCIP_DIDNOTFIND
1710 && *result != SCIP_DIDNOTRUN )
1711 {
1712 SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from external solution branching\n",
1713 branchrule->name, *result);
1714 return SCIP_INVALIDRESULT;
1715 }
1716 if( *result == SCIP_CONSADDED && !allowaddcons )
1717 {
1718 SCIPerrorMessage("branching rule <%s> added a constraint in external solution branching without permission\n",
1719 branchrule->name);
1720 return SCIP_INVALIDRESULT;
1721 }
1722
1723 /* update statistics */
1724 if( *result != SCIP_DIDNOTRUN )
1725 branchrule->nexterncalls++;
1726 if( *result == SCIP_CUTOFF )
1727 branchrule->ncutoffs++;
1728 if( *result != SCIP_BRANCHED )
1729 {
1730 assert(tree->nchildren == 0);
1731
1732 /* update domain reductions; therefore remove the domain
1733 * reduction counts which were generated in probing mode */
1734 branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
1735 branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
1736
1737 branchrule->ncutsfound += SCIPsepastoreGetNCuts(sepastore) - oldncuts; /*lint !e776*/
1738 branchrule->nconssfound += stat->nactiveconss - oldnactiveconss; /*lint !e776*/
1739 }
1740 else
1741 branchrule->nchildren += tree->nchildren;
1742 }
1743 }
1744 return SCIP_OKAY;
1745 }
1746
1747 /** executes branching rule for not completely fixed pseudo solution */
SCIPbranchruleExecPseudoSol(SCIP_BRANCHRULE * branchrule,SCIP_SET * set,SCIP_STAT * stat,SCIP_TREE * tree,SCIP_Real cutoffbound,SCIP_Bool allowaddcons,SCIP_RESULT * result)1748 SCIP_RETCODE SCIPbranchruleExecPseudoSol(
1749 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1750 SCIP_SET* set, /**< global SCIP settings */
1751 SCIP_STAT* stat, /**< problem statistics */
1752 SCIP_TREE* tree, /**< branch and bound tree */
1753 SCIP_Real cutoffbound, /**< global upper cutoff bound */
1754 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
1755 SCIP_RESULT* result /**< pointer to store the result of the callback method */
1756 )
1757 {
1758 assert(branchrule != NULL);
1759 assert(set != NULL);
1760 assert(tree != NULL);
1761 assert(tree->nchildren == 0);
1762 assert(result != NULL);
1763
1764 *result = SCIP_DIDNOTRUN;
1765 if( branchrule->branchexecps != NULL
1766 && (branchrule->maxdepth == -1 || branchrule->maxdepth >= SCIPtreeGetCurrentDepth(tree)) )
1767 {
1768 SCIP_Real loclowerbound;
1769 SCIP_Real glblowerbound;
1770 SCIP_Bool runbranchrule;
1771
1772 loclowerbound = SCIPnodeGetLowerbound(tree->focusnode);
1773 glblowerbound = SCIPtreeGetLowerbound(tree, set);
1774
1775 /* we distinguish between finite and infinite global lower bounds to avoid comparisons between different values > SCIPinfinity() */
1776 if( SCIPsetIsInfinity(set, -glblowerbound) )
1777 runbranchrule = SCIPsetIsInfinity(set, -loclowerbound) || SCIPsetIsGE(set, branchrule->maxbounddist, 1.0);
1778 else
1779 {
1780 assert(!SCIPsetIsInfinity(set, -loclowerbound));
1781 runbranchrule = SCIPsetIsLE(set, loclowerbound - glblowerbound, branchrule->maxbounddist * (cutoffbound - glblowerbound));
1782 }
1783
1784 if( runbranchrule )
1785 {
1786 SCIP_Longint oldndomchgs;
1787 SCIP_Longint oldnprobdomchgs;
1788 SCIP_Longint oldnactiveconss;
1789
1790 SCIPsetDebugMsg(set, "executing pseudo branching rule <%s>\n", branchrule->name);
1791
1792 oldndomchgs = stat->nboundchgs + stat->nholechgs;
1793 oldnprobdomchgs = stat->nprobboundchgs + stat->nprobholechgs;
1794 oldnactiveconss = stat->nactiveconss;
1795
1796 /* start timing */
1797 SCIPclockStart(branchrule->branchclock, set);
1798
1799 /* call external method */
1800 SCIP_CALL( branchrule->branchexecps(set->scip, branchrule, allowaddcons, result) );
1801
1802 /* stop timing */
1803 SCIPclockStop(branchrule->branchclock, set);
1804
1805 /* evaluate result */
1806 if( *result != SCIP_CUTOFF
1807 && *result != SCIP_CONSADDED
1808 && *result != SCIP_REDUCEDDOM
1809 && *result != SCIP_BRANCHED
1810 && *result != SCIP_DIDNOTFIND
1811 && *result != SCIP_DIDNOTRUN )
1812 {
1813 SCIPerrorMessage("branching rule <%s> returned invalid result code <%d> from pseudo solution branching\n",
1814 branchrule->name, *result);
1815 return SCIP_INVALIDRESULT;
1816 }
1817 if( *result == SCIP_CONSADDED && !allowaddcons )
1818 {
1819 SCIPerrorMessage("branching rule <%s> added a constraint in pseudo solution branching without permission\n",
1820 branchrule->name);
1821 return SCIP_INVALIDRESULT;
1822 }
1823
1824 /* update statistics */
1825 if( *result != SCIP_DIDNOTRUN )
1826 branchrule->npseudocalls++;
1827 if( *result == SCIP_CUTOFF )
1828 branchrule->ncutoffs++;
1829 if( *result != SCIP_BRANCHED )
1830 {
1831 assert(tree->nchildren == 0);
1832
1833 /* update domain reductions; therefore remove the domain
1834 * reduction counts which were generated in probing mode */
1835 branchrule->ndomredsfound += stat->nboundchgs + stat->nholechgs - oldndomchgs;
1836 branchrule->ndomredsfound -= (stat->nprobboundchgs + stat->nprobholechgs - oldnprobdomchgs);
1837
1838 branchrule->nconssfound += stat->nactiveconss - oldnactiveconss;
1839 }
1840 else
1841 branchrule->nchildren += tree->nchildren;
1842 }
1843 }
1844
1845 return SCIP_OKAY;
1846 }
1847
1848 /** gets user data of branching rule */
SCIPbranchruleGetData(SCIP_BRANCHRULE * branchrule)1849 SCIP_BRANCHRULEDATA* SCIPbranchruleGetData(
1850 SCIP_BRANCHRULE* branchrule /**< branching rule */
1851 )
1852 {
1853 assert(branchrule != NULL);
1854
1855 return branchrule->branchruledata;
1856 }
1857
1858 /** sets user data of branching rule; user has to free old data in advance! */
SCIPbranchruleSetData(SCIP_BRANCHRULE * branchrule,SCIP_BRANCHRULEDATA * branchruledata)1859 void SCIPbranchruleSetData(
1860 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1861 SCIP_BRANCHRULEDATA* branchruledata /**< new branching rule user data */
1862 )
1863 {
1864 assert(branchrule != NULL);
1865
1866 branchrule->branchruledata = branchruledata;
1867 }
1868
1869 /** sets copy method of branching rule */
SCIPbranchruleSetCopy(SCIP_BRANCHRULE * branchrule,SCIP_DECL_BRANCHCOPY ((* branchcopy)))1870 void SCIPbranchruleSetCopy(
1871 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1872 SCIP_DECL_BRANCHCOPY ((*branchcopy)) /**< copy method of branching rule or NULL if you don't want to copy your plugin into sub-SCIPs */
1873 )
1874 {
1875 assert(branchrule != NULL);
1876
1877 branchrule->branchcopy = branchcopy;
1878 }
1879
1880 /** sets destructor method of branching rule */
SCIPbranchruleSetFree(SCIP_BRANCHRULE * branchrule,SCIP_DECL_BRANCHFREE ((* branchfree)))1881 void SCIPbranchruleSetFree(
1882 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1883 SCIP_DECL_BRANCHFREE ((*branchfree)) /**< destructor of branching rule */
1884 )
1885 {
1886 assert(branchrule != NULL);
1887
1888 branchrule->branchfree = branchfree;
1889 }
1890
1891 /** sets initialization method of branching rule */
SCIPbranchruleSetInit(SCIP_BRANCHRULE * branchrule,SCIP_DECL_BRANCHINIT ((* branchinit)))1892 void SCIPbranchruleSetInit(
1893 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1894 SCIP_DECL_BRANCHINIT ((*branchinit)) /**< initialize branching rule */
1895 )
1896 {
1897 assert(branchrule != NULL);
1898
1899 branchrule->branchinit = branchinit;
1900 }
1901
1902 /** sets deinitialization method of branching rule */
SCIPbranchruleSetExit(SCIP_BRANCHRULE * branchrule,SCIP_DECL_BRANCHEXIT ((* branchexit)))1903 void SCIPbranchruleSetExit(
1904 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1905 SCIP_DECL_BRANCHEXIT ((*branchexit)) /**< deinitialize branching rule */
1906 )
1907 {
1908 assert(branchrule != NULL);
1909
1910 branchrule->branchexit = branchexit;
1911 }
1912
1913 /** sets solving process initialization method of branching rule */
SCIPbranchruleSetInitsol(SCIP_BRANCHRULE * branchrule,SCIP_DECL_BRANCHINITSOL ((* branchinitsol)))1914 void SCIPbranchruleSetInitsol(
1915 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1916 SCIP_DECL_BRANCHINITSOL((*branchinitsol)) /**< solving process initialization method of branching rule */
1917 )
1918 {
1919 assert(branchrule != NULL);
1920
1921 branchrule->branchinitsol = branchinitsol;
1922 }
1923
1924 /** sets solving process deinitialization method of branching rule */
SCIPbranchruleSetExitsol(SCIP_BRANCHRULE * branchrule,SCIP_DECL_BRANCHEXITSOL ((* branchexitsol)))1925 void SCIPbranchruleSetExitsol(
1926 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1927 SCIP_DECL_BRANCHEXITSOL((*branchexitsol)) /**< solving process deinitialization method of branching rule */
1928 )
1929 {
1930 assert(branchrule != NULL);
1931
1932 branchrule->branchexitsol = branchexitsol;
1933 }
1934
1935
1936
1937 /** sets branching execution method for fractional LP solutions */
SCIPbranchruleSetExecLp(SCIP_BRANCHRULE * branchrule,SCIP_DECL_BRANCHEXECLP ((* branchexeclp)))1938 void SCIPbranchruleSetExecLp(
1939 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1940 SCIP_DECL_BRANCHEXECLP((*branchexeclp)) /**< branching execution method for fractional LP solutions */
1941 )
1942 {
1943 assert(branchrule != NULL);
1944
1945 branchrule->branchexeclp = branchexeclp;
1946 }
1947
1948 /** sets branching execution method for external candidates */
SCIPbranchruleSetExecExt(SCIP_BRANCHRULE * branchrule,SCIP_DECL_BRANCHEXECEXT ((* branchexecext)))1949 void SCIPbranchruleSetExecExt(
1950 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1951 SCIP_DECL_BRANCHEXECEXT((*branchexecext)) /**< branching execution method for external candidates */
1952 )
1953 {
1954 assert(branchrule != NULL);
1955
1956 branchrule->branchexecext = branchexecext;
1957 }
1958
1959 /** sets branching execution method for not completely fixed pseudo solutions */
SCIPbranchruleSetExecPs(SCIP_BRANCHRULE * branchrule,SCIP_DECL_BRANCHEXECPS ((* branchexecps)))1960 void SCIPbranchruleSetExecPs(
1961 SCIP_BRANCHRULE* branchrule, /**< branching rule */
1962 SCIP_DECL_BRANCHEXECPS((*branchexecps)) /**< branching execution method for not completely fixed pseudo solutions */
1963 )
1964 {
1965 assert(branchrule != NULL);
1966
1967 branchrule->branchexecps = branchexecps;
1968 }
1969
1970 /** gets name of branching rule */
SCIPbranchruleGetName(SCIP_BRANCHRULE * branchrule)1971 const char* SCIPbranchruleGetName(
1972 SCIP_BRANCHRULE* branchrule /**< branching rule */
1973 )
1974 {
1975 assert(branchrule != NULL);
1976
1977 return branchrule->name;
1978 }
1979
1980 /** gets description of branching rule */
SCIPbranchruleGetDesc(SCIP_BRANCHRULE * branchrule)1981 const char* SCIPbranchruleGetDesc(
1982 SCIP_BRANCHRULE* branchrule /**< branching rule */
1983 )
1984 {
1985 assert(branchrule != NULL);
1986
1987 return branchrule->desc;
1988 }
1989
1990 /** gets priority of branching rule */
SCIPbranchruleGetPriority(SCIP_BRANCHRULE * branchrule)1991 int SCIPbranchruleGetPriority(
1992 SCIP_BRANCHRULE* branchrule /**< branching rule */
1993 )
1994 {
1995 assert(branchrule != NULL);
1996
1997 return branchrule->priority;
1998 }
1999
2000 /** sets priority of branching rule */
SCIPbranchruleSetPriority(SCIP_BRANCHRULE * branchrule,SCIP_SET * set,int priority)2001 void SCIPbranchruleSetPriority(
2002 SCIP_BRANCHRULE* branchrule, /**< branching rule */
2003 SCIP_SET* set, /**< global SCIP settings */
2004 int priority /**< new priority of the branching rule */
2005 )
2006 {
2007 assert(branchrule != NULL);
2008 assert(set != NULL);
2009
2010 branchrule->priority = priority;
2011 set->branchrulessorted = FALSE;
2012 }
2013
2014 /** gets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
SCIPbranchruleGetMaxdepth(SCIP_BRANCHRULE * branchrule)2015 int SCIPbranchruleGetMaxdepth(
2016 SCIP_BRANCHRULE* branchrule /**< branching rule */
2017 )
2018 {
2019 assert(branchrule != NULL);
2020
2021 return branchrule->maxdepth;
2022 }
2023
2024 /** sets maximal depth level, up to which this branching rule should be used (-1 for no limit) */
SCIPbranchruleSetMaxdepth(SCIP_BRANCHRULE * branchrule,int maxdepth)2025 void SCIPbranchruleSetMaxdepth(
2026 SCIP_BRANCHRULE* branchrule, /**< branching rule */
2027 int maxdepth /**< new maxdepth of the branching rule */
2028 )
2029 {
2030 assert(branchrule != NULL);
2031 assert(maxdepth >= -1);
2032
2033 branchrule->maxdepth = maxdepth;
2034 }
2035
2036 /** gets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
SCIPbranchruleGetMaxbounddist(SCIP_BRANCHRULE * branchrule)2037 SCIP_Real SCIPbranchruleGetMaxbounddist(
2038 SCIP_BRANCHRULE* branchrule /**< branching rule */
2039 )
2040 {
2041 assert(branchrule != NULL);
2042
2043 return branchrule->maxbounddist;
2044 }
2045
2046 /** sets maximal relative distance from current node's dual bound to primal bound for applying branching rule */
SCIPbranchruleSetMaxbounddist(SCIP_BRANCHRULE * branchrule,SCIP_Real maxbounddist)2047 void SCIPbranchruleSetMaxbounddist(
2048 SCIP_BRANCHRULE* branchrule, /**< branching rule */
2049 SCIP_Real maxbounddist /**< new maxbounddist of the branching rule */
2050 )
2051 {
2052 assert(branchrule != NULL);
2053 assert(maxbounddist >= -1);
2054
2055 branchrule->maxbounddist = maxbounddist;
2056 }
2057
2058 /** enables or disables all clocks of \p branchrule, depending on the value of the flag */
SCIPbranchruleEnableOrDisableClocks(SCIP_BRANCHRULE * branchrule,SCIP_Bool enable)2059 void SCIPbranchruleEnableOrDisableClocks(
2060 SCIP_BRANCHRULE* branchrule, /**< the branching rule for which all clocks should be enabled or disabled */
2061 SCIP_Bool enable /**< should the clocks of the branching rule be enabled? */
2062 )
2063 {
2064 assert(branchrule != NULL);
2065
2066 SCIPclockEnableOrDisable(branchrule->setuptime, enable);
2067 SCIPclockEnableOrDisable(branchrule->branchclock, enable);
2068 }
2069
2070 /** gets time in seconds used in this branching rule for setting up for next stages */
SCIPbranchruleGetSetupTime(SCIP_BRANCHRULE * branchrule)2071 SCIP_Real SCIPbranchruleGetSetupTime(
2072 SCIP_BRANCHRULE* branchrule /**< branching rule */
2073 )
2074 {
2075 assert(branchrule != NULL);
2076
2077 return SCIPclockGetTime(branchrule->setuptime);
2078 }
2079
2080 /** gets time in seconds used in this branching rule */
SCIPbranchruleGetTime(SCIP_BRANCHRULE * branchrule)2081 SCIP_Real SCIPbranchruleGetTime(
2082 SCIP_BRANCHRULE* branchrule /**< branching rule */
2083 )
2084 {
2085 assert(branchrule != NULL);
2086
2087 return SCIPclockGetTime(branchrule->branchclock);
2088 }
2089
2090 /** gets the total number of times, the branching rule was called on an LP solution */
SCIPbranchruleGetNLPCalls(SCIP_BRANCHRULE * branchrule)2091 SCIP_Longint SCIPbranchruleGetNLPCalls(
2092 SCIP_BRANCHRULE* branchrule /**< branching rule */
2093 )
2094 {
2095 assert(branchrule != NULL);
2096
2097 return branchrule->nlpcalls;
2098 }
2099
2100 /** gets the total number of times, the branching rule was called on an external solution */
SCIPbranchruleGetNExternCalls(SCIP_BRANCHRULE * branchrule)2101 SCIP_Longint SCIPbranchruleGetNExternCalls(
2102 SCIP_BRANCHRULE* branchrule /**< branching rule */
2103 )
2104 {
2105 assert(branchrule != NULL);
2106
2107 return branchrule->nexterncalls;
2108 }
2109
2110 /** gets the total number of times, the branching rule was called on a pseudo solution */
SCIPbranchruleGetNPseudoCalls(SCIP_BRANCHRULE * branchrule)2111 SCIP_Longint SCIPbranchruleGetNPseudoCalls(
2112 SCIP_BRANCHRULE* branchrule /**< branching rule */
2113 )
2114 {
2115 assert(branchrule != NULL);
2116
2117 return branchrule->npseudocalls;
2118 }
2119
2120 /** gets the total number of times, the branching rule detected a cutoff */
SCIPbranchruleGetNCutoffs(SCIP_BRANCHRULE * branchrule)2121 SCIP_Longint SCIPbranchruleGetNCutoffs(
2122 SCIP_BRANCHRULE* branchrule /**< branching rule */
2123 )
2124 {
2125 assert(branchrule != NULL);
2126
2127 return branchrule->ncutoffs;
2128 }
2129
2130 /** gets the total number of cuts, the branching rule separated */
SCIPbranchruleGetNCutsFound(SCIP_BRANCHRULE * branchrule)2131 SCIP_Longint SCIPbranchruleGetNCutsFound(
2132 SCIP_BRANCHRULE* branchrule /**< branching rule */
2133 )
2134 {
2135 assert(branchrule != NULL);
2136
2137 return branchrule->ncutsfound;
2138 }
2139
2140 /** gets the total number of constraints, the branching rule added to the respective local nodes (not counting constraints
2141 * that were added to the child nodes as branching decisions)
2142 */
SCIPbranchruleGetNConssFound(SCIP_BRANCHRULE * branchrule)2143 SCIP_Longint SCIPbranchruleGetNConssFound(
2144 SCIP_BRANCHRULE* branchrule /**< branching rule */
2145 )
2146 {
2147 assert(branchrule != NULL);
2148
2149 return branchrule->nconssfound;
2150 }
2151
2152 /** gets the total number of domain reductions, the branching rule found */
SCIPbranchruleGetNDomredsFound(SCIP_BRANCHRULE * branchrule)2153 SCIP_Longint SCIPbranchruleGetNDomredsFound(
2154 SCIP_BRANCHRULE* branchrule /**< branching rule */
2155 )
2156 {
2157 assert(branchrule != NULL);
2158
2159 return branchrule->ndomredsfound;
2160 }
2161
2162 /** gets the total number of children, the branching rule created */
SCIPbranchruleGetNChildren(SCIP_BRANCHRULE * branchrule)2163 SCIP_Longint SCIPbranchruleGetNChildren(
2164 SCIP_BRANCHRULE* branchrule /**< branching rule */
2165 )
2166 {
2167 assert(branchrule != NULL);
2168
2169 return branchrule->nchildren;
2170 }
2171
2172 /** is branching rule initialized? */
SCIPbranchruleIsInitialized(SCIP_BRANCHRULE * branchrule)2173 SCIP_Bool SCIPbranchruleIsInitialized(
2174 SCIP_BRANCHRULE* branchrule /**< branching rule */
2175 )
2176 {
2177 assert(branchrule != NULL);
2178
2179 return branchrule->initialized;
2180 }
2181
2182
2183
2184
2185 /*
2186 * branching methods
2187 */
2188
2189 /** calculates the branching score out of the gain predictions for a binary branching */
SCIPbranchGetScore(SCIP_SET * set,SCIP_VAR * var,SCIP_Real downgain,SCIP_Real upgain)2190 SCIP_Real SCIPbranchGetScore(
2191 SCIP_SET* set, /**< global SCIP settings */
2192 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
2193 SCIP_Real downgain, /**< prediction of objective gain for rounding downwards */
2194 SCIP_Real upgain /**< prediction of objective gain for rounding upwards */
2195 )
2196 {
2197 SCIP_Real score;
2198 SCIP_Real eps;
2199
2200 assert(set != NULL);
2201
2202 /* adjust scores near zero to always yield product score greater than 0 */
2203 eps = SCIPsetSumepsilon(set);
2204 if( set->branch_sumadjustscore )
2205 {
2206 /* adjust scores by adding eps to keep near zero score differences between variables */
2207 downgain = downgain + eps;
2208 upgain = upgain + eps;
2209 }
2210 else
2211 {
2212 /* disregard near zero score differences between variables and consider the branching factor for them */
2213 downgain = MAX(downgain, eps);
2214 upgain = MAX(upgain, eps);
2215 }
2216
2217 switch( set->branch_scorefunc )
2218 {
2219 case 's': /* linear sum score function */
2220 /* weigh the two child nodes with branchscorefac and 1-branchscorefac */
2221 if( downgain > upgain )
2222 score = set->branch_scorefac * downgain + (1.0-set->branch_scorefac) * upgain;
2223 else
2224 score = set->branch_scorefac * upgain + (1.0-set->branch_scorefac) * downgain;
2225 break;
2226
2227 case 'p': /* product score function */
2228 score = downgain * upgain;
2229 break;
2230 case 'q': /* quotient score function */
2231 if( downgain > upgain )
2232 score = upgain * upgain / downgain;
2233 else
2234 score = downgain * downgain / upgain;
2235 break;
2236 default:
2237 SCIPerrorMessage("invalid branching score function <%c>\n", set->branch_scorefunc);
2238 SCIPABORT();
2239 score = 0.0;
2240 }
2241
2242 /* apply the branch factor of the variable */
2243 if( var != NULL )
2244 score *= SCIPvarGetBranchFactor(var);
2245
2246 return score;
2247 }
2248
2249 /** calculates the branching score out of the gain predictions for a branching with arbitrary many children */
SCIPbranchGetScoreMultiple(SCIP_SET * set,SCIP_VAR * var,int nchildren,SCIP_Real * gains)2250 SCIP_Real SCIPbranchGetScoreMultiple(
2251 SCIP_SET* set, /**< global SCIP settings */
2252 SCIP_VAR* var, /**< variable, of which the branching factor should be applied, or NULL */
2253 int nchildren, /**< number of children that the branching will create */
2254 SCIP_Real* gains /**< prediction of objective gain for each child */
2255 )
2256 {
2257 SCIP_Real min1;
2258 SCIP_Real min2;
2259 int c;
2260
2261 assert(nchildren == 0 || gains != NULL);
2262
2263 /* search for the two minimal gains in the child list and use these to calculate the branching score */
2264 min1 = SCIPsetInfinity(set);
2265 min2 = SCIPsetInfinity(set);
2266 for( c = 0; c < nchildren; ++c )
2267 {
2268 if( gains[c] < min1 )
2269 {
2270 min2 = min1;
2271 min1 = gains[c];
2272 }
2273 else if( gains[c] < min2 )
2274 min2 = gains[c];
2275 }
2276
2277 return SCIPbranchGetScore(set, var, min1, min2);
2278 }
2279
2280 /** computes a branching point for a (not necessarily discrete) variable
2281 * a suggested branching point is first projected onto the box
2282 * if no point is suggested, then the value in the current LP or pseudo solution is used
2283 * if this value is at infinity, then 0.0 projected onto the bounds and then moved inside the interval is used
2284 * for a discrete variable, it is ensured that the returned value is fractional
2285 * for a continuous variable, the parameter branching/clamp defines how far a branching point need to be from the bounds of a variable
2286 * the latter is only applied if no point has been suggested, or the suggested point is not inside the variable's interval
2287 */
SCIPbranchGetBranchingPoint(SCIP_SET * set,SCIP_TREE * tree,SCIP_VAR * var,SCIP_Real suggestion)2288 SCIP_Real SCIPbranchGetBranchingPoint(
2289 SCIP_SET* set, /**< global SCIP settings */
2290 SCIP_TREE* tree, /**< branch and bound tree */
2291 SCIP_VAR* var, /**< variable, of which the branching point should be computed */
2292 SCIP_Real suggestion /**< suggestion for branching point, or SCIP_INVALID if no suggestion */
2293 )
2294 {
2295 SCIP_Real branchpoint;
2296 SCIP_Real lb;
2297 SCIP_Real ub;
2298
2299 assert(set != NULL);
2300 assert(var != NULL);
2301
2302 lb = SCIPvarGetLbLocal(var);
2303 ub = SCIPvarGetUbLocal(var);
2304
2305 /* for a fixed variable, we cannot branch further */
2306 assert(!SCIPsetIsEQ(set, lb, ub));
2307
2308 if( !SCIPsetIsInfinity(set, REALABS(suggestion)) )
2309 {
2310 /* use user suggested branching point */
2311
2312 /* first, project it onto the current domain */
2313 branchpoint = MAX(lb, MIN(suggestion, ub));
2314
2315 if( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
2316 {
2317 /* if it is a discrete variable, then round it down and up and accept this choice */
2318 if( SCIPsetIsEQ(set, branchpoint, ub) )
2319 {
2320 /* in the right branch, variable is fixed to its current upper bound */
2321 return SCIPsetFloor(set, branchpoint) - 0.5;
2322 }
2323 else
2324 {
2325 /* in the left branch, variable is fixed to its current lower bound */
2326 return SCIPsetFloor(set, branchpoint) + 0.5;
2327 }
2328 }
2329 else if( (SCIPsetIsInfinity(set, -lb) || SCIPsetIsRelGT(set, branchpoint, lb)) &&
2330 (SCIPsetIsInfinity(set, ub) || SCIPsetIsRelLT(set, branchpoint, ub)) )
2331 {
2332 /* if it is continuous and inside the box, then accept it */
2333 return branchpoint;
2334 }
2335 /* if it is continuous and suggestion is on of the bounds, continue below */
2336 }
2337 else
2338 {
2339 /* if no point is suggested, try the LP or pseudo solution */
2340 branchpoint = SCIPvarGetSol(var, SCIPtreeHasCurrentNodeLP(tree));
2341
2342 if( REALABS(branchpoint) > 1e+12 )
2343 {
2344 /* if the value in the LP or pseudosolution is large (here 1e+12), use 0.0 (will be projected onto bounds below) */
2345 branchpoint = 0.0;
2346 }
2347 else if( SCIPtreeHasCurrentNodeLP(tree) && set->branch_midpull > 0.0 && !SCIPsetIsInfinity(set, -lb) && !SCIPsetIsInfinity(set, ub) )
2348 {
2349 /* if the value is from the LP and midpull is activated, then push towards middle of domain */
2350 SCIP_Real midpull = set->branch_midpull;
2351 SCIP_Real glb;
2352 SCIP_Real gub;
2353 SCIP_Real reldomainwidth;
2354
2355 /* shrink midpull if width of local domain, relative to global domain, is small
2356 * that is, if there has been already one or several branchings on this variable, then give more emphasis on LP solution
2357 *
2358 * do this only if the relative domain width is below the minreldomainwidth value
2359 */
2360 glb = SCIPvarGetLbGlobal(var);
2361 gub = SCIPvarGetUbGlobal(var);
2362 assert(glb < gub);
2363
2364 if( !SCIPsetIsInfinity(set, -glb) && !SCIPsetIsInfinity(set, gub) )
2365 reldomainwidth = (ub - lb) / (gub - glb);
2366 else
2367 reldomainwidth = SCIPsetEpsilon(set);
2368
2369 if( reldomainwidth < set->branch_midpullreldomtrig )
2370 midpull *= reldomainwidth;
2371
2372 branchpoint = midpull * (lb+ub) / 2.0 + (1.0 - midpull) * branchpoint;
2373 }
2374
2375 /* make sure branchpoint is on interval, below we make sure that it is within bounds for continuous vars */
2376 branchpoint = MAX(lb, MIN(branchpoint, ub));
2377 }
2378
2379 /* if value is at +/- infty, then choose some value a bit off from bounds or 0.0 */
2380 if( SCIPsetIsInfinity(set, branchpoint) )
2381 {
2382 /* if value is at +infty, then the upper bound should be at infinity */
2383 assert(SCIPsetIsInfinity(set, ub));
2384
2385 /* choose 0.0 or something above lower bound if lower bound > 0 */
2386 if( SCIPsetIsPositive(set, lb) )
2387 branchpoint = lb + 1000.0;
2388 else
2389 branchpoint = 0.0;
2390 }
2391 else if( SCIPsetIsInfinity(set, -branchpoint) )
2392 {
2393 /* if value is at -infty, then the lower bound should be at -infinity */
2394 assert(SCIPsetIsInfinity(set, -lb));
2395
2396 /* choose 0.0 or something below upper bound if upper bound < 0 */
2397 if( SCIPsetIsNegative(set, ub) )
2398 branchpoint = ub - 1000.0;
2399 else
2400 branchpoint = 0.0;
2401 }
2402
2403 assert(SCIPsetIsInfinity(set, ub) || SCIPsetIsLE(set, branchpoint, ub));
2404 assert(SCIPsetIsInfinity(set, -lb) || SCIPsetIsGE(set, branchpoint, lb));
2405
2406 if( SCIPvarGetType(var) >= SCIP_VARTYPE_IMPLINT )
2407 {
2408 if( !SCIPsetIsInfinity(set, -lb) || !SCIPsetIsInfinity(set, ub) )
2409 {
2410 /* if one bound is missing, we are temporarily guessing the other one, so we can apply the clamp below */
2411 if( SCIPsetIsInfinity(set, ub) )
2412 {
2413 ub = lb + MIN(MAX(0.5 * REALABS(lb), 1000), 0.9 * (SCIPsetInfinity(set) - lb)); /*lint !e666*/
2414 }
2415 else if( SCIPsetIsInfinity(set, -lb) )
2416 {
2417 lb = ub - MIN(MAX(0.5 * REALABS(ub), 1000), 0.9 * (SCIPsetInfinity(set) + ub)); /*lint !e666*/
2418 }
2419
2420 /* if branching point is too close to the bounds, move more into the middle of the interval */
2421 if( SCIPrelDiff(ub, lb) <= 2.02 * SCIPsetEpsilon(set) )
2422 {
2423 /* for very tiny intervals we set it exactly into the middle */
2424 branchpoint = (lb+ub)/2.0;
2425 }
2426 else
2427 {
2428 /* otherwise we project it away from the bounds */
2429 SCIP_Real minbrpoint;
2430 SCIP_Real maxbrpoint;
2431 SCIP_Real scale;
2432 SCIP_Real lbabs;
2433 SCIP_Real ubabs;
2434
2435 lbabs = REALABS(lb);
2436 ubabs = REALABS(ub);
2437
2438 scale = MAX3(lbabs, ubabs, 1.0);
2439
2440 /* the minimal branching point should be
2441 * - set->clamp away from the lower bound - relative to the local domain size
2442 * - SCIPsetEpsilon(set)*scale above the lower bound - in absolute value
2443 */
2444 minbrpoint = (1.0 - set->branch_clamp) * lb + set->branch_clamp * ub;
2445 minbrpoint = MAX(lb + 1.01*SCIPsetEpsilon(set)*scale, minbrpoint); /*lint !e666*/
2446
2447 /* the maximal branching point should be
2448 * - set->clamp away from the upper bound - relative to the local domain size
2449 * - SCIPsetEpsilon(set)*scale below the upper bound - in absolute value
2450 */
2451 maxbrpoint = set->branch_clamp * lb + (1.0 - set->branch_clamp) * ub;
2452 maxbrpoint = MIN(ub - 1.01*SCIPsetEpsilon(set)*scale, maxbrpoint); /*lint !e666*/
2453
2454 /* project branchpoint into [minbrpoint, maxbrpoint] */
2455 branchpoint = MAX(minbrpoint, MIN(branchpoint, maxbrpoint));
2456
2457 /* if selected branching point is close to 0.0 and bounds are away from 0.0, it often makes sense to branch exactly on 0.0 */
2458 if( SCIPsetIsFeasZero(set, branchpoint) && SCIPsetIsFeasNegative(set, lb) && SCIPsetIsFeasPositive(set, ub) )
2459 branchpoint = 0.0;
2460
2461 assert(SCIPsetIsRelLT(set, SCIPvarGetLbLocal(var), branchpoint));
2462 assert(SCIPsetIsRelLT(set, branchpoint, SCIPvarGetUbLocal(var)));
2463 }
2464 }
2465
2466 /* ensure fractional branching point for implicit integer variables */
2467 if( SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT && SCIPsetIsIntegral(set, branchpoint) )
2468 {
2469 /* if branchpoint is integral but not on bounds, then it should be one of the value {lb+1, ..., ub-1} */
2470 assert(SCIPsetIsGE(set, SCIPsetRound(set, branchpoint), lb + 1.0));
2471 assert(SCIPsetIsLE(set, SCIPsetRound(set, branchpoint), ub - 1.0));
2472 /* if branchpoint is integral, create one branch with x <= x'-1 and one with x >= x'
2473 * @todo could in the same way be x <= x' and x >= x'+1; is there some easy way to know which is better?
2474 */
2475 return branchpoint - 0.5;
2476 }
2477
2478 return branchpoint;
2479 }
2480 else
2481 {
2482 /* discrete variables */
2483 if( branchpoint <= lb + 0.5 )
2484 {
2485 /* if branchpoint is on lower bound, create one branch with x = lb and one with x >= lb+1 */
2486 return lb + 0.5;
2487 }
2488 else if( branchpoint >= ub - 0.5 )
2489 {
2490 /* if branchpoint is on upper bound, create one branch with x = ub and one with x <= ub-1 */
2491 return ub - 0.5;
2492 }
2493 else if( SCIPsetIsIntegral(set, branchpoint) )
2494 {
2495 /* if branchpoint is integral but not on bounds, then it should be one of the value {lb+1, ..., ub-1} */
2496 assert(SCIPsetIsGE(set, SCIPsetRound(set, branchpoint), lb + 1.0));
2497 assert(SCIPsetIsLE(set, SCIPsetRound(set, branchpoint), ub - 1.0));
2498 /* if branchpoint is integral, create one branch with x <= x'-1 and one with x >= x'
2499 * @todo could in the same way be x <= x' and x >= x'+1; is there some easy way to know which is better? */
2500 return branchpoint - 0.5;
2501 }
2502 else
2503 {
2504 /* branchpoint is somewhere between bounds and fractional, so just round down and up */
2505 return branchpoint;
2506 }
2507 }
2508 }
2509
2510 /** calls branching rules to branch on an LP solution; if no fractional variables exist, the result is SCIP_DIDNOTRUN;
2511 * if the branch priority of an unfixed variable is larger than the maximal branch priority of the fractional
2512 * variables, pseudo solution branching is applied on the unfixed variables with maximal branch priority
2513 */
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)2514 SCIP_RETCODE SCIPbranchExecLP(
2515 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
2516 SCIP_SET* set, /**< global SCIP settings */
2517 SCIP_STAT* stat, /**< problem statistics */
2518 SCIP_PROB* transprob, /**< transformed problem after presolve */
2519 SCIP_PROB* origprob, /**< original problem */
2520 SCIP_TREE* tree, /**< branch and bound tree */
2521 SCIP_REOPT* reopt, /**< reoptimization data structure */
2522 SCIP_LP* lp, /**< current LP data */
2523 SCIP_SEPASTORE* sepastore, /**< separation storage */
2524 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2525 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2526 SCIP_Real cutoffbound, /**< global upper cutoff bound */
2527 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
2528 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
2529 )
2530 {
2531 int i;
2532 int nalllpcands; /* sum of binary, integer, and implicit branching candidates */
2533
2534 assert(branchcand != NULL);
2535 assert(result != NULL);
2536
2537 *result = SCIP_DIDNOTRUN;
2538
2539 /* calculate branching candidates */
2540 SCIP_CALL( branchcandCalcLPCands(branchcand, set, stat, lp) );
2541 assert(0 <= branchcand->npriolpcands && branchcand->npriolpcands <= branchcand->nlpcands);
2542 assert((branchcand->npriolpcands == 0) == (branchcand->nlpcands == 0));
2543
2544 SCIPsetDebugMsg(set, "branching on LP solution with %d (+%d) fractional (+implicit fractional) variables (%d of maximal priority)\n",
2545 branchcand->nlpcands, branchcand->nimpllpfracs, branchcand->npriolpcands);
2546
2547 nalllpcands = branchcand->nlpcands + branchcand->nimpllpfracs;
2548 /* do nothing, if no fractional variables exist */
2549 if( nalllpcands == 0 )
2550 return SCIP_OKAY;
2551
2552 /* if there is a non-fixed variable with higher priority than the maximal priority of the fractional candidates,
2553 * use pseudo solution branching instead
2554 */
2555 if( branchcand->pseudomaxpriority > branchcand->lpmaxpriority )
2556 {
2557 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cutoffbound,
2558 allowaddcons, result) );
2559 assert(*result != SCIP_DIDNOTRUN && *result != SCIP_DIDNOTFIND);
2560 return SCIP_OKAY;
2561 }
2562
2563 /* sort the branching rules by priority */
2564 SCIPsetSortBranchrules(set);
2565
2566 /* try all branching rules until one succeeded to branch */
2567 for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2568 {
2569 SCIP_CALL( SCIPbranchruleExecLPSol(set->branchrules[i], set, stat, tree, sepastore, cutoffbound, allowaddcons, result) );
2570 }
2571
2572 if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND )
2573 {
2574 SCIP_VAR* var;
2575 SCIP_Real factor;
2576 SCIP_Real bestfactor;
2577 int priority;
2578 int bestpriority;
2579 int bestcand;
2580
2581 /* no branching method succeeded in choosing a branching: just branch on the first fractional variable with maximal
2582 * priority, and out of these on the one with maximal branch factor
2583 */
2584 bestcand = -1;
2585 bestpriority = INT_MIN;
2586 bestfactor = SCIP_REAL_MIN;
2587 for( i = 0; i < nalllpcands; ++i )
2588 {
2589 priority = SCIPvarGetBranchPriority(branchcand->lpcands[i]);
2590 factor = SCIPvarGetBranchFactor(branchcand->lpcands[i]);
2591 if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) )
2592 {
2593 bestcand = i;
2594 bestpriority = priority;
2595 bestfactor = factor;
2596 }
2597 }
2598 assert(0 <= bestcand && bestcand < nalllpcands);
2599
2600 var = branchcand->lpcands[bestcand];
2601 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS);
2602 assert(branchcand->nlpcands == 0 || SCIPvarGetType(var) != SCIP_VARTYPE_IMPLINT);
2603
2604 assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2605
2606 SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, SCIP_INVALID,
2607 NULL, NULL, NULL) );
2608
2609 *result = SCIP_BRANCHED;
2610 }
2611
2612 return SCIP_OKAY;
2613 }
2614
2615 /** calls branching rules to branch on an external solution; if no external branching candidates exist, the result is SCIP_DIDNOTRUN */
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)2616 SCIP_RETCODE SCIPbranchExecExtern(
2617 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
2618 SCIP_SET* set, /**< global SCIP settings */
2619 SCIP_STAT* stat, /**< problem statistics */
2620 SCIP_PROB* transprob, /**< transformed problem after presolve */
2621 SCIP_PROB* origprob, /**< original problem */
2622 SCIP_TREE* tree, /**< branch and bound tree */
2623 SCIP_REOPT* reopt, /**< reoptimization data structure */
2624 SCIP_LP* lp, /**< current LP data */
2625 SCIP_SEPASTORE* sepastore, /**< separation storage */
2626 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2627 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2628 SCIP_Real cutoffbound, /**< global upper cutoff bound */
2629 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
2630 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
2631 )
2632 {
2633 int i;
2634
2635 assert(branchcand != NULL);
2636 assert(result != NULL);
2637 assert(0 <= branchcand->nprioexterncands && branchcand->nprioexterncands <= branchcand->nexterncands);
2638 assert((branchcand->nprioexterncands == 0) == (branchcand->nexterncands == 0));
2639
2640 *result = SCIP_DIDNOTRUN;
2641
2642 SCIPsetDebugMsg(set, "branching on external solution with %d branching candidates (%d of maximal priority)\n",
2643 branchcand->nexterncands, branchcand->nprioexterncands);
2644
2645 /* do nothing, if no external candidates exist */
2646 if( branchcand->nexterncands == 0 )
2647 return SCIP_OKAY;
2648
2649 /* if there is a non-fixed variable with higher priority than the maximal priority of the external candidates,
2650 * use pseudo solution branching instead
2651 */
2652 if( branchcand->pseudomaxpriority > branchcand->externmaxpriority )
2653 {
2654 /* @todo: adjust this, that also LP branching might be called, if lpmaxpriority != externmaxpriority.
2655 * Therefor, it has to be clear which of both has the higher priority
2656 */
2657 SCIP_CALL( SCIPbranchExecPseudo(blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cutoffbound,
2658 allowaddcons, result) );
2659 assert(*result != SCIP_DIDNOTRUN && *result != SCIP_DIDNOTFIND);
2660 return SCIP_OKAY;
2661 }
2662
2663 /* sort the branching rules by priority */
2664 SCIPsetSortBranchrules(set);
2665
2666 /* try all branching rules until one succeeded to branch */
2667 for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2668 {
2669 SCIP_CALL( SCIPbranchruleExecExternSol(set->branchrules[i], set, stat, tree, sepastore, cutoffbound, allowaddcons, result) );
2670 }
2671
2672 if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND )
2673 {
2674 SCIP_VAR* var;
2675 SCIP_Real val;
2676 SCIP_Real bestfactor;
2677 SCIP_Real bestdomain;
2678 int bestpriority;
2679 int bestcand;
2680
2681 /* if all branching rules did nothing, then they should also not have cleared all branching candidates */
2682 assert(branchcand->nexterncands > 0);
2683
2684 /* no branching method succeeded in choosing a branching: just branch on the first branching candidates with maximal
2685 * priority, and out of these on the one with maximal branch factor, and out of these on the one with largest domain
2686 */
2687 bestcand = -1;
2688 bestpriority = INT_MIN;
2689 bestfactor = SCIP_REAL_MIN;
2690 bestdomain = 0.0;
2691 for( i = 0; i < branchcand->nexterncands; ++i )
2692 {
2693 SCIP_VAR* cand;
2694 SCIP_Real domain;
2695 SCIP_Real factor;
2696 int priority;
2697
2698 cand = branchcand->externcands[i];
2699 priority = SCIPvarGetBranchPriority(cand);
2700 factor = SCIPvarGetBranchFactor(cand);
2701
2702 /* the domain size is infinite, iff one of the bounds is infinite */
2703 if( SCIPsetIsInfinity(set, -SCIPvarGetLbLocal(cand)) || SCIPsetIsInfinity(set, SCIPvarGetUbLocal(cand)) )
2704 domain = SCIPsetInfinity(set);
2705 else
2706 domain = SCIPvarGetUbLocal(cand) - SCIPvarGetLbLocal(cand);
2707
2708 /* choose variable with higher priority, higher factor, larger domain (in that order) */
2709 if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) || (priority == bestpriority && factor == bestfactor && domain > bestdomain) ) /*lint !e777*/
2710 {
2711 bestcand = i;
2712 bestpriority = priority;
2713 bestfactor = factor;
2714 bestdomain = domain;
2715 }
2716 }
2717 assert(0 <= bestcand && bestcand < branchcand->nexterncands);
2718
2719 var = branchcand->externcands[bestcand];
2720 val = SCIPbranchGetBranchingPoint(set, tree, var, branchcand->externcandssol[bestcand]);
2721 assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2722 assert(SCIPrelDiff(SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var)) <= 2.02 * SCIPsetEpsilon(set)
2723 || SCIPsetIsLT(set, SCIPvarGetLbLocal(var), val));
2724 assert(SCIPrelDiff(SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var)) <= 2.02 * SCIPsetEpsilon(set)
2725 || SCIPsetIsLT(set, val, SCIPvarGetUbLocal(var)));
2726
2727 SCIPsetDebugMsg(set, "no branching method succeeded; fallback selected to branch on variable <%s> with bounds [%g, %g] on value %g\n",
2728 SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), val);
2729
2730 SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, val,
2731 NULL, NULL, NULL) );
2732
2733 if( tree->nchildren >= 1 )
2734 *result = SCIP_BRANCHED;
2735 /* if the bounds are too close, it may happen that we cannot branch but rather fix the variable */
2736 else
2737 {
2738 assert(SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2739 *result = SCIP_REDUCEDDOM;
2740 }
2741 }
2742
2743 return SCIP_OKAY;
2744 }
2745
2746 /** calls branching rules to branch on a pseudo solution; if no unfixed variables exist, the result is SCIP_DIDNOTRUN */
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)2747 SCIP_RETCODE SCIPbranchExecPseudo(
2748 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
2749 SCIP_SET* set, /**< global SCIP settings */
2750 SCIP_STAT* stat, /**< problem statistics */
2751 SCIP_PROB* transprob, /**< transformed problem after presolve */
2752 SCIP_PROB* origprob, /**< original problem */
2753 SCIP_TREE* tree, /**< branch and bound tree */
2754 SCIP_REOPT* reopt, /**< reoptimization data structure */
2755 SCIP_LP* lp, /**< current LP data */
2756 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2757 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2758 SCIP_Real cutoffbound, /**< global upper cutoff bound */
2759 SCIP_Bool allowaddcons, /**< should adding constraints be allowed to avoid a branching? */
2760 SCIP_RESULT* result /**< pointer to store the result of the branching (s. branch.h) */
2761 )
2762 {
2763 int i;
2764
2765 assert(branchcand != NULL);
2766 assert(result != NULL);
2767
2768 SCIPsetDebugMsg(set, "branching on pseudo solution with %d unfixed variables\n", branchcand->npseudocands);
2769
2770 *result = SCIP_DIDNOTRUN;
2771
2772 /* do nothing, if no unfixed variables exist */
2773 if( branchcand->npseudocands == 0 )
2774 return SCIP_OKAY;
2775
2776 /* sort the branching rules by priority */
2777 SCIPsetSortBranchrules(set);
2778
2779 /* try all branching rules until one succeeded to branch */
2780 for( i = 0; i < set->nbranchrules && (*result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND); ++i )
2781 {
2782 SCIP_CALL( SCIPbranchruleExecPseudoSol(set->branchrules[i], set, stat, tree, cutoffbound, allowaddcons, result) );
2783 }
2784
2785 if( *result == SCIP_DIDNOTRUN || *result == SCIP_DIDNOTFIND )
2786 {
2787 SCIP_VAR* var;
2788 SCIP_Real factor;
2789 SCIP_Real bestfactor;
2790 int priority;
2791 int bestpriority;
2792 int bestcand;
2793
2794 /* no branching method succeeded in choosing a branching: just branch on the first unfixed variable with maximal
2795 * priority, and out of these on the one with maximal branch factor
2796 */
2797 bestcand = -1;
2798 bestpriority = INT_MIN;
2799 bestfactor = SCIP_REAL_MIN;
2800 for( i = 0; i < branchcand->npseudocands; ++i )
2801 {
2802 priority = SCIPvarGetBranchPriority(branchcand->pseudocands[i]);
2803 factor = SCIPvarGetBranchFactor(branchcand->pseudocands[i]);
2804 if( priority > bestpriority || (priority == bestpriority && factor > bestfactor) )
2805 {
2806 bestcand = i;
2807 bestpriority = priority;
2808 bestfactor = factor;
2809 }
2810 }
2811 assert(0 <= bestcand && bestcand < branchcand->npseudocands);
2812
2813 var = branchcand->pseudocands[bestcand];
2814 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS);
2815 assert(!SCIPsetIsEQ(set, SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var)));
2816
2817 SCIP_CALL( SCIPtreeBranchVar(tree, reopt, blkmem, set, stat, transprob, origprob, lp, branchcand, eventqueue, var, SCIP_INVALID,
2818 NULL, NULL, NULL) );
2819
2820 *result = SCIP_BRANCHED;
2821 }
2822
2823 return SCIP_OKAY;
2824 }
2825
2826