Derived Interval Overlap

[milikic17]

Notes

• I intentionally simplified some regulation details to keep this readable.
• I used AI chatbot to help me better explain the problem.

Context

ELDs are devices legally required to be used by commercial truck drivers in USA, and they serve a purpose of recording activities like driving, on duty (and also rest time).
Hours of Service (HoS) regulations limit driving time without sufficient rest.

What I'm building

An optimization engine for HoS compliance. My tool shows drivers how they could have rearranged rest periods to avoid violations with minimal schedule disruption — it's educational.

This problem is deeply personal to me — a family member was, not too long ago, hit by a truck driver who was in violation of HoS rules at the time — and I want to contribute something practical that improves compliance outcomes. I plan to offer this through an API to all ELD providers, essentially at no profit prices (just covering server expenses), so all drivers (over 15M) in USA can get finally get the proper training on HoS regulations, instead of just being thrown behind the wheel knowing nothing.

The problem

• Fixed-order sequence of activities (driving, on-duty) with fixed durations, with optional rest period between them.
• Total (rest) time is fixed, which implies that total period time is fixed.
• The solver decides when each activity happens (and since rest is simply the time between activities, this effectively determines how rest is distributed).
• Modeled with interval variables, AddNoOverlap, start-time ordering. Objective: minimize displacement of on-duty activities from their original positions.

How HoS regulations work?

All regulations (4 in total, each having a minor exception) follow the same pattern — reservoir/rolling window mechanism:

• Activity (driving and/or on-duty, depending on the regulation) fills the reservoir
• A qualifying rest (≥ threshold) drains it back to 0. Importantly, the reset is binary — one minute short and the rest has zero effect. (this causes so many problems..........)
• If the level exceeds a limit (e.g., 660 min) during a driving activity, that's a violation — exceeding the limit during on-duty is not a violation by itself

Why not AddReservoirConstraint then?

Three issues:

• Demands are constants — but rest period durations are decision variables, so we can't know whether a rest is gonna qualify for a reset (and therefore drain amounts)
• No "reset to 0" semantic — there's no way to say "drain whatever the current level is back to 0." You'd need a variable demand equal to the current accumulation, which isn't supported
• Violation is type-dependent — exceeding max_level is only a violation during driving, not during on-duty. The reservoir constraint enforces the level bound unconditionally at all times

Approach 1: Accumulator with ceiling flip

Instead of a reservoir that resets, I flip the model: accumulation only grows (monotonically), and qualifying rests boost the ceiling by the limit amount. Violation = accumulation > ceiling at any driving endpoint.

This works cleanly for the base rules. But one regulation's exception ("split sleeper") allows two non-adjacent rests to combine as a virtual reset (both ≥ 2h, one ≥ 7h, sum ≥ 10h). Modeling this requires tracking pairing state (best candidate, shift boundaries, accumulation history) — the conditional chain per step explodes in variables and constraints, and propagation through long OnlyEnforceIf chains is weak.

Approach 2: Backward zone lookback

Key insight: we don't need to track exact accumulation. For each driving, we just look back over a bounded zone and check if there's a qualifying rest (or valid pair) that "liberates" it (makes it not violated).

Since activity durations are fixed and order is preserved, each driving's zone (how far back to look) is precomputable. One AddBoolOr per driving over the candidate rests in its zone — compact and SAT-friendly. This is my current best solver.

But it breaks when I introduce splittable driving. To give the solver more flexibility, I allow it to split a driving into two segments by presplitting driving into two intervals and then constrain their cumulative duration to the duration of original driving. I also insert both of them in NoOverlap, and rest can be inserted between them by separating them.

Now zone boundaries depend on segment durations (decision variables), so they can't be precomputed. The backward zone approach loses its key advantage.

Where I'm stuck

What I fundamentally need is the ability to compute a cumulative sum over a variable-bounded range of intervals — "sum the durations of all driving intervals that fall within [x, y]", where both bounds depend on decision variables.

This would directly express every regulation check: "how much driving (or activity) has occurred since the last qualifying rest?"

