Performance enhancement: a static, acyclic (DAG) collection-root @ShadowSources still forces the ARBITRARY tier and full-graph Tarjan on every move; cost scales with node count, not edge count

Start in GraphStructure.determineGraphStructure to see how a GROUP parent is classified as arbitrary, then read DefaultTopologicalOrderGraph.commitChanges, which rebuilds the full Tarjan SCC on every move. The issue offers four options, from a WARN diagnostic naming the causing @ShadowSources path to a new incremental tier, and the maintainers have not chosen one. Any first change should be the smallest option, the diagnostic, with a test that checks the warning is logged.

Summary

A custom shadow variable supplier that reads a shadow variable of entities held in a
problem-fact collection (e.g. @ShadowSources({"resource", "previousJob.endTime", "predecessorJobs[].endTime"}))
is classified with ParentVariableType.GROUP, which makes the graph structure
ARBITRARY_SINGLE_ENTITY_AT_MOST_ONE_DIRECTIONAL_PARENT_TYPE. That tier rebuilds the topological order
(DefaultTopologicalOrderGraph.commitChanges → full Tarjan SCC over every node of the session) on
every move.

Two properties of this make the cost very hard to reason about from the model source alone:

1. It is a step function, not a gradient — a single dependency row flips the whole model from the
   incremental SINGLE_DIRECTIONAL_PARENT path to the full-graph path.
2. The cost is proportional to node count (entities × shadow variable groups), not to the number of
   dependency edges. Removing 100% of the dependency edges from the model while keeping the declared source
   changes runtime by only 0.85–1.11× (noise band).

