Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

bibd.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Bugfixes provided by:
00009  *     Olof Sivertsson <olsi0767@student.uu.se>
00010  *
00011  *  Last modified:
00012  *     $Date: 2005-10-31 13:17:08 +0100 (Mon, 31 Oct 2005) $ by $Author: schulte $
00013  *     $Revision: 2435 $
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  See the file "LICENSE" for information on usage and
00020  *  redistribution of this file, and for a
00021  *     DISCLAIMER OF ALL WARRANTIES.
00022  *
00023  */
00024 
00025 #include "examples/support.hh"
00026 
00035 class BIBD : public Example {
00036 protected:
00038   BoolVarArray _p;
00039 public:
00041   class Par {
00042   public:
00043     int v, b, r, k, lambda;
00044   };
00045   static Par par;
00046 
00048   BoolVar& p(int i, int j) {
00049     // row, column
00050     return _p[i*par.b+j];
00051   }
00052 
00054   BIBD(const Options& opt)
00055     : _p(this,par.v*par.b,0,1) {
00056     // r ones per row
00057     for (int i=par.v; i--; ) {
00058       BoolVarArgs row(par.b);
00059       for (int j=par.b; j--; )
00060         row[j] = p(i,j);
00061       linear(this, row, IRT_EQ, par.r);
00062     }
00063     // k ones per column
00064     for (int j=par.b; j--; ) {
00065       BoolVarArgs col(par.v);
00066       for (int i=par.v; i--; )
00067         col[i] = p(i,j);
00068       linear(this, col, IRT_EQ, par.k);
00069     }
00070     // Exactly lambda ones in scalar product between two different rows
00071     for (int i1=0; i1<par.v; i1++)
00072       for (int i2=i1+1; i2<par.v; i2++) {
00073         BoolVarArgs row(par.b);
00074         for (int j=par.b; j--; ) {
00075           BoolVar b(this,0,1);
00076           bool_and(this,p(i1,j),p(i2,j),b);
00077           row[j] = b;
00078         }
00079         linear(this, row, IRT_EQ, par.lambda);
00080       }
00081 
00082     for (int i=1;i<par.v;i++) {
00083       BoolVarArgs row1(par.b);
00084       BoolVarArgs row2(par.b);
00085       for (int j=par.b; j--; ) {
00086         row1[j] = p(i-1,j);
00087         row2[j] = p(i,j);
00088       }
00089       lex(this, row1, IRT_GQ, row2);
00090     }
00091     for (int j=1;j<par.b;j++) {
00092       BoolVarArgs col1(par.v);
00093       BoolVarArgs col2(par.v);
00094       for (int i=par.v; i--; ) {
00095         col1[i] = p(i,j-1);
00096         col2[i] = p(i,j);
00097       }
00098       lex(this, col1, IRT_GQ, col2);
00099     }
00100 
00101     branch(this, _p, BVAR_NONE, BVAL_MAX);
00102   }
00103 
00105   virtual void
00106   print(void) {
00107     std::cout << "\tBIBD("
00108               << par.v << "," << par.b << ","
00109               << par.r << "," << par.k << ","
00110               << par.lambda << ")" << std::endl;
00111     for (int i = 0; i < par.v; i++) {
00112       std::cout << "\t\t";
00113       for (int j = 0; j< par.b; j++)
00114         std::cout << p(i,j) << " ";
00115       std::cout << std::endl;
00116     }
00117     std::cout << std::endl;
00118   }
00119 
00121   BIBD(bool share, BIBD& s)
00122     : Example(share,s) {
00123     _p.update(this,share,s._p);
00124   }
00125 
00127   virtual Space*
00128   copy(bool share) {
00129     return new BIBD(share,*this);
00130   }
00131 
00132 };
00133 
00134 
00135 BIBD::Par BIBD::par;
00136 
00140 int
00141 main(int argc, char** argv) {
00142   Options opt("BIBD");
00143   opt.solutions  = 1;
00144   opt.iterations = 25;
00145   opt.size       = 4;
00146   opt.c_d        = 10;
00147   opt.parse(argc,argv);
00148   BIBD::Par p;
00149   switch (opt.size) {
00150   case 0:
00151     p.v=7; p.b=7; p.r=3; p.k=3; p.lambda=1; break;
00152   case 1:
00153     p.v=6; p.b=10; p.r=5; p.k=3; p.lambda=2; break;
00154   case 2:
00155     p.v=8; p.b=14; p.r=7; p.k=4; p.lambda=3; break;
00156   case 3:
00157     p.v=6; p.b=20; p.r=10; p.k=3; p.lambda=4; break;
00158   case 4:
00159     p.v=11; p.b=55; p.r=15; p.k=3; p.lambda=3; break;
00160   case 5:
00161     p.v=7; p.b=70; p.r=30; p.k=3; p.lambda=10; break;
00162   default:
00163     std::cerr << "Error: size must be between 0 and 5" << std::endl;
00164     return 1;
00165   }
00166   BIBD::par = p;
00167   
00168   Example::run<BIBD,DFS>(opt);
00169   return 0;
00170 }
00171 
00172 // STATISTICS: example-any
00173