自定义 GeCode 传播器没有得到安排

Question

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

我在 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 的调用将 return 未检查的 ExecStatus。不检查结果意味着 propagate_impl 中报告的任何失败或包含都将被丢弃。用 GECODE_ES_CHECK 包围调用将检查这些情况并适当地 return 。这是一个明显的错误，我没有检查是否还有其他问题。

一些提示。

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

自定义 GeCode 传播器没有得到安排

Custom GeCode propagator not getting scheduled

constraint-programming

gecode