Gecode element约束使用INT_VAL_RAND时大间隔元素致程序挂起问题

问题现象 #

• 仅在使用INT_VAL_RAND分支策略时程序出现挂起，INT_VAL_MIN可正常运行（通过宏USE_MIN_BRANCHING=0/1控制）；
• 强制Gecode仅使用单个索引值时程序恢复正常（通过宏FORCE_SINGLE_IDX=0/1控制）；
• 元素范围间隔较小时程序运行正常（通过宏DELTA控制，如取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;
}

编译运行命令 #

假设环境变量GECODE_HOME指向Gecode安装目录：

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

问题原因分析 #

核心问题在于分支变量的选择顺序和分支策略的特性：

1. INT_VAL_MIN正常的原因：该策略从变量域的最小值开始分支。对于a来说，其有效域是两个不相交的小范围（如1000000000~1000000007和2000000000~2000000007），最小值落在第一个有效区间内。此时约束传播会立刻推导出idx只能是0，后续分支都在有效域内进行，搜索效率极高。
2. INT_VAL_RAND挂起的原因：该策略随机选择a的域值。当DELTA很大时，两个有效区间之间的无效范围（如1000000008~1999999999）远大于有效区间，随机选中无效值的概率几乎是100%。每次选中无效值后，约束传播才会发现矛盾并回溯，但大量的无效分支会导致搜索树爆炸，程序陷入无休止的回溯循环，表现为挂起。
3. FORCE_SINGLE_IDX=1正常的原因：固定idx后，a的域被限制在单个有效小区间内，随机选值几乎都是有效的，不会产生大量无效分支。
4. DELTA较小时正常的原因：两个有效区间间隔小，无效范围占比低，随机选中无效值的概率低，无效分支数量可控，程序能较快完成搜索。

解决建议 #

• 调整分支顺序：优先对离散变量idx进行分支，再分支a。无论采用何种分支策略，先确定idx后，a的域会被限制在对应小区间内，避免无效值的随机选择。
• 优化a的初始域：在初始化a时，直接将其域设置为所有有效区间的并集（而非全局最小到最大），这样INT_VAL_RAND只会在有效域内选值，不会产生无效分支。
• 选择更合适的分支策略：对于大域变量，可使用如INT_VAL_SPLIT_MIN或INT_VAL_SPLIT_MAX等分割式分支策略，避免随机选中无效值。

内容的提问来源于stack exchange，提问作者Krishna