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