SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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;
113 }
114 else if( (*bestscore) == score ) /*lint !e777*/
115 {
116 SCIP_Real bestobj;
117 SCIP_Real candobj;
118
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;
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*/
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
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
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
263SCIP_Real getAggrScore(
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
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{
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 */
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{
419 SCIP_Real bestval;
424 int nbestcands;
425 int c;
426
427 assert(ncands > 0);
428 assert(result != NULL);
429
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 */
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,
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,
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,
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,
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,
482 }
483 }
484
485 assert(nbestcands == 0 || bestcands[0] != NULL);
486
487 /* final tie breaking */
488 if( nbestcands > 1 )
489 {
491 nbestcands = 1;
492 }
493
494 assert(nbestcands == 1);
495
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
510
511 /* free temporary memory */
513
515
516 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, conflict=%g cutoff=%g, inference=%g)\n",
521
522 assert(candsols != NULL);
523 /* perform the branching */
525
526 if( downchild != NULL || eqchild != NULL || upchild != NULL )
527 {
529 }
530 else
531 {
532 /* if there are no children, then variable should have been fixed by SCIPbranchVar(Val) */
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{
557 SCIP_Real bestval;
558 SCIP_Real bestaggrscore;
559 SCIP_Real bestvaluescore;
560 SCIP_Real bestbranchpoint;
566 int nbestcands;
567
570 bestvaluescore = 0.0;
572
573 assert(ncands > 0);
574 assert(result != NULL);
575
577
578 /* allocate temporary memory */
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
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",
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;
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 */
621
622 SCIPdebugMsg(scip, "current best value candidate <%s>[%g,%g] %s <%g> (value %g)\n",
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 */
635 }
636 }
637 else
638 {
639 int c;
640
641 bestaggrcand = cands[0];
642 assert(cands[0] != NULL);
643
645
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
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 */
673 }
674 }
675
676 /* free temporary memory */
678
680
681 SCIPdebugMsg(scip, " -> %d candidates, selected variable <%s>[%g,%g] (prio=%d, solval=%.12f, score=%g, conflict=%g cutoff=%g, inference=%g)\n",
686
687 if( bestbranchpoint == SCIP_UNKNOWN ) /*lint !e777*/
688 {
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
701
702 downprio = 0.0;
703 upprio = 0.0;
704
706 {
707 downprio = 1.0;
709 uplb = bestbranchpoint + 1.0;
710 }
711 else
712 {
713 upprio = 1.0;
714 downub = bestbranchpoint - 1.0;
716 }
717
718 /* calculate the child estimate */
720
721 /* create down child */
723
724 /* change upper bound in down child */
726
727 /* calculate the child estimate */
729
730 /* create up child */
732
733 /* change lower bound in up child */
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 {
743 }
744 else
745 {
746 /* if there are no children, then variable should have been fixed by SCIPbranchVar(Val) */
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
761{ /*lint --e{715}*/
762 assert(scip != NULL);
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
775{ /*lint --e{715}*/
776 SCIP_BRANCHRULEDATA* branchruledata;
777
778 /* free branching rule data */
779 branchruledata = SCIPbranchruleGetData(branchrule);
780 SCIPfreeBlockMemory(scip, &branchruledata);
782
783 return SCIP_OKAY;
784}
785
786/** branching execution method for fractional LP solutions */
787static
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
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 */
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
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;
884
885 /* create inference branching rule data */
886 SCIP_CALL( SCIPallocBlockMemory(scip, &branchruledata) );
887
888 /* include branching rule */
891
893
894 /* set non-fundamental callbacks via specific setter functions*/
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 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)
#define DEFAULT_RELIABLESCORE
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)
#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_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
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 SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition branch.c:1849
SCIP_RETCODE SCIPsetBranchruleExecExt(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition branch.c:1859
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPgetExternBranchCands(SCIP *scip, SCIP_VAR ***externcands, SCIP_Real **externcandssol, SCIP_Real **externcandsscore, int *nexterncands, int *nprioexterncands, int *nprioexternbins, int *nprioexternints, int *nprioexternimpls)
SCIP_Real SCIPgetBranchingPoint(SCIP *scip, SCIP_VAR *var, SCIP_Real suggestion)
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
SCIP_RETCODE SCIPbranchVarVal(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
SCIP_RETCODE SCIPgetPseudoBranchCands(SCIP *scip, SCIP_VAR ***pseudocands, int *npseudocands, int *npriopseudocands)
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
#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:9475
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:4892
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:2309
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:9243
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4848
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
Definition scip_var.c:9792
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
return SCIP_OKAY
int c
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_VAR * var
int bestcand
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
#define SCIP_DECL_BRANCHEXECPS(x)
#define SCIP_DECL_BRANCHEXECLP(x)
#define SCIP_DECL_BRANCHEXECEXT(x)
#define SCIP_DECL_BRANCHCOPY(x)
Definition type_branch.h:67
#define SCIP_DECL_BRANCHFREE(x)
Definition type_branch.h:75
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
Definition type_branch.h:57
@ SCIP_BRANCHDIR_DOWNWARDS
@ SCIP_BRANCHDIR_UPWARDS
enum SCIP_BranchDir SCIP_BRANCHDIR
@ 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
enum SCIP_Retcode SCIP_RETCODE