Method Steiner

examples/steiner.cpp:65–130

Actual model

  /// Actual model
  Steiner(const SizeOptions& opt)
    : Script(opt), n(opt.size()), noOfTriples((n*(n-1))/6),
      triples(*this, noOfTriples, IntSet::empty, 1, n, 3U, 3U) {

    for (int i=0; i<noOfTriples; i++) {
      for (int j=i+1; j<noOfTriples; j++) {
        SetVar x = triples[i];
        SetVar y = triples[j];

        SetVar atmostOne(*this,IntSet::empty,1,n,0U,1U);
        rel(*this, (x & y) == atmostOne);

        IntVar x1(*this,1,n);
        IntVar x2(*this,1,n);
        IntVar x3(*this,1,n);
        IntVar y1(*this,1,n);
        IntVar y2(*this,1,n);
        IntVar y3(*this,1,n);

        if (opt.model() == MODEL_NONE) {
          /* Naive alternative:
           * just including the ints in the set
           */
          rel(*this, singleton(x1) <= x);
          rel(*this, singleton(x2) <= x);
          rel(*this, singleton(x3) <= x);
          rel(*this, singleton(y1) <= y);
          rel(*this, singleton(y2) <= y);
          rel(*this, singleton(y3) <= y);

        } else if (opt.model() == MODEL_MATCHING) {
          /* Smart alternative:
           * Using matching constraints
           */

          channelSorted(*this, {x1,x2,x3}, x);
          channelSorted(*this, {y1,y2,y3}, y);
        } else if (opt.model() == MODEL_SEQ) {
          SetVar sx1 = expr(*this, singleton(x1));
          SetVar sx2 = expr(*this, singleton(x2));
          SetVar sx3 = expr(*this, singleton(x3));
          SetVar sy1 = expr(*this, singleton(y1));
          SetVar sy2 = expr(*this, singleton(y2));
          SetVar sy3 = expr(*this, singleton(y3));
          sequence(*this,{sx1,sx2,sx3},x);
          sequence(*this,{sy1,sy2,sy3},y);
        }

        /* Breaking symmetries */
        rel(*this, x1 < x2);
        rel(*this, x2 < x3);
        rel(*this, x1 < x3);

        rel(*this, y1 < y2);
        rel(*this, y2 < y3);
        rel(*this, y1 < y3);

        linear(*this,