Why can't one clone a `Space` in Gecode before solving the original one?

203 views Asked by At

I'm looking for a way to copy Space instances in Gecode and then analyze the difference between the spaces later.

However it goes already wrong after the first copy. When one copies the code in the book Modelling and Programming in Gecode, as shown here below, and simply modifies it such that a copy is made first (SendMoreMoney* smm = m->copy(true);), one gets a Segmentation fault, regardless whether the shared option is true or false.

#include <gecode/int.hh>
#include <gecode/search.hh>

using namespace Gecode;

class SendMoreMoney : public Space {
protected:
  IntVarArray l;
public:
  SendMoreMoney(void) : l(*this, 8, 0, 9) {
    IntVar s(l[0]), e(l[1]), n(l[2]), d(l[3]),
           m(l[4]), o(l[5]), r(l[6]), y(l[7]);
    // no leading zeros
    rel(*this, s, IRT_NQ, 0);
    rel(*this, m, IRT_NQ, 0);
    // all letters distinct
    distinct(*this, l);
    // linear equation
    IntArgs c(4+4+5); IntVarArgs x(4+4+5);
    c[0]=1000; c[1]=100; c[2]=10; c[3]=1;
    x[0]=s;    x[1]=e;   x[2]=n;  x[3]=d;
    c[4]=1000; c[5]=100; c[6]=10; c[7]=1;
    x[4]=m;    x[5]=o;   x[6]=r;  x[7]=e;
    c[8]=-10000; c[9]=-1000; c[10]=-100; c[11]=-10; c[12]=-1;
    x[8]=m;      x[9]=o;     x[10]=n;    x[11]=e;   x[12]=y;
    linear(*this, c, x, IRT_EQ, 0);
    // post branching
    branch(*this, l, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
  }
  // search support
  SendMoreMoney(bool share, SendMoreMoney& s) : Space(share, s) {
    l.update(*this, share, s.l);
  }
  virtual SendMoreMoney* copy(bool share) {
    return new SendMoreMoney(share,*this);
  }
  // print solution
  void print(void) const {
    std::cout << l << std::endl;
  }
};

// main function
int main(int argc, char* argv[]) {
  // create model and search engine
  SendMoreMoney* m = new SendMoreMoney;
  SendMoreMoney* mc = m->copy(true);
  DFS<SendMoreMoney> e(m);
  delete m;
  // search and print all solutions
  while (SendMoreMoney* s = e.next()) {
    s->print(); delete s;
  }
  return 0;
}

How can one make a real copy?

3

There are 3 answers

0
willeM_ Van Onsem On

As a workaround, one can create a totally independent space and then use equality constraints on the variable level to reduce the domains of these variables.

Example:

void cloneHalfValues(SendMoreMoney* origin) {
    int n = l.size();
    for(int i = 0x00; i < n/2; i++) {
        if(origin->l[i].assigned()) {
            rel(*this, l[i], IRT_EQ, origin->l[i].val());
        }
    }
}

The reason why one can't clone a Space is however still a mystery.

0
Anonymous On

You have to call status() on the Space first.

0
Nick Porubsky On

I found this exchange in the Gecode mailing list archives: https://www.gecode.org/users-archive/2006-March/000439.html

It would seem that internally, Gecode uses the copy function and constructor for its own internal purposes, so to make a "copy-by-value" copy of a space, you need to use the clone() function defined in the Space interface. However, as noted in @Anonymous answer, you need to call status() before calling clone or it will throw an exception of type SpaceNotStable

I augmented my space with the function below to automatically call status, make the clone, and return a pointer of my derived type:

struct Example : public Space {
    ...
    Example * cast_clone() {
        status();
        return static_cast<Example *>(this->clone());
    }
    ...
}