It would also handle a regulation I haven't modeled yet: one rule provides ceiling boosts at calendar midnight boundaries, regardless of activity positions. Since midnight can fall in the middle of an activity, a cumsum-over-variable-range primitive is the natural fit — it doesn't need to be tied to interval start/end events.

I can decompose this into per-candidate booleans today, but it's O(candidates × drivings) with weak propagation — each membership check is independent, so the solver can't reason globally about the window.

What would be ideal (in my opinion)

CP-SAT is missing a way to compute the overlap between intervals as a first-class concept.
Today, if I want to know how much two intervals overlap, I have to decompose it manually:

How much does interval A overlap with interval B?
clipped_start = model.new_int_var(0, horizon, 'cs')
model.add_max_equality(clipped_start, [start_a, start_b])

clipped_end = model.new_int_var(0, horizon, 'ce')
model.add_min_equality(clipped_end, [end_a, end_b])

raw = model.new_int_var(-horizon, horizon, 'raw')
model.add(raw == clipped_end - clipped_start)

overlap = model.new_int_var(0, horizon, 'overlap')
model.add_max_equality(overlap, [raw, 0])

That's 4 intermediate variables and 4 constraints per pair — and each propagates independently with no global view. For N intervals this scales poorly, and the solver has no idea these variables are geometrically related.

Two things that would help:

1. overlap_size as a derived variable

ov = model.overlap_size(interval_a, interval_b)
# ov is an IntVar equal to max(0, min(end_a, end_b) - max(start_a, start_b))

model.add(ov <= 120)
model.add(ov >= 30)
model.minimize(ov)

This isn't just syntactic sugar hiding the same 4-variable decomposition. Under the hood, the solver can maintain ov directly as a function of the four bounds (start_a, end_a, start_b, end_b) without intermediate variables. When any bound changes, ov gets updated in one step — no chain of propagations through clipped_start, clipped_end, raw.

2. add_max_overlap as a global constraint

Think of it as a cousin of add_no_overlap:

• add_no_overlap(intervals) = total pairwise overlap must be zero
• add_max_overlap(intervals, max) = total pairwise overlap must be <= max

#Activities can't overlap each other (already exists)
model.add_no_overlap(activities)

# But the total overlap of activities with regulation periods must be bounded
model.add_max_overlap(activities + regulation_periods, max=660)

Example:

Interval A: [4, 8]
Interval B: [6, 12]
Interval C: [10, 14]

Pairwise overlaps:  
    A ∩ B = [6, 8]  = 2  
    B ∩ C = [10, 12] = 2  
    A ∩ C = 0
    
Total overlap = 4

With add_max_overlap([A, B, C], max=3), this would be rejected.

A native propagator for this would see all intervals at once. When the total overlap approaches the limit, it can push interval bounds apart or report a conflict — with one wake-up, one reason, global deduction. The decomposed version can't do this because each overlap variable is independent.

If add_no_overlap with its 6 internal propagators is the "zero overlap" extreme, add_max_overlap is the relaxed version. The same sweep and profile techniques (Theta-trees, detectable precedences, edge-finding) could be adapted for bounded total overlap rather than zero overlap.

Progress

The solver works on shorter logs but becomes too slow on longer periods.
I believe the main gains are in model improvement, not hardware.

Question

Is there a modeling pattern or existing constraint that handles this efficiently in CP-SAT today? If not, would either of the above extensions be realistic/useful beyond my use case? @lperron @Mizux

[lperron]

how do you count if 3 intervals overlap at the same time ?

[milikic17]

Hi @lperron — thank you very much for taking the time to respond. I genuinely appreciate it.

In my specific use case, activity intervals are already strictly ordered and constrained with addNoOverlap, so activities themselves never overlap. The only overlaps that can occur are between activity intervals and abstract “regulation window” intervals.

Because of that structure, in my model there are never more than two intervals overlapping at the same time — essentially one activity interval intersecting one regulation interval.

A simplified example of what I’d like to express is something like:

“The total overlap between activity intervals and a given shift window must not exceed 11 hours.”

So structurally it’s bipartite (activities vs. regulation windows), not arbitrary many-to-many overlaps.

