Module org.maxicp
Package org.maxicp.cp.engine.constraints.scheduling

Class NoOverlapWithPosition

java.lang.Object
org.maxicp.cp.engine.core.AbstractCPConstraint
org.maxicp.cp.engine.constraints.scheduling.NoOverlapWithPosition
All Implemented Interfaces:
CPConstraint, ConcreteConstraint<ConcreteCPModel>
public class NoOverlapWithPosition extends AbstractCPConstraint
A global constraint that enforces a permutation (ordering) of interval variables with minimum transition times, using set-variable-based propagation for stronger filtering than the binary decomposition NoOverlapWithPositionDecomposition.

Model

Each interval i is assigned a position posOfInterval[i] in 0..n-1 (all positions distinct via an InversePerm channeling to intervalInPos). A global NoOverlap enforces that intervals do not overlap.

Set-based position reasoning

For each interval i, a set variable befores[i] represents the set of intervals that precede i in the sequence. Its cardinality is channeled to the position: |befores[i]| = posOfInterval[i]. The following equivalences are posted for every ordered pair (i, j), i ≠ j:

  • i ∈ befores[j] ⇔ posOfInterval[i] < posOfInterval[j] (via IsIncluded + isLt)
  • befores[i] ⊆ befores[j] ⇔ i ∈ befores[j] (via IsSubset — enforces transitivity: if i precedes j, every interval before i is also before j)
  • i ∈ befores[j] ⇔ end(i) + trans[i][j] ≤ start(j) (via IsEndBeforeStartWithTransition — channels temporal ordering)
  • isIncludedVars[i][j] ≠ isIncludedVars[j][i] (exactly one of the two orderings holds — redundant but helps propagation)

Global sweep propagation

The propagate() method, triggered on any domain change of the position variables, set variables, or interval bounds, runs a sweep algorithm for each interval i:

  1. Collect the mandatory and possible predecessors of i from befores[i].
  2. Compute an earliest completion time profile ect[0..k] by scheduling all predecessors using a variant of Jackson's rule (SR-ECT sweep, implemented with two priority queues). ect[p] is the earliest time at which the p-th predecessor can complete.
  3. Compute a latest completion time profile lct[0..k] symmetrically, scheduling predecessors backward from their latest end times.
  4. For each candidate position p of interval i:
    • Earliest start: est = max(ect[p] + transitionAdjustment, startMin(i)), where transitionAdjustment accounts for the minimum transition times between the p predecessors and between the last predecessor and i.
    • Latest start: lst = min(lct[p] - transitionAdjustment - lengthMin(i), startMax(i)).
    • If est > startMax(i) or lst < startMin(i), position p is removed from posOfInterval[i].
    • Otherwise, update startMin(i) := min(est) and startMax(i) := max(lst).

The transition time adjustment uses the global minimum transition minTransition (minimum over all distinct pairs) as a lower bound for inter-predecessor gaps, and minTransToI (minimum transition from any possible predecessor to i) for the gap between the last predecessor and i. This is a conservative relaxation that never removes feasible solutions while still providing useful pruning.

Complexity

Each propagation call is O(n² log n): for each of the n intervals, the sweep algorithm runs in O(k log k) where k is the number of predecessors, and the position check is O(n). The O(n²) IsEndBeforeStartWithTransition constraints provide event-driven pairwise channeling and are only woken up when the relevant variables change.

See Also:

  • Field Details

    • n

      public final int n
      Number of intervals.

    • intervals

      public final CPIntervalVar[] intervals
      Intervals to be sequenced.

    • posOfInterval

      public final CPIntVar[] posOfInterval
      posOfInterval[i] is the position of interval i in the sequence.

    • intervalInPos

      public final CPIntVar[] intervalInPos
      intervalInPos[p] is the interval at position p in the sequence.

  • Constructor Details

    • NoOverlapWithPosition

      public NoOverlapWithPosition(CPIntervalVar[] intervals, CPIntVar[] posOfInterval, CPIntVar[] intervalInPos)
      Creates a global permutation constraint with zero transition times.
      Parameters:
      intervals - the interval variables to be sequenced (all must be present and share the same solver)
      posOfInterval - position variables: posOfInterval[i] is the position of interval i (domain 0..n-1)
      intervalInPos - inverse position variables: intervalInPos[p] is the interval at position p (domain 0..n-1)

    • NoOverlapWithPosition

      public NoOverlapWithPosition(CPIntervalVar[] intervals, CPIntVar[] posOfInterval, CPIntVar[] intervalInPos, int[][] minTransition)
      Creates a global permutation constraint with minimum transition times between intervals.

      The transition time matrix must satisfy the triangular inequality property, i.e., for all i, j, k: minTransition[i][j] <= minTransition[i][k] + minTransition[k][j].

      Parameters:
      intervals - the interval variables to be sequenced (all must be present, same solver)
      posOfInterval - position variables: posOfInterval[i] is the position of interval i (domain 0..n-1)
      intervalInPos - inverse position variables: intervalInPos[p] is the interval at position p (domain 0..n-1)
      minTransition - n×n matrix where minTransition[i][j] is the minimum transition time from interval i to interval j
      Throws:
      AssertionError - if the matrix dimensions don't match or triangular inequality is violated

  • Method Details