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
00050
00051 class Graph {
00052 public:
00053 const int n_v;
00054 const int n_e;
00055 const int* e;
00056 Graph(const int n_v0, const int n_e0, const int* e0)
00057 : n_v(n_v0), n_e(n_e0), e(e0) {}
00058 };
00059
00060 const int e_20_10[] = {
00061 0, 4, 2,12, 12,14, 18,19, 7,10,
00062 9,12, 5,11, 6,15, 3,18, 7,16
00063 };
00064
00065 const Graph g_20_10(20,10,e_20_10);
00066
00067 const int e_40_20[] = {
00068 21,30, 11,30, 19,38, 20,25, 11,24,
00069 20,33, 8,39, 4, 5, 6,16, 5,32,
00070 0, 9, 5,24, 25,28, 36,38, 14,20,
00071 19,25, 11,22, 13,30, 7,36, 15,33
00072 };
00073
00074 const Graph g_40_20(40, 20, e_40_20);
00076
00077
00084 class IndSet : public IntMaximizeScript {
00085 protected:
00087 const Graph& g;
00089 BoolVarArray v;
00091 IntVar k;
00092 public:
00094 IndSet(const SizeOptions& opt)
00095 : IntMaximizeScript(opt),
00096 g(opt.size() == 0 ? g_20_10 : g_40_20),
00097 v(*this,g.n_v,0,1), k(*this,0,g.n_v) {
00098 const int* e = g.e;
00099 for (int i = g.n_e; i--; ) {
00100 const int* e1 = e++; const int* e2 = e++;
00101 rel(*this, v[*e1], BOT_AND, v[*e2], 0);
00102 }
00103 linear(*this, v, IRT_EQ, k);
00104 branch(*this, v, BOOL_VAR_NONE(), BOOL_VAL_MIN());
00105 }
00106
00108 IndSet(bool share, IndSet& s) : IntMaximizeScript(share,s), g(s.g) {
00109 v.update(*this, share, s.v);
00110 k.update(*this, share, s.k);
00111 }
00113 virtual Space*
00114 copy(bool share) {
00115 return new IndSet(share,*this);
00116 }
00118 virtual void
00119 print(std::ostream& os) const {
00120 os << "\tk = " << k << std::endl
00121 << "\tv[] = " << v << std::endl;
00122 }
00124 virtual IntVar cost(void) const {
00125 return k;
00126 }
00127 };
00128
00129
00133 int
00134 main(int argc, char* argv[]) {
00135 SizeOptions opt("IndSet");
00136 opt.solutions(0);
00137 opt.size(1);
00138 opt.iterations(2000);
00139 opt.parse(argc,argv);
00140 IntMaximizeScript::run<IndSet,BAB,SizeOptions>(opt);
00141 return 0;
00142 }
00143
00144
00145