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 #include <gecode/driver.hh>
00035 #include <gecode/int.hh>
00036 #include <gecode/minimodel.hh>
00037
00038 using namespace Gecode;
00039
00045 class Partition : public Script {
00046 protected:
00048 IntVarArray x;
00050 IntVarArray y;
00051 public:
00053 Partition(const SizeOptions& opt)
00054 : Script(opt),
00055 x(*this,opt.size(),1,2*opt.size()),
00056 y(*this,opt.size(),1,2*opt.size()) {
00057 const int n = opt.size();
00058
00059
00060 rel(*this, x, IRT_LE);
00061 rel(*this, y, IRT_LE);
00062
00063 rel(*this, x[0], IRT_LE, y[0]);
00064
00065 IntVarArgs xy(2*n);
00066 for (int i = n; i--; ) {
00067 xy[i] = x[i]; xy[n+i] = y[i];
00068 }
00069 distinct(*this, xy, opt.ipl());
00070
00071 IntArgs c(2*n);
00072 for (int i = n; i--; ) {
00073 c[i] = 1; c[n+i] = -1;
00074 }
00075 linear(*this, c, xy, IRT_EQ, 0);
00076
00077
00078 IntVarArgs sxy(2*n), sx(n), sy(n);
00079
00080 for (int i = n; i--; ) {
00081 sx[i] = sxy[i] = expr(*this, sqr(x[i]));
00082 sy[i] = sxy[n+i] = expr(*this, sqr(y[i]));
00083 }
00084 linear(*this, c, sxy, IRT_EQ, 0);
00085
00086
00087 linear(*this, x, IRT_EQ, 2*n*(2*n+1)/4);
00088 linear(*this, y, IRT_EQ, 2*n*(2*n+1)/4);
00089 linear(*this, sx, IRT_EQ, 2*n*(2*n+1)*(4*n+1)/12);
00090 linear(*this, sy, IRT_EQ, 2*n*(2*n+1)*(4*n+1)/12);
00091
00092 branch(*this, xy, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
00093 }
00094
00096 Partition(Partition& s) : Script(s) {
00097 x.update(*this, s.x);
00098 y.update(*this, s.y);
00099 }
00101 virtual Space*
00102 copy(void) {
00103 return new Partition(*this);
00104 }
00106 virtual void
00107 print(std::ostream& os) const {
00108 os << "\t";
00109 int a, b;
00110 a = b = 0;
00111 for (int i = 0; i < x.size(); i++) {
00112 a += x[i].val();
00113 b += x[i].val()*x[i].val();
00114 os << x[i] << ", ";
00115 }
00116 os << " = " << a << ", " << b << std::endl << "\t";
00117 a = b = 0;
00118 for (int i = 0; i < y.size(); i++) {
00119 a += y[i].val();
00120 b += y[i].val()*y[i].val();
00121 os << y[i] << ", ";
00122 }
00123 os << " = " << a << ", " << b << std::endl;
00124 }
00125 };
00126
00131 int
00132 main(int argc, char* argv[]) {
00133 SizeOptions opt("Partition");
00134 opt.size(32);
00135 opt.ipl(IPL_BND);
00136 opt.parse(argc,argv);
00137 Script::run<Partition,DFS,SizeOptions>(opt);
00138 return 0;
00139 }
00140
00141
00142
00143