Propagation Engine

The propagation engine is the heart of any CP solver. In MaxiCP it is implemented in the MaxiCP class and follows a priority-based fixed-point algorithm.

Source: MaxiCP.java

Priority-Based Scheduling

Constraints implement the CPConstraint interface, which exposes a propagate() method and a priority() method. When a variable domain changes, every constraint subscribed to that event is scheduled for propagation. The engine drains a priority queue so that cheap constraints (bounds, equality) run before expensive global constraints (AllDifferent, Cumulative).

public void fixPoint() {
    notifyFixPoint();
    while (!propagationQueue.isEmpty()) {
        CPConstraint c = propagationQueue.poll();
        c.setScheduled(false);
        if (c.isActive()) c.propagate();
    }
}

public void schedule(CPConstraint c) {
    if (c.isActive() && !c.isScheduled()) {
        c.setScheduled(true);
        propagationQueue.add(c, c.priority());
    }
}

If propagate() throws InconsistencyException the queue is cleared and the exception propagates to the search layer, which handles backtracking.

Event-Driven Constraint Activation

Constraints register to specific domain events. Only the relevant constraints are re-scheduled when a variable changes.

Integer variables (``CPIntVar``)

• propagateOnFix — variable assigned a single value.

• propagateOnBoundChange — minimum or maximum changes.

• propagateOnDomainChange — any value removed.

Interval variables (``CPIntervalVar``)

• propagateOnChange — any attribute (start, end, length, presence) changes.

• propagateOnFix — interval fully fixed.

Sequence variables (``CPSeqVar``)

• propagateOnInsert — a node is inserted into the partial sequence.

• propagateOnExclude — a node is excluded.

• propagateOnRequire — a node becomes required.

Registering a constraint to an event is a reversible operation and is automatically undone on backtrack.

Posting Constraints

cp.post(constraint) invokes post(), which typically:

1. Registers the constraint to the relevant variable events.

2. Calls propagate() for an initial domain reduction.

By default, a full fixed-point is computed immediately. Use cp.post(constraint, false) to defer it and trigger it later via cp.fixPoint().

Because constraint registration is reversible, branching decisions can simply be implemented by posting constraints that define each alternative branch.

Implementing a Custom Constraint

Extend AbstractCPConstraint and implement post() and propagate().

Source: LessOrEqual.java

public class LessOrEqual extends AbstractCPConstraint {
    private final CPIntVar x, y;

    public LessOrEqual(CPIntVar x, CPIntVar y) {
        super(x.getSolver());
        this.x = x; this.y = y;
    }

    @Override
    public void post() {
        x.propagateOnBoundChange(this);
        y.propagateOnBoundChange(this);
        propagate();
    }

    @Override
    public void propagate() {
        x.removeAbove(y.max());
        y.removeBelow(x.min());
    }
}

removeAbove / removeBelow throw InconsistencyException when the domain becomes empty, triggering backtracking.

Delta-Based Incremental Propagation

For higher performance, a constraint can subscribe to delta events and react only to the values removed since its last execution, instead of re-scanning full domains.

The Element constraint (z = t[y]) below uses this approach. y.delta(this) returns a DeltaCPIntVar; calling yDelta.fillArray(buf) fills buf with the values removed from y since the last propagation call and returns their count.

Source: Element1D.java

public class Element extends AbstractCPConstraint {

    private final int[] t;
    private final CPIntVar y, z;
    private DeltaCPIntVar yDelta, zDelta;
    private int[] yValues, zValues;
    private int offZ;
    private StateInt[] supportCounter;

    public Element(int[] array, CPIntVar y, CPIntVar z) {
        super(y.getSolver()); this.t = array; this.y = y; this.z = z;
    }

    @Override
    public void post() {
        y.removeBelow(0); y.removeAbove(t.length - 1);
        y.propagateOnDomainChange(this);
        yDelta = y.delta(this);
        yValues = new int[y.size()];

        z.removeBelow(Arrays.stream(t).min().getAsInt());
        z.removeAbove(Arrays.stream(t).max().getAsInt());
        z.propagateOnDomainChange(this);
        zDelta = z.delta(this);
        zValues = new int[z.size()];

        supportCounter = new StateInt[z.size()];
        offZ = z.min();
        for (int i = 0; i < z.size(); i++)
            supportCounter[i] = getSolver().getStateManager().makeStateInt(0);
        for (int i = 0; i < t.length; i++)
            if (y.contains(i)) supportCounter[t[i] - offZ].increment();

        propagate();
    }

    @Override
    public void propagate() {
        if (zDelta.size() > 0) {
            int sz = zDelta.fillArray(zValues);
            for (int i = 0; i < sz; i++) {
                int v = zValues[i];
                int sy = y.fillArray(yValues);
                for (int j = 0; j < sy; j++)
                    if (t[yValues[j]] == v) y.remove(yValues[j]);
            }
        }
        if (yDelta.size() > 0) {
            int sy = yDelta.fillArray(yValues);
            for (int i = 0; i < sy; i++) {
                int v = yValues[i];
                if (supportCounter[t[v] - offZ].decrement() == 0)
                    z.remove(t[v]);
            }
        }
    }
}

supportCounter is an array of StateInt objects whose values are automatically restored on backtrack, keeping the counts consistent with the current search state.

Global Constraints

Source of the constraints package: org.maxicp.cp.engine.constraints

Integer / Boolean constraints

