自定义GeCode传播程序未被调度

Question

我正在GeCode中实现一个自定义和传播器。我试图建模的问题涉及一些和约束，每个约束都可以根据特定于问题的启发式进一步传播。所有这些款项的总和代表成本函数。我使用分支和定界搜索，目标是最小化总和，正如您可以想象的那样，我的边界的有效性在很大程度上取决于上述每个自定义和约束的传播质量。

我在IntVarArray上分支，我的自定义和传播器订阅了这些元素。随着IntVarArray中的值被分配的越多，我的和的范围就越窄。每个和传播子订阅特定于给定问题实例的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非常陌生，所以很可能这不是最好的方法。

Answer 1

对propagate_impl的调用将返回未检查的ExecStatus。不检查结果意味着propagate_impl中报告的任何故障或包含将被丢弃。围绕使用检查的调用将检查这些情况并适当地返回。这是一个明显的错误，我没有检查是否还有任何问题。

一些小窍门。

• 为了简化传播器的实现，可以使用方便类NaryOnePropagator来处理更新和订阅。
• IntArgs不适合在传播器中存储值。例如，使用SharedArray更好。