forked from Gecode/MPG
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathm-branch.tex.in
executable file
·1822 lines (1611 loc) · 69.7 KB
/
m-branch.tex.in
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
% -*- mode: LaTeX; -*-
\chapter{Branching}
\label{chap:m:branch}
This chapter discusses how \emph{branching} is used for solving Gecode
models. Branching defines the shape of the search
tree. Exploration defines a strategy how to explore parts of the
search tree and is discussed in \autoref{chap:m:search}.
\paragraph{Overview.}
\mbox{}\autoref{sec:m:branch:basics} explains the basics of
Gecode's predefined branchings. An overview of available
branchings for integer and Boolean variables is provided in
\autoref{sec:m:branch:int}, for set variables in
\autoref{sec:m:branch:set}, and for float variables in
\autoref{sec:m:branch:float}. These sections belong to the basic
reading material of \autoref{part:m}.
Advanced topics for branchings are discussed in the remaining
sections: local versus shared variable selection
\ptsmbranchshared, random selection \ptsmbranchrnd, user-defined
variable \ptsmbranchuservar{} and value \ptsmbranchuserval{}
selection, tie-breaking \ptsmbranchtie, dynamic symmetry breaking \ptsmbranchsym, branch filter functions
\ptsmbranchfilter, variable-value print functions
\ptsmbranchprint, assigning variables \ptsmbranchassign, and
executing code between branchers \ptsmbranchcode.
\begin{convention}
Note that the same conventions hold as in \autoref{chap:m:int}.
\end{convention}
\section{Branching basics}
\label{sec:m:branch:basics}
Gecode offers predefined \emph{variable-value branching}: when
calling \?branch()? to post a branching, the third argument defines
which variable is selected for branching, whereas the fourth
argument defines which values are selected for branching.
For example, for an array of integer or Boolean variables \?x?
the following call to branch
\begin{code}
branch(home, x, INT_VAR_MIN_MIN(), INT_VAL_SPLIT_MIN());
\end{code}
selects a variable $y$ with the smallest minimum value (in case
of ties, the first such variable in \?x? is selected) and creates
a choice with two alternatives $y\leq n$ and $y>n$ where
$$n=\left\lfloor\frac{\min(y)+\max(y)}{2}\right\rfloor$$
The posted brancher assigns all
variables and then ceases to exist. If more branchers exist,
search continues with the next brancher. Search \emph{commits} a
brancher to alternatives during search.
The \?branch()? function also accepts a branch filter function
and a variable-value print function as optional arguments, see
\autoref{sec:m:branch:filter} and \autoref{sec:m:branch:print}
for details.
\paragraph{Several branchers.}
A space in Gecode can have \emph{several} branchers posted on
behalf of a \emph{branching} that are
executed in order of creation. Assume that in
\begin{code}
branch(home, x, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
...
branch(home, y, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
\end{code}
both calls to \?branch()? create a brancher. Search branches first
on the variables \?x? and then on the variables \?y?. Here, it
does not matter whether propagators are created in between the
creation of branchers.
\paragraph{Branching on single variables.}
In addition to branching on an array of variables, Gecode also
supports branching on a single variable.
For example, if \?x? is an integer variable of type \?IntVar?,
then
\begin{code}
branch(home, x, INT_VAL_MIN());
\end{code}
branches on the single variable \?x? by first trying the smallest
value of \?x?.
Assume that \?x? is an array of integer variables. Then the
following code
\begin{code}
for (int i=0; i<x.size(); i++)
branch(home, x[i], INT_VAL_MIN());
\end{code}
is equivalent, albeit considerably less efficient, to
\begin{code}
branch(home, x, INT_VAR_NONE(), INT_VAL_MIN());
\end{code}
\paragraph{Brancher groups.}
Branchers can be controlled by brancher groups, they are
discussed in detail in \autoref{sec:m:group:branch}.
\section{Branching on integer and Boolean variables}
\label{sec:m:branch:int}
\begin{important}
\begin{samepage}
Do not forget to add
\begin{code}
#include <gecode/int.hh>
\end{code}
\end{samepage}
to your program when you want to branch on integer and
Boolean variables.
\end{important}
\begin{figure}
\begin{center}
\begin{tabular}{l@{\quad}l}
\?INT_VAR_NONE()? & first unassigned\\
\?INT_VAR_RND(r)? & randomly\\
\?INT_VAR_MERIT_MIN(m,?\OptArg{\?t?}\?)? & smallest value of merit function \?m?\\
\?INT_VAR_MERIT_MAX(m,?\OptArg{\?t?}\?)? & largest value of merit function \?m?\\
\?INT_VAR_DEGREE_MIN(?\OptArg{\?t?}\?)? & smallest degree\\
\?INT_VAR_DEGREE_MAX(?\OptArg{\?t?}\?)? & largest degree\\
\?INT_VAR_AFC_MIN(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & smallest accumulated failure count (AFC)\\
\?INT_VAR_AFC_MAX(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & largest accumulated failure count (AFC)\\
\?INT_VAR_ACTION_MIN(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & lowest action\\
\?INT_VAR_ACTION_MAX(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & highest action\\
\?INT_VAR_CHB_MIN(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? &
lowest chb Q-score\\
\?INT_VAR_CHB_MAX(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? &
highest chb Q-score\\
\?INT_VAR_MIN_MIN(?\OptArg{\?t?}\?)? & smallest minimum value\\
\?INT_VAR_MIN_MAX(?\OptArg{\?t?}\?)? & largest minimum value\\
\?INT_VAR_MAX_MIN(?\OptArg{\?t?}\?)? & smallest maximum value\\
\?INT_VAR_MAX_MAX(?\OptArg{\?t?}\?)? & largest maximum value\\
\?INT_VAR_SIZE_MIN(?\OptArg{\?t?}\?)? & smallest domain size\\
\?INT_VAR_SIZE_MAX(?\OptArg{\?t?}\?)? & largest domain size\\
\?INT_VAR_DEGREE_SIZE_MIN(?\OptArg{\?t?}\?)? & smallest degree
divided by domain size\\
\?INT_VAR_DEGREE_SIZE_MAX(?\OptArg{\?t?}\?)? & largest degree by domain size\\
\?INT_VAR_AFC_SIZE_MIN(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & smallest AFC by domain size\\
\?INT_VAR_AFC_SIZE_MAX(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & largest AFC by domain size\\
\?INT_VAR_ACTION_SIZE_MIN(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & smallest
action by domain size\\
\?INT_VAR_ACTION_SIZE_MAX(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & largest
action by domain size\\
\?INT_VAR_CHB_SIZE_MIN(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? & smallest
chb by domain size\\
\?INT_VAR_CHB_SIZE_MAX(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? & largest
chb by domain size\\
\?INT_VAR_REGRET_MIN_MIN(?\OptArg{\?t?}\?)? & smallest minimum-regret\\
\?INT_VAR_REGRET_MIN_MAX(?\OptArg{\?t?}\?)? & largest minimum-regret\\
\?INT_VAR_REGRET_MAX_MIN(?\OptArg{\?t?}\?)? & smallest maximum-regret\\
\?INT_VAR_REGRET_MAX_MAX(?\OptArg{\?t?}\?)? & largest
maximum-regret\\
\end{tabular}
\end{center}
\caption{Integer variable selection}
\label{fig:m:branch:int:var:int}
\end{figure}
\paragraph{Branching on integer variables.}
For integer variables, variable selection is defined
by a value of class \gecoderef[class]{IntVarBranch} and value
selection is defined by a value of type
\gecoderef[class]{IntValBranch}. Values of these types are
obtained by calling functions (possibly taking arguments) that
correspond to variable and value selection strategies. For
example, a call \?INT_VAR_SIZE_MIN()? returns an object of class
\gecoderef[class]{IntVarBranch}.
For an overview of the available variable selection strategies,
see \autoref{fig:m:branch:int:var:int} (see also
\gecoderef[group]{TaskModelIntBranchVar}) where \OptArg{$\cdot$}~denotes an optional argument and~\SpecialArg{$\cdot$} is a
special argument to be explained below. Here, an argument \?r?
refers to a random number generator of type
\gecoderef[class]{Rnd}. Using random number generators for
branching is discussed in \autoref{sec:m:branch:rnd}. An
argument \?m? refers to a user-defined merit function of type
\gecoderef[typedef]{IntBranchMerit} for integer variables and
\gecoderef[typedef]{BoolBranchMerit} for Boolean variables.
User-defined merit functions are discussed in
\autoref{sec:m:branch:uservar}. An argument \?afc?
refers to accumulated failure count (AFC) information for integer
variables (of class \gecoderef[class]{IntAFC}). An
argument \?act? refers to action information for integer variables (of class \gecoderef[class]{IntAction}). An
argument \?chb? refers to CHB information for integer variables (of class \gecoderef[class]{IntCHB}). For
a discussion of AFC, action, and CHB, see
\autoref{sec:m:branch:shared}. Both \SpecialArg{\?afc?}
and \SpecialArg{\?act?} can also be optional arguments of type
\?double? defining a decay-factor, whereas the argument
\SpecialArg{\?chb?} can be omitted. The optional argument \?t?
refers to a tie-breaking limit function of type
\gecoderef[typedef]{BranchTbl} and is discussed in
\autoref{sec:m:branch:tbl}.
Omitting the variable selection strategy is equivalent to using
\?INT_VAR_NONE()?.
\begin{figure}
\begin{center}
\begin{tabular}{l@{\quad}l}
\?INT_VAL_RND(r)? & random value\\
\?INT_VAL(v,?\OptArg{\?c?}\?)? & defined by value function \?v? and commit
function \?c?\\
\?INT_VAL_MIN()? & smallest value\\
\?INT_VAL_MED()? & greatest value not greater than the median\\
\?INT_VAL_MAX()? & largest value\\
\?INT_VAL_SPLIT_MIN()? & values not greater than mean of smallest
and largest value\\
\?INT_VAL_SPLIT_MAX()? & values greater than mean of smallest
and largest value\\
\?INT_VAL_RANGE_MIN()? & values from smallest range, if domain has
several ranges;\\
& otherwise, values not greater than mean\\
\?INT_VAL_RANGE_MAX()? & values from largest range, if domain has
several ranges;\\
& otherwise, values greater than mean\\
\?INT_VALUES_MIN()? & all values starting from smallest\\
\?INT_VALUES_MAX()? & all values starting from largest\\
\end{tabular}
\end{center}
\caption{Integer value selection}
\label{fig:m:branch:int:val:int}
\end{figure}
An overview of the available value selection strategies for
integer variables can be found in
\autoref{fig:m:branch:int:val:int} (see also
\gecoderef[group]{TaskModelIntBranchVal}) where \OptArg{$\cdot$}~denotes
an optional argument. Here, an argument \?r? refers to
a random number generator of type \gecoderef[class]{Rnd} which is
discussed in \autoref{sec:m:branch:rnd}. An argument \?v?
refers to a value selection function of type
\gecoderef[typedef]{IntBranchVal}. An
optional argument \?c? refers to a commit function of type
\gecoderef[typedef]{IntBranchCommit}.
Value and commit functions are discussed in
\autoref{sec:m:branch:userval}.
Note that variable-value branchers are just common cases for
branching based on the idea of selecting variables and values. In
Gecode also arbitrary other branchers can be programmed, see
\autoref{part:b}.
\tip{Variables are re-selected during branching}{
\label{tip:m:branch:reselected}
A variable-value branching selects a variable for each choice
it creates. Consider as an example a script using an integer
variable array \?x? with three variables and domains
$\range{1}{4}$ created by
\begin{code}
IntVarArray x(home, 3, 1, 4);
\end{code}
\begin{samepage}
Let us assume that no constraints are posted on the variables in
\?x? and that a branching is posted by
\begin{code}
branch(home, x, INT_VAR_SIZE_MAX(), INT_VAL_SPLIT_MIN());
\end{code}
\end{samepage}
The branching starts by selecting \?x[0]? as the first variable with the
largest domain in the array \?x? and creates the choice
$$
(\mbox{\?x[0]?}\leq 2)\vee
(\mbox{\?x[0]?}> 2)
$$
Now assume that search explores the first alternative which
results in the domain $\{1,2\}$ for \?x[0]?. When search continues,
the branching again selects the first variable with a largest
domain: hence \?x[1]? is selected and \emph{not} \?x[0]?.
In other words, a variable-value branching does not stick to a
selected variable until the variable becomes assigned. Instead, a
variable-value branching re-selects a variable for each choice it
creates. }
\tip{Do not try all values}{%
Note that for \?INT_VALUES_MIN()? and \?INT_VALUES_MAX()?, a
variable-value branching creates a choice for each selected
variable with one alternative per value of the variable.
This is typically a poor choice, as none of the alternatives
can benefit from propagation that arises when other values of
the same variable are tried. These branchings exist for
instructional purposes (well, they do create beautiful trees in
Gist). }
\paragraph{Branching on Boolean variables.}
\begin{figure}
\begin{center}
\begin{tabular}{l@{\quad}l}
\?BOOL_VAR_NONE()? & first unassigned\\
\?BOOL_VAR_RND(r)? & randomly\\
\?BOOL_VAR_MERIT_MIN(m,?\OptArg{\?t?}\?)? & smallest value of merit function \?m?\\
\?BOOL_VAR_MERIT_MAX(m,?\OptArg{\?t?}\?)? & largest value of merit function \?m?\\
\?BOOL_VAR_DEGREE_MIN(?\OptArg{\?t?}\?)? & smallest degree\\
\?BOOL_VAR_DEGREE_MAX(?\OptArg{\?t?}\?)? & largest degree\\
\?BOOL_VAR_AFC_MIN(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & smallest accumulated failure count (AFC)\\
\?BOOL_VAR_AFC_MAX(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & largest accumulated failure count (AFC)\\
\?BOOL_VAR_ACTION_MIN(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & lowest action\\
\?BOOL_VAR_ACTION_MAX(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & highest action\\
\?BOOL_VAR_CHB_MIN(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? &
lowest CHB Q-score\\
\?BOOL_VAR_CHB_MAX(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? &
highest CHB Q-score\\
\end{tabular}
\end{center}
\caption{Boolean variable selection}
\label{fig:m:branch:int:var:bool}
\end{figure}
Similar to integer variables, variable selection for Boolean
variables is defined
by a value of class \gecoderef[class]{BoolVarBranch} and value
selection is defined by a value of type
\gecoderef[class]{BoolValBranch}. Values of these types are
obtained by calling functions (possibly taking arguments) that
correspond to variable and value selection strategies.
For an overview of the available variable selection strategies,
see \autoref{fig:m:branch:int:var:bool} (see also
\gecoderef[group]{TaskModelIntBranchVar}) where
\OptArg{$\cdot$}~denotes an optional argument
and~\SpecialArg{$\cdot$} is a special argument to be explained
below. Here, an argument \?r? refers to a random number
generator of type \gecoderef[class]{Rnd}. An argument \?m? refers
to a user-defined merit function of type
\gecoderef[typedef]{BoolBranchMerit}. An argument \?afc? refers
to accumulated failure count (AFC) information for Boolean
variables (of class \gecoderef[class]{BoolAFC}). An argument
\?act? refers to action information for Boolean variables (of
class \gecoderef[class]{BoolAction}). An argument
\?chb? refers to CHB information for Boolean variables (of
class \gecoderef[class]{BoolCHB}). The optional argument
\?t? refers to a tie-breaking limit function of type
\gecoderef[typedef]{BranchTbl}.
Omitting the variable selection strategy is equivalent to using
\?BOOL_VAR_NONE()?.
\begin{figure}
\begin{center}
\begin{tabular}{l@{\quad}l}
\?BOOL_VAL_RND(r)? & random value\\
\?BOOL_VAL(v,?\OptArg{\?c?}\?)? & defined by value function \?v? and commit
function \?c?\\
\?BOOL_VAL_MIN()? & smallest value\\
\?BOOL_VAL_MAX()? & largest value\\
\end{tabular}
\end{center}
\caption{Boolean value selection}
\label{fig:m:branch:int:val:bool}
\end{figure}
An overview of the available value selection strategies for
Boolean variables can be found in
\autoref{fig:m:branch:int:val:bool} (see also
\gecoderef[group]{TaskModelIntBranchVal}) where
\OptArg{$\cdot$}~denotes an optional argument. Here, an argument
\?r? refers to a random number generator of type
\gecoderef[class]{Rnd}. An argument \?v? refers to a value
selection function of type \gecoderef[typedef]{BoolBranchVal}. An
optional argument \?c? refers to a commit function of type
\gecoderef[typedef]{BoolBranchCommit}.
\section{Branching on set variables}
\label{sec:m:branch:set}
\begin{important}
Do not forget to add
\begin{code}
#include <gecode/set.hh>
\end{code}
to your program when you want to branch on set variables.
\end{important}
\begin{figure}
\begin{center}
\begin{tabular}{l@{\quad}l}
\?SET_VAR_NONE()? & first unassigned\\
\?SET_VAR_RND(r)? & randomly\\
\?SET_VAR_MERIT_MIN(m,?\OptArg{\?t?}\?)? & smallest value of merit function \?m?\\
\?SET_VAR_MERIT_MAX(m,?\OptArg{\?t?}\?)? & largest value of merit function \?m?\\
\?SET_VAR_DEGREE_MIN(?\OptArg{\?t?}\?)? & smallest degree\\
\?SET_VAR_DEGREE_MAX(?\OptArg{\?t?}\?)? & largest degree\\
\?SET_VAR_AFC_MIN(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & smallest accumulated failure count (AFC)\\
\?SET_VAR_AFC_MAX(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & largest accumulated failure count (AFC)\\
\?SET_VAR_ACTION_MIN(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & lowest action\\
\?SET_VAR_ACTION_MAX(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & highest action\\
\?SET_VAR_CHB_MIN(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? &
lowest CHB Q-score\\
\?SET_VAR_CHB_MAX(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? &
highest CHB Q-score\\
\?SET_VAR_MIN_MIN(?\OptArg{\?t?}\?)? & smallest minimum unknown element\\
\?SET_VAR_MIN_MAX(?\OptArg{\?t?}\?)? & largest minimum unknown element\\
\?SET_VAR_MAX_MIN(?\OptArg{\?t?}\?)? & smallest maximum unknown element\\
\?SET_VAR_MAX_MAX(?\OptArg{\?t?}\?)? & largest maximum unknown element\\
\?SET_VAR_SIZE_MIN(?\OptArg{\?t?}\?)? & smallest unknown set\\
\?SET_VAR_SIZE_MAX(?\OptArg{\?t?}\?)? & largest unknown set\\
\?SET_VAR_DEGREE_SIZE_MIN(?\OptArg{\?t?}\?)? & smallest degree divided by domain size\\
\?SET_VAR_DEGREE_SIZE_MAX(?\OptArg{\?t?}\?)? & largest degree divided by domain size\\
\?SET_VAR_AFC_SIZE_MIN(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & smallest AFC divided by domain size\\
\?SET_VAR_AFC_SIZE_MAX(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & largest AFC divided by domain size\\
\?SET_VAR_ACTION_SIZE_MIN(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & smallest action divided by domain size\\
\?SET_VAR_ACTION_SIZE_MAX(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & largest action divided by domain size\\
\?SET_VAR_CHB_SIZE_MIN(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? & smallest CHB divided by domain size\\
\?SET_VAR_CHB_SIZE_MAX(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? & largest CHB divided by domain size\\
\end{tabular}
\end{center}
\caption{Set variable selection}
\label{fig:m:branch:set:var}
\end{figure}
For set variables, variable selection is defined
by a value of class \gecoderef[class]{SetVarBranch} (see also
\gecoderef[group]{TaskModelSetBranchVar}) and value selection is defined
by a value of type \gecoderef[class]{SetValBranch} (see also
\gecoderef[group]{TaskModelSetBranchVal}).
For an overview of the available variable selection strategies,
see \autoref{fig:m:branch:set:var} (see also
\gecoderef[group]{TaskModelSetBranchVar}) where
\OptArg{$\cdot$}~denotes an optional argument
and~\SpecialArg{$\cdot$} is a special argument to be explained
below. Here, an argument \?r? refers to a random number
generator of type \gecoderef[class]{Rnd}. Using random number
generators for branching is discussed in
\autoref{sec:m:branch:rnd}. An argument \?m? refers to a
user-defined merit function of type
\gecoderef[typedef]{SetBranchMerit}. User-defined merit
functions are discussed in
\autoref{sec:m:branch:uservar}. An argument \?afc?
refers to accumulated failure count (AFC) information for set
variables (of class \gecoderef[class]{SetAFC}). An argument
\?act? refers to action information for set variables (of class
\gecoderef[class]{SetAction}). An argument
\?chb? refers to CHB information for set variables (of class
\gecoderef[class]{SetCHB}). For a discussion of AFC,
action, and CHB, see \autoref{sec:m:branch:shared}. Both
\SpecialArg{\?afc?} and \SpecialArg{\?act?} can also be optional
arguments of type \?double? defining a decay-factor. The argument
\SpecialArg{?chb?} can be omitted. The optional
argument \?t? refers to a tie-breaking limit function of type
\gecoderef[typedef]{BranchTbl} and is discussed in
\autoref{sec:m:branch:tbl}.
Omitting the variable selection strategy is equivalent to using
\?SET_VAR_NONE()?.
\begin{figure}
\begin{center}
\begin{tabular}{l@{\quad}l}
\?SET_VAL_RND_INC(r)? &include random element\\
\?SET_VAL_RND_EXC(r)? &exclude random element\\
\?SET_VAL(v,?\OptArg{\?c?}\?)? & defined by value function \?v? and commit
function \?c?\\
\?SET_VAL_MIN_INC()? &include smallest element\\
\?SET_VAL_MIN_EXC()? &exclude smallest element\\
\?SET_VAL_MED_INC()? &include median element (rounding downwards)\\
\?SET_VAL_MED_EXC()? &exclude median element (rounding downwards)\\
\?SET_VAL_MAX_INC()? &include largest element\\
\?SET_VAL_MAX_EXC()? &exclude largest element\\
\end{tabular}
\end{center}
\caption{Set value selection}
\label{fig:m:branch:set:val}
\end{figure}
An overview of the available value selection strategies for set
variables can be found in \autoref{fig:m:branch:set:val} where
\OptArg{$\cdot$}~denotes an optional argument. Here, an argument
\?r? refers to a random number generator of type
\gecoderef[class]{Rnd} which is discussed in
\autoref{sec:m:branch:rnd}. An argument \?v? refers to a
value selection function of type
\gecoderef[typedef]{SetBranchVal}. An optional argument \?c?
refers to a commit function of type
\gecoderef[typedef]{SetBranchCommit}. Value and commit function
are discussed in \autoref{sec:m:branch:userval}.
\section{Branching on float variables}
\label{sec:m:branch:float}
\begin{important}
Do not forget to add
\begin{code}
#include <gecode/float.hh>
\end{code}
to your program when you want to branch on float variables.
\end{important}
\begin{figure}
\begin{center}
\begin{tabular}{l@{\quad}l}
\?FLOAT_VAR_NONE()? & first unassigned\\
\?FLOAT_VAR_RND(r)? & randomly\\
\?FLOAT_VAR_MERIT_MIN(m,?\OptArg{\?t?}\?)? & smallest value of merit function \?m?\\
\?FLOAT_VAR_MERIT_MAX(m,?\OptArg{\?t?}\?)? & largest value of merit function \?m?\\
\?FLOAT_VAR_DEGREE_MIN(?\OptArg{\?t?}\?)? & smallest degree\\
\?FLOAT_VAR_DEGREE_MAX(?\OptArg{\?t?}\?)? & largest degree\\
\?FLOAT_VAR_AFC_MIN(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & smallest accumulated failure count (AFC)\\
\?FLOAT_VAR_AFC_MAX(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & largest accumulated failure count (AFC)\\
\?FLOAT_VAR_ACTION_MIN(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & lowest action\\
\?FLOAT_VAR_ACTION_MAX(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & highest action\\
\?FLOAT_VAR_CHB_MIN(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? &
lowest CHB Q-score\\
\?FLOAT_VAR_CHB_MAX(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? &
highest CHB Q-score\\
\?FLOAT_VAR_MIN_MIN(?\OptArg{\?t?}\?)? & smallest minimum value\\
\?FLOAT_VAR_MIN_MAX(?\OptArg{\?t?}\?)? & largest minimum value\\
\?FLOAT_VAR_MAX_MIN(?\OptArg{\?t?}\?)? & smallest maximum value\\
\?FLOAT_VAR_MAX_MAX(?\OptArg{\?t?}\?)? & largest maximum value\\
\?FLOAT_VAR_SIZE_MIN(?\OptArg{\?t?}\?)? & smallest domain size\\
\?FLOAT_VAR_SIZE_MAX(?\OptArg{\?t?}\?)? & largest domain size\\
\?FLOAT_VAR_DEGREE_SIZE_MIN(?\OptArg{\?t?}\?)? & smallest degree divided by domain size\\
\?FLOAT_VAR_DEGREE_SIZE_MAX(?\OptArg{\?t?}\?)? & largest degree divided by domain size\\
\?FLOAT_VAR_AFC_SIZE_MIN(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & smallest AFC divided by domain size\\
\?FLOAT_VAR_AFC_SIZE_MAX(?\SpecialArg{\?afc?}\?,?\OptArg{\?t?}\?)? & largest AFC divided by domain size\\
\?FLOAT_VAR_ACTION_SIZE_MIN(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & smallest action divided by domain size\\
\?FLOAT_VAR_ACTION_SIZE_MAX(?\SpecialArg{\?act?}\?,?\OptArg{\?t?}\?)? & largest action divided by domain size\\
\?FLOAT_VAR_CHB_SIZE_MIN(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)?
& smallest chb divided by domain size\\
\?FLOAT_VAR_CHB_SIZE_MAX(?\SpecialArg{\?chb?}\?,?\OptArg{\?t?}\?)? & largest chb divided by domain size\\
\end{tabular}
\end{center}
\caption{Float variable selection}
\label{fig:m:branch:float:var}
\end{figure}
For float variables, variable selection is defined
by a value of class \gecoderef[class]{FloatVarBranch} (see also
\gecoderef[group]{TaskModelFloatBranchVar}) and value selection is defined
by a value of type \gecoderef[class]{FloatValBranch} (see also
\gecoderef[group]{TaskModelFloatBranchVal}).
For an overview of the available variable selection strategies,
see \autoref{fig:m:branch:float:var} (see also
\gecoderef[group]{TaskModelFloatBranchVar}) where
\OptArg{$\cdot$}~denotes an optional argument
and~\SpecialArg{$\cdot$} is a special argument to be explained
below. Here, an argument~\?r? refers to a random number
generator of type \gecoderef[class]{Rnd}. Using random number
generators for branching is discussed in
\autoref{sec:m:branch:rnd}. An argument~\?m? refers to a
user-defined merit function of type
\gecoderef[typedef]{FloatBranchMerit}. User-defined merit
functions are discussed in
\autoref{sec:m:branch:uservar}. An argument \?afc?
refers to accumulated failure count (AFC) information for float
variables (of class \gecoderef[class]{FloatAFC}). An argument
\?act? refers to action information for float variables (of
class \gecoderef[class]{FloatAction}). An argument
\?chb? refers to CHB information for float variables (of
class \gecoderef[class]{FloatCHB}). For a discussion of AFC,
action, and CHB, see \autoref{sec:m:branch:shared}. Both
\SpecialArg{\?afc?} and \SpecialArg{\?act?} can also be optional
arguments of type \?double? defining a decay-factor. The argument
\SpecialArg{\?chb?} can be ommitted. The optional
argument \?t? refers to a tie-breaking limit function of type
\gecoderef[typedef]{BranchTbl} and is discussed in
\autoref{sec:m:branch:tbl}.
Omitting the variable selection strategy is equivalent to using
\?FLOAT_VAR_NONE()?.
\begin{figure}
\begin{center}
\begin{tabular}{l@{\quad}l}
\?FLOAT_VAL(v,?\OptArg{\?c?}\?)? & defined by value function \?v? and commit
function \?c?\\
\?FLOAT_VAL_SPLIT_RND(r)? &values not smaller or larger than mean\\
& (smaller or larger is randomly selected)\\
\?FLOAT_VAL_SPLIT_MIN()? &values not greater than mean\\
\?FLOAT_VAL_SPLIT_MAX()? &values not smaller than mean\\
\end{tabular}
\end{center}
\caption{Float value selection}
\label{fig:m:branch:float:val}
\end{figure}
An overview of the available value selection strategies for float
variables can be found in \autoref{fig:m:branch:float:val} where \OptArg{$\cdot$} denotes
an optional argument. Here,
an argument \?r? refers to a random number generator of type
\gecoderef[class]{Rnd} which is discussed in
\autoref{sec:m:branch:rnd}. An argument \?v? refers to a
value selection function of type
\gecoderef[typedef]{FloatBranchVal}. An optional argument \?c? refers to a
commit function of type \gecoderef[typedef]{FloatBranchCommit}.
Value and commit function are discussed in
\autoref{sec:m:branch:userval}.
\section{Local versus shared variable selection criteria}
\label{sec:m:branch:shared}
The criteria used for selecting variables are either \emph{local}
or \emph{shared}. A \emph{local} variable selection
criterion depends only on a brancher's home space. A
\emph{shared} variable selection criterion depends not only on
the brancher's home space but also on all spaces that have been
created during search sharing the same root space where the
brancher had originally been posted. That entails that a shared
criterion can use information that is collected during search. In
terms of \autoref{sec:m:search:re}, a shared variable selection
criterion depends on all equivalent spaces created by cloning.
\subsection{Local variable selection criteria}
All selection criteria but those based on \emph{AFC},
\emph{action}, and \emph{CHB} are local: they either select
variables without using any information on a variable
(\?INT_VAR_NONE()?), select variables randomly
(\?INT_VAR_RND(r)?, see also \autoref{sec:m:branch:rnd}), or use
the degree or domain of a variable for selection. The
user-defined selection criteria \?INT_VAR_MERIT_MIN()? and
\?INT_VAR_MERIT_MAX()? in addition have access to the home space
and the selected variable's position, see
\autoref{sec:m:branch:uservar} for details.
The \emph{degree} of a variable is the number of propagators
depending on the variable (useful as an approximate measure of
how constrained a variables is).
The \emph{minimum-regret} for integer and Boolean variables is
the difference between the smallest and second smallest value in
the domain of a variable (\emph{maximum-regret} is analogous).
\subsection{Selection using accumulated failure count}
\label{sec:m:branch:afc}
The accumulated failure count (AFC) of a variable is a shared
selection criterion. It is defined as the sum of the AFCs of all
propagators depending on the variable plus its degree (to give a
good initial value if the AFCs of all propagators are still
zero). The AFC of a propagator counts how often the propagator
has failed during search. The AFC of a variable is also known as
the weighted degree of a variable~\cite{AFC}.
AFC in Gecode supports decay as follows. Each time a propagator
fails during constraint propagation (by executing the \?status()?
function of a space, see also \autoref{tip:m:started:status}),
the AFC of all propagators is updated:
\begin{itemize}
\item If the propagator \?p? failed, the AFC
$\mathtt{afc}(\mathtt p)$ of \?p? is incremented by $1$:
$$\mathtt{afc}(\mathtt p)=\mathtt{afc}(\mathtt p)+1$$
For all other propagators \?q?, the AFC
$\mathtt{afc}(\mathtt q)$ of \?q? is updated by a decay-factor
$\mathtt{d}$ ($0<\mathtt{d}\leq 1$):
$$\mathtt{afc}(\mathtt q)=\mathtt{d}\cdot\mathtt{afc}(\mathtt q)$$
\item The AFC $\mathtt{afc}(\mathtt x)$ of a variable \?x? is
then defined as:
$$\mathtt{afc}(\mathtt
x)=\mathtt{afc}(\mathtt{p}_1)+\cdots+\mathtt{afc}(\mathtt{p}_n)$$
where the propagators $\mathtt{p}_i$ depend on \?x?.
\item The AFC $\mathtt{afc}(\mathtt p)$ of a propagator \?p? is
initialized to $1$. That entails that the AFC of a variable \?x? is
initialized to its degree.
\end{itemize}
In order to use AFC for branching, one must create an object of
class \gecoderef[class]{IntAFC} for integer variables, an object
of class \gecoderef[class]{BoolAFC} for Boolean variables, an
object of class \gecoderef[class]{SetAFC} for set variables, or
an object of class \gecoderef[class]{FloatAFC} for float
variables. The object is responsible for recording AFC
information\footnote{Gecode cheats a little bit with the
implementation of AFC: while it is possible (but not common) to
have more than a single AFC object, all will use the same
decay-factor \?d?. The decay-factor used is the one defined by
the AFC object created last. But as using several AFC objects
with different decay-factors is not really that useful, Gecode
takes a shortcut here.}.
\begin{samepage}
If \?x? is an integer variable array, then
\begin{code}
IntAFC afc(home,x,0.99);
\end{code}
\end{samepage}
initializes the AFC information \?afc? for the variables in \?x?
with decay-factor $\mathtt{d}=\mathtt{0.99}$. The decay-factor is
optional and defaults to no decay ($\mathtt{d}=1$).
\begin{samepage}
The decay-factor can be changed later, say to
$\mathtt{d}=\mathtt{0.95}$, by
\begin{code}
afc.decay(0.95);
\end{code}
\end{samepage}
and \?afc.decay()? returns the current decay-factor of \?afc?.
A branching for integer variables using AFC information must
be given an object of type \?IntAFC? as argument:
\begin{code}
branch(home, x, INT_VAR_AFC_MAX(afc), INT_VAL_MIN());
\end{code}
Here the integer variable array \?x? must be exactly the same
that has been used for creating the integer AFC object
\?afc?.
The AFC object can be omitted if one does not want to
change the decay-factor later, hence it is sufficient to pass the
decay-factor as argument. For example:
\begin{code}
branch(home, x, INT_VAR_AFC_MAX(0.99), INT_VAL_MIN());
\end{code}
uses AFC information with a decay-factor of \?0.99?. Even the
decay-factor can be omitted and defaults to \?1? (that is, no decay).
AFC for other variable types is analogous.
For an example using a decay-factor with AFC, see
\autoref{sec:c:crossword:info}.
\subsection{Selection using action}
\label{sec:m:branch:action}
The action of a variable is a shared criterion and captures how
often the domain of a variable has been reduced during constraint
propagation.
The action of a variable is maintained by constraint propagation
as follows. Each time constraint propagation finishes (even if it
finishes with failure) during search (by executing the
\?status()? function of a space, see also
\autoref{tip:m:started:status}), the action of a variable
$\mathtt x$ is updated~\cite{activity}:
\begin{itemize}
\item If the variable \?x? has not been pruned (that is, no
values have been removed from the domain of \?x? through
propagation), the action $\mathtt{action}(\mathtt x)$ of \?x? is
updated by a decay-factor $\mathtt{d}$ ($0<\mathtt{d}\leq 1$):
$$\mathtt{action}(\mathtt x)=\mathtt{d}\cdot\mathtt{action}(\mathtt x)$$
\item If the variable \?x? has been pruned, the action
$\mathtt{action}(\mathtt x)$ of \?x? is incremented by $1$:
$$\mathtt{action}(\mathtt x)=\mathtt{action}(\mathtt x)+1$$
\item The action of a variable \?x? is initialized to be one.
\end{itemize}
Note that in~\cite{activity} action is called activity. However,
as the activity of a variable during search in SAT is a
well-established and different concept (see for
example~\cite{minisat}), Gecode uses the term action instead.
In order to use action for branching, one must create an object
of class \gecoderef[class]{IntAction} for integer variables, an
object of class \gecoderef[class]{BoolAction} for Boolean
variables, an object of class \gecoderef[class]{SetAction} for
set variables, or an object of class
\gecoderef[class]{FloatAction} for float variables. The object
is responsible for recording action information.
\begin{samepage}
If \?x? is an integer variable array, then
\begin{code}
IntAction act(home,x,0.99);
\end{code}
\end{samepage}
initializes the action information \?act? for the variables in \?x?
with decay-factor $\mathtt{d}=\mathtt{0.99}$. The decay-factor is
optional and defaults to no decay ($\mathtt{d}=1$).
Note that it can be specified whether the action counter is
incremented when a variable is pruned (propagation) or when a
variable domain has been wiped out (failure). For example, the
following creates action information that onky considers
propagation:
\begin{code}
IntAction act(home,x,0.99,true,false);
\end{code}
whereas the following only considers failure:
\begin{code}
IntAction act(home,x,0.99,false,true);
\end{code}
By default, both are considered which corresponds to:
\begin{code}
IntAction act(home,x,0.99,true,true);
\end{code}
The action of each variable in an array \?x? can be initialized
by a merit function, see \autoref{sec:m:branch:uservar}. Here
\begin{code}
IntAction act(home,x,0.99,true,true
[](const Space& home, IntVar x, int i) {
return 1.0;
});
\end{code}
initializes the action of \?x[i]? to \?1.0?.
The decay-factor can be changed later, say to
$\mathtt{d}=\mathtt{0.95}$, by
\begin{code}
act.decay(0.95);
\end{code}
and \?act.decay()? returns the current decay-factor of \?act?.
A branching for integer variables using action information must
be given an object of type \?IntAction? as argument:
\begin{code}
branch(home, x, INT_VAR_ACTION_MAX(act), INT_VAL_MIN());
\end{code}
Here the integer variable array \?x? must be exactly the same
that has been used for creating the integer action object
\?act?.
The action object can be omitted if one does not want to
change the decay-factor later, hence it is sufficient to pass the
decay-factor as argument. For example:
\begin{code}
branch(home, x, INT_VAR_ACTION_MAX(0.99), INT_VAL_MIN());
\end{code}
uses action information with a decay-factor of \?0.99?. Even the
decay-factor can be omitted and defaults to \?1? (that is, no decay).
Action for other variable types is analogous.
\subsection{Selection using CHB}
\label{sec:m:branch:chb}
The CHB (for conflict-history based branching) Q-score of a
variable is a shared criterion and combines how often the domain
of a variable has been reduced during constraint propagation with
how recently the variable has been reduced during failure. CHB in
Gecode is based on~\cite{chb} which presents the heuristic for a
SAT solver. Here, we use the term failure instead of conflict as
originally in~\cite{chb}.
The \emph{Q-score} $\mathtt{qs}(\mathtt x)$ of a variable
$\mathtt x$ is maintained by constraint propagation as follows.
For the computation of the Q-score, the following two variables
are used:
\begin{itemize}
\item The \emph{failure counter} $\mathtt{\#f}$ counts how often
failure has been encountered. That is, each time a space is
failed, $\mathtt{\#f}$ is incremented by one and it is
initialized to zero.
\item The \emph{step size} $\alpha$ is also updated when a
failure occurs, it is updated by
$$\alpha = \alpha - \mathtt{10}^{-\mathtt 6}$$
provided $\alpha>0.06$. If $\alpha\leq 0.06$, its value does not
change. $\alpha$ is initialized to $0.4$.
\end{itemize}
In addition to the Q-score for a variable, CHB also maintains the
\emph{last failure} $\mathtt{lf}(\mathtt x)$ of a variable
$\mathtt x$. Each time constraint propagation finishes during
search (by executing the \?status()? function of a space, see
also \autoref{tip:m:started:status}), the Q-score
$\mathtt{qs}(\mathtt x)$ and the last failure
$\mathtt{lf}(\mathtt x)$ of a variable $\mathtt x$ are updated as
follows:
\begin{itemize}
\item If the variable \?x? has not been pruned (that is, no
values have been removed from the domain of \?x? through
propagation), the Q-score $\mathtt{qs}(\mathtt x)$ and the last
failure $\mathtt{lf}(\mathtt x)$ do not change.
\item If the variable \?x? has been pruned and propagation has
failed, the last failure $\mathtt{lf}(\mathtt x)$ is updated to
$$\mathtt{lf}(\mathtt x)=\mathtt{\#f}$$
and the Q-score is updated to
$$\mathtt{qs}(\mathtt x)=(1-\alpha)\mathtt{qs}(\mathtt x) +
\alpha r$$
where the reward $r$ is defined as
$$
r=\frac{1}{\mathtt{\#f}-\mathtt{lf}(\mathtt x) + 1}
$$
\item If the variable \?x? has been pruned and propagation has
not failed, the last failure $\mathtt{lf}(\mathtt x)$ remains
unchanged and the Q-score is updated to
$$\mathtt{qs}(\mathtt x)=(1-\alpha)\mathtt{qs}(\mathtt x) +
\alpha r$$
where the reward $r$ is defined as
$$
r=\frac{0.9}{\mathtt{\#f}-\mathtt{lf}(\mathtt x) + 1}
$$
\item The Q-score $\mathtt{qs}(\mathtt x)$ of a variable \?x? is
by default initialized to be $0.05$.
\end{itemize}
In order to use CHB Q-scores for branching, one must create an object
of class \gecoderef[class]{IntCHB} for integer variables, an
object of class \gecoderef[class]{BoolCHB} for Boolean
variables, an object of class \gecoderef[class]{SetCHB} for
set variables, or an object of class
\gecoderef[class]{FloatCHB} for float variables. The object
is responsible for recording CHB Q-score information.
\begin{samepage}
If \?x? is an integer variable array, then
\begin{code}
IntCHB chb(home,x);
\end{code}
\end{samepage}
initializes the CHB information \?chb? for the variables in \?x?.
The Q-score of each variable in an array \?x? can be initialized
by a merit function, see \autoref{sec:m:branch:uservar}. Here
\begin{code}
IntCHB chb(home,x,
[](const Space& home, IntVar x, int i) {
return 0.0;
});
\end{code}
initializes the Q-score of \?x[i]? to \?1.0?.
A branching for integer variables using CHB information must be
given an object of type \?IntCHB? as argument. For example, the
following brancher will select variables with largest Q-score as
defined by \?chb? first:
\begin{code}
branch(home, x, INT_VAR_CHB_MAX(chb), INT_VAL_MIN());
\end{code}
Here the integer variable array \?x? must be exactly the same
that has been used for creating the integer CHB object
\?chb?.
The CHB object can be omitted if one does not want to initialize
the Q-score explicitly as described above.
CHB for other variable types is analogous.
\section{Random variable and value selection}
\label{sec:m:branch:rnd}
One particular strategy for variable and value selection is by
random. For integer variables, \?INT_VAR_RND(r)?
selects a random variable and \?INT_VAL_RND(r)? selects a random
value where \?r? is a random number generator of class
\gecoderef[class]{Rnd}. For Boolean variables,
\?BOOL_VAR_RND(r)? selects a random variable and
\?BOOL_VAL_RND(r)? selects a random value. For set variables, \?SET_VAR_RND(r)?
selects a random variable and \?SET_VAL_RND_INC(r)? and
\?SET_VAL_RND_EXC(r)? include and exclude a random value from a
set variable. For float variables, \?FLOAT_VAR_RND(r)? selects a
random variable and \?FLOAT_VAL_SPLIT_RND(r)? randomly selects
the lower or upper half of the domain of a float variable.
\begin{samepage}
The random number generators used for random variable and value
selection follow a uniform distribution and must be initialized by
a seed value. For example, a random number generator \?r? is
created and initialized with a seed value of \?1? (the seed value
must be an \?unsigned int?) by
\begin{code}
Rnd r(1U);
\end{code}
\end{samepage}
The seed value can be changed with the \?seed()? function (if
needed, the \?seed()? function initializes the random number
generator). For example, by
\begin{code}
r.seed(2U);
\end{code}
the seed value is set to \?2? (the \?seed()? function also
expects an argument of type \?unsigned int?).
A random number generator is passed by reference to the
brancher. In the terms of \autoref{sec:m:integer:proper}, a
random number generator is a proper data structure. When a random
number generator is stored as a member of a space it must be
updated by using the \?update()? function of the random number
generator.
\begin{samepage}
It is possible to use the same random number generator for both
variable and value selection. For example, by
\begin{code}
Rnd r(1U);
branch(home, x, INT_VAR_RND(r), INT_VAL_RND(r));
\end{code}
\end{samepage}
both the variable in \?x? as well as its value are randomly
selected using the numbers generated by \?r?. It is of course
also possible to use two separate random number generators as in:
\begin{code}
Rnd r1(1U), r2(1U);
branch(home, x, INT_VAR_RND(r1), INT_VAL_RND(r2));