linear.cpp

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: 2011-09-02 13:27:53 +0200 (Fri, 02 Sep 2011) $ by $Author: tack $
00011  *     $Revision: 12389 $
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;
00068        int c;
00069      public:
00071        IntInt(const std::string& s, const Gecode::IntSet& d,
00072               const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
00073               int c0, Gecode::IntConLevel icl=Gecode::ICL_BND)
00074          : Test("Linear::Int::Int::"+
00075                 str(irt0)+"::"+str(icl)+"::"+s+"::"+str(c0)+"::"
00076                 +str(a0.size()),
00077                 a0.size(),d,icl != Gecode::ICL_DOM,icl),
00078          a(a0), irt(irt0), c(c0) {}
00080        virtual bool solution(const Assignment& x) const {
00081          double e = 0.0;
00082          for (int i=0; i<x.size(); i++)
00083            e += a[i]*x[i];
00084          return cmp(e, irt, static_cast<double>(c));
00085        }
00087        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00088          if (one(a))
00089            Gecode::linear(home, x, irt, c, icl);
00090          else
00091            Gecode::linear(home, a, x, irt, c, icl);
00092        }
00094        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00095                          Gecode::BoolVar b) {
00096          if (one(a))
00097            Gecode::linear(home, x, irt, c, b, icl);
00098          else
00099            Gecode::linear(home, a, x, irt, c, b, icl);
00100        }
00101      };
00102 
00104      class IntVar : public Test {
00105      protected:
00107        Gecode::IntArgs a;
00109        Gecode::IntRelType irt;
00110      public:
00112        IntVar(const std::string& s, const Gecode::IntSet& d,
00113               const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
00114               Gecode::IntConLevel icl=Gecode::ICL_BND)
00115          : Test("Linear::Int::Var::"+
00116                 str(irt0)+"::"+str(icl)+"::"+s+"::"+str(a0.size()),
00117                 a0.size()+1,d,icl != Gecode::ICL_DOM,icl),
00118            a(a0), irt(irt0) {}
00120        virtual bool solution(const Assignment& x) const {
00121          double e = 0.0;
00122          for (int i=0; i<a.size(); i++)
00123            e += a[i]*x[i];
00124          return cmp(e, irt, static_cast<double>(x[a.size()]));
00125        }
00127        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00128          int n = a.size();
00129          Gecode::IntVarArgs y(n);
00130          for (int i=n; i--; )
00131            y[i] = x[i];
00132          if (one(a))
00133            Gecode::linear(home, y, irt, x[n], icl);
00134          else
00135            Gecode::linear(home, a, y, irt, x[n], icl);
00136        }
00138        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00139                          Gecode::BoolVar b) {
00140          int n = a.size();
00141          Gecode::IntVarArgs y(n);
00142          for (int i=n; i--; )
00143            y[i] = x[i];
00144          if (one(a))
00145            Gecode::linear(home, y, irt, x[n], b, icl);
00146          else
00147            Gecode::linear(home, a, y, irt, x[n], b, icl);
00148        }
00149      };
00150 
00152      class BoolInt : public Test {
00153      protected:
00155        Gecode::IntArgs a;
00157        Gecode::IntRelType irt;
00159        int c;
00160      public:
00162        BoolInt(const std::string& s, const Gecode::IntArgs& a0,
00163                Gecode::IntRelType irt0, int c0)
00164          : Test("Linear::Bool::Int::"+
00165                 str(irt0)+"::"+s+"::"+str(a0.size())+"::"+str(c0),
00166                 a0.size(),0,1,true,Gecode::ICL_DEF),
00167            a(a0), irt(irt0), c(c0) {
00168        }
00170        virtual bool solution(const Assignment& x) const {
00171          double e = 0.0;
00172          for (int i=0; i<x.size(); i++)
00173            e += a[i]*x[i];
00174          return cmp(e, irt, static_cast<double>(c));
00175        }
00177        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00178          Gecode::BoolVarArgs y(x.size());
00179          for (int i=x.size(); i--; )
00180            y[i]=Gecode::channel(home,x[i]);
00181          if (one(a))
00182            Gecode::linear(home, y, irt, c, Gecode::ICL_DEF);
00183          else
00184            Gecode::linear(home, a, y, irt, c, Gecode::ICL_DEF);
00185        }
00187        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00188                          Gecode::BoolVar b) {
00189          Gecode::BoolVarArgs y(x.size());
00190          for (int i=x.size(); i--; )
00191            y[i]=Gecode::channel(home,x[i]);
00192          if (one(a))
00193            Gecode::linear(home, y, irt, c, b, Gecode::ICL_DEF);
00194          else
00195            Gecode::linear(home, a, y, irt, c, b, Gecode::ICL_DEF);
00196        }
00197      };
00198 
00200      class BoolVar : public Test {
00201      protected:
00203        Gecode::IntArgs a;
00205        Gecode::IntRelType irt;
00206      public:
00208        BoolVar(const std::string& s,
00209                int min, int max, const Gecode::IntArgs& a0,
00210                Gecode::IntRelType irt0)
00211          : Test("Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1,
00212                 min,max,true),
00213            a(a0), irt(irt0) {}
00215        virtual bool solution(const Assignment& x) const {
00216          int n=x.size()-1;
00217          for (int i=0; i<n; i++)
00218            if ((x[i] < 0) || (x[i] > 1))
00219              return false;
00220          double e = 0.0;
00221          for (int i=0; i<n; i++)
00222            e += a[i]*x[i];
00223          return cmp(e, irt, static_cast<double>(x[n]));
00224        }
00226        virtual bool ignore(const Assignment& x) const {
00227          for (int i=x.size()-1; i--; )
00228            if ((x[i] < 0) || (x[i] > 1))
00229              return true;
00230          return false;
00231        }
00233        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00234          int n=x.size()-1;
00235          Gecode::BoolVarArgs y(n);
00236          for (int i=n; i--; )
00237            y[i]=Gecode::channel(home,x[i]);
00238          if (one(a))
00239            Gecode::linear(home, y, irt, x[n]);
00240          else
00241            Gecode::linear(home, a, y, irt, x[n]);
00242        }
00244        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00245                          Gecode::BoolVar b) {
00246          int n=x.size()-1;
00247          Gecode::BoolVarArgs y(n);
00248          for (int i=n; i--; )
00249            y[i]=Gecode::channel(home,x[i]);
00250          if (one(a))
00251            Gecode::linear(home, y, irt, x[n], b);
00252          else
00253            Gecode::linear(home, a, y, irt, x[n], b);
00254        }
00255      };
00256 
00258      class Create {
00259      public:
00261        Create(void) {
00262          using namespace Gecode;
00263          {
00264            IntSet d1(-2,2);
00265            const int dv2[] = {-4,-1,0,1,4};
00266            IntSet d2(dv2,5);
00267 
00268            const int dv3[] = {0,1500000000};
00269            IntSet d3(dv3,2);
00270 
00271            IntArgs a1(1, 0);
00272 
00273            for (IntRelTypes irts; irts(); ++irts) {
00274              (void) new IntInt("11",d1,a1,irts.irt(),0);
00275              (void) new IntVar("11",d1,a1,irts.irt());
00276              (void) new IntInt("21",d2,a1,irts.irt(),0);
00277              (void) new IntVar("21",d2,a1,irts.irt());
00278              (void) new IntInt("31",d3,a1,irts.irt(),150000000);
00279            }
00280            (void) new IntInt("11",d1,a1,IRT_EQ,0,ICL_DOM);
00281            (void) new IntVar("11",d1,a1,IRT_EQ,ICL_DOM);
00282            (void) new IntInt("21",d2,a1,IRT_EQ,0,ICL_DOM);
00283            (void) new IntVar("21",d2,a1,IRT_EQ,ICL_DOM);
00284 
00285            const int av2[5] = {1,1,1,1,1};
00286            const int av3[5] = {1,-1,-1,1,-1};
00287            const int av4[5] = {2,3,5,7,11};
00288            const int av5[5] = {-2,3,-5,7,-11};
00289 
00290            for (int i=1; i<=5; i++) {
00291              IntArgs a2(i, av2);
00292              IntArgs a3(i, av3);
00293              IntArgs a4(i, av4);
00294              IntArgs a5(i, av5);
00295              for (IntRelTypes irts; irts(); ++irts) {
00296                (void) new IntInt("12",d1,a2,irts.irt(),0);
00297                (void) new IntInt("13",d1,a3,irts.irt(),0);
00298                (void) new IntInt("14",d1,a4,irts.irt(),0);
00299                (void) new IntInt("15",d1,a5,irts.irt(),0);
00300                (void) new IntInt("22",d2,a2,irts.irt(),0);
00301                (void) new IntInt("23",d2,a3,irts.irt(),0);
00302                (void) new IntInt("24",d2,a4,irts.irt(),0);
00303                (void) new IntInt("25",d2,a5,irts.irt(),0);
00304                (void) new IntInt("32",d3,a2,irts.irt(),1500000000);
00305                if (i < 5) {
00306                  (void) new IntVar("12",d1,a2,irts.irt());
00307                  (void) new IntVar("13",d1,a3,irts.irt());
00308                  (void) new IntVar("14",d1,a4,irts.irt());
00309                  (void) new IntVar("15",d1,a5,irts.irt());
00310                  (void) new IntVar("22",d2,a2,irts.irt());
00311                  (void) new IntVar("23",d2,a3,irts.irt());
00312                  (void) new IntVar("24",d2,a4,irts.irt());
00313                  (void) new IntVar("25",d2,a5,irts.irt());
00314                }
00315              }
00316              (void) new IntInt("12",d1,a2,IRT_EQ,0,ICL_DOM);
00317              (void) new IntInt("13",d1,a3,IRT_EQ,0,ICL_DOM);
00318              (void) new IntInt("14",d1,a4,IRT_EQ,0,ICL_DOM);
00319              (void) new IntInt("15",d1,a5,IRT_EQ,0,ICL_DOM);
00320              (void) new IntInt("22",d2,a2,IRT_EQ,0,ICL_DOM);
00321              (void) new IntInt("23",d2,a3,IRT_EQ,0,ICL_DOM);
00322              (void) new IntInt("24",d2,a4,IRT_EQ,0,ICL_DOM);
00323              (void) new IntInt("25",d2,a5,IRT_EQ,0,ICL_DOM);
00324              if (i < 4) {
00325                (void) new IntVar("12",d1,a2,IRT_EQ,ICL_DOM);
00326                (void) new IntVar("13",d1,a3,IRT_EQ,ICL_DOM);
00327                (void) new IntVar("14",d1,a4,IRT_EQ,ICL_DOM);
00328                (void) new IntVar("15",d1,a5,IRT_EQ,ICL_DOM);
00329              }
00330            }
00331          }
00332          {
00333            const int av1[10] = { 
00334              1, 1, 1, 1, 1, 1, 1, 1, 1, 1
00335            };
00336            const int av2[10] = {
00337              -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
00338            };
00339 
00340            for (int i=1; i<=10; i += 3) {
00341              IntArgs a1(i, av1);
00342              IntArgs a2(i, av2);
00343              for (int c=0; c<=6; c++)
00344                for (IntRelTypes irts; irts(); ++irts) {
00345                  (void) new BoolInt("1",a1,irts.irt(),c);
00346                  (void) new BoolInt("2",a2,irts.irt(),-c);
00347                }
00348            }
00349 
00350            IntArgs a3(5, 1,2,3,4,5);
00351            IntArgs a4(5, -1,-2,-3,-4,-5);
00352            IntArgs a5(5, -1,-2,1,2,4);
00353 
00354            for (IntRelTypes irts; irts(); ++irts) {
00355              for (int c=0; c<=16; c++) {
00356                (void) new BoolInt("3",a3,irts.irt(),c);
00357                (void) new BoolInt("4",a4,irts.irt(),-c);
00358                (void) new BoolInt("5",a5,irts.irt(),c);
00359                (void) new BoolInt("6",a5,irts.irt(),-c);
00360              }
00361            }
00362 
00363            for (int i=1; i<=5; i += 2) {
00364              IntArgs a1(i, av1);
00365              IntArgs a2(i, av2);
00366              for (IntRelTypes irts; irts(); ++irts) {
00367                (void) new BoolVar("1::"+Test::str(i),0,5,a1,irts.irt());
00368                (void) new BoolVar("2::"+Test::str(i),-5,0,a2,irts.irt());
00369              }
00370            }
00371 
00372            IntArgs a6(4, 1,2,3,4);
00373            IntArgs a7(4, -1,-2,-3,-4);
00374            IntArgs a8(4, -1,-2,1,2);
00375            IntArgs a9(6, -1,-2,1,2,-3,3);
00376 
00377            for (IntRelTypes irts; irts(); ++irts) {
00378              (void) new BoolVar("6",0,10,a6,irts.irt());
00379              (void) new BoolVar("7",-10,0,a7,irts.irt());
00380              (void) new BoolVar("8",-3,3,a8,irts.irt());
00381              (void) new BoolVar("9",-3,3,a9,irts.irt());
00382            }
00383 
00384          }
00385        }
00386      };
00387 
00388      Create c;
00390 
00391    }
00392 }}
00393 
00394 // STATISTICS: test-int