AI Glossary / Graphs and symbolic AI / Intermediate

Disjunctive constraint

Definition

A disjunctive constraint requires at least one of several alternative conditions to hold. Its logical form is an OR between constraints. In scheduling, the term commonly describes a non-overlap requirement: when two tasks use the same exclusive resource, either the first must finish before the second starts or the second must finish before the first starts.

What it means

A fixed precedence constraint chooses one order in advance. A disjunctive constraint can leave the order undecided and let a solver choose whichever alternative fits the rest of the problem. That flexibility is valuable when many task pairs compete for resources.
The general idea is broader than scheduling. A configuration may be allowed if it meets one of two alternative specifications. However, an ordinary logical OR means at least one alternative, not necessarily exactly one. In a scheduling example with positive task durations, the two opposite non-overlap orders cannot both hold, but that exclusivity comes from the task model rather than the meaning of OR alone.

How it works

Write each permitted alternative precisely, including its variables and boundary conventions. A solver must find an assignment satisfying at least one branch of the disjunction as well as all the other constraints. Propagation can sometimes eliminate an impossible alternative before an explicit search decision is made.
For tasks A and B with start times sA and sB and durations dA and dB, a basic exclusive-resource constraint is sA + dA <= sB OR sB + dB <= sA. Equality allows one task to start exactly when the other ends. Global no-overlap constraints can handle a collection of intervals more directly and exploit their combined structure, with additional rules needed for optional tasks or transition times.

Three practical examples

• Two print jobs using one printer may run in either order but must not overlap.
• A configuration rule allows either a compact package within one size limit or a larger package with an additional handling provision.
• Two objects placed on a line must satisfy either left-of or right-of separation, leaving the solver to select their relative order.

Think of it this way

Think of a single-lane passage where two deliveries must take turns. Either delivery can go first, but they cannot occupy the passage together. The analogy is limited because a general disjunctive constraint can involve many alternatives and need not describe a resource or a temporal order.

Worked example

Let task A last 3 hours and task B last 2 hours. Both use one machine, neither can start before time 0, and both must finish by time 5. Their non-overlap condition is sA + 3 <= sB OR sB + 2 <= sA.
The schedule sA = 0, sB = 3 satisfies the first alternative, with A occupying [0,3) and B occupying [3,5). The schedule sB = 0, sA = 2 satisfies the second, with B occupying [0,2) and A occupying [2,5). The candidate sA = 1, sB = 2 fails both: 1 + 3 <= 2 is false, and 2 + 2 <= 1 is false. The tasks overlap.
Now add the condition sB >= 1. If B runs before A, B cannot finish before time 3, so A cannot finish before time 6, violating the deadline. The second ordering is impossible, while A from 0 to 3 followed by B from 3 to 5 remains valid. The additional condition resolves the disjunction without changing the resource rule.

Illustrative case study

At fictional Maple Print, a team builds a small scheduling model. An early version fixes every job pair in arrival order, excluding feasible schedules that could use another order. The revised model states resource non-overlap separately from genuine customer-required precedence.
The team checks the resulting schedules against release times and deadlines before using them. This fictional case illustrates the difference between necessary constraints and an arbitrary ordering choice. It does not claim that changing the representation guarantees faster solving or a better schedule for every instance.

Common misconceptions and mistakes

Replacing OR with AND usually changes the problem radically. For two positive-duration tasks, requiring both opposite precedences makes the pair impossible. Conversely, leaving out the non-overlap disjunction permits simultaneous use of an exclusive resource.
Do not confuse a disjunctive constraint with an objective or a preference. It specifies acceptable assignments; it does not say which acceptable one is best. Endpoint conventions and setup times also matter. If a machine needs cleaning between jobs, merely allowing the next start at the previous end is insufficient. Optional tasks need presence-aware semantics so an absent task does not create an unintended restriction.

Business use

Disjunctive constraints help businesses express flexible alternatives without choosing prematurely. Identify which orders are truly mandatory and which should remain solver choices. Validate durations, release times, deadlines, and transition requirements together. For a larger scheduling model, a dedicated global no-overlap constraint may provide a clearer and stronger representation than manually listing every pair, but the exact solver semantics still need to match the intended operation.

People also ask

Does disjunctive mean exactly one alternative?

Generally it means at least one. Additional conditions may make alternatives mutually exclusive.

How does it differ from fixed precedence?

Fixed precedence selects an order; a disjunction can allow either order.

Does satisfying every pairwise non-overlap rule finish the schedule?

No. Other constraints, such as availability and deadlines, must also hold.

Check your understanding

Why does sB >= 1 rule out B before A in the example?

Answer: B would finish no earlier than 3, and the three-hour A would then finish no earlier than 6, beyond the deadline of 5.

Related terms

• Constraint satisfaction
• Scheduling
• Precedence constraints
• Disjunction
• precedence constraint
• no-overlap constraint
• exclusive resource
• interval variable
• propagation
• alternative constraint

Learn next

Learn global constraints next. Compare a collection-wide no-overlap model with separate pairwise disjunctions, then add a transition delay and an optional task. State the intended behavior before selecting the implementation syntax.

More in Graphs and symbolic AI

• Discount factor - A discount factor is a number used to reduce the weight of later rewards relative to earlier rewards in a sequential decision problem.
• Discrete events - In knowledge representation, discrete events are occurrences with a definite structure and identifiable boundaries.
• Discretization - Discretization represents a continuous quantity or space using a set of distinct values, categories, intervals, or grid points.
• Disparity - Disparity, in stereo vision, is the difference between the image positions of corresponding scene points in two views.
• Dispersion - Dispersion, in the network-analysis sense used here, measures how separated the mutual neighbors of two connected nodes are from one another.
• Distance-Regular Graphs - Distance-regular graphs are connected graphs whose local connection counts around pairs of vertices depend on their graph distance rather than on the...

Sources

Primary sources: IBM CP Optimizer official interval sequencing and no-overlap semantics, https://www.ibm.com/docs/en/icos/22.1.1?topic=concepts-interval-variable-sequencing-in-cp-optimizer ; official interval-constraint overview, https://www.ibm.com/docs/en/icos/22.1.2?topic=models-modeling-constraints-interval-variables . The two-task schedule and fictional case are original illustrations.

Previous: Disjunction Next: Disocclusion