Constraint (source)	Semantics
AllDifferentDC	All variables take pairwise distinct values. Uses Régin’s arc-consistent filtering based on maximum bipartite matching [7].
AllDifferentFWC	Forward-checking (bounds-consistent) variant of AllDifferent, cheaper but weaker than DC.
Among	Constrains the number of variables in x whose value belongs to a given set S: lb ≤ |{i | x[i] ∈ S}| ≤ ub.
AtLeastNValueDC / AtLeastNValueFWC	The number of distinct values taken by the variables is at least n. DC and FWC variants.
BinPacking	x[i] is the bin of item i with weight w[i]; load[b] equals the total weight in bin b: load[b] = Σ{i | x[i]=b} w[i] [8].
BinaryKnapsack	Binary knapsack: each item is either taken (x[i]=1) or not; total weight Σ w[i]·x[i] ≤ capa and total profit Σ p[i]·x[i] = profit.
CardinalityMaxFWC / CardinalityMinFWC	Upper / lower cardinality bounds on how many variables take each value (forward-checking).
Circuit	succ defines a Hamiltonian circuit: succ[i] is the successor of node i and the graph forms a single cycle covering all nodes.
SubCircuit	Weaker form of Circuit allowing sub-tours; used for open routing models.
CostAllDifferentDC	AllDifferent with an assignment cost matrix; filters both the all-different and the total-cost variable using min-cost matching.
CostCardinalityMaxDC	Global Cardinality Constraint (upper bounds only) combined with a cost variable: |{i | x[i]=v}| ≤ ub[v] and Σ cost[i][x[i]] ≤ H. Filtering uses min-cost flow [9].
SoftCardinalityDC	Soft GCC: for each value v with bounds [lb[v], ub[v]], the per-value violation is max(0, lb[v]-c[v], c[v]-ub[v]); a global viol variable equals the sum of violations [10] [11].
Element1D / Element1DDC	z = t[y]: z equals the element of constant array t at index y. DC variant achieves domain consistency.
Element1DVar	z = t[y]: same as Element1D but t is an array of CPIntVar instead of constants.
Element2D	z = t[x][y]: z equals the element of a 2-D constant matrix at row x, column y.
Equal	x = y (or x = c): equality between two integer variables or between a variable and a constant.
NotEqual	x ≠ y (or x ≠ c).
LessOrEqual	x ≤ y (bounds-consistent).
Sum	x[0] + x[1] + … + x[n-1] = s: sum of an array of variables equals s (or a constant).
Maximum	m = max(x[0], …, x[n-1]).
Mul / MulVar / MulCte / MulCteRes	x · y = z and specialised variants: MulVar (three variables), MulCte (constant multiplier c·x = y), MulCteRes (x · y = c where c is fixed).
Square	y = x².
Absolute	y = |x|.
Sorted	x[0] ≤ x[1] ≤ … ≤ x[n-1] and y is a sorted permutation of x.
InversePerm	y[x[i]] = i for all i: x and y are inverse permutations.
Or	At least one Boolean variable in the array is true: x[0] ∨ x[1] ∨ … ∨ x[n-1].
IsOr	Reified disjunction: b ↔ (x[0] ∨ … ∨ x[n-1]).
IsEqual / IsEqualVar	Reified equality: b ↔ (x = c) and b ↔ (x = y).
IsLessOrEqual / IsLessOrEqualVar	Reified inequality: b ↔ (x ≤ c) and b ↔ (x ≤ y).
TableCT	Positive extensional constraint: the assignment of x must match at least one row in table T. Uses the Compact-Table (CT) filtering algorithm [12].
NegTableCT	Negative extensional constraint (forbidden tuples): the assignment must not match any row in T.
ShortTableCT	Short (starred) table constraint with wildcard * entries, filtered via CT.

Scheduling constraints (org.maxicp.cp.engine.constraints.scheduling)

Constraint (source)	Semantics
NoOverlap	No two interval variables in the group execute at the same time. Filtering uses Vilim’s edge-finding and not-first/not-last algorithms (Theta-Lambda tree) [13].
NoOverlapBC	Bounds-consistent (overload-check + detectable precedences only) variant of NoOverlap; faster but weaker.
NoOverlapBinary	Pairwise disjunctive constraint over exactly two interval variables: end(a) ≤ start(b) ∨ end(b) ≤ start(a).
NoOverlapBinaryWithTransitionTime	Pairwise disjunctive constraint with a sequence-dependent setup time between two tasks.
CumulativeDecomposition	Decomposition-based cumulative constraint (reference implementation).
EndBeforeStart and temporal ordering family	Temporal precedence constraints between interval variables. The family covers all combinations of {Start,End}Before/At{Start,End}: e.g. EndBeforeStart(a,b) enforces end(a) ≤ start(b).
Alternative	a is executed on exactly one of the alternative tasks b[0], …, b[k-1]: the selected alternative mirrors the presence, start, and end of a.

Sequence-variable constraints (org.maxicp.cp.engine.constraints.seqvar)

Constraint (source)	Semantics
Insert	Inserts node immediately after pred in the partial sequence.
Exclude	Removes node from all feasible extensions of the sequence.
Require	Marks node as required: it must appear in every feasible sequence.
NotBetween	Forbids node from appearing between pred and succ in the sequence.
Precedence	Node i must appear before node j whenever both are present in the sequence.
Distance	totalDist = Σ dist[pred(v)][v] over all consecutive pairs in the sequence [14].
TransitionTimes	For each consecutive pair (u, v) in the sequence: time[u] + dist[u][v] ≤ time[v].
Cumulative	Pickup-and-delivery load constraint on a sequence variable: enforces capacity at every node, pickup-before-delivery ordering, and that both nodes of a request belong to the same sequence [15].
SubSequence	A given partial sequence sub must appear as a sub-sequence of the sequence variable.
RelaxedSequence	Fixes all non-relaxed nodes to follow their order in a reference solution while leaving relaxed nodes free for re-insertion. Used in LNS.