That said, I completely understand that for a feature to even be considered it needs to be general and well-defined for all cases — not just mine.

To answer your question directly:

If 3 intervals overlap at the same time, I would count that as multiple pairwise overlaps. So if A, B, and C all overlap over the same time span, that contributes:

overlap(A, B)

overlap(A, C)

overlap(B, C)

In other words, triple overlap would be counted multiple times (combinatorially). My reasoning is that this keeps the definition simple and compositional. If a user does not want that behavior (like in my case), they can already enforce structural properties such as addNoOverlap or addCumulative to prevent multi-way overlaps from occurring in the first place.

When I initially proposed addMaxOverlap, I thought of it as a relaxed cousin of addNoOverlap. But after looking more closely at the implementation and the literature behind addNoOverlap (detectable precedences, edge-finding, etc.), it’s clear they are fundamentally different animals. The strength of addNoOverlap comes from reasoning about ordering, which disappears once overlap is allowed.

So perhaps the more realistic and targeted primitive is something like a first-class overlap_size(a, b) expression with dedicated propagation, rather than a global “total overlap” constraint. Even that alone would already help significantly in models like mine, where many overlap computations share structure and bounds.

I would really value your thoughts on what modeling direction you think is most appropriate for problems with this structure. I suspect there are other use cases (rolling windows, bounded exposure time, regulated workload limits, etc.) that run into similar patterns.

Thanks again for engaging — it means a lot.

[lperron]

you can use a cumulative with capacity 2. And have optional intervals that fills the capacity 1 -> 2. Then add the intervals, the window intervals, and the optional intervals and either minimize the optional, or the size of the optional intervals. Depending on the granularity. Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 Le jeu. 12 févr. 2026 à 22:35, milikic17 ***@***.***> a écrit :

…

Hi @lperron <https://github.com/lperron> — thank you very much for taking the time to respond. I genuinely appreciate it. In my specific use case, activity intervals are already strictly ordered and constrained with addNoOverlap, so activities themselves never overlap. The only overlaps that can occur are between activity intervals and abstract “regulation window” intervals. Because of that structure, in my model there are never more than two intervals overlapping at the same time — essentially one activity interval intersecting one regulation interval. A simplified example of what I’d like to express is something like: “The total overlap between activity intervals and a given shift window must not exceed 11 hours.” So structurally it’s bipartite (activities vs. regulation windows), not arbitrary many-to-many overlaps. That said, I completely understand that for a feature to even be considered it needs to be general and well-defined for all cases — not just mine. *To answer your question directly:* If 3 intervals overlap at the same time, I would count that as multiple pairwise overlaps. So if A, B, and C all overlap over the same time span, that contributes: overlap(A, B) overlap(A, C) overlap(B, C) In other words, triple overlap would be counted multiple times (combinatorially). My reasoning is that this keeps the definition simple and compositional. If a user does not want that behavior (like in my case), they can already enforce structural properties such as addNoOverlap or addCumulative to prevent multi-way overlaps from occurring in the first place. When I initially proposed addMaxOverlap, I thought of it as a relaxed cousin of addNoOverlap. But after looking more closely at the implementation and the literature behind addNoOverlap (detectable precedences, edge-finding, etc.), it’s clear they are fundamentally different animals. The strength of addNoOverlap comes from reasoning about ordering, which disappears once overlap is allowed. So perhaps the more realistic and targeted primitive is something like a first-class overlap_size(a, b) expression with dedicated propagation, rather than a global “total overlap” constraint. Even that alone would already help significantly in models like mine, where many overlap computations share structure and bounds. I would really value your thoughts on what modeling direction you think is most appropriate for problems with this structure. I suspect there are other use cases (rolling windows, bounded exposure time, regulated workload limits, etc.) that run into similar patterns. Thanks again for engaging — it means a lot. — Reply to this email directly, view it on GitHub <#5043 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3JAOJEP5IQDRDFRKBT4LTW2ZAVCNFSM6AAAAACUXCUN6KVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTKNZYHAYDQOA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[milikic17]

Let me make sure I understood your suggestion correctly:

