00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041
00042 using namespace Gecode;
00043
00049 class Partition : public Script {
00050 protected:
00052 IntVarArray x;
00054 IntVarArray y;
00055 public:
00057 Partition(const SizeOptions& opt)
00058 : x(*this,opt.size(),1,2*opt.size()),
00059 y(*this,opt.size(),1,2*opt.size()) {
00060 const int n = opt.size();
00061
00062 rel(*this, x, IRT_LE);
00063 rel(*this, y, IRT_LE);
00064
00065 rel(*this, x[0], IRT_LE, y[0]);
00066
00067 IntVarArgs xy(2*n);
00068 for (int i = n; i--; ) {
00069 xy[i] = x[i]; xy[n+i] = y[i];
00070 }
00071 distinct(*this, xy, opt.icl());
00072
00073 IntArgs c(2*n);
00074 for (int i = n; i--; ) {
00075 c[i] = 1; c[n+i] = -1;
00076 }
00077 linear(*this, c, xy, IRT_EQ, 0);
00078
00079
00080 IntVarArgs sxy(2*n), sx(n), sy(n);
00081
00082 for (int i = n; i--; ) {
00083 sx[i] = sxy[i] = sqr(*this, x[i]);
00084 sy[i] = sxy[n+i] = sqr(*this, y[i]);
00085 }
00086 linear(*this, c, sxy, IRT_EQ, 0);
00087
00088
00089 linear(*this, x, IRT_EQ, 2*n*(2*n+1)/4);
00090 linear(*this, y, IRT_EQ, 2*n*(2*n+1)/4);
00091 linear(*this, sx, IRT_EQ, 2*n*(2*n+1)*(4*n+1)/12);
00092 linear(*this, sy, IRT_EQ, 2*n*(2*n+1)*(4*n+1)/12);
00093 branch(*this, xy, INT_VAR_SIZE_MIN, INT_VAL_MIN);
00094 }
00095
00097 Partition(bool share, Partition& s) : Script(share,s) {
00098 x.update(*this, share, s.x);
00099 y.update(*this, share, s.y);
00100 }
00102 virtual Space*
00103 copy(bool share) {
00104 return new Partition(share,*this);
00105 }
00107 virtual void
00108 print(std::ostream& os) const {
00109 os << "\t";
00110 int a, b;
00111 a = b = 0;
00112 for (int i = 0; i < x.size(); i++) {
00113 a += x[i].val();
00114 b += x[i].val()*x[i].val();
00115 os << x[i] << ", ";
00116 }
00117 os << " = " << a << ", " << b << std::endl << "\t";
00118 a = b = 0;
00119 for (int i = 0; i < y.size(); i++) {
00120 a += y[i].val();
00121 b += y[i].val()*y[i].val();
00122 os << y[i] << ", ";
00123 }
00124 os << " = " << a << ", " << b << std::endl;
00125 }
00126 };
00127
00132 int
00133 main(int argc, char* argv[]) {
00134 SizeOptions opt("Partition");
00135 opt.size(32);
00136 opt.icl(ICL_BND);
00137 opt.parse(argc,argv);
00138 Script::run<Partition,DFS,SizeOptions>(opt);
00139 return 0;
00140 }
00141
00142
00143
00144