Skip to main content

Alternative Constraints

So far, every task in our model has been mandatory: it must be executed exactly once. But real scheduling problems often involve choices:

  • A task can be performed on machine A or machine B
  • A delivery can go by truck or by air
  • A manufacturing step can use method 1 (slow, cheap) or method 2 (fast, expensive)

In our furniture workshop, let's introduce a choice for sanding: hand sanding (slow but doesn't require equipment) or power sander (faster but the power sander is a shared resource).

Sanding Options​

We'll modify our model so that sanding can be done two ways:

  • Hand sanding:

    • Desk: 30 minutes (slower than the original 20 minutes)
    • Chair: 25 minutes (slower than the original 15 minutes)
    • No special equipment needed

  • Power sanding:

    • Desk: 15 minutes (faster)
    • Chair: 10 minutes (faster)
    • Requires the power sander (one available, shared between desk and chair)

The solver will choose which method to use for each item to minimize makespan.

Optional Intervals​

To model choices, we use optional intervals: intervals that may or may not be executed. We create one interval for each option, mark them all as optional=True, and then add an alternative constraint to ensure exactly one is chosen.

# Sanding the desk parts - two options
sand_desk_parts = model.interval_var(name="SandDeskParts")  # Main task (always present)
sand_desk_hand  = model.interval_var(length=30, optional=True, name="SandDeskHand")
sand_desk_power = model.interval_var(length=15, optional=True, name="SandDeskPower")

# Alternative: exactly one option is executed
model.alternative(sand_desk_parts, [sand_desk_hand, sand_desk_power])

How Alternative Works​

The alternative(main, [option1, option2, ...]) constraint ensures:

  1. Exactly one option is present: One of the options must be executed, and the others are absent
  2. Main interval covers the chosen option: The main interval starts when the chosen option starts and ends when it ends
  3. Presence is synchronized: If main is present, exactly one option is present; if main is absent, all options are absent

In our model, sand_desk_parts is mandatory (not optional), so exactly one sanding method will always be chosen. But the main interval can also be optional—useful when the entire choice is conditional.

This pattern lets you model choices while maintaining a single "handle" (sand_desk_parts) that other constraints can reference.

Power Sander as a Shared Resource​

If both desk and chair are power-sanded, they can't use the power sander simultaneously. We add a no-overlap constraint on the power sanding options:

# Power sander is shared - can only be used by one item at a time
model.no_overlap([sand_desk_power, sand_chair_power])

If one or both sanding operations choose hand sanding instead, those intervals are absent, and they don't participate in the no-overlap constraint. OptalCP handles this automatically.

Constraining the Main Interval​

Best Practice: Use Main Intervals in Constraints

Use the main interval in constraints and expressions whenever possible—not just for precedence, but for cumulative constraints, objectives, and any other constraints that apply regardless of which option is chosen.

Our precedence constraints reference the main intervals (sand_desk_parts, sand_chair_parts), not the individual options:

# Precedence uses the main intervals
cut_desk_wood.end_before_start(sand_desk_parts)
sand_desk_parts.end_before_start(assemble_desk)

This approach has two benefits:

  1. Simpler model: You write one constraint instead of duplicating it for each option
  2. Better performance: The solver can propagate constraints more effectively through the main interval

Since sand_desk_parts covers whichever option is chosen, the precedence works correctly regardless of which sanding method is selected.

When to constrain option intervals instead: Use the option interval when the constraint is specific to that option. For example, the power sander no-overlap constraint only applies to sand_desk_power and sand_chair_power—it wouldn't make sense to put it on the main intervals.

Complete Model with Alternatives​

Let's integrate the sanding alternatives into our full model:

import optalcp as cp

model = cp.Model()

# Create interval variables
cut_desk_wood    = model.interval_var(length=30, name="CutDeskWood")
cut_chair_wood   = model.interval_var(length=25, name="CutChairWood")

# [NEW] Sanding alternatives for desk
sand_desk_parts  = model.interval_var(name="SandDeskParts")
sand_desk_hand   = model.interval_var(length=30, optional=True, name="SandDeskHand")
sand_desk_power  = model.interval_var(length=15, optional=True, name="SandDeskPower")
model.alternative(sand_desk_parts, [sand_desk_hand, sand_desk_power])

# [NEW] Sanding alternatives for chair
sand_chair_parts = model.interval_var(name="SandChairParts")
sand_chair_hand  = model.interval_var(length=25, optional=True, name="SandChairHand")
sand_chair_power = model.interval_var(length=10, optional=True, name="SandChairPower")
model.alternative(sand_chair_parts, [sand_chair_hand, sand_chair_power])

# Rest of the tasks
assemble_desk    = model.interval_var(length=45, name="AssembleDesk")
assemble_chair   = model.interval_var(length=35, name="AssembleChair")
stain_desk       = model.interval_var(length=20, name="StainDesk")
stain_chair      = model.interval_var(length=15, name="StainChair")
apply_finish     = model.interval_var(length=30, name="ApplyFinish")
final_inspect    = model.interval_var(length=10, name="FinalInspect")

