Gecode element constraint seems to hang with large seperation between elements

[krishvk]

I am just getting started with Gecode element constraints. It seems to hang when the list elements are too far apart.

Here is the full program to demonstrate the issue, with a few knobs (MACROS) to change the behavior.

1. The issue seems to manifest only when using INT_VAL_RAND, INT_VAL_MIN is working fine (Controllable with Knob USE_MIN_BRANCHING=0/1)
2. If I force Gecode to use only one element, it is again working fine (Controllable with Knob FORCE_SINGLE_IDX=0/1)
3. If I use relatively close ranges, it's working fine (Controllable with Knob DELTA=Say Powers of 10)

#include <iostream>
#include <vector>

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

using namespace std;
typedef unsigned int uint_t;
using namespace Gecode;

class Class : public Space {
public:
  IntVar a, idx;
  inline static IntArgs ranges;
  inline static vector<int> idxes;

  Class() :
  a(*this, Int::Limits::min, Int::Limits::max),
  idx(*this, IntSet(&idxes[0], idxes.size())) {
    if (USE_MIN_BRANCHING) {
      branch(*this, a, INT_VAL_MIN());
      branch(*this, idx, INT_VAL_MIN());
    } else {
      Rnd rndA(rand());
      branch(*this, a, INT_VAL_RND(rndA));

      Rnd rndIdx(rand());
      branch(*this, idx, INT_VAL_RND(rndIdx));
    }

    rel(*this, a >= element(ranges, idx));
    rel(*this, a <= element(ranges, idx + 1));
    if (FORCE_SINGLE_IDX) {
      rel(*this, idx == 2);
    }
  }

  void show() {
    for (IntVarRanges i(a); i(); ++i) {
      cout << "a: " << i.min() << ".." << i.max() << "\n" << flush;
    }
    for (IntVarRanges i(idx); i(); ++i) {
      cout << "idx: " << i.min() << ".." << i.max() << "\n" << flush;
    }
    cout << "-----------------\n" << flush;
  }

  //Search support
  Class(Class& s) : Space(s) {
    a.update(*this, s.a);
    idx.update(*this, s.idx);
  }

  virtual Space* copy(void) {
    return new Class(*this);
  }

  // print solution
  void print() {
    cout << idx.val() << " " << a.val() << "\n" << flush;
  }
};

int main(int argc, char* argv[]) {
    srand(1);

    unsigned int from;
    for (int i=0; i < 2; i++) {
      from = 1000000000 + i * DELTA;
      Class::ranges << from;
      Class::ranges << from + 7;
      Class::idxes.push_back(i << 1);
      cout << "" << from << "\n" << flush;
    }

    // Print all solutions in MIN branching
    Class* c = new Class;
    c->show();
    DFS<Class> e(c);
    delete c;

    while (c = e.next()) {
      c->print();
      delete c;
    }

    return 0;
}

To run (Assuming an envvar GECODE_HOME pointing to the GECODE installation)

g++ -std=c++20 -O3 ./bla.cc -DDELTA=1000000000 -DUSE_MIN_BRANCHING=0 -DFORCE_SINGLE_IDX=0 -I $GECODE_HOME/include -L$GECODE_HOME/lib -lgecodesearch -lgecodeminimodel -lgecodeint -lgecodekernel -lgecodesupport ; ./a.out

Here is the summary of the results

Why is GECODE unable to optimize for large numbers just with INT_VAL_RAND? What am I missing?

PS: The example might not make sense to use a constraint solver, but please note that it is stripped down to demonstrate the issue and there are more variables involved in the actual constraint.

[zayenz]

It is not really the case that Gecode hangs from the element constraint. When you use random branching on the a variable the domain will become very large lists of segments, while branching on the minimum value while keep the domain of the variable as just a couple of segments.

While Gecode (and most constraint programming systems) can handle large domains, it is mostly feasible when the domains are mostly used for bounds.

So closing with a works as intended, and I hope you can solve your larger problem.