我正在 GeCode 中实现自定义总和传播器。我试图建模的问题涉及许多总和约束，每个总和约束都可以根据特定问题的启发式进一步传播。所有这些总和的总和表示成本函数。我正在使用分支定界搜索，目的是最小化这个总和，正如您可以想象的那样，我的边界的有效性高度依赖于上述每个自定义总和约束中的传播质量。
我在 IntVarArray 上进行分支，我的自定义 sum 传播器订阅的元素。随着 IntVarArray 中的更多值被分配，我的总和域越窄。每个 sum 传播器订阅特定于给定问题实例的 IntVarArray 子集。这是模型实现构造函数的片段（“exclusiveCostSum”的实现附在下面）：
for (int t=0; t<T-1; t++) {
IntVarArgs overlaps
IntArgs overlap_lines;
// ... Logic to gather relevant overlaps from IntVarArray ...
cost_period[t] = exclusiveCostSum(*this, overlaps, overlap_lines);
}
cost_total = expr(*this, sum(cost_period));
我遇到的问题是（对于某些问题实例）我的分支设法分配 IntVarArray 的所有值，而无需调度我所有的总和传播器。或者至少其中一些在发布解决方案之前没有达到固定点。这给我留下了一个不完全有界的结果。自定义传播器被编写为始终声明包含并在分配所有相关变量时完全绑定。
我将避免详细说明我的实际传播逻辑的细节，因为它很难很快做到，而且我相当相信它是正确实现的。但是，我在下面包含了完整的传播器实现：
class ExclusiveCostSum : public Propagator {
protected:
Int::IntView sum;
ViewArray<Int::IntView> p_loc;
IntArgs p_lines;
public:
// Posting constructor
ExclusiveCostSum(Home home, Int::IntView x, ViewArray<Int::IntView>& ys, IntArgs& plns)
: Propagator(home), sum(x), p_loc(ys), p_lines(plns) {
sum.subscribe(home, *this, Int::PC_INT_DOM);
p_loc.subscribe(home, *this, Int::PC_INT_DOM);
}
// Posting
static ExecStatus post(Home home, Int::IntView x, ViewArray<Int::IntView> ys, IntArgs plns) {
// Run one initial round of propagation (yields small variable domains for other propgators to be posted)
propagate_impl(home, x, ys, plns);
// Check if subsumed already, in which case no propagator is needed, otherwise construct and post
if(!ys.assigned() && x.min() != x.max())
(void) new (home) ExclusiveCostSum(home, x, ys, plns);
return ES_OK;
}
// Disposal
virtual size_t dispose(Space& home) {
sum.cancel(home, *this, Int::PC_INT_DOM);
p_loc.cancel(home, *this, Int::PC_INT_DOM);
(void) Propagator::dispose(home);
return sizeof(*this);
}
// Copying constructor
ExclusiveCostSum(Space& home, bool share, ExclusiveCostSum& p)
: Propagator(home, share, p) {
sum.update(home, share, p.sum);
p_loc.update(home, share, p.p_loc);
p_lines = p.p_lines;
}
// Copying
virtual Propagator* copy(Space& home, bool share) {
return new (home) ExclusiveCostSum(home, share, *this);
}
// Cost computation
virtual PropCost cost(const Space&, const ModEventDelta&) const {
return PropCost::binary(PropCost::LO);
}
// Propgation
virtual ExecStatus propagate(Space& home, const ModEventDelta&) {
// Domain pruning (fail if unsatisfiable)
propagate_impl(home, sum, p_loc, p_lines); // NOTE: Expects locations to be sorted by ascending travel cost
// Subsumed or just fixpoint? (dispose propagator if the propergator will never propagate again)
if(p_loc.assigned() || sum.min() == sum.max())
return home.ES_SUBSUMED(*this);
else
return ES_FIX;
}
private:
static ExecStatus propagate_impl(Home home, Int::IntView x, ViewArray<Int::IntView> ys, IntArgs p_lines) {
const int M = ys.size();
// Construct array of (location, lines) pairs
std::vector <locpair>locs;
locs.clear();
for(int m=0; m<M; m++) {
int lines = p_lines[m];
locs.push_back(locpair(ys[m], p_lines[m]));
}
// Sort the array of pairs by number of lines
std::sort(locs.begin(), locs.end(), [](locpair lhs, locpair rhs) {
return std::get<1>(lhs) > std::get<1>(rhs);
});
// Find best and worst assignment (Place un-assigned variables in whicever locations remaining, matching highest number of lines with lowest travel cost and vice-versa)
int *b_loc = new int[L];
int *w_loc = new int[L];
std::fill_n(b_loc, L, -1);
std::fill_n(w_loc, L, -1);
int b_cursor = 0;
int w_cursor = L-1;
int assign_count = 0;
for (int m=0; m<M; m++) {
locpair p = locs[m];
Int::IntView loc = std::get<0>(p);
int lines = std::get<1>(p);
// If already given an assignment by solver ..
if(loc.assigned()) {
// .. use existing assignment ..
int val = loc.val();
b_loc[val] = lines;
w_loc[val] = lines;
assign_count++;
} else {
// .. Otherwise, assign to best remaining location in "best-assignment" ..
while(b_loc[b_cursor] != -1) {
b_cursor++;
}
b_loc[b_cursor] = lines;
// .. and assign to worst remaining location in "worst-assignment"
while(w_loc[w_cursor] != -1) {
w_cursor--;
}
w_loc[w_cursor] = lines;
}
}
// Calculate total costs for best assignments
int best_cost = 0;
for (int m=0; m<L; m++) {
int lines = b_loc[m];
if(lines > -1) {
best_cost += lines * travel->at(m);
}
}
// Calculate total costs for worst assignments
int worst_cost = 0;
for (int m=0; m<L; m++) {
int lines = w_loc[m];
if(lines > -1) {
worst_cost += lines * travel->at(m);
}
}
if(assign_count == M || worst_cost == best_cost) {
// Subsumed
GECODE_ME_CHECK(x.eq(home, best_cost));
} else {
// Do actual domain pruning
GECODE_ME_CHECK(x.lq(home, worst_cost));
GECODE_ME_CHECK(x.gq(home, best_cost));
}
}
};
// Constraint post function
IntVar exclusiveCostSum(Home home, const IntVarArgs& p_loc, const IntArgs& p_lines) {
IntVar sum(home, 0, Int::Limits::max);
Int::IntView x(sum);
ViewArray<Int::IntView> ys(home, p_loc);
if(ExclusiveCostSum::post(home, x, ys, p_lines) != ES_OK)
home.fail();
return sum;
}
欢迎任何关于如何进一步调试的想法。我也很高兴听到配置 GeCode 以完成相同的边界启发式的替代方法。我对 GeCode 很陌生，所以这很可能不是最好的方法。