# Precedence constraints - Desk
cut_desk_wood.end_before_start(sand_desk_parts)
sand_desk_parts.end_before_start(assemble_desk)
assemble_desk.end_before_start(stain_desk)
stain_desk.end_before_start(apply_finish)

# Precedence constraints - Chair
cut_chair_wood.end_before_start(sand_chair_parts)
sand_chair_parts.end_before_start(assemble_chair)
assemble_chair.end_before_start(stain_chair)
stain_chair.end_before_start(apply_finish)

# Final inspection
apply_finish.end_before_start(final_inspect)

# Resource constraint: one saw
model.no_overlap([cut_desk_wood, cut_chair_wood])

# [NEW] Resource constraint: power sander (only if both choose power sanding)
model.no_overlap([sand_desk_power, sand_chair_power])

# Resource constraint: 2 workers
# Note: Use main intervals for worker counting
worker_usage = [
    model.pulse(cut_desk_wood, 1),
    model.pulse(cut_chair_wood, 1),
    model.pulse(sand_desk_parts, 1),
    model.pulse(sand_chair_parts, 1),
    model.pulse(assemble_desk, 2),
    model.pulse(assemble_chair, 1),
    model.pulse(stain_desk, 1),
    model.pulse(stain_chair, 1),
    model.pulse(apply_finish, 1),
    model.pulse(final_inspect, 1),
]
model.enforce(model.sum(worker_usage) <= 2)

# Resource constraint: spray booth with transitions
spray_booth_seq = model.sequence_var([stain_desk, stain_chair, apply_finish])
transitions = [
    [0, 10, 5],
    [10, 0, 5],
    [5, 5, 0],
]
model.no_overlap(spray_booth_seq, transitions)

# Minimize makespan
model.minimize(final_inspect.end())

# Solve
result = model.solve()

if result.solution:
    print(f"Makespan: {result.objective} minutes")
    print(f"Optimal: {result.proof}")

    # Check which sanding method was chosen
    if result.solution.is_present(sand_desk_hand):
        print("Desk: hand sanding")
    elif result.solution.is_present(sand_desk_power):
        print("Desk: power sanding")

    if result.solution.is_present(sand_chair_hand):
        print("Chair: hand sanding")
    elif result.solution.is_present(sand_chair_power):
        print("Chair: power sanding")

What Will the Solver Choose?​

The solver will compare scenarios:

  1. Both hand sanding: Slower (30 + 25 = 55 minutes total), but can be done in parallel
  2. Both power sanding: Faster (15 + 10 = 25 minutes total), but must be sequential (shared resource)
  3. Mixed: One hand, one power—combines benefits and drawbacks

The optimal choice depends on the rest of the schedule. If there's parallelism to exploit, hand sanding might win. If the critical path benefits from speed, power sanding might be better. Building on our previous model (makespan: 200 minutes with transition times), adding alternatives gives the optimal makespan of 195 minutes—the alternatives provide flexibility that improves the schedule.

Absent Semantics​

Optional intervals interact naturally with other constraints:

  • No-overlap: Absent intervals don't participate (as if they don't exist)
  • Cumulative: Pulses on absent intervals contribute 0
  • Precedence: If an optional interval is absent, constraints involving it are ignored
  • Expressions: Expressions involving absent intervals are also absent (unless guarded)

This makes modeling flexible: you don't need special cases for "what if this task isn't chosen."

Other Uses of Optional Intervals​

With Alternatives​

Alternative constraints work well for many scenarios:

  • Machine selection: An operation can be performed on multiple machines (create one optional interval per machine)
  • Method selection: A task can use different methods with different durations and resource requirements
  • Alternative routes: A delivery can take route A or route B

Without Alternatives​

Optional intervals are also useful without the alternative constraint:

  • Oversubscribed systems: You have more requests than you can fulfill—make each request an optional interval and maximize the number of present intervals
  • Soft constraints: A task is preferred but not required—make it optional and add a penalty to the objective if it's absent
Modeling Pitfalls

Don't fake absence with dummy values. Don't model "not chosen" by length=0 or start=999999. This creates unnecessary complexity and hurts solver performance. Use optional=True instead—that's exactly what optional intervals are for.

Don't use alternatives for equivalent resources. If you have multiple identical workers or machines, use a cumulative constraint (as we did in the cumulative chapter), not alternatives. You can always assign tasks to specific workers in postprocessing. Use alternatives when the options have different characteristics (different durations, costs, or capabilities).

What We Learned​

In this chapter, we:

  • Created optional intervals to represent choices
  • Used the alternative constraint to select exactly one option
  • Modeled a shared resource (power sander) that's only used if certain options are chosen
  • Checked which options were selected in the solution using is_present()

Alternatives are useful for modeling real-world flexibility and trade-offs.

See Also​

Next Steps​

In the final chapter, we'll model reservoir resources: cutting and sanding generate dust that accumulates over time, and the workshop must be cleaned before dust exceeds safety limits.

Continue to: Reservoir Constraints →