Download
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
// Low Autocorrelation Binary Sequences
 
/* Code written by Ian Gent, Feb 1999, ipg@cs.strath.ac.uk
 
   For description of techniques used, see
     
   Symmetry Breaking during Search in Constraint Programming
 
   Ian P Gent and Barbara M Smith
 
   University of Leeds Research Report, 1999.
 
  This code does NOT contain the symmetry breaking techniques described
in the report, so if you are interested in those contact the authors.
  Instead two simple constraints break some symmetries, by asserting that
the first two bits are both -1.
 
*/
 
#include <ilsolver/ilcint.h>
 
 
IlcInt nBits;
 
 
IlcConstraint SimpleMod(IlcIntVar var, IlcInt mod, IlcIntVar remainder) {
    return   (0 <= remainder) && (remainder < mod)
         && ( (var-remainder) == ((var-remainder)/mod)*mod) ;}
IlcConstraint SimpleMod(IlcIntVar var, IlcInt mod, IlcInt remainder) {
    if ((0 <= remainder) && (remainder < mod)) {
        return ( (var-remainder) == ((var-remainder)/mod)*mod) ;}
        else {var.getManager().fail(); } ;}
       // impossible to satisfy
     
IlcConstraint SimpleMod(IlcInt var, IlcInt mod, IlcIntVar remainder) {
    return   (0 <= remainder) && (remainder < mod)
         && ( (var-remainder) == ((var-remainder)/mod)*mod) ;}
 
