constraint-programminggecode

Custom GeCode propagator not getting scheduled


I'm implementing a custom sum propagator in GeCode. The problem I'm trying to model involves a number of sum constraints each of which can be propagated further according to a problem-specific heuristic. The total sum of all these sums represent the cost function. I'm using branch-and-bound search with the objective of minimizing this total sum and as you can imagine the effectiveness of my bounding is highly dependent on the quality of propagation in each of the above mentioned custom sum constraints.

I'm branching on an IntVarArray, the elements of which my custom sum propagator subscribes to. As more of the values in the IntVarArray get assigned the more narrow the domain of my sum gets. Each sum propagator subscribes to a subset of the IntVarArray specific to the given problem instance. Here's a snippet from model implementation constructor (Implementation of "exclusiveCostSum" attached further down):

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));

The issue I am experiencing is that (for some problem instances) my branching manages to assign all values of the IntVarArray without scheduling all of my sum propagators. Or at least some of them don't reach a fixpoint before a solution is posted. This leaves me with a not fully bounded result. The custom propagators are written to always declare subsumtion and bound fully when all relevant variables have been assigned.

I will refrain from elaborating on the details of my actual propagation logic as it's difficult to do shortly and I'm fairly convinced it is correctly implemented. However, I have included the full propagator implementation below:

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;
}

Any ideas how to further debug this are welcome. I'm also happy to hear about alternative ways of configuring GeCode to accomplish the same bounding heuristic. I'm very new to GeCode, so it's quite possible this is not the best approach.


Solution

  • The call to propagate_impl will return an ExecStatus that is not checked. Not checking the result means that any failure or subsumption reported in propagate_impl will be discarded. Surrounding the call with GECODE_ES_CHECK will check for those cases and return appropriately. This is a clear error, I have not checked if there are any more issues.

    A few tips.