linear.cc

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2005
00008  *
00009  *  Last modified:
00010  *     $Date: 2008-02-25 07:30:26 +0100 (Mon, 25 Feb 2008) $ by $Author: schulte $
00011  *     $Revision: 6290 $
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 "test/int.hh"
00039 
00040 #include "gecode/minimodel.hh"
00041 
00042 namespace Test { namespace Int {
00043 
00045    namespace Linear {
00046 
00048      bool one(const Gecode::IntArgs& a) {
00049       for (int i=a.size(); i--; )
00050         if (a[i] != 1)
00051           return false;
00052       return true;
00053     }
00054         
00060 
00061      class IntInt : public Test {
00062      protected:
00064        Gecode::IntArgs a;
00066        Gecode::IntRelType irt;
00067      public:
00069        IntInt(const std::string& s, const Gecode::IntSet& d,
00070               const Gecode::IntArgs& a0, Gecode::IntRelType irt0, 
00071               Gecode::IntConLevel icl=Gecode::ICL_BND)
00072          : Test("Linear::Int::Int::"+
00073                 str(irt0)+"::"+str(icl)+"::"+s+"::"+str(a0.size()),
00074                 a0.size(),d,icl != Gecode::ICL_DOM,icl), 
00075          a(a0), irt(irt0) {}
00077        virtual bool solution(const Assignment& x) const {
00078          double e = 0.0;
00079          for (int i=0; i<x.size(); i++)
00080            e += a[i]*x[i];
00081          return cmp(e, irt, static_cast<double>(0));
00082        }
00084        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00085          if (one(a))
00086            Gecode::linear(home, x, irt, 0, icl);
00087          else
00088            Gecode::linear(home, a, x, irt, 0, icl);
00089        }
00091        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x, 
00092                          Gecode::BoolVar b) {
00093          if (one(a))
00094            Gecode::linear(home, x, irt, 0, b, icl);
00095          else
00096            Gecode::linear(home, a, x, irt, 0, b, icl);
00097        }
00098      };
00099    
00101      class IntVar : public Test {
00102      protected:
00104        Gecode::IntArgs a;
00106        Gecode::IntRelType irt;
00107      public:
00109        IntVar(const std::string& s, const Gecode::IntSet& d,
00110               const Gecode::IntArgs& a0, Gecode::IntRelType irt0, 
00111               Gecode::IntConLevel icl=Gecode::ICL_BND)
00112          : Test("Linear::Int::Var::"+
00113                 str(irt0)+"::"+str(icl)+"::"+s+"::"+str(a0.size()),
00114                 a0.size()+1,d,icl != Gecode::ICL_DOM,icl), 
00115            a(a0), irt(irt0) {}
00117        virtual bool solution(const Assignment& x) const {
00118          double e = 0.0;
00119          for (int i=0; i<a.size(); i++)
00120            e += a[i]*x[i];
00121          return cmp(e, irt, static_cast<double>(x[a.size()]));
00122        }
00124        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00125          int n = a.size();
00126          Gecode::IntVarArgs y(n);
00127          for (int i=n; i--; )
00128            y[i] = x[i];
00129          if (one(a))
00130            Gecode::linear(home, y, irt, x[n], icl);
00131          else
00132            Gecode::linear(home, a, y, irt, x[n], icl);
00133        }
00135        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x, 
00136                          Gecode::BoolVar b) {
00137          int n = a.size();
00138          Gecode::IntVarArgs y(n);
00139          for (int i=n; i--; )
00140            y[i] = x[i];
00141          if (one(a))
00142            Gecode::linear(home, y, irt, x[n], b, icl);
00143          else
00144            Gecode::linear(home, a, y, irt, x[n], b, icl);
00145        }
00146      };
00147    
00149      class BoolInt : public Test {
00150      protected:
00152        Gecode::IntArgs a;
00154        Gecode::IntRelType irt;
00156        int c;
00157      public:
00159        BoolInt(const std::string& s, const Gecode::IntArgs& a0, 
00160                Gecode::IntRelType irt0, int c0,
00161                Gecode::PropKind pk=Gecode::PK_DEF)
00162          : Test("Linear::Bool::Int::"+
00163                 str(irt0)+"::"+s+"::"+str(a0.size())+"::"+str(c0)+"::"+str(pk),
00164                 a0.size(),0,1,true,Gecode::ICL_DEF,pk), 
00165            a(a0), irt(irt0), c(c0) {}
00167        virtual bool solution(const Assignment& x) const {
00168          double e = 0.0;
00169          for (int i=0; i<x.size(); i++)
00170            e += a[i]*x[i];
00171          return cmp(e, irt, static_cast<double>(c));
00172        }
00174        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00175          Gecode::BoolVarArgs y(x.size());
00176          for (int i=x.size(); i--; )
00177            y[i]=Gecode::channel(home,x[i]);
00178          if (one(a))
00179            Gecode::linear(home, y, irt, c, Gecode::ICL_DEF, pk);
00180          else
00181            Gecode::linear(home, a, y, irt, c, Gecode::ICL_DEF, pk);
00182        }
00184        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x, 
00185                          Gecode::BoolVar b) {
00186          Gecode::BoolVarArgs y(x.size());
00187          for (int i=x.size(); i--; )
00188            y[i]=Gecode::channel(home,x[i]);
00189          if (one(a))
00190            Gecode::linear(home, y, irt, c, b, Gecode::ICL_DEF, pk);
00191          else
00192            Gecode::linear(home, a, y, irt, c, b, Gecode::ICL_DEF, pk);
00193        }
00194      };
00195    
00197      class BoolVar : public Test {
00198      protected:
00200        Gecode::IntArgs a;
00202        Gecode::IntRelType irt;
00203      public:
00205        BoolVar(const std::string& s, 
00206                int min, int max, const Gecode::IntArgs& a0, 
00207                Gecode::IntRelType irt0)
00208          : Test("Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1,
00209                 min,max,true), 
00210            a(a0), irt(irt0) {}
00212        virtual bool solution(const Assignment& x) const {
00213          int n=x.size()-1;
00214          for (int i=0; i<n; i++)
00215            if ((x[i] < 0) || (x[i] > 1))
00216              return false;
00217          double e = 0.0;
00218          for (int i=0; i<n; i++)
00219            e += a[i]*x[i];
00220          return cmp(e, irt, static_cast<double>(x[n]));
00221        }
00223        virtual bool ignore(const Assignment& x) const {
00224          for (int i=x.size()-1; i--; )
00225            if ((x[i] < 0) || (x[i] > 1))
00226              return true;
00227          return false;
00228        }
00230        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x) {
00231          int n=x.size()-1;
00232          Gecode::BoolVarArgs y(n);
00233          for (int i=n; i--; )
00234            y[i]=Gecode::channel(home,x[i]);
00235          if (one(a))
00236            Gecode::linear(home, y, irt, x[n]);
00237          else
00238            Gecode::linear(home, a, y, irt, x[n]);
00239        }
00241        virtual void post(Gecode::Space* home, Gecode::IntVarArray& x, 
00242                          Gecode::BoolVar b) {
00243          int n=x.size()-1;
00244          Gecode::BoolVarArgs y(n);
00245          for (int i=n; i--; )
00246            y[i]=Gecode::channel(home,x[i]);
00247          if (one(a))
00248            Gecode::linear(home, y, irt, x[n], b);
00249          else
00250            Gecode::linear(home, a, y, irt, x[n], b);
00251        }
00252      };
00253    
00255      class Create {
00256      public:
00258        Create(void) {
00259          using namespace Gecode;
00260          {
00261            IntSet d1(-2,2);
00262            const int dv2[] = {-4,-1,0,1,4};
00263            IntSet d2(dv2,5);
00264            
00265            IntArgs a1(1, 0);
00266            
00267            for (IntRelTypes irts; irts(); ++irts) {
00268              (void) new IntInt("11",d1,a1,irts.irt());
00269              (void) new IntVar("11",d1,a1,irts.irt());
00270              (void) new IntInt("21",d2,a1,irts.irt());
00271              (void) new IntVar("21",d2,a1,irts.irt());
00272            }
00273            (void) new IntInt("11",d1,a1,IRT_EQ,ICL_DOM);
00274            (void) new IntVar("11",d1,a1,IRT_EQ,ICL_DOM);
00275            (void) new IntInt("21",d2,a1,IRT_EQ,ICL_DOM);
00276            (void) new IntVar("21",d2,a1,IRT_EQ,ICL_DOM);
00277    
00278            const int av2[5] = {1,1,1,1,1};
00279            const int av3[5] = {1,-1,-1,1,-1};
00280            const int av4[5] = {2,3,5,7,11};
00281            const int av5[5] = {-2,3,-5,7,-11};
00282    
00283            for (int i=1; i<=5; i++) {
00284              IntArgs a2(i, av2);
00285              IntArgs a3(i, av3);
00286              IntArgs a4(i, av4);
00287              IntArgs a5(i, av5);
00288              for (IntRelTypes irts; irts(); ++irts) {
00289                (void) new IntInt("12",d1,a2,irts.irt());
00290                (void) new IntInt("13",d1,a3,irts.irt());
00291                (void) new IntInt("14",d1,a4,irts.irt());
00292                (void) new IntInt("15",d1,a5,irts.irt());
00293                (void) new IntInt("22",d2,a2,irts.irt());
00294                (void) new IntInt("23",d2,a3,irts.irt());
00295                (void) new IntInt("24",d2,a4,irts.irt());
00296                (void) new IntInt("25",d2,a5,irts.irt());
00297                if (i < 5) {
00298                  (void) new IntVar("12",d1,a2,irts.irt());
00299                  (void) new IntVar("13",d1,a3,irts.irt());
00300                  (void) new IntVar("14",d1,a4,irts.irt());
00301                  (void) new IntVar("15",d1,a5,irts.irt());
00302                  (void) new IntVar("22",d2,a2,irts.irt());
00303                  (void) new IntVar("23",d2,a3,irts.irt());
00304                  (void) new IntVar("24",d2,a4,irts.irt());
00305                  (void) new IntVar("25",d2,a5,irts.irt());
00306                }
00307              }
00308              (void) new IntInt("12",d1,a2,IRT_EQ,ICL_DOM);
00309              (void) new IntInt("13",d1,a3,IRT_EQ,ICL_DOM);
00310              (void) new IntInt("14",d1,a4,IRT_EQ,ICL_DOM);
00311              (void) new IntInt("15",d1,a5,IRT_EQ,ICL_DOM);
00312              (void) new IntInt("22",d2,a2,IRT_EQ,ICL_DOM);
00313              (void) new IntInt("23",d2,a3,IRT_EQ,ICL_DOM);
00314              (void) new IntInt("24",d2,a4,IRT_EQ,ICL_DOM);
00315              (void) new IntInt("25",d2,a5,IRT_EQ,ICL_DOM);
00316              if (i < 4) {
00317                (void) new IntVar("12",d1,a2,IRT_EQ,ICL_DOM);
00318                (void) new IntVar("13",d1,a3,IRT_EQ,ICL_DOM);
00319                (void) new IntVar("14",d1,a4,IRT_EQ,ICL_DOM);
00320                (void) new IntVar("15",d1,a5,IRT_EQ,ICL_DOM);
00321              }
00322            }
00323          }
00324          {
00325            const int av1[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
00326            const int av2[10] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
00327            
00328            for (int i=1; i<=10; i += 3) {
00329              IntArgs a1(i, av1);
00330              IntArgs a2(i, av2);
00331              for (int c=0; c<=6; c += 3)
00332                for (IntRelTypes irts; irts(); ++irts)
00333                  for (PropKinds pks; pks(); ++pks) {
00334                    (void) new BoolInt("1",a1,irts.irt(),c,pks.pk());
00335                    (void) new BoolInt("2",a2,irts.irt(),-c,pks.pk());
00336                  }
00337            }
00338            
00339            IntArgs a3(5, 1,2,3,4,5);
00340            IntArgs a4(5, -1,-2,-3,-4,-5);
00341            IntArgs a5(5, -1,-2,1,2,4);
00342            
00343            for (int c=0; c<=16; c++)
00344              for (IntRelTypes irts; irts(); ++irts) {
00345                (void) new BoolInt("3",a3,irts.irt(),c);
00346                (void) new BoolInt("4",a4,irts.irt(),-c);
00347                (void) new BoolInt("5",a5,irts.irt(),c);
00348                (void) new BoolInt("6",a5,irts.irt(),-c);
00349              }
00350            
00351    
00352            for (int i=1; i<=5; i += 2) {
00353              IntArgs a1(i, av1);
00354              IntArgs a2(i, av2);
00355              for (IntRelTypes irts; irts(); ++irts) {
00356                (void) new BoolVar("1::"+Test::str(i),0,5,a1,irts.irt());
00357                (void) new BoolVar("2::"+Test::str(i),-5,0,a2,irts.irt());
00358              }
00359            }
00360            
00361            IntArgs a6(4, 1,2,3,4);
00362            IntArgs a7(4, -1,-2,-3,-4);
00363            IntArgs a8(4, -1,-2,1,2);
00364            IntArgs a9(6, -1,-2,1,2,-3,3);
00365    
00366            for (IntRelTypes irts; irts(); ++irts) {
00367              (void) new BoolVar("6",0,10,a6,irts.irt());
00368              (void) new BoolVar("7",-10,0,a7,irts.irt());
00369              (void) new BoolVar("8",-3,3,a8,irts.irt());
00370              (void) new BoolVar("9",-3,3,a9,irts.irt());
00371            }
00372            
00373          }
00374        }
00375      };
00376    
00377      Create c;
00379    
00380    }
00381 }}
00382 
00383 // STATISTICS: test-int