Scippy

SCIP

Solving Constraint Integer Programs

branch_inference.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file branch_inference.c
26 * @ingroup DEFPLUGINS_BRANCH
27 * @brief inference history branching rule
28 * @author Tobias Achterberg
29 * @author Timo Berthold
30 * @author Stefan Heinz
31 */
32
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34
36#include "scip/pub_branch.h"
37#include "scip/pub_history.h"
38#include "scip/pub_message.h"
39#include "scip/pub_var.h"
40#include "scip/scip_branch.h"
41#include "scip/scip_message.h"
42#include "scip/scip_mem.h"
43#include "scip/scip_numerics.h"
44#include "scip/scip_param.h"
45#include "scip/scip_var.h"
46#include <string.h>
47
48
49/**@name Branching rule properties
50 *
51 * @{
52 */
53
54#define BRANCHRULE_NAME "inference"
55#define BRANCHRULE_DESC "inference history branching"
56#define BRANCHRULE_PRIORITY 1000
57#define BRANCHRULE_MAXDEPTH -1
58#define BRANCHRULE_MAXBOUNDDIST 1.0
59
60/**@} */
61
62/**@name Default parameter values
63 *
64 * @{
65 */
66
67#define DEFAULT_CONFLICTWEIGHT 1000.0 /**< weight in score calculations for conflict score */
68#define DEFAULT_CUTOFFWEIGHT 1.0 /**< weight in score calculations for cutoff score */
69#define DEFAULT_INFERENCEWEIGHT 1.0 /**< weight in score calculations for inference score */
70#define DEFAULT_RELIABLESCORE 0.001 /**< score which is seen to be reliable for a branching decision */
71#define DEFAULT_FRACTIONALS TRUE /**< should branching on LP solution be restricted to the fractional variables? */
72#define DEFAULT_USEWEIGHTEDSUM TRUE /**< should a weighted sum of inference, conflict and cutoff weights be used? */
73
74#define DEFAULT_CONFLICTPRIO 1 /**< priority value for using conflict weights in lex. order */
75#define DEFAULT_CUTOFFPRIO 1 /**< priority value for using cutoff weights in lex. order */
76
77/**@} */
78
79/** branching rule data */
80struct SCIP_BranchruleData
81{
82 SCIP_Real conflictweight; /**< weight in score calculations for conflict score */
83 SCIP_Real cutoffweight; /**< weight in score calculations for cutoff score */
84 SCIP_Real inferenceweight; /**< weight in score calculations for inference score */
85 SCIP_Real reliablescore; /**< score which is seen to be reliable for a branching decision */
86 SCIP_Bool fractionals; /**< should branching on LP solution be restricted to the fractional variables? */
87 SCIP_Bool useweightedsum; /**< should a weighted sum of inference, conflict and cutoff weights be used? */
88 int conflictprio; /**< priority value for using conflict weights in lexicographic order */
89 int cutoffprio; /**< priority value for using cutoff weights in lexicographic order */
90};
91
92/** evaluate the given candidate with the given score against the currently best know candidate, tiebreaking included */
93static
95 SCIP_VAR* cand, /**< candidate to be checked */
96 SCIP_Real score, /**< score of the candidate */
97 SCIP_Real branchpoint, /**< potential branching point */
98 SCIP_BRANCHDIR branchdir, /**< potential branching direction */
99 SCIP_VAR** bestcand, /**< pointer to the currently best candidate */
100 SCIP_Real* bestscore, /**< pointer to the score of the currently best candidate */
101 SCIP_Real* bestbranchpoint, /**< pointer to store the (best) branching point */
102 SCIP_BRANCHDIR* bestbranchdir /**< pointer to store the branching direction relative to the branching point */
103 )
104{
105 /* evaluate the candidate against the currently best candidate */
106 if( *bestscore < score )
107 {
108 /* the score of the candidate is better than the currently best know candidate */
109 *bestscore = score;
110 *bestcand = cand;
111 *bestbranchpoint = branchpoint;
112 *bestbranchdir = branchdir;
113 }
114 else if( (*bestscore) == score ) /*lint !e777*/
115 {
116 SCIP_Real bestobj;
117 SCIP_Real candobj;
118
119 bestobj = REALABS(SCIPvarGetObj(*bestcand));
120 candobj = REALABS(SCIPvarGetObj(cand));
121
122 /* the candidate has the same score as the best known candidate; therefore we use a second and third
123 * criteria to detect a unique best candidate;
124 *
125 * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
126 * since branching on that variable might trigger further propagation w.r.t. objective function
127 * - if the absolute values of the objective coefficient are equal the variable index is used to define a
128 * unique best candidate
129 *
130 * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
131 * performance to much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
132 * SCIPgetLPBranchCands()) gets dynamically changed during the solution process. In particular,
133 * starting a probing mode might already change the order of these arrays. To be independent of that
134 * the selection should be unique. Otherwise, to selection process can get influenced by starting a
135 * probing or not.
136 */
137 if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(*bestcand) < SCIPvarGetIndex(cand)) ) /*lint !e777*/
138 {
139 *bestcand = cand;
140 *bestbranchpoint = branchpoint;
141 *bestbranchdir = branchdir;
142 }
143 }
144}
145
146/** evaluate the given candidate with the given score against the currently best know candidate */
147static
149 SCIP* scip, /**< SCIP data structure */
150 SCIP_VAR* cand, /**< candidate to be checked */
151 SCIP_Real score, /**< score of the candidate */
152 SCIP_Real val, /**< solution value of the candidate */
153 SCIP_VAR** bestcand, /**< pointer to the currently best candidate */
154 SCIP_Real* bestscore, /**< pointer to the score of the currently best candidate */
155 SCIP_Real* bestval, /**< pointer to the solution value of the currently best candidate */
156 SCIP_VAR** bestcands, /**< buffer array to return selected candidates */
157 int* nbestcands /**< pointer to return number of selected candidates */
158 )
159{
160 /* evaluate the candidate against the currently best candidate */
161 /* TODO: consider a weaker comparison of some kind */
162 if( *bestscore < score )
163 {
164 /* the score of the candidate is better than the currently best know candidate, so it should be the first candidate in bestcands and nbestcands should be set to 1*/
165 *bestscore = score;
166 *bestcand = cand;
167 *bestval = val;
168 *nbestcands = 1;
169 bestcands[0] = cand;
170 }
171 /* TODO: consider a weaker comparison of some kind */
172 else if( SCIPisEQ(scip, *bestscore, score) )
173 {
174 /* the score of the candidate is comparable to the currently known best, so we add it to bestcands and increase nbestcands by 1*/
175 bestcands[*nbestcands] = cand;
176 (*nbestcands)++;
177 }
178}
179
180/** choose a singular best candidate from bestcands and move it to the beginning of the candidate array */
181static
183 SCIP_VAR** bestcands, /**< buffer array to return selected candidates */
184 int nbestcands /**< number of selected candidates */
185 )
186{
187 int c;
188
189 for( c = 0; c < nbestcands; ++c )
190 {
191 SCIP_Real bestobj;
192 SCIP_Real candobj;
193
194 bestobj = REALABS(SCIPvarGetObj(bestcands[0]));
195 candobj = REALABS(SCIPvarGetObj(bestcands[c]));
196
197 /* the candidate has the same score as the best known candidate; therefore we use a second and third
198 * criteria to detect a unique best candidate;
199 *
200 * - the second criteria prefers the candidate with a larger absolute value of its objective coefficient
201 * since branching on that variable might trigger further propagation w.r.t. objective function
202 * - if the absolute values of the objective coefficient are equal the variable index is used to define a
203 * unique best candidate
204 *
205 * @note It is very important to select a unique best candidate. Otherwise the solver might vary w.r.t. the
206 * performance too much since the candidate array which is used here (SCIPgetPseudoBranchCands() or
207 * SCIPgetLPBranchCands()) gets dynamically changed during the solution process. In particular,
208 * starting a probing mode might already change the order of these arrays. To be independent of that
209 * the selection should be unique. Otherwise, to selection process can get influenced by starting a
210 * probing or not.
211 */
212 if( bestobj < candobj || (bestobj == candobj && SCIPvarGetIndex(bestcands[0]) < SCIPvarGetIndex(bestcands[c])) ) /*lint !e777*/
213 {
214 bestcands[0] = bestcands[c];
215 }
216 }
217}
218
219/** check if the score for the given domain value and variable domain value is better than the current best know one */
220static
222 SCIP_Real value, /**< domain value */
223 SCIP_HISTORY* history, /**< variable history for given donain value */
224 SCIP_BRANCHDIR dir, /**< branching direction */
225 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
226 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
227 SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
228 SCIP_Real* bestscore, /**< pointer to store the best score */
229 SCIP_Real* branchpoint, /**< pointer to store the (best) branching point */
230 SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
231 )
232{
233 SCIP_Real conflictscore;
234 SCIP_Real cutoffscore;
235 SCIP_Real score;
236
237 conflictscore = SCIPhistoryGetVSIDS(history, dir);
238 cutoffscore = SCIPhistoryGetCutoffSum(history, dir);
239
240 /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
241 * unreliable
242 */
243 if( conflictscore < reliablescore )
244 conflictscore = 0.0;
245
246 /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
247 if( cutoffscore < reliablescore )
248 cutoffscore = 0.0;
249
250 /* compute weight score */
251 score = conflictweight * conflictscore + cutoffweight * cutoffscore;
252
253 if( score > *bestscore )
254 {
255 (*bestscore) = score;
256 (*branchpoint) = value;
257 (*branchdir) = dir;
258 }
259}
260
261/** return an aggregated score for the given variable using the conflict score and cutoff score */
262static
264 SCIP* scip, /**< SCIP data structure */
265 SCIP_VAR* var, /**< problem variable */
266 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
267 SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
268 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
269 SCIP_Real reliablescore /**< score which is seen to be reliable for a branching decision */
270 )
271{
272 SCIP_Real conflictscore;
273 SCIP_Real cutoffscore;
274
275 conflictscore = SCIPgetVarConflictScore(scip, var);
276 cutoffscore = SCIPgetVarAvgInferenceCutoffScore(scip, var, cutoffweight);
277
278 /* in case the conflict score is below the reliable score we set it to zero since it is seen to be
279 * unreliable
280 */
281 if( conflictscore < reliablescore )
282 conflictscore = 0.0;
283
284 /* in case the cutoff score is below the reliable score we set it to zero since it is seen to be unreliable */
285 if( cutoffscore < reliablescore )
286 cutoffscore = 0.0;
287
288 /* compute weighted score for the candidate */
289 return (conflictweight * conflictscore + inferenceweight * cutoffscore);
290}
291
292/** return an aggregated score for the given variable using the conflict score and cutoff score */
293static
295 SCIP_VAR* var, /**< problem variable */
296 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
297 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
298 SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
299 SCIP_Real* branchpoint, /**< pointer to store the branching point */
300 SCIP_BRANCHDIR* branchdir /**< pointer to store the branching direction relative to the branching point */
301 )
302{
303 SCIP_VALUEHISTORY* valuehistory;
304 SCIP_Real bestscore;
305
306 (*branchpoint) = SCIP_UNKNOWN;
307 (*branchdir) = SCIP_BRANCHDIR_UPWARDS;
308
309 valuehistory = SCIPvarGetValuehistory(var);
310 bestscore = 0.0;
311
312 if( valuehistory != NULL )
313 {
314 SCIP_HISTORY** histories;
315 SCIP_Real* values;
316 int nvalues;
317 int v;
318
319 histories = SCIPvaluehistoryGetHistories(valuehistory);
320 values = SCIPvaluehistoryGetValues(valuehistory);
321 nvalues = SCIPvaluehistoryGetNValues(valuehistory);
322
323 for( v = 0; v < nvalues; ++v )
324 {
325 SCIP_Real value;
326
327 value = values[v];
328
329 /* skip all domain values which are smaller or equal to the lower bound */
330 if( value <= SCIPvarGetLbLocal(var) )
331 continue;
332
333 /* skip all domain values which are larger or equal to the upper bound */
334 if( value >= SCIPvarGetUbLocal(var) )
335 break;
336
337 /* check var <= value */
338 checkValueScore(value, histories[v], SCIP_BRANCHDIR_DOWNWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir);
339
340 /* check var >= value */
341 checkValueScore(value, histories[v], SCIP_BRANCHDIR_UPWARDS, conflictweight, cutoffweight, reliablescore, &bestscore, branchpoint, branchdir);
342 }
343 }
344
345 return bestscore;
346}
347
348static
350 SCIP* scip, /**< SCIP data structure */
351 SCIP_VAR** cands, /**< candidate array */
352 SCIP_Real* candsols, /**< array of candidate solution values, or NULL */
353 int ncands, /**< number of candidates */
354 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
355 SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
356 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
357 SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
358 SCIP_VAR** bestcands, /**< buffer array to return selected candidates */
359 int* nbestcands /**< pointer to return number of selected candidates */
360 )
361{
362 SCIP_VAR* bestaggrcand;
363 SCIP_Real bestval;
364 SCIP_Real bestaggrscore;
365 int c;
366
367 bestaggrcand = cands[0];
368 assert(cands[0] != NULL);
369
370 bestval = candsols[0];
371 bestcands[0] = cands[0];
372 *nbestcands = 1;
373
374 /* get aggregated score for the first candidate */
375 bestaggrscore = getAggrScore(scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore);
376
377 for( c = 1; c < ncands; ++c )
378 {
379 SCIP_VAR* cand;
380 SCIP_Real val;
381 SCIP_Real aggrscore;
382
383 cand = cands[c];
384 assert(cand != NULL);
385
386 val = candsols[c];
387
388 /* get score for the candidate */
389 aggrscore = getAggrScore(scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore);
390
391 /*lint -e777*/
392 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
393 val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore);
394
395 /* evaluate the candidate against the currently best candidate w.r.t. aggregated score */
396 evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, nbestcands);
397 }
398} /*lint --e{438}*/
399
400
401/** selects a variable out of the given candidate array and performs the branching */
402static
404 SCIP* scip, /**< SCIP data structure */
405 SCIP_VAR** cands, /**< candidate array */
406 SCIP_Real* candsols, /**< array of candidate solution values, or NULL */
407 int ncands, /**< number of candidates */
408 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
409 SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
410 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
411 SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
412 SCIP_Bool useweightedsum, /**< should a weighted sum of inference, conflict and cutoff weights be used? */
413 SCIP_RESULT* result, /**< buffer to store result (branched, reduced domain, ...) */
414 int conflictprio, /**< priority value for using conflict weights in lex. order */
415 int cutoffprio /**< priority value for using conflict weights in lex. order */
416 )
417{
418 SCIP_VAR* bestaggrcand;
419 SCIP_Real bestval;
420 SCIP_NODE* downchild;
421 SCIP_NODE* eqchild;
422 SCIP_NODE* upchild;
423 SCIP_VAR** bestcands;
424 int nbestcands;
425 int c;
426
427 assert(ncands > 0);
428 assert(result != NULL);
429
430 *result = SCIP_DIDNOTFIND;
431
432 /* check if conflict score, inferences, and cutoff score should be used in combination; otherwise just use
433 * inference */
434 if( useweightedsum == FALSE )
435 {
436 conflictprio = 0;
437 cutoffprio = 0;
438 conflictweight = 0.0;
439 inferenceweight = 1.0;
440 cutoffweight = 0.0;
441 }
442
443 /* allocate temporary memory */
444 SCIP_CALL( SCIPallocClearBufferArray(scip, &bestcands, ncands) );
445 nbestcands = 0;
446
447 if( conflictprio > cutoffprio )
448 {
449 /* select the best candidates w.r.t. the first criterion */
450 selectBestCands(scip, cands, candsols, ncands, conflictweight, 0.0, 0.0, reliablescore,
451 bestcands, &nbestcands);
452
453 /* select the best candidates w.r.t. the second criterion; we use bestcands and nbestcands as input and
454 * output, so the method must make sure to overwrite the last argument only at the very end */
455 if( nbestcands > 1 )
456 {
457 selectBestCands(scip, bestcands, candsols, nbestcands, 0.0, inferenceweight, cutoffweight, reliablescore,
458 bestcands, &nbestcands);
459 }
460 }
461 else if( conflictprio == cutoffprio )
462 {
463 /* select the best candidates w.r.t. weighted sum of both criteria */
464 selectBestCands(scip, cands, candsols, ncands, conflictweight, inferenceweight, cutoffweight, reliablescore,
465 bestcands, &nbestcands);
466 }
467 else
468 {
469 assert(conflictprio < cutoffprio);
470
471 /* select the best candidates w.r.t. the first criterion */
472 selectBestCands(scip, cands, candsols, ncands, 0.0, inferenceweight, cutoffweight, reliablescore,
473 bestcands, &nbestcands);
474
475 /* select the best candidates w.r.t. the second criterion; we use bestcands and nbestcands as input and
476 * output, so the method must make sure to overwrite the last argument only at the very end */
477 if( nbestcands > 1 )
478 {
479 /* select the best candidates w.r.t. the first criterion */
480 selectBestCands(scip, bestcands, candsols, nbestcands, conflictweight, 0.0, 0.0, reliablescore,
481 bestcands, &nbestcands);
482 }
483 }
484
485 assert(nbestcands == 0 || bestcands[0] != NULL);
486
487 /* final tie breaking */
488 if( nbestcands > 1 )
489 {
490 tiebreakAggrCand(bestcands, nbestcands);
491 nbestcands = 1;
492 }
493
494 assert(nbestcands == 1);
495
496 bestaggrcand = bestcands[0];
497 bestval = -SCIP_INVALID;
498
499 /* loop over cands, find bestcands[0], and store corresponding candsols value in bestval */
500 for( c = 0; c < ncands; ++c )
501 {
502 if( bestaggrcand == cands[c] )
503 {
504 bestval = candsols[c];
505 break;
506 }
507 }
508
509 assert(bestval != -SCIP_INVALID);
510
511 /* free temporary memory */
512 SCIPfreeBufferArray(scip, &bestcands);
513
514 assert(bestaggrcand != NULL);
515
516 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, conflict=%g cutoff=%g, inference=%g)\n",
517 ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand),
518 bestval == SCIP_UNKNOWN ? SCIPgetVarSol(scip, bestaggrcand) : bestval, /*lint !e777*/
519 SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight),
520 SCIPgetVarAvgInferenceScore(scip, bestaggrcand));
521
522 assert(candsols != NULL);
523 /* perform the branching */
524 SCIP_CALL( SCIPbranchVarVal(scip, bestaggrcand, SCIPgetBranchingPoint(scip, bestaggrcand, bestval), &downchild, &eqchild, &upchild) );
525
526 if( downchild != NULL || eqchild != NULL || upchild != NULL )
527 {
528 *result = SCIP_BRANCHED;
529 }
530 else
531 {
532 /* if there are no children, then variable should have been fixed by SCIPbranchVar(Val) */
533 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestaggrcand), SCIPvarGetUbLocal(bestaggrcand)));
534 *result = SCIP_REDUCEDDOM;
535 }
536
537 return SCIP_OKAY;
538}
539
540
541/** selects a variable out of the given candidate array and performs the branching */
542static
544 SCIP* scip, /**< SCIP data structure */
545 SCIP_VAR** cands, /**< candidate array */
546 int ncands, /**< number of candidates */
547 SCIP_Real conflictweight, /**< weight in score calculations for conflict score */
548 SCIP_Real inferenceweight, /**< weight in score calculations for inference score */
549 SCIP_Real cutoffweight, /**< weight in score calculations for cutoff score */
550 SCIP_Real reliablescore, /**< score which is seen to be reliable for a branching decision */
551 SCIP_Bool useweightedsum, /**< should a weighted sum of inference, conflict and cutoff weights be used? */
552 SCIP_RESULT* result /**< buffer to store result (branched, reduced domain, ...) */
553 )
554{
555 SCIP_VAR* bestaggrcand;
556 SCIP_VAR* bestvaluecand;
557 SCIP_Real bestval;
558 SCIP_Real bestaggrscore;
559 SCIP_Real bestvaluescore;
560 SCIP_Real bestbranchpoint;
561 SCIP_BRANCHDIR bestbranchdir;
562 SCIP_NODE* downchild;
563 SCIP_NODE* eqchild;
564 SCIP_NODE* upchild;
565 SCIP_VAR** bestcands;
566 int nbestcands;
567
568 bestbranchpoint = SCIP_UNKNOWN;
569 bestbranchdir = SCIP_BRANCHDIR_DOWNWARDS;
570 bestvaluescore = 0.0;
571 bestvaluecand = NULL;
572
573 assert(ncands > 0);
574 assert(result != NULL);
575
576 *result = SCIP_DIDNOTFIND;
577
578 /* allocate temporary memory */
579 SCIP_CALL( SCIPallocBufferArray(scip, &bestcands, ncands) );
580 nbestcands = 0;
581
582 /* check if the weighted sum between the average inferences and conflict score should be used */
583 if( useweightedsum )
584 {
585 int c;
586
587 bestaggrcand = cands[0];
588 bestvaluecand = cands[0];
589 assert(cands[0] != NULL);
590
591 bestval = SCIP_UNKNOWN;
592
593 /* get domain value score for the first candidate */
594 bestvaluescore = getValueScore(cands[0], conflictweight, cutoffweight, reliablescore, &bestbranchpoint, &bestbranchdir);
595 SCIPdebugMsg(scip, "current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n",
596 SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand),
597 bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS ? "<=" : ">=", bestbranchpoint, bestvaluescore);
598
599 /* get aggregated score for the first candidate */
600 bestaggrscore = getAggrScore(scip, cands[0], conflictweight, inferenceweight, cutoffweight, reliablescore);
601
602 for( c = 1; c < ncands; ++c )
603 {
604 SCIP_VAR* cand;
605 SCIP_Real val;
606 SCIP_Real aggrscore;
607 SCIP_Real branchpoint;
608 SCIP_BRANCHDIR branchdir;
609 SCIP_Real valuescore;
610
611 cand = cands[c];
612 assert(cand != NULL);
613
614 val = SCIP_UNKNOWN;
615
616 /* get domain value score for the candidate */
617 valuescore = getValueScore(cand, conflictweight, cutoffweight, reliablescore, &branchpoint, &branchdir);
618
619 /* evaluate the candidate against the currently best candidate w.r.t. domain value score */
620 evaluateValueCand(cand, valuescore, branchpoint, branchdir, &bestvaluecand, &bestvaluescore, &bestbranchpoint, &bestbranchdir);
621
622 SCIPdebugMsg(scip, "current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n",
623 SCIPvarGetName(bestvaluecand), SCIPvarGetLbLocal(bestvaluecand), SCIPvarGetUbLocal(bestvaluecand),
624 bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS ? "<=" : ">=", bestbranchpoint, bestvaluescore);
625
626 /* get aggregated score for the candidate */
627 aggrscore = getAggrScore(scip, cand, conflictweight, inferenceweight, cutoffweight, reliablescore);
628
629 /*lint -e777*/
630 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
631 val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore);
632
633 /* evaluate the candidate against the currently best candidate w.r.t. aggregated score */
634 evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, &nbestcands);
635 }
636 }
637 else
638 {
639 int c;
640
641 bestaggrcand = cands[0];
642 assert(cands[0] != NULL);
643
644 bestval = SCIP_UNKNOWN;
645
646 bestaggrscore = SCIPgetVarAvgInferenceScore(scip, cands[0]);
647
648 /* search for variable with best score w.r.t. average inferences per branching */
649 for( c = 1; c < ncands; ++c )
650 {
651 SCIP_VAR* cand;
652 SCIP_Real val;
653 SCIP_Real aggrscore;
654
655 cand = cands[c];
656 assert(cand != NULL);
657
658 val = SCIP_UNKNOWN;
659
660 aggrscore = SCIPgetVarAvgInferenceScore(scip, cand);
661
662 /* in case the average inferences score is below the reliable score we set it to zero since it is seen to be
663 * unreliable
664 */
665 if( aggrscore < reliablescore )
666 aggrscore = 0.0;
667
668 SCIPdebugMsg(scip, " -> cand <%s>: prio=%d, solval=%g, score=%g\n", SCIPvarGetName(cand), SCIPvarGetBranchPriority(cand),
669 val == SCIP_UNKNOWN ? SCIPgetVarSol(scip, cand) : val, aggrscore); /*lint !e777*/
670
671 /* evaluate the candidate against the currently best candidate */
672 evaluateAggrCand(scip, cand, aggrscore, val, &bestaggrcand, &bestaggrscore, &bestval, bestcands, &nbestcands);
673 }
674 }
675
676 /* free temporary memory */
677 SCIPfreeBufferArray(scip, &bestcands);
678
679 assert(bestaggrcand != NULL);
680
681 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, score=%g, conflict=%g cutoff=%g, inference=%g)\n",
682 ncands, SCIPvarGetName(bestaggrcand), SCIPvarGetLbLocal (bestaggrcand), SCIPvarGetUbLocal(bestaggrcand), SCIPvarGetBranchPriority(bestaggrcand),
683 bestval == SCIP_UNKNOWN ? SCIPgetVarSol(scip, bestaggrcand) : bestval, bestaggrscore, /*lint !e777*/
684 SCIPgetVarConflictScore(scip, bestaggrcand), SCIPgetVarAvgInferenceCutoffScore(scip, bestaggrcand, cutoffweight),
685 SCIPgetVarAvgInferenceScore(scip, bestaggrcand));
686
687 if( bestbranchpoint == SCIP_UNKNOWN ) /*lint !e777*/
688 {
689 SCIP_CALL( SCIPbranchVar(scip, bestaggrcand, &downchild, &eqchild, &upchild) );
690 }
691 else
692 {
693 /* perform the branching */
694 SCIP_Real estimate;
695 SCIP_Real downprio;
696 SCIP_Real upprio;
697 SCIP_Real downub;
698 SCIP_Real uplb;
699
700 assert(bestvaluecand != NULL);
701
702 downprio = 0.0;
703 upprio = 0.0;
704
705 if( bestbranchdir == SCIP_BRANCHDIR_DOWNWARDS )
706 {
707 downprio = 1.0;
708 downub = bestbranchpoint;
709 uplb = bestbranchpoint + 1.0;
710 }
711 else
712 {
713 upprio = 1.0;
714 downub = bestbranchpoint - 1.0;
715 uplb = bestbranchpoint;
716 }
717
718 /* calculate the child estimate */
719 estimate = SCIPcalcChildEstimate(scip, bestvaluecand, downub);
720
721 /* create down child */
722 SCIP_CALL( SCIPcreateChild(scip, &downchild, downprio, estimate) );
723
724 /* change upper bound in down child */
725 SCIP_CALL( SCIPchgVarUbNode(scip, downchild, bestvaluecand, downub) );
726
727 /* calculate the child estimate */
728 estimate = SCIPcalcChildEstimate(scip, bestvaluecand, uplb);
729
730 /* create up child */
731 SCIP_CALL( SCIPcreateChild(scip, &upchild, upprio, estimate) );
732
733 /* change lower bound in up child */
734 SCIP_CALL( SCIPchgVarLbNode(scip, upchild, bestvaluecand, uplb) );
735
736 SCIPdebugMsg(scip, "branch on variable <%s> and value <%g>\n", SCIPvarGetName(bestvaluecand), bestbranchpoint);
737
738 eqchild = NULL;
739 }
740 if( downchild != NULL || eqchild != NULL || upchild != NULL )
741 {
742 *result = SCIP_BRANCHED;
743 }
744 else
745 {
746 /* if there are no children, then variable should have been fixed by SCIPbranchVar(Val) */
747 assert(SCIPisEQ(scip, SCIPvarGetLbLocal(bestaggrcand), SCIPvarGetUbLocal(bestaggrcand)));
748 *result = SCIP_REDUCEDDOM;
749 }
750
751 return SCIP_OKAY;
752}
753
754/*
755 * Callback methods
756 */
757
758/** copy method for branchrule plugins (called when SCIP copies plugins) */
759static
760SCIP_DECL_BRANCHCOPY(branchCopyInference)
761{ /*lint --e{715}*/
762 assert(scip != NULL);
763 assert(branchrule != NULL);
764 assert(strcmp(SCIPbranchruleGetName(branchrule), BRANCHRULE_NAME) == 0);
765
766 /* call inclusion method of branchrule */
768
769 return SCIP_OKAY;
770}
771
772/** destructor of branching rule to free user data (called when SCIP is exiting) */
773static
774SCIP_DECL_BRANCHFREE(branchFreeInference)
775{ /*lint --e{715}*/
776 SCIP_BRANCHRULEDATA* branchruledata;
777
778 /* free branching rule data */
779 branchruledata = SCIPbranchruleGetData(branchrule);
780 SCIPfreeBlockMemory(scip, &branchruledata);
781 SCIPbranchruleSetData(branchrule, NULL);
782
783 return SCIP_OKAY;
784}
785
786/** branching execution method for fractional LP solutions */
787static
788SCIP_DECL_BRANCHEXECLP(branchExeclpInference)
789{ /*lint --e{715}*/
790 SCIP_BRANCHRULEDATA* branchruledata;
791 SCIP_VAR** cands;
792 int ncands;
793
794 SCIPdebugMsg(scip, "Execlp method of inference branching\n");
795
796 /* get branching rule data */
797 branchruledata = SCIPbranchruleGetData(branchrule);
798 assert(branchruledata != NULL);
799
800 if( branchruledata->fractionals )
801 {
802 /* get LP candidates (fractional integer variables) */
803 SCIP_CALL( SCIPgetLPBranchCands(scip, &cands, NULL, NULL, NULL, &ncands, NULL) );
804 }
805 else
806 {
807 /* get pseudo candidates (non-fixed integer variables) */
808 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, NULL, &ncands) );
809 }
810
811 /* perform the branching */
812 SCIP_CALL( performBranchingNoSol(scip, cands, ncands, branchruledata->conflictweight,
813 branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
814 branchruledata->useweightedsum, result) );
815
816 return SCIP_OKAY;
817}
818
819
820/** branching execution method for external candidates */
821static
822SCIP_DECL_BRANCHEXECEXT(branchExecextInference)
823{ /*lint --e{715}*/
824 SCIP_BRANCHRULEDATA* branchruledata;
825 SCIP_VAR** cands;
826 SCIP_Real* candsols;
827 int ncands;
828
829 SCIPdebugMsg(scip, "Execext method of inference branching\n");
830
831 /* get branching rule data */
832 branchruledata = SCIPbranchruleGetData(branchrule);
833 assert(branchruledata != NULL);
834
835 /* get branching candidates */
836 SCIP_CALL( SCIPgetExternBranchCands(scip, &cands, &candsols, NULL, &ncands, NULL, NULL, NULL, NULL) );
837 assert(ncands > 0);
838
839 /* perform the branching */
840 SCIP_CALL( performBranchingSol(scip, cands, candsols, ncands, branchruledata->conflictweight,
841 branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
842 branchruledata->useweightedsum, result, branchruledata->conflictprio, branchruledata->cutoffprio) );
843
844 return SCIP_OKAY;
845}
846
847/** branching execution method for not completely fixed pseudo solutions */
848static
849SCIP_DECL_BRANCHEXECPS(branchExecpsInference)
850{ /*lint --e{715}*/
851 SCIP_BRANCHRULEDATA* branchruledata;
852 SCIP_VAR** cands;
853 int ncands;
854
855 SCIPdebugMsg(scip, "Execps method of inference branching\n");
856
857 /* get branching rule data */
858 branchruledata = SCIPbranchruleGetData(branchrule);
859 assert(branchruledata != NULL);
860
861 /* get pseudo candidates (non-fixed integer variables) */
862 SCIP_CALL( SCIPgetPseudoBranchCands(scip, &cands, NULL, &ncands) );
863
864 /* perform the branching */
865 SCIP_CALL( performBranchingNoSol(scip, cands, ncands, branchruledata->conflictweight,
866 branchruledata->inferenceweight, branchruledata->cutoffweight, branchruledata->reliablescore,
867 branchruledata->useweightedsum, result) );
868
869 return SCIP_OKAY;
870}
871
872
873/*
874 * branching specific interface methods
875 */
876
877/** creates the inference history branching rule and includes it in SCIP */
879 SCIP* scip /**< SCIP data structure */
880 )
881{
882 SCIP_BRANCHRULEDATA* branchruledata;
883 SCIP_BRANCHRULE* branchrule;
884
885 /* create inference branching rule data */
886 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
887
888 /* include branching rule */
891
892 assert(branchrule != NULL);
893
894 /* set non-fundamental callbacks via specific setter functions*/
895 SCIP_CALL( SCIPsetBranchruleCopy(scip, branchrule, branchCopyInference) );
896 SCIP_CALL( SCIPsetBranchruleFree(scip, branchrule, branchFreeInference) );
897 SCIP_CALL( SCIPsetBranchruleExecLp(scip, branchrule, branchExeclpInference) );
898 SCIP_CALL( SCIPsetBranchruleExecExt(scip, branchrule, branchExecextInference) );
899 SCIP_CALL( SCIPsetBranchruleExecPs(scip, branchrule, branchExecpsInference) );
900
901 /* inference branching rule parameters */
903 "branching/inference/conflictweight",
904 "weight in score calculations for conflict score",
905 &branchruledata->conflictweight, TRUE, DEFAULT_CONFLICTWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
907 "branching/inference/inferenceweight",
908 "weight in score calculations for inference score",
909 &branchruledata->inferenceweight, TRUE, DEFAULT_INFERENCEWEIGHT, SCIP_REAL_MIN, SCIP_REAL_MAX, NULL, NULL) );
911 "branching/inference/cutoffweight",
912 "weight in score calculations for cutoff score",
913 &branchruledata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
915 "branching/inference/fractionals",
916 "should branching on LP solution be restricted to the fractional variables?",
917 &branchruledata->fractionals, TRUE, DEFAULT_FRACTIONALS, NULL, NULL) );
919 "branching/inference/useweightedsum",
920 "should a weighted sum of inference, conflict and cutoff weights be used?",
921 &branchruledata->useweightedsum, FALSE, DEFAULT_USEWEIGHTEDSUM, NULL, NULL) );
922 /* inference branching rule parameters */
924 "branching/inference/reliablescore",
925 "weight in score calculations for conflict score",
926 &branchruledata->reliablescore, TRUE, DEFAULT_RELIABLESCORE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
927 /* parameters for lexicographical ordering */
929 "branching/inference/conflictprio",
930 "priority value for using conflict weights in lex. order",
931 &branchruledata->conflictprio, FALSE, DEFAULT_CONFLICTPRIO, 0, INT_MAX, NULL, NULL) );
933 "branching/inference/cutoffprio",
934 "priority value for using cutoff weights in lex. order",
935 &branchruledata->cutoffprio, FALSE, DEFAULT_CUTOFFPRIO, 0, INT_MAX, NULL, NULL) );
936
937 return SCIP_OKAY;
938}
#define BRANCHRULE_DESC
static void evaluateAggrCand(SCIP *scip, SCIP_VAR *cand, SCIP_Real score, SCIP_Real val, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestval, SCIP_VAR **bestcands, int *nbestcands)
static SCIP_DECL_BRANCHCOPY(branchCopyInference)
static SCIP_DECL_BRANCHEXECPS(branchExecpsInference)
static void tiebreakAggrCand(SCIP_VAR **bestcands, int nbestcands)
static SCIP_RETCODE performBranchingSol(SCIP *scip, SCIP_VAR **cands, SCIP_Real *candsols, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Bool useweightedsum, SCIP_RESULT *result, int conflictprio, int cutoffprio)
#define BRANCHRULE_PRIORITY
static void evaluateValueCand(SCIP_VAR *cand, SCIP_Real score, SCIP_Real branchpoint, SCIP_BRANCHDIR branchdir, SCIP_VAR **bestcand, SCIP_Real *bestscore, SCIP_Real *bestbranchpoint, SCIP_BRANCHDIR *bestbranchdir)
#define DEFAULT_CONFLICTPRIO
static void selectBestCands(SCIP *scip, SCIP_VAR **cands, SCIP_Real *candsols, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_VAR **bestcands, int *nbestcands)
#define DEFAULT_INFERENCEWEIGHT
#define BRANCHRULE_NAME
static SCIP_Real getAggrScore(SCIP *scip, SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore)
#define DEFAULT_USEWEIGHTEDSUM
#define DEFAULT_CONFLICTWEIGHT
static void checkValueScore(SCIP_Real value, SCIP_HISTORY *history, SCIP_BRANCHDIR dir, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *bestscore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
#define DEFAULT_FRACTIONALS
#define DEFAULT_CUTOFFWEIGHT
static SCIP_Real getValueScore(SCIP_VAR *var, SCIP_Real conflictweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Real *branchpoint, SCIP_BRANCHDIR *branchdir)
static SCIP_DECL_BRANCHEXECLP(branchExeclpInference)
#define DEFAULT_RELIABLESCORE
static SCIP_DECL_BRANCHFREE(branchFreeInference)
static SCIP_RETCODE performBranchingNoSol(SCIP *scip, SCIP_VAR **cands, int ncands, SCIP_Real conflictweight, SCIP_Real inferenceweight, SCIP_Real cutoffweight, SCIP_Real reliablescore, SCIP_Bool useweightedsum, SCIP_RESULT *result)
static SCIP_DECL_BRANCHEXECEXT(branchExecextInference)
#define DEFAULT_CUTOFFPRIO
#define BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXBOUNDDIST
inference history branching rule
#define NULL
Definition: def.h:267
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define SCIP_UNKNOWN
Definition: def.h:194
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_REAL_MIN
Definition: def.h:175
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPincludeBranchruleInference(SCIP *scip)
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECEXT((*branchexecext)))
Definition: scip_branch.c:265
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:116
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
Definition: scip_branch.c:511
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
Definition: scip_branch.c:897
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:947
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1126
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1050
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
Definition: scip_branch.c:733
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1017
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPgetVarAvgInferenceScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9473
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4890
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17758
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPgetVarSol(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:2307
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
int SCIPvarGetBranchPriority(SCIP_VAR *var)
Definition: var.c:18250
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:9241
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4846
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
Definition: scip_var.c:9790
SCIP_VALUEHISTORY * SCIPvarGetValuehistory(SCIP_VAR *var)
Definition: var.c:18520
int SCIPvaluehistoryGetNValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:363
SCIP_HISTORY ** SCIPvaluehistoryGetHistories(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:373
SCIP_Real * SCIPvaluehistoryGetValues(SCIP_VALUEHISTORY *valuehistory)
Definition: history.c:383
SCIP_Real SCIPhistoryGetCutoffSum(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:678
SCIP_Real SCIPhistoryGetVSIDS(SCIP_HISTORY *history, SCIP_BRANCHDIR dir)
Definition: history.c:536
public methods for branching rules
public methods for branching and inference history structure
public methods for message output
public methods for problem variables
public methods for branching rule plugins and branching
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for SCIP variables
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition: type_branch.h:57
@ SCIP_BRANCHDIR_DOWNWARDS
Definition: type_history.h:43
@ SCIP_BRANCHDIR_UPWARDS
Definition: type_history.h:44
enum SCIP_BranchDir SCIP_BRANCHDIR
Definition: type_history.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_BRANCHED
Definition: type_result.h:54
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63