efpa.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Mikael Lagerkvist <lagerkvist@gecode.org> 00005 * 00006 * Copyright: 00007 * Mikael Lagerkvist, 2009 00008 * 00009 * Last modified: 00010 * $Date: 2010-05-08 13:09:21 +0200 (Sat, 08 May 2010) $ by $Author: tack $ 00011 * $Revision: 10907 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <gecode/driver.hh> 00039 #include <gecode/int.hh> 00040 #include <gecode/minimodel.hh> 00041 00042 using namespace Gecode; 00043 00049 class EFPAOptions : public Options { 00050 private: 00051 Driver::UnsignedIntOption _v; 00052 Driver::UnsignedIntOption _q; 00053 Driver::UnsignedIntOption _l; 00054 Driver::UnsignedIntOption _d; 00055 Driver::StringOption _permutation; 00056 00057 public: 00059 EFPAOptions(const char* s, 00060 int v0 = 5, int q0 = 3, int lambda0 = 2, int d0 = 4) 00061 : Options(s), 00062 _v("-v", "number of sequences", v0 ), 00063 _q("-q", "number of symbols", q0 ), 00064 _l("-l", "sets of symbols per sequence (lambda)", lambda0), 00065 _d("-d", "Hamming distance between sequences", d0 ), 00066 _permutation("-permutation", "use permutation constraints if d=4", 00067 false) 00068 { 00069 // Add options 00070 add(_d); 00071 add(_l); 00072 add(_q); 00073 add(_v); 00074 add(_permutation); 00075 add(_symmetry); 00076 00077 // Add permutation options 00078 _permutation.add(true, "full" ); 00079 _permutation.add(false, "none"); 00080 // Add symmetry options 00081 _symmetry.add(true, "true" ); 00082 _symmetry.add(false, "false"); 00083 } 00085 void parse(int& argc, char* argv[]) { 00086 Options::parse(argc,argv); 00087 } 00089 int v(void) const { return _v.value(); } 00091 int q(void) const { return _q.value(); } 00093 int l(void) const { return _l.value(); } 00095 int d(void) const { return _d.value(); } 00096 00098 bool permutation(void) const { return d() == 4 && _permutation.value(); } 00100 bool symmetry(void) const { return _symmetry.value(); } 00101 }; 00102 00103 00118 class EFPA : public Script { 00119 protected: 00120 int v; 00121 int q; 00122 int l; 00123 int d; 00124 int n; 00125 int nseqpair; 00126 IntVarArray c; 00127 BoolVarArray diff; 00128 00129 public: 00131 EFPA(const EFPAOptions& opt) 00132 : v(opt.v()), 00133 q(opt.q()), 00134 l(opt.l()), 00135 d(opt.d()), 00136 n(q*l), 00137 nseqpair((v*(v-1))/2), 00138 c(*this, n*v, 1,q), 00139 diff(*this, n*nseqpair, 0, 1) 00140 { 00141 // Matrix access 00142 // q*lambda=n columns, and v rows 00143 Matrix<IntVarArray> cm(c, n, v); 00144 // q*lambda=n columns, and nseqpair rows 00145 Matrix<BoolVarArray> diffm(diff, n, nseqpair); 00146 00147 // Counting symbols in rows 00148 { 00149 IntArgs values(q); 00150 for (int i = q; i--; ) values[i] = i+1; 00151 IntSet cardinality(l, l); 00152 for (int i = v; i--; ) 00153 count(*this, cm.row(i), cardinality, values, opt.icl()); 00154 } 00155 00156 // Difference variables 00157 { 00158 int nseqi = 0; 00159 for (int a = 0; a < v; ++a) { 00160 for (int b = a+1; b < v; ++b) { 00161 for (int i = n; i--; ) { 00162 rel(*this, cm(i, a), IRT_NQ, cm(i, b), diffm(i, nseqi)); 00163 } 00164 ++nseqi; 00165 } 00166 } 00167 assert(nseqi == nseqpair); 00168 } 00169 00170 // Counting the Hamming difference 00171 { 00172 for (int i = nseqpair; i--; ) { 00173 linear(*this, diffm.row(i), IRT_EQ, d); 00174 } 00175 } 00176 00177 // Symmetry breaking 00178 if (opt.symmetry()) { 00179 IntRelType row_less = d==0 ? IRT_EQ : IRT_LE; 00180 // order rows 00181 for (int r = 0; r<v-1; ++r) { 00182 rel(*this, cm.row(r), row_less, cm.row(r+1)); 00183 } 00184 // order columns 00185 for (int c = 0; c<n-1; ++c) { 00186 rel(*this, cm.col(c), IRT_LQ, cm.col(c+1)); 00187 } 00188 // Set first row according to symmetry breaking 00189 int color = 1; 00190 int ncolor = 0; 00191 for (int c = 0; c < n; ++c) { 00192 rel(*this, cm(c, 0), IRT_EQ, color); 00193 if (++ncolor == l) { 00194 ncolor = 0; 00195 ++color; 00196 } 00197 } 00198 } 00199 00200 // Permutation constraints 00201 if (opt.permutation()) { 00202 const int k[][4] = { // inverse indexing of the permutation 00203 {0, 1, 3, 2}, // cform == 0, ((1, 2)(3, 4)) 00204 {1, 2, 3, 0}, // cform == 1, ((1, 2, 3, 4)) 00205 }; 00206 assert(d == 4); 00207 // Constraint on each pair of rows 00208 for (int r1 = 0; r1 < v; ++r1) { 00209 for (int r2 = r1+1; r2 < v; ++r2) { 00210 IntVarArgs row1 = cm.row(r1); 00211 IntVarArgs row2 = cm.row(r2); 00212 // Perm is the 00213 IntVarArgs perm(d); 00214 for (int i = d; i--; ) perm[i] = IntVar(*this, 0, n-1); 00215 // cform is the cycle-form of the permutation 00216 IntVar cform(*this, 0, 1); 00217 BoolVar cformb = channel(*this, cform); 00218 00219 /* Permutation mapping*/ 00220 // Values from row1... 00221 IntVarArgs _p(2*d); 00222 for (int i = 2*d; i--; ) _p[i] = IntVar(*this, 1, q); 00223 Matrix<IntVarArgs> p(_p, d, 2); 00224 for (int i = 0; i < 2; ++i) { 00225 for (int j = 0; j < d; ++j) { 00226 element(*this, row1, perm[k[i][j]], p(j, i)); 00227 } 00228 } 00229 00230 // ...into values in row2 00231 for (int i = 0; i < d; ++i) { 00232 IntVar index(*this, 0, 2*d); 00233 rel(*this, cform*d + i == index); 00234 IntVar value(*this, 1, q); 00235 element(*this, _p, index, value); 00236 element(*this, row2, perm[i], value); 00237 } 00238 00239 /* Rows r1 and r2 are equal at indices not in perm */ 00240 // uses Boolean representations pib for perm[i] 00241 BoolVarArgs p1b(*this, n, 0, 1); 00242 channel(*this, p1b, perm[0]); 00243 BoolVarArgs p2b(*this, n, 0, 1); 00244 channel(*this, p2b, perm[1]); 00245 BoolVarArgs p3b(*this, n, 0, 1); 00246 channel(*this, p3b, perm[2]); 00247 BoolVarArgs p4b(*this, n, 0, 1); 00248 channel(*this, p4b, perm[3]); 00249 for (int i = n; i--; ) { 00250 // No perm-variable uses i is equivalent to the reows 00251 // being equal at i 00252 rel(*this, (!p1b[i] && !p2b[i] && !p3b[i] && !p4b[i]) == 00253 (row1[i] == row2[i])); 00254 } 00255 00256 /* Constraints for fixing the permutation */ 00257 // Common non-equality constraints - derangements 00258 rel(*this, perm[0], IRT_NQ, perm[1]); 00259 rel(*this, perm[2], IRT_NQ, perm[3]); 00260 // Conditional non-equality constraints - derangment of cform 1 00261 // Implements distinct(*this, perm, cformb); 00262 rel(*this, perm[0], IRT_NQ, perm[2], cformb); 00263 rel(*this, perm[0], IRT_NQ, perm[3], cformb); 00264 rel(*this, perm[1], IRT_NQ, perm[2], cformb); 00265 rel(*this, perm[1], IRT_NQ, perm[3], cformb); 00266 // Common ordering-constraints - symmetry breaking 00267 rel(*this, perm[0], IRT_LE, perm[1]); 00268 rel(*this, perm[0], IRT_LE, perm[2]); 00269 rel(*this, perm[0], IRT_LE, perm[3]); 00270 // Conditional ordering constraint - symmetry breaking for cform 0 00271 rel(*this, (!cformb) >> (perm[2] < perm[3])); 00272 } 00273 } 00274 } 00275 00276 branch(*this, c, INT_VAR_NONE, INT_VAL_MIN); 00277 } 00278 00280 virtual void 00281 print(std::ostream& os) const { 00282 Matrix<IntVarArray> cm(c, n, v); 00283 for (int i = 0; i < v; ++i) { 00284 IntVarArgs r = cm.row(i); 00285 os << r << std::endl; 00286 } 00287 os << std::endl; 00288 } 00289 00291 EFPA(bool share, EFPA& s) 00292 : Script(share,s), 00293 v(s.v), 00294 q(s.q), 00295 l(s.l), 00296 d(s.d), 00297 n(s.n), 00298 nseqpair(s.nseqpair) 00299 { 00300 c.update(*this, share, s.c); 00301 diff.update(*this, share, s.diff); 00302 } 00304 virtual Space* 00305 copy(bool share) { 00306 return new EFPA(share,*this); 00307 } 00308 }; 00309 00313 int 00314 main(int argc, char* argv[]) { 00315 EFPAOptions opt("Equidistant Frequency Permutation Arrays"); 00316 opt.icl(ICL_DOM); 00317 opt.parse(argc,argv); 00318 00319 Script::run<EFPA,DFS,EFPAOptions>(opt); 00320 return 0; 00321 } 00322 00323 // STATISTICS: example-any