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