void ModCorrelation(IlcIntVarArray Bits, IlcInt k, IlcIntVar Correlation)
  {
  IlcManager m = Bits.getManager();
  IlcIntArray BitValues(m,2,-1,1);
 
  IlcInt numCorrelations = IlcMin(k,nBits-k);
 
  IlcIntVar Mod4Value(m,0,3);
  IlcIntVarArray Mod4Values(m,numCorrelations,0,3);
  IlcIntVarArray SequenceCorrelations(m,numCorrelations);
 
  IlcInt length ;
 
  for(IlcInt ki = 0; ki < numCorrelations; ki++) {
     length = (nBits-1-ki)/k;       // hope that's right -- CHECK!!
 
        // length = 0 -> no correlation at this distance
        // although I think formula still holds as first value = 0?
     if (length > 0) {
        IlcIntVarArray products(m,0,length,1,IlcIntVar(m,BitValues));
        for(IlcInt j = 0; j < length; j++) {
        products[j] = Bits[j*k + ki]*Bits[(j+1)*k+ki];
       
        SequenceCorrelations[ki] = IlcSum(products);
 
        m.add(SimpleMod(SequenceCorrelations[ki],2,length%2));
 
        m.add( SimpleMod((length%4) - (2*(Bits[ki] != Bits[ki+(length*k)])),
                     4, Mod4Values[ki]) );
        m.add(SimpleMod(SequenceCorrelations[ki],4,Mod4Values[ki]));
        }
     else {
        assert(1 == 0) ; // error if we get here!
        SequenceCorrelations[ki] = IlcIntVar(m,0,0);
        m.add( Mod4Values[ki] == 0) ; } ;
     };
 
  m.add(Correlation == IlcSum(SequenceCorrelations));
 
  m.add(SimpleMod(IlcSum(Mod4Values),4,Mod4Value));
  m.add(SimpleMod(Correlation,4,Mod4Value));
  }
 
void SimpleCorrelation(IlcIntVarArray Bits, IlcInt k, IlcIntVar Correlation)
  {
  IlcManager m = Bits.getManager();
  IlcIntArray BitValues(m,2,-1,1);
 
  IlcInt numCorrelations = IlcMin(k,nBits-k);
 
  IlcIntVarArray SequenceCorrelations(m,numCorrelations);
 
  IlcInt length ;
 
  for(IlcInt ki = 0; ki < numCorrelations; ki++) {
     length = (nBits-1-ki)/k;       // hope that's right -- CHECK!!
 
        // length = 0 -> no correlation at this distance
        // although I think formula still holds as first value = 0?
     if (length > 0) {
        IlcIntVarArray products(m,0,length,1,IlcIntVar(m,BitValues));
        for(IlcInt j = 0; j < length; j++) {
        products[j] = Bits[j*k + ki]*Bits[(j+1)*k+ki];
       
        SequenceCorrelations[ki] = IlcSum(products);
        m.add(SimpleMod(SequenceCorrelations[ki],2,length%2));
        }
     else {
        assert(1 == 0) ; // error if we get here!
        SequenceCorrelations[ki] = IlcIntVar(m,0,0);
        }
     };
  m.add(Correlation == IlcSum(SequenceCorrelations));
  }
   
   
 
 
 
//$doc:CHOOSE
IlcChooseIndex1(IlcChooseOutermost,
                IlcMin(varIndex,nBits-varIndex),
                IlcIntVar)
//end:CHOOSE
 
 
//$doc:MAIN1
int main(int argc, char** argv){
  IlcManager m(IlcNoEdit);
  IlcInt i ; // loop variable
 
#if defined(ILCLOGFILE)
  m.openLogFile("labs.log");
#endif
 
  nBits = (argc > 1) ? atoi(argv[1]) : 10;
 
  IlcIntVar zeroVar(m,0,0);
 
  IlcIntArray BitValues(m,2,-1,1);
  IlcIntVarArray Bits(m,0,nBits,1,IlcIntVar(m,BitValues));
 
// Set up domains of even/odd squares
  IlcIntArray EvenSquares(m,(nBits/2)+1) ;
  IlcIntArray OddSquares(m,(nBits+1)/2) ;
  for(i=0;i<(nBits/2)+1;i++) {
    EvenSquares[i]= IlcSquare(i*2); }
  for(i=0;i<(nBits+1)/2;i++) {
    OddSquares[i]= IlcSquare(i*2+1); }
 
//  IlcIntVarArray *shiftedBits = new(m.getHeap()) IlcIntVarArray[nBits];
  // IlcIntVarArray *differences = new(m.getHeap()) IlcIntVarArray[nBits];
 
  IlcIntVarArray Correlations(m,nBits,-nBits,nBits);
  Correlations[0] = zeroVar;    // so that Correlations[i] matches distance i
   
  //shiftedBits[0] = Bits;
 //  differences[0] = Bits;
 
  IlcIntVarArray SquareCorrelations(m,nBits);
  SquareCorrelations[0] = zeroVar;
 
// general correlation mod work
 
  for(i=1; i < nBits; i++) {
 
      if (i <= (nBits/2)) {
         ModCorrelation(Bits,i,Correlations[i]) ;  }
      else { SimpleCorrelation(Bits,i,Correlations[i]) ; } ;
 
      if (((nBits-i) %2) == 0L) {
    SquareCorrelations[i] = IlcIntVar(m,EvenSquares); }
      else {
    SquareCorrelations[i] = IlcIntVar(m,OddSquares); }
      m.add(SquareCorrelations[i] == IlcSquare(Correlations[i]));
      }
 
  IlcIntVar TotalSquareCorrelation = IlcSum(SquareCorrelations);
     
  m.setObjMin(TotalSquareCorrelation);
 
 
// simple symmetry breaking:
 
     m.add(Bits[0] == -1);  m.add(Bits[1] == -1);
 
//end:MAIN1
  /*
*/
//$doc:GEN2
  m.add(IlcGenerate(Bits,IlcChooseOutermost));
//end:GEN2
//$doc:MAIN2
   
 
     while (m.nextSolution()) {
       m.out() << "Cost:\t" << TotalSquareCorrelation.getValue() << endl;
       m.storeSolution();
       m.printInformation();
       m.out() << endl;
       }
 
     m.restart();
     m.nextSolution();
 
     m.out() << "Optimal Correlation Cost:\t" << TotalSquareCorrelation.getValue() << endl;
 
     m.out() << Bits << endl;
     m.out() << SquareCorrelations << endl;
 
     m.printInformation();
 
 
#if defined(ILCLOGFILE)
  m.closeLogFile();
#endif
  m.end();
  return 0;
}
 
//end:MAIN2