We are not asking about job-shop specifics: the class we think deserves its own tier is a collection-root
source whose edge set is static and forms a directed acyclic graph. In that class, the parent membership
comes from problem facts that are wired once before the solve and never change during it — a move can change a
shadow value, but it cannot add, remove or redirect an edge. Acyclicity is therefore decidable once, at
session build, and re-validating it per move can never discover anything new. Our own instance of that class is
a strictly forward Finish-to-Start graph with fan-out 1 (the same argument holds for forward SS/FF variants, and
for any static DAG, not just scheduling). The conservative "the graph may be arbitrary" assumption never pays for
itself here — yet we cannot drop the source either, because it is load-bearing for score correctness (see
Why we can't just remove it below).

Measured impact (Timefold 2.5.0, single-threaded, 60s budgets)

Production-shaped dataset: 3009 jobs, 1004 dependency edges (100% Finish-to-Start, max fan-out 1),
13 resources, ~9027 declarative shadow nodes (3 shadow variable groups per job).

Reading	With predecessorJobs[].* sources (current model)	Both sources removed
Graph structure tier	ARBITRARY_SINGLE_ENTITY_AT_MOST_ONE_DIRECTIONAL_PARENT_TYPE	SINGLE_DIRECTIONAL_PARENT
Construction heuristic move evaluation speed	477/sec	5591/sec (11.7×)
Placed entities in 60 s	217–258 of 3009 (5 runs, median 224)	805–830 (4 runs, median 814.5) (≈3.6×)
CPU samples whose stack contains DefaultTopologicalOrderGraph	85.0–86.6%	0.0% (all 4 runs)
CPU samples whose stack contains DefaultVariableReferenceGraph	90.6–92.1%	0.0%
CPU samples in ...impl.domain.variable.declarative.*	91.8–93.6%	35.2–36.0%
Time to first feasible solution	2739–2957 ms	2301–2413 ms

Scaling of the per-move cost with node count (synthetic fixture, same topology, 100 resource chains):

Nodes	Relative commitChanges cost
9027 (baseline)	1.0×
×3	×5–7
×10	×19.6–20.8

Edge-count scaling, same node count: dependency edges 1004 → 0 gives 0.85–1.11× (i.e. no effect).

Environment: Timefold Solver 2.5.0, JDK 21, Windows 11 (build 26300) x64, single solve thread,
fixed withRandomSeed, list variable model (@PlanningListVariable on resources + @PlanningPinToIndex).

Checked against the current release line before filing

2.7.0 (2026-09-24) shipped "shadows: decrease allocations in shadow variable processing" and "shadows: improve
move evaluation speed", and its notes tell heavy shadow-variable users to expect an order-of-magnitude move-speed
gain. We have not re-measured on 2.6/2.7 — the numbers above are 2.5.0 only. What we did check is whether the
two structural facts this issue is about still hold on main, by reading the sources:

• GraphStructure still treats a collection-root (GROUP) parent — like INDIRECT / INVERSE / VARIABLE /
  LIST_ELEMENT — as isArbitrary, so a static forward-only DAG gets no cheaper tier.
• DefaultTopologicalOrderGraph.commitChanges(BitSet changed) still clears componentMap and calls
  strongConnect for every index in 0..forwardEdges.length-1. The changed argument is only written to
  (changed.set(node)), never read to bound the traversal.

So whatever the 2.7.0 work optimizes, it does not change how many nodes are touched per move, which is the part
that behaves as a step function on the declared source shape.

Why we can't just remove the source

The supplier needs the predecessor's actual shadow times to compute a start-time lower bound.
If we read them without declaring them (e.g. via a code lookup on the solution), the read does not enter
the propagation graph, so a predecessor moving on another resource does not trigger recomputation of the
successor — incrementally scored state diverges from fully recalculated state.

We reproduced exactly that: with the sources removed and a small cross-resource FS dependency,
EnvironmentMode.FULL_ASSERT throws (this is from a synthetic three-entity fixture, not production data):

Score corruption (-120hard/120soft): the workingScore (-120hard/0medium/-240soft) is not the
uncorruptedScore (0hard/0medium/-360soft) after completedAction (2-Opt(firstEntity=Resource(M1),
secondEntity=Resource(M1), firstEndpointIndex=0, secondEndpointIndex=2)):
  The corrupted scoreDirector has 2 ConstraintMatch(es) which should not be there:
    Job dependency timing violation/[Job(B), JobDependency, Job(A), 120]=-120hard/0medium/0soft
Shadow variable corruption in the corrupted scoreDirector: None

Note the last line: the framework reports no shadow variable corruption, so this class of bug gets
misattributed to the constraint implementation rather than to the missing source path — which is part of
what makes ask (1) below worth doing. So the collection-root source is required for correctness;
the only lever we have is which graph tier the framework chooses.

What we are asking for

Any of the following would remove the cliff. Listed from cheapest to most invasive:

1. Diagnostics (smallest change, biggest usability win): when the selected structure is one of the
   ARBITRARY* tiers, log at WARN which @ShadowSources path caused the downgrade (which root path resolved
   to GROUP/INDIRECT/...), together with the resulting node count. Today we had to read
   GraphStructure.determineGraphStructure and run a JFR profile to learn that a single declared path was
   costing 85% of CPU.
2. A tier for the static-DAG case: at session build, run Tarjan/SCC once. If the graph is acyclic and
   every collection-root (GROUP) path resolves to a problem-fact collection whose membership is immutable
   during the solve, then the edge set cannot change and per-move re-validation is pure overhead. Such a model
   could take a cheaper per-move path: propagate along the precomputed topological order, restricted to the
   downstream closure of the changed nodes, with the usual early-exit when a value doesn't change. Multiple
   parents are not a problem there — a node is simply revisited after each of its parents, which is what the
   existing SINGLE_DIRECTIONAL_PARENT path already does for one parent.
3. Detection, not declaration would be preferable to an opt-in, but if auto-detection is judged too risky, an
   explicit opt-in is acceptable (annotation attribute or solver config flag) — with the build-time check
   failing the session when the declared assumption does not hold, rather than silently falling back.
   FULL_ASSERT already gives the safety net for the cases the check cannot prove statically, so the downside of
   being wrong is a loud error in development, not a wrong best solution in production.
4. Failing all of the above, make the arbitrary tier incremental: on commitChanges, restrict the
   Tarjan/SCC re-run to the dirty closure of the changed nodes instead of the whole session graph. Even a partial
   improvement here pays off super-linearly on thousand-entity models, since the current implementation rebuilds
   the order and reallocates the per-SCC bitsets and index arrays on every move.

Alternatives considered

• Drop the dependency source and accept stale shadows: rejected, causes the score corruption above.
• Reduce the number of dependency edges / fan-out: measured no effect (0.85–1.11×), because cost scales
  with nodes, not edges.
• Reduce entity count per solve (batching): works, and is what we are doing as a workaround, but it pushes a
  framework limitation into application-level model splitting.
• Compute the lower bound as a plain problem fact refreshed between solve rounds: also works (keeps the fast
  tier), but it changes the semantics — successors no longer follow predecessors within a round, so it needs
  multi-round iteration and its own convergence criteria. We would rather not have to choose between
  expressiveness and a usable move rate.

Related

• #2506 (sourcing declarative shadow variables from list elements) — adjacent but different root
  (list variable elements vs. an entity-held problem-fact collection).
• #1728 / the domain-modeling docs "tips and tricks for optimal performance" for shadow variables — the docs
  acknowledge that shadow variable modelling choices cost performance and note the solver still works
  "albeit with slightly lesser performance". In this case the loss is not slight (11.7× move-rate gap), which
  is why we think it deserves more than a doc note.
• #1659 (optimize the updater used for shadow variables) — possibly overlapping with ask (4).

Reproduction

The dataset and harness are proprietary, but the effect is fully reproducible from the shape alone:
a job-shop with N resources as list variables, jobs with startTime/endTime declarative shadows, a
predecessorJobs problem-fact collection wired once at solution build time, and one
@ShadowSources("predecessorJobs[].endTime"). Asserting GraphStructure.determineGraphStructure(...) returns
ARBITRARY_SINGLE_ENTITY_AT_MOST_ONE_DIRECTIONAL_PARENT_TYPE, versus SINGLE_DIRECTIONAL_PARENT once the
source is removed.