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: 2009-01-20 23:44:27 +0100 (Tue, 20 Jan 2009) $ by $Author: schulte $
00011  *     $Revision: 8082 $
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          : Test("Linear::Bool::Int::"+
00162                 str(irt0)+"::"+s+"::"+str(a0.size())+"::"+str(c0),
00163                 a0.size(),0,1,true,Gecode::ICL_DEF),
00164            a(a0), irt(irt0), c(c0) {}
00166        virtual bool solution(const Assignment& x) const {
00167          double e = 0.0;
00168          for (int i=0; i<x.size(); i++)
00169            e += a[i]*x[i];
00170          return cmp(e, irt, static_cast<double>(c));
00171        }
00173        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00174          Gecode::BoolVarArgs y(x.size());
00175          for (int i=x.size(); i--; )
00176            y[i]=Gecode::channel(home,x[i]);
00177          if (one(a))
00178            Gecode::linear(home, y, irt, c, Gecode::ICL_DEF);
00179          else
00180            Gecode::linear(home, a, y, irt, c, Gecode::ICL_DEF);
00181        }
00183        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00184                          Gecode::BoolVar b) {
00185          Gecode::BoolVarArgs y(x.size());
00186          for (int i=x.size(); i--; )
00187            y[i]=Gecode::channel(home,x[i]);
00188          if (one(a))
00189            Gecode::linear(home, y, irt, c, b, Gecode::ICL_DEF);
00190          else
00191            Gecode::linear(home, a, y, irt, c, b, Gecode::ICL_DEF);
00192        }
00193      };
00194 
00196      class BoolVar : public Test {
00197      protected:
00199        Gecode::IntArgs a;
00201        Gecode::IntRelType irt;
00202      public:
00204        BoolVar(const std::string& s,
00205                int min, int max, const Gecode::IntArgs& a0,
00206                Gecode::IntRelType irt0)
00207          : Test("Linear::Bool::Var::"+str(irt0)+"::"+s,a0.size()+1,
00208                 min,max,true),
00209            a(a0), irt(irt0) {}
00211        virtual bool solution(const Assignment& x) const {
00212          int n=x.size()-1;
00213          for (int i=0; i<n; i++)
00214            if ((x[i] < 0) || (x[i] > 1))
00215              return false;
00216          double e = 0.0;
00217          for (int i=0; i<n; i++)
00218            e += a[i]*x[i];
00219          return cmp(e, irt, static_cast<double>(x[n]));
00220        }
00222        virtual bool ignore(const Assignment& x) const {
00223          for (int i=x.size()-1; i--; )
00224            if ((x[i] < 0) || (x[i] > 1))
00225              return true;
00226          return false;
00227        }
00229        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00230          int n=x.size()-1;
00231          Gecode::BoolVarArgs y(n);
00232          for (int i=n; i--; )
00233            y[i]=Gecode::channel(home,x[i]);
00234          if (one(a))
00235            Gecode::linear(home, y, irt, x[n]);
00236          else
00237            Gecode::linear(home, a, y, irt, x[n]);
00238        }
00240        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x,
00241                          Gecode::BoolVar b) {
00242          int n=x.size()-1;
00243          Gecode::BoolVarArgs y(n);
00244          for (int i=n; i--; )
00245            y[i]=Gecode::channel(home,x[i]);
00246          if (one(a))
00247            Gecode::linear(home, y, irt, x[n], b);
00248          else
00249            Gecode::linear(home, a, y, irt, x[n], b);
00250        }
00251      };
00252 
00254      class Create {
00255      public:
00257        Create(void) {
00258          using namespace Gecode;
00259          {
00260            IntSet d1(-2,2);
00261            const int dv2[] = {-4,-1,0,1,4};
00262            IntSet d2(dv2,5);
00263 
00264            IntArgs a1(1, 0);
00265 
00266            for (IntRelTypes irts; irts(); ++irts) {
00267              (void) new IntInt("11",d1,a1,irts.irt());
00268              (void) new IntVar("11",d1,a1,irts.irt());
00269              (void) new IntInt("21",d2,a1,irts.irt());
00270              (void) new IntVar("21",d2,a1,irts.irt());
00271            }
00272            (void) new IntInt("11",d1,a1,IRT_EQ,ICL_DOM);
00273            (void) new IntVar("11",d1,a1,IRT_EQ,ICL_DOM);
00274            (void) new IntInt("21",d2,a1,IRT_EQ,ICL_DOM);
00275            (void) new IntVar("21",d2,a1,IRT_EQ,ICL_DOM);
00276 
00277            const int av2[5] = {1,1,1,1,1};
00278            const int av3[5] = {1,-1,-1,1,-1};
00279            const int av4[5] = {2,3,5,7,11};
00280            const int av5[5] = {-2,3,-5,7,-11};
00281 
00282            for (int i=1; i<=5; i++) {
00283              IntArgs a2(i, av2);
00284              IntArgs a3(i, av3);
00285              IntArgs a4(i, av4);
00286              IntArgs a5(i, av5);
00287              for (IntRelTypes irts; irts(); ++irts) {
00288                (void) new IntInt("12",d1,a2,irts.irt());
00289                (void) new IntInt("13",d1,a3,irts.irt());
00290                (void) new IntInt("14",d1,a4,irts.irt());
00291                (void) new IntInt("15",d1,a5,irts.irt());
00292                (void) new IntInt("22",d2,a2,irts.irt());
00293                (void) new IntInt("23",d2,a3,irts.irt());
00294                (void) new IntInt("24",d2,a4,irts.irt());
00295                (void) new IntInt("25",d2,a5,irts.irt());
00296                if (i < 5) {
00297                  (void) new IntVar("12",d1,a2,irts.irt());
00298                  (void) new IntVar("13",d1,a3,irts.irt());
00299                  (void) new IntVar("14",d1,a4,irts.irt());
00300                  (void) new IntVar("15",d1,a5,irts.irt());
00301                  (void) new IntVar("22",d2,a2,irts.irt());
00302                  (void) new IntVar("23",d2,a3,irts.irt());
00303                  (void) new IntVar("24",d2,a4,irts.irt());
00304                  (void) new IntVar("25",d2,a5,irts.irt());
00305                }
00306              }
00307              (void) new IntInt("12",d1,a2,IRT_EQ,ICL_DOM);
00308              (void) new IntInt("13",d1,a3,IRT_EQ,ICL_DOM);
00309              (void) new IntInt("14",d1,a4,IRT_EQ,ICL_DOM);
00310              (void) new IntInt("15",d1,a5,IRT_EQ,ICL_DOM);
00311              (void) new IntInt("22",d2,a2,IRT_EQ,ICL_DOM);
00312              (void) new IntInt("23",d2,a3,IRT_EQ,ICL_DOM);
00313              (void) new IntInt("24",d2,a4,IRT_EQ,ICL_DOM);
00314              (void) new IntInt("25",d2,a5,IRT_EQ,ICL_DOM);
00315              if (i < 4) {
00316                (void) new IntVar("12",d1,a2,IRT_EQ,ICL_DOM);
00317                (void) new IntVar("13",d1,a3,IRT_EQ,ICL_DOM);
00318                (void) new IntVar("14",d1,a4,IRT_EQ,ICL_DOM);
00319                (void) new IntVar("15",d1,a5,IRT_EQ,ICL_DOM);
00320              }
00321            }
00322          }
00323          {
00324            const int av1[10] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
00325            const int av2[10] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
00326 
00327            for (int i=1; i<=10; i += 3) {
00328              IntArgs a1(i, av1);
00329              IntArgs a2(i, av2);
00330              for (int c=0; c<=6; c += 3)
00331                for (IntRelTypes irts; irts(); ++irts) {
00332                  (void) new BoolInt("1",a1,irts.irt(),c);
00333                  (void) new BoolInt("2",a2,irts.irt(),-c);
00334                }
00335            }
00336 
00337            IntArgs a3(5, 1,2,3,4,5);
00338            IntArgs a4(5, -1,-2,-3,-4,-5);
00339            IntArgs a5(5, -1,-2,1,2,4);
00340 
00341            for (int c=0; c<=16; c++)
00342              for (IntRelTypes irts; irts(); ++irts) {
00343                (void) new BoolInt("3",a3,irts.irt(),c);
00344                (void) new BoolInt("4",a4,irts.irt(),-c);
00345                (void) new BoolInt("5",a5,irts.irt(),c);
00346                (void) new BoolInt("6",a5,irts.irt(),-c);
00347              }
00348 
00349 
00350            for (int i=1; i<=5; i += 2) {
00351              IntArgs a1(i, av1);
00352              IntArgs a2(i, av2);
00353              for (IntRelTypes irts; irts(); ++irts) {
00354                (void) new BoolVar("1::"+Test::str(i),0,5,a1,irts.irt());
00355                (void) new BoolVar("2::"+Test::str(i),-5,0,a2,irts.irt());
00356              }
00357            }
00358 
00359            IntArgs a6(4, 1,2,3,4);
00360            IntArgs a7(4, -1,-2,-3,-4);
00361            IntArgs a8(4, -1,-2,1,2);
00362            IntArgs a9(6, -1,-2,1,2,-3,3);
00363 
00364            for (IntRelTypes irts; irts(); ++irts) {
00365              (void) new BoolVar("6",0,10,a6,irts.irt());
00366              (void) new BoolVar("7",-10,0,a7,irts.irt());
00367              (void) new BoolVar("8",-3,3,a8,irts.irt());
00368              (void) new BoolVar("9",-3,3,a9,irts.irt());
00369            }
00370 
00371          }
00372        }
00373      };
00374 
00375      Create c;
00377 
00378    }
00379 }}
00380 
00381 // STATISTICS: test-int