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