Generated on Thu Apr 11 13:58:59 2019 for Gecode by doxygen 1.6.3

linear.cpp

Go to the documentation of this file.
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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include "test/int.hh"
00035 
00036 #include <gecode/minimodel.hh>
00037 
00038 namespace Test { namespace Int {
00039 
00041    namespace Linear {
00042 
00044      bool one(const Gecode::IntArgs& a) {
00045       for (int i=a.size(); i--; )
00046         if (a[i] != 1)
00047           return false;
00048       return true;
00049     }
00050 
00056 
00057      class IntInt : public Test {
00058      protected:
00060        Gecode::IntArgs a;
00062        Gecode::IntRelType irt;
00064        int c;
00065      public:
00067        IntInt(const std::string& s, const Gecode::IntSet& d,
00068               const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
00069               int c0, Gecode::IntPropLevel ipl=Gecode::IPL_BND)
00070          : Test("Linear::Int::Int::"+
00071                 str(irt0)+"::"+str(ipl)+"::"+s+"::"+str(c0)+"::"
00072                 +str(a0.size()),
00073                 a0.size(),d,ipl != Gecode::IPL_DOM,ipl),
00074          a(a0), irt(irt0), c(c0) {
00075          testfix=false;
00076        }
00078        virtual bool solution(const Assignment& x) const {
00079          double e = 0.0;
00080          for (int i=0; i<x.size(); i++)
00081            e += a[i]*x[i];
00082          return cmp(e, irt, static_cast<double>(c));
00083        }
00085        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00086          if (one(a))
00087            Gecode::linear(home, x, irt, c, ipl);
00088          else
00089            Gecode::linear(home, a, x, irt, c, ipl);
00090        }
00092        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00093                          Gecode::Reify r) {
00094          if (one(a))
00095            Gecode::linear(home, x, irt, c, r, ipl);
00096          else
00097            Gecode::linear(home, a, x, irt, c, r, ipl);
00098        }
00099      };
00100 
00102      class IntVar : public Test {
00103      protected:
00105        Gecode::IntArgs a;
00107        Gecode::IntRelType irt;
00108      public:
00110        IntVar(const std::string& s, const Gecode::IntSet& d,
00111               const Gecode::IntArgs& a0, Gecode::IntRelType irt0,
00112               Gecode::IntPropLevel ipl=Gecode::IPL_BND)
00113          : Test("Linear::Int::Var::"+
00114                 str(irt0)+"::"+str(ipl)+"::"+s+"::"+str(a0.size()),
00115                 a0.size()+1,d,ipl != Gecode::IPL_DOM,ipl),
00116            a(a0), irt(irt0) {
00117          testfix=false;
00118        }
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], ipl);
00134          else
00135            Gecode::linear(home, a, y, irt, x[n], ipl);
00136        }
00138        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00139                          Gecode::Reify r) {
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], r, ipl);
00146          else
00147            Gecode::linear(home, a, y, irt, x[n], r, ipl);
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::IPL_DEF),
00167            a(a0), irt(irt0), c(c0) {
00168          testfix=false;
00169        }
00171        virtual bool solution(const Assignment& x) const {
00172          double e = 0.0;
00173          for (int i=0; i<x.size(); i++)
00174            e += a[i]*x[i];
00175          return cmp(e, irt, static_cast<double>(c));
00176        }
00178        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00179          Gecode::BoolVarArgs y(x.size());
00180          for (int i=x.size(); i--; )
00181            y[i]=Gecode::channel(home,x[i]);
00182          if (one(a))
00183            Gecode::linear(home, y, irt, c, Gecode::IPL_DEF);
00184          else
00185            Gecode::linear(home, a, y, irt, c, Gecode::IPL_DEF);
00186        }
00188        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00189                          Gecode::Reify r) {
00190          Gecode::BoolVarArgs y(x.size());
00191          for (int i=x.size(); i--; )
00192            y[i]=Gecode::channel(home,x[i]);
00193          if (one(a))
00194            Gecode::linear(home, y, irt, c, r, Gecode::IPL_DEF);
00195          else
00196            Gecode::linear(home, a, y, irt, c, r, Gecode::IPL_DEF);
00197        }
00198      };
00199 
00201      class BoolVar : public Test {
00202      protected:
00204        Gecode::IntArgs a;
00206        Gecode::IntRelType irt;
00207      public:
00209        BoolVar(const std::string& s,
00210                int min, int max, const Gecode::IntArgs& a0,
00211                Gecode::IntRelType irt0)
00212          : Test("Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1,
00213                 min,max,true),
00214            a(a0), irt(irt0) {
00215          testfix=false;
00216        }
00218        virtual bool solution(const Assignment& x) const {
00219          int n=x.size()-1;
00220          for (int i=0; i<n; i++)
00221            if ((x[i] < 0) || (x[i] > 1))
00222              return false;
00223          double e = 0.0;
00224          for (int i=0; i<n; i++)
00225            e += a[i]*x[i];
00226          return cmp(e, irt, static_cast<double>(x[n]));
00227        }
00229        virtual bool ignore(const Assignment& x) const {
00230          for (int i=x.size()-1; i--; )
00231            if ((x[i] < 0) || (x[i] > 1))
00232              return true;
00233          return false;
00234        }
00236        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00237          int n=x.size()-1;
00238          Gecode::BoolVarArgs y(n);
00239          for (int i=n; i--; )
00240            y[i]=Gecode::channel(home,x[i]);
00241          if (one(a))
00242            Gecode::linear(home, y, irt, x[n]);
00243          else
00244            Gecode::linear(home, a, y, irt, x[n]);
00245        }
00247        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00248                          Gecode::Reify r) {
00249          int n=x.size()-1;
00250          Gecode::BoolVarArgs y(n);
00251          for (int i=n; i--; )
00252            y[i]=Gecode::channel(home,x[i]);
00253          if (one(a))
00254            Gecode::linear(home, y, irt, x[n], r);
00255          else
00256            Gecode::linear(home, a, y, irt, x[n], r);
00257        }
00258      };
00259 
00261      class Create {
00262      public:
00264        Create(void) {
00265          using namespace Gecode;
00266          {
00267            IntSet d1(-2,2);
00268            const int dv2[] = {-4,-1,0,1,4};
00269            IntSet d2(dv2,5);
00270 
00271            const int dv3[] = {0,1500000000};
00272            IntSet d3(dv3,2);
00273 
00274            IntArgs a1({0});
00275 
00276            for (IntRelTypes irts; irts(); ++irts) {
00277              (void) new IntInt("11",d1,a1,irts.irt(),0);
00278              (void) new IntVar("11",d1,a1,irts.irt());
00279              (void) new IntInt("21",d2,a1,irts.irt(),0);
00280              (void) new IntVar("21",d2,a1,irts.irt());
00281              (void) new IntInt("31",d3,a1,irts.irt(),150000000);
00282            }
00283            (void) new IntInt("11",d1,a1,IRT_EQ,0,IPL_DOM);
00284            (void) new IntVar("11",d1,a1,IRT_EQ,IPL_DOM);
00285            (void) new IntInt("21",d2,a1,IRT_EQ,0,IPL_DOM);
00286            (void) new IntVar("21",d2,a1,IRT_EQ,IPL_DOM);
00287 
00288            const int av2[5] = {1,1,1,1,1};
00289            const int av3[5] = {1,-1,-1,1,-1};
00290            const int av4[5] = {2,3,5,7,11};
00291            const int av5[5] = {-2,3,-5,7,-11};
00292 
00293 
00294            for (int i=1; i<=5; i++) {
00295              IntArgs a2(i, av2);
00296              IntArgs a3(i, av3);
00297              IntArgs a4(i, av4);
00298              IntArgs a5(i, av5);
00299              for (IntRelTypes irts; irts(); ++irts) {
00300                (void) new IntInt("12",d1,a2,irts.irt(),0);
00301                (void) new IntInt("13",d1,a3,irts.irt(),0);
00302                (void) new IntInt("14",d1,a4,irts.irt(),0);
00303                (void) new IntInt("15",d1,a5,irts.irt(),0);
00304                (void) new IntInt("22",d2,a2,irts.irt(),0);
00305                (void) new IntInt("23",d2,a3,irts.irt(),0);
00306                (void) new IntInt("24",d2,a4,irts.irt(),0);
00307                (void) new IntInt("25",d2,a5,irts.irt(),0);
00308                (void) new IntInt("32",d3,a2,irts.irt(),1500000000);
00309                if (i < 5) {
00310                  (void) new IntVar("12",d1,a2,irts.irt());
00311                  (void) new IntVar("13",d1,a3,irts.irt());
00312                  (void) new IntVar("14",d1,a4,irts.irt());
00313                  (void) new IntVar("15",d1,a5,irts.irt());
00314                  (void) new IntVar("22",d2,a2,irts.irt());
00315                  (void) new IntVar("23",d2,a3,irts.irt());
00316                  (void) new IntVar("24",d2,a4,irts.irt());
00317                  (void) new IntVar("25",d2,a5,irts.irt());
00318                }
00319              }
00320              (void) new IntInt("12",d1,a2,IRT_EQ,0,IPL_DOM);
00321              (void) new IntInt("13",d1,a3,IRT_EQ,0,IPL_DOM);
00322              (void) new IntInt("14",d1,a4,IRT_EQ,0,IPL_DOM);
00323              (void) new IntInt("15",d1,a5,IRT_EQ,0,IPL_DOM);
00324              (void) new IntInt("22",d2,a2,IRT_EQ,0,IPL_DOM);
00325              (void) new IntInt("23",d2,a3,IRT_EQ,0,IPL_DOM);
00326              (void) new IntInt("24",d2,a4,IRT_EQ,0,IPL_DOM);
00327              (void) new IntInt("25",d2,a5,IRT_EQ,0,IPL_DOM);
00328              if (i < 4) {
00329                (void) new IntVar("12",d1,a2,IRT_EQ,IPL_DOM);
00330                (void) new IntVar("13",d1,a3,IRT_EQ,IPL_DOM);
00331                (void) new IntVar("14",d1,a4,IRT_EQ,IPL_DOM);
00332                (void) new IntVar("15",d1,a5,IRT_EQ,IPL_DOM);
00333              }
00334            }
00335          }
00336          {
00337            const int av1[10] = {
00338              1, 1, 1, 1, 1, 1, 1, 1, 1, 1
00339            };
00340            const int av2[10] = {
00341              -1,-1,-1,-1,-1,-1,-1,-1,-1,-1
00342            };
00343            
00344            for (int i=1; i<=10; i += 3) {
00345              IntArgs a1(i, av1);
00346              IntArgs a2(i, av2);
00347              for (int c=0; c<=6; c++)
00348                for (IntRelTypes irts; irts(); ++irts) {
00349                  (void) new BoolInt("1",a1,irts.irt(),c);
00350                  (void) new BoolInt("2",a2,irts.irt(),-c);
00351                }
00352            }
00353 
00354            IntArgs a3({1,2,3,4,5});
00355            IntArgs a4({-1,-2,-3,-4,-5});
00356            IntArgs a5({-1,-2,1,2,4});
00357 
00358            for (IntRelTypes irts; irts(); ++irts) {
00359              for (int c=0; c<=16; c++) {
00360                (void) new BoolInt("3",a3,irts.irt(),c);
00361                (void) new BoolInt("4",a4,irts.irt(),-c);
00362                (void) new BoolInt("5",a5,irts.irt(),c);
00363                (void) new BoolInt("6",a5,irts.irt(),-c);
00364              }
00365            }
00366 
00367            for (int i=1; i<=5; i += 2) {
00368              IntArgs a1(i, av1);
00369              IntArgs a2(i, av2);
00370              for (IntRelTypes irts; irts(); ++irts) {
00371                (void) new BoolVar("1::"+Test::str(i),0,5,a1,irts.irt());
00372                (void) new BoolVar("2::"+Test::str(i),-5,0,a2,irts.irt());
00373              }
00374            }
00375 
00376            IntArgs a6({1,2,3,4});
00377            IntArgs a7({-1,-2,-3,-4});
00378            IntArgs a8({-1,-2,1,2});
00379            IntArgs a9({-1,-2,1,2,-3,3});
00380 
00381            for (IntRelTypes irts; irts(); ++irts) {
00382              (void) new BoolVar("6",0,10,a6,irts.irt());
00383              (void) new BoolVar("7",-10,0,a7,irts.irt());
00384              (void) new BoolVar("8",-3,3,a8,irts.irt());
00385              (void) new BoolVar("9",-3,3,a9,irts.irt());
00386            }
00387 
00388          }
00389        }
00390      };
00391 
00392      Create c;
00394 
00395    }
00396 }}
00397 
00398 // STATISTICS: test-int