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
00063 rel(*this, x, IRT_LE);
00064 rel(*this, y, IRT_LE);
00065
00066 rel(*this, x[0], IRT_LE, y[0]);
00067
00068 IntVarArgs xy(2*n);
00069 for (int i = n; i--; ) {
00070 xy[i] = x[i]; xy[n+i] = y[i];
00071 }
00072 distinct(*this, xy, opt.icl());
00073
00074 IntArgs c(2*n);
00075 for (int i = n; i--; ) {
00076 c[i] = 1; c[n+i] = -1;
00077 }
00078 linear(*this, c, xy, IRT_EQ, 0);
00079
00080
00081 IntVarArgs sxy(2*n), sx(n), sy(n);
00082
00083 for (int i = n; i--; ) {
00084 sx[i] = sxy[i] = expr(*this, sqr(x[i]));
00085 sy[i] = sxy[n+i] = expr(*this, sqr(y[i]));
00086 }
00087 linear(*this, c, sxy, IRT_EQ, 0);
00088
00089
00090 linear(*this, x, IRT_EQ, 2*n*(2*n+1)/4);
00091 linear(*this, y, IRT_EQ, 2*n*(2*n+1)/4);
00092 linear(*this, sx, IRT_EQ, 2*n*(2*n+1)*(4*n+1)/12);
00093 linear(*this, sy, IRT_EQ, 2*n*(2*n+1)*(4*n+1)/12);
00094
00095 branch(*this, xy, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
00096 }
00097
00099 Partition(bool share, Partition& s) : Script(share,s) {
00100 x.update(*this, share, s.x);
00101 y.update(*this, share, s.y);
00102 }
00104 virtual Space*
00105 copy(bool share) {
00106 return new Partition(share,*this);
00107 }
00109 virtual void
00110 print(std::ostream& os) const {
00111 os << "\t";
00112 int a, b;
00113 a = b = 0;
00114 for (int i = 0; i < x.size(); i++) {
00115 a += x[i].val();
00116 b += x[i].val()*x[i].val();
00117 os << x[i] << ", ";
00118 }
00119 os << " = " << a << ", " << b << std::endl << "\t";
00120 a = b = 0;
00121 for (int i = 0; i < y.size(); i++) {
00122 a += y[i].val();
00123 b += y[i].val()*y[i].val();
00124 os << y[i] << ", ";
00125 }
00126 os << " = " << a << ", " << b << std::endl;
00127 }
00128 };
00129
00134 int
00135 main(int argc, char* argv[]) {
00136 SizeOptions opt("Partition");
00137 opt.size(32);
00138 opt.icl(ICL_BND);
00139 opt.parse(argc,argv);
00140 Script::run<Partition,DFS,SizeOptions>(opt);
00141 return 0;
00142 }
00143
00144
00145
00146