• Use addCumulative with capacity = 2.
• The regulation window interval has demand = 1.
• The activity intervals have demand = 1.
• Then create additional "filler" intervals (also demand = 1) that are constrained to live inside the regulation window.

Since the window already occupies 1 unit of capacity, activities and fillers compete for the remaining 1 unit at every time point — they can't coexist at the same minute.
The filler intervals thus cover exactly the idle time inside the window.
By constraining the total filler size >= (window_size - max_allowed_activity), we indirectly bound the total activity overlap with the window.

This is a genuinely elegant trick — turning an aggregate overlap problem into a per-point capacity competition using existing infrastructure. I wouldn't have thought of it.

Regarding granularity: I'm already working at single-minute resolution (a 14-hour shift = 840 units, 11-hour driving limit = 660 units), so that part is straightforward.

My Concern

context: In realistic HoS scenario, longer periods have ~500 activities over a multiple days, with multiple overlapping regulation windows (shift driving limit, 14-hour on-duty window, 70-hour/8-day rolling limit, 30-minute break rule — each with their own cycle/reset logic).

My concern is about scale. Each regulation window would need its own cumulative instance with its own set of filler intervals. With N activities per window, that's up to N+1 optional filler intervals per window — each adding a presence boolean, start, end, and size variable. Across all windows, that's thousands of artificial variables and constraints that don't represent anything in the actual problem, plus the aggregate constraint on filler sizes still requires computing how much filler falls inside each window.

---

That said, I'm not going to play the smartass and speculate about whether this will be fast enough — I'll go ahead and fully implement this approach, test it against real driver logs, and then report back. It's the least I can do given your help.

[milikic17]

Hi Laurent,

As I started implementing your cumulative-based suggestion, I realized that my earlier example (“total overlap between activity intervals and a shift window must not exceed 11 hours”) unintentionally made the problem look simpler than it actually is.

For two of the four HoS regulations, that formulation is accurate — the rule is essentially a bound on total driving time inside a window. In those cases, your cumulative trick works : we can convert an aggregate bound into a per-time-point capacity competition, and that enforces the limit cleanly.

However, the other two regulations have a different structure that I did not articulate clearly — the previous example was only meant to motivate the need for derived interval overlap, not to fully characterize the problem.

Let me use the cycle regulation as the clearest example.

A cycle begins and ends with a 34-hour consecutive rest period.
Within a cycle, total working time (driving + on-duty) accumulates.
Once 70 hours (4200 minutes) of working time has accumulated, no further driving is allowed until the next 34-hour reset.

Crucially:

• On Duty (fuel, pickup/delivery, inspection..) time past 70h is allowed.
• Only driving past that threshold is forbidden.
• So the violation is type-dependent and position-dependent.

This is not a “total working time ≤ 70h” constraint. It is:

“Find the point inside the cycle where cumulative working time reaches 70h. From that point until the cycle ends, driving is prohibited.”

So what I need to derive is a time boundary determined by accumulated overlap.

Concretely, inside a cycle window [cycle_start, cycle_end]:

1. Compute total working time in the cycle (driving + on-duty).
2. Identify the first time at which cumulative working time reaches 4200.
3. Create a derived “no-driving zone” interval from that time to cycle_end.
4. Enforce addNoOverlap between this zone and all driving intervals.

The cumulative trick helps bound totals, but here I need to derive a boundary in time from accumulated overlap. That is where the idea of a first-class overlap_size becomes central — not just to cap totals, but to compute how much activity lies inside a variable window and to reason about where thresholds are crossed.

So the earlier 11-hour example was only illustrating one simpler use case. The deeper requirement is the ability to compute:

“how much of a set of intervals overlaps a variable-bounded window”

as a proper integer expression that can participate in further structural modeling.

If you see a better way to model this pattern — one that can derive such a boundary without exploding into per-candidate Booleans — I would genuinely appreciate your guidance.

If not, do you think a primitive of this kind could realistically make it into CP-SAT in the foreseeable future?

And if that’s also unlikely: is something like this even architecturally feasible within CP-SAT’s current design, or are there internal reasons (e.g., propagation architecture, scheduling layer interfaces, linearization limits, etc.) that make this kind of derived-overlap construct fundamentally hard to support?

If it is feasible, could you advise how one might go about building it (even at the C++ level / custom propagator level)? I’m prepared to invest whatever time it takes — even years if needed (I'm a very persistent person) — because, as I mentioned in the original post, this problem has deep personal meaning to me, which I’d be happy to discuss privately.

Also, if you think this would realistically require someone with more solver implementation experience or higher level of expertise, could you recommend anyone who might be open to collaborating? I’d be happy to compensate financially.

Thank you again for your time and guidance.

[jmarca]

@milikic17, I’d be interested in contributing/collaborating.  I did a project several years ago implementing the HOS rules in the routing solver with dummy nodes, etc. in the truckload case. I’ve been thinking that the CP-SAT solver would be a much better fit for handling the side constraints.   And your problem domain (plus the fact that you have actual logs) sounds a lot more interesting.  Feel free to message me directly if you want to collaborate. But be aware that my approach to the problem is very different from yours.  James (edited to fix the email to github mangling) On Feb 12, 2026, at 21:19, milikic17 ***@***.***> wrote: Hi Laurent, As I started implementing your cumulative-based suggestion, I realized that my earlier example (“total overlap between activity intervals and a shift window must not exceed 11 hours”) unintentionally made the problem look simpler than it actually is. For two of the four HoS regulations, that formulation is accurate — the rule is essentially a bound on total driving time inside a window. In those cases, your cumulative trick works : we can convert an aggregate bound into a per-time-point capacity competition, and that enforces the limit cleanly. However, the other two regulations have a different structure that I did not articulate clearly — the previous example was only meant to motivate the need for derived interval overlap, not to fully characterize the problem. Let me use the cycle regulation as the clearest example. A cycle begins and ends with a 34-hour consecutive rest period. Within a cycle, total working time (driving + on-duty) accumulates. Once 70 hours (4200 minutes) of working time has accumulated, no further driving is allowed until the next 34-hour reset. Crucially: On Duty (fuel, pickup/delivery, inspection..) time past 70h is allowed. Only driving past that threshold is forbidden. So the violation is type-dependent and position-dependent. This is not a “total working time ≤ 70h” constraint. It is: “Find the point inside the cycle where cumulative working time reaches 70h. From that point until the cycle ends, driving is prohibited.” So what I need to derive is a time boundary determined by accumulated overlap. Concretely, inside a cycle window [cycle_start, cycle_end]: Compute total working time in the cycle (driving + on-duty). Identify the first time at which cumulative working time reaches 4200. Create a derived “no-driving zone” interval from that time to cycle_end. Enforce addNoOverlap between this zone and all driving intervals. The cumulative trick helps bound totals, but here I need to derive a boundary in time from accumulated overlap. That is where the idea of a first-class overlap_size becomes central — not just to cap totals, but to compute how much activity lies inside a variable window and to reason about where thresholds are crossed. So the earlier 11-hour example was only illustrating one simpler use case. The deeper requirement is the ability to compute: “how much of a set of intervals overlaps a variable-bounded window” as a proper integer expression that can participate in further structural modeling. If you see a better way to model this pattern — one that can derive such a boundary without exploding into per-candidate Booleans — I would genuinely appreciate your guidance. If not, do you think a primitive of this kind could realistically make it into CP-SAT in the foreseeable future? And if that’s also unlikely: is something like this even architecturally feasible within CP-SAT’s current design, or are there internal reasons (e.g., propagation architecture, scheduling layer interfaces, linearization limits, etc.) that make this kind of derived-overlap construct fundamentally hard to support? If it is feasible, could you advise how one might go about building it (even at the C++ level / custom propagator level)? I’m prepared to invest whatever time it takes — even years if needed (I'm a very persistent person) — because, as I mentioned in the original post, this problem has deep personal meaning to me, which I’d be happy to discuss privately. Also, if you think this would realistically require someone with more solver implementation experience or higher level of expertise, could you recommend anyone who might be open to collaborating? I’d be happy to compensate financially. Thank you again for your time and guidance. —Reply to this email directly, view it on GitHub, or unsubscribe.You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>