Readiness at the Critical Point

Abstract

Sustainment organizations that maintain fleets of complex repairable assets face a mechanism ordinary scheduling theory omits. It is cannibalization: deferred maintenance forces parts to be taken from other assets, which disables those assets, which creates further demand. The practice is documented across the services and inconsistently tracked [14]. What [14] establishes is that cannibalization is widespread; the behaviour of readiness under it is what this paper derives.

We show that a model of that mechanism does not predict a smooth decline in readiness as maintenance capacity tightens. It predicts readiness holding, and then collapsing.

This paper argues that the collapse is a saddle-node bifurcation, and traces what that implies for the optimization problem sitting on top of it. We formalize Readiness-Constrained Sustainment Scheduling (RCSS), a joint maintenance induction and logistics routing problem over a fleet whose failures are correlated through shared part lots, shared environments, and shared repair capacity.

Our first result is negative in a way that redirects the rest of the work. We show that expected readiness can be written as a scalar response function composed with a monotone submodular coverage function, and that on the stable branch this response is concave for every feedback strength. Readiness is therefore monotone submodular, its submodularity ratio is one, and the standard guarantees apply unchanged. The cannibalization cascade, which is the feature practitioners find most alarming, does not damage the approximation guarantee at all. We expected the opposite and the algebra says otherwise.

What the bifurcation damages instead is conditioning. The derivative of the response diverges as (π_max - π)^−1/2 on approach to the tipping point, so the ratio of extreme slopes tends to zero even though concavity is preserved. The objective becomes stiff, not non-submodular: the marginal value of an induction varies by a large and growing factor across the operating range. Stiffness falls on estimation, not on optimization. We show that the sensitivity of predicted readiness to error in the coupling parameters diverges with the same exponent, which makes calibration of the graph learning and language model components a structural requirement rather than a refinement.

Submodularity does fail, but for an unrelated reason: mission requirements are conjunctive. When readiness is the probability that at least m assets are simultaneously capable, the response is S-shaped and early inductions show increasing returns. We give the exact condition under which this occurs, m - 1 > (n - 1) q_lo, and a general bound γ ≥ inf h' / sup h' covering both regimes.

Finally we ask which features of the problem leave many near-optimal schedules indistinguishable to single-element moves. We find two: proximity to the bifurcation, and the conjunctive objective. That is the only setting in which we think a quantum heuristic has a defensible reason to be tried. We state it as a falsifiable hypothesis with a test protocol, and we are explicit that classical solvers currently dominate at every fleet size of practical interest.

1. Introduction

1.1 The observation

Consider an organization responsible for keeping a fleet of aircraft mission capable. It has a fixed number of depot slots per period, a spare parts inventory with finite depth, and assets that degrade under use. The standard treatment is a scheduling problem: predict which assets will fail, induct them before they do, subject to capacity.

That treatment omits the dominant dynamic. When a part is needed and inventory is empty, it is frequently removed from another aircraft. The second aircraft is then not mission capable. If its part is later needed elsewhere, the process repeats. The practice is documented across the services, and the GAO has reported that it is both widespread and inconsistently tracked, with the Army at that time not recording it service-wide at all [14].

Structurally, a shortfall creates demand. In the model of Section 3.4, feedback of this kind produces two regimes: one in which capacity changes barely move readiness, one in which they move it enormously, and a sharp transition between them. Figure 1 draws the loop.

1.2 What this paper claims

The claim is not that cannibalization is harmful, which is obvious, or that readiness is nonlinear, which is known. The claim concerns where the difficulty lands.

A natural expectation, and the one this work began with, is that the cascade destroys the diminishing-returns structure that approximation algorithms rely on. It does not. Section 5 proves that readiness remains submodular on the stable branch for every feedback strength, so the standard guarantees survive right up to the edge of collapse.

The difficulty moves elsewhere. We establish four things:

1. Readiness is submodular under the cascade (Theorem 2, Section 5.5, proved). The feedback does not cost anything in approximation ratio.
2. The objective becomes ill-conditioned near the bifurcation (Section 5.4, derived). The slope ratio tends to zero while concavity survives.
3. Sensitivity to parameter error diverges with the same inverse square root exponent (Observation 1, Section 8.4, derived). Any estimator inherits this; it comes from the bifurcation.
4. Conjunctive mission requirements do break submodularity (Proposition 2, Section 5.6, proved with an exact threshold), independently of the cascade.

We also state one refutable hypothesis about where non-classical optimization could matter (Section 7.2) and give the experiment that would settle it.

In practice, then, spend the next unit of effort on calibrated estimation and not on a better combinatorial algorithm. Optimization papers usually point the other way.

1.3 What this paper does not claim

It reports no measured results on any fleet. It demonstrates no quantum advantage and argues at length that none is available at relevant scale. The experimental protocol in Section 9 is a design, not a report.

On the question of whether combining graph learning, quantum optimization, approximation theory, and complex systems is substantive or decorative, the honest answer is that the central theorem needs two of the four. Theorem 2 is proved from a bifurcation analysis of the scarcity feedback (complex systems) and from submodular function theory (approximation algorithms). Graph learning enters in Section 8 because the theorem's inputs have to be estimated from maintenance records, and Observation 1 shows that estimation is where the difficulty concentrates. Quantum optimization enters in Section 7 as a hypothesis about the inner subproblem and contributes nothing to the theorem. Two pillars carry the result; the other two are where its consequences land. We would rather state that than claim a four-way necessity the paper does not demonstrate.

2. Related work

Submodular maximization. Nemhauser, Wolsey and Fisher established that greedy maximization of a monotone submodular function under a cardinality constraint achieves 1 - (1 - 1/k)^k, which tends to 1 - 1/e [1]. The companion paper gives 1/2 for a single matroid and, more generally, 1/(p + 1) for an intersection of p matroids [2]. Călinescu, Chekuri, Pál and Vondrák later achieved 1 - 1/e for a single matroid using continuous greedy with pipage rounding [3]. These distinctions matter here, because the feasible region of RCSS is an intersection of two matroids and the three constants are different. Feige's 1 - 1/e inapproximability for maximum coverage, which holds under P ≠ NP, makes the cardinality constant optimal [4].

Approximate submodularity. Das and Kempe introduced the submodularity ratio γ and proved a 1 - e^−γ guarantee for greedy on set functions that are not submodular, under a cardinality constraint [5]. We use it for the conjunctive objective of Section 5.6. It is not needed for the fractional objective, which Theorem 2 shows is submodular.

Cascading failure and critical phenomena. Motter and Lai analyzed load-redistribution cascades [6], Buldyrev and colleagues showed that interdependent networks fail more abruptly than isolated ones [7], and the percolation literature supplies the standard apparatus for locating critical points [8]. Branching-process facts used here are standard [15]. Our contribution is not to this theory but to connecting it to an optimization guarantee.

Inventory and sustainment. Sherbrooke's METRIC model is the foundation of multi-echelon repairable inventory [9] and, like most of that literature, treats demand as exogenous Poisson. The feature driving our analysis is that demand is endogenous.

Prognostics. Remaining useful life estimation on turbofan degradation data is a mature benchmark task following the Commercial Modular Aero-Propulsion System Simulation (C-MAPSS) datasets [10], whose generation methodology is documented separately [11].

Conformal prediction. Distribution-free coverage under exchangeability originates with Vovk, Gammerman and Shafer [12]; we follow the exposition in [13].

3. Problem formulation

3.1 Objects

Let A be a fleet of n repairable assets, D a set of depots, and T = {1, ..., T} a planning horizon.

An induction is a triple a = (i, d, t) in G = A × D × T, meaning asset i enters depot d in period t. A schedule is a subset S ⊆ G.

Each asset is itself a graph of components, and is mission capable when every component in a designated critical set is serviceable. This conjunctive requirement returns in Section 5.6.

Table 1 lists the notation. The tables in this paper are inline exhibits, not numbered floats; each is read with the paragraph that introduces it. It is written in the same alphabet as the body: where the paper sets κ, the table says κ. Rows are ordered by where the symbol is first used.

Two symbols are overloaded. We flag them here instead of renaming, because context disambiguates each.

• T is both the horizon set and its cardinality.
• M is a matroid in 3.2 and a superset in Lemma 1, and M_k in 5.6 is a Poisson-binomial count, unrelated to either.

Three more collisions have been removed outright: the generic set function of Lemma 1 is ν, not m; the independent-rounding indicators of Section 6 are Y_i, not X_i; and the disabled count is X, since D is the depot set.

3.2 Constraints

Asset constraint. Each asset may be inducted at most k_i times over the horizon. Partitioning G by asset gives a partition matroid M₁.

Capacity constraint. Depot d has c_d,t slots in period t. Partitioning G by the pair (d, t) gives a partition matroid M₂.

A schedule is admissible when it is independent in both, so the feasible region is the intersection M₁ ∩ M₂. This is a bipartite degree-constrained structure, and it is important to be precise about what that costs. For a linear objective it is a transportation problem solvable in polynomial time. For a monotone submodular objective, greedy gives 1/3 over an intersection of two matroids [2], not the 1/2 of a single matroid and not the 1 - 1/e of continuous greedy on a single matroid [3]. When T = 1 and a single depot is available, M₂ collapses to a cardinality constraint and the 1 - 1/e results apply. We state which regime is in force wherever a constant appears.

Logistics feasibility. An induction (i, d, t) is effective only if the parts it requires are present at d by t. We write Λ(S) ⊆ S for the inductions supportable by some feasible routing. Maintenance and logistics are therefore not separable, which is why the problem is posed jointly.

3.3 Degradation with coupling

Let W be a symmetric nonnegative coupling matrix on A, where w_ij aggregates shared part lots, shared operating environment, and shared maintenance crews. Section 8 concerns how W is estimated; here it is given. Absent intervention, asset i suffers a primary failure within the horizon with probability p_i.

3.4 The scarcity feedback

Let u ∈ [0, 1] be the mission-capable fraction. Secondary failures induced by cannibalization are modeled as a branching process whose mean offspring number depends on the state:

β(u) = β₀ · (1 + κ · (1 - u))

β₀ is the baseline propensity for one failure to induce another in a healthy fleet, and κ ≥ 0 is the feedback strength. Setting κ = 0 recovers exogenous demand.

For a Galton-Watson process with mean offspring β < 1, the expected total progeny including the root is 1 / (1 - β) and the process is almost surely finite. At β = 1, for a non-degenerate offspring distribution, the process remains almost surely finite but its expectation diverges [15].

3.5 Coverage and the readiness objective

Inductions replace parts, and a replaced part protects every asset depending on that lot. Let σ(S) ⊆ A be the set of assets protected by effective inductions in S, and define the covered failure mass

Q(S) = Σi ∈ σ(S) pi

Assumption 1 (per-induction effectiveness). Each induction a protects a fixed asset set σ_a, so that σ(S) = ⋃_{a ∈ S} σ_a.

Assumption 1 is what makes Q a coverage function, and it is a genuine restriction rather than bookkeeping. Section 3.2 allows a schedule to be only partly supportable by a routing, and when effectiveness depends on the whole schedule through Λ(S), adding an induction can consume the capacity that made another one effective. In that case σ need not be monotone and Q need not be submodular. Everything from Lemma 1 onward assumes Q is monotone submodular, so everything from Lemma 1 onward assumes Assumption 1; where routing feasibility couples inductions, Q(S) must be read as Q(Λ(S)) and we do not prove submodularity.

Under Assumption 1, distinct inductions can still protect overlapping asset sets, so Q is a weighted coverage function: monotone, normalized (Q(∅) = 0), and submodular, not modular. This overlap is what makes the problem combinatorially hard, and Section 4 depends on it. Write P(S) = Q(G) - Q(S) for the uncovered mass.

Expected disabled count X satisfies a self-consistency condition, since each unit of primary failure mass generates 1 / (1 - β(u)) disablements in expectation while u itself depends on X. We write X rather than D, which already denotes the depot set:

X = P(S) / (1 - β(1 - X/n))                                    (1)

Readiness is the expected mission-capable fraction, R(S) = (n - X*(P(S))) / n, where X* is the stable equilibrium of the associated dynamics defined in Section 5.4.

Definition 1 (RCSS). Given A, D, T, matroids M₁, M₂, routing network and part requirements, coupling W, failure probabilities p, and feedback parameters (β₀, κ), find an admissible schedule S with a supporting routing maximizing R(S).

4. Hardness

Proposition 1. RCSS is NP-hard even when κ = 0, T = 1, and a single depot is available. On the subfamily of instances with Σ_i p_i = n(1 - β₀), no polynomial-time algorithm achieves a ratio better than 1 - 1/e unless P = NP.

Proof. Set κ = 0, so β = β₀ is constant and (1) gives X* = P(S)/(1 - β₀). Then

R(S) = 1 - (Q(G) - Q(S)) / (n(1 - β₀)) = c + Q(S) / (n(1 - β₀)),     c = 1 - Q(G) / (n(1 - β₀))

which is affine and strictly increasing in Q(S). An affine strictly increasing map preserves the argmax, so maximizing R exactly is maximizing the weighted coverage Q(S) exactly, and NP-hardness transfers at once. With T = 1 and one depot the constraint is a cardinality bound of c inductions, and weighted maximum coverage under a cardinality bound is NP-hard [4].

The ratio does not transfer for free, because the offset c is nonnegative and an additive offset makes a maximization problem easier to approximate. Scale the coverage instance so that Σ_i p_i = n(1 - β₀), which is always possible since the ratio of a coverage instance is invariant under a common rescaling of its weights. Then c = 0, R(S) = Q(S)/(n(1 - β₀)) is a positive scalar multiple of Q(S), and the reduction is ratio-preserving. Feige showed maximum coverage cannot be approximated within 1 - 1/e + ε for any ε > 0 unless P = NP [4], and that bound now carries over. ∎

The restriction is not a technicality to be waved through. Without it the offset is strictly positive and the empty schedule can already beat 1 - 1/e: with n = 10, p_i = 0.1 and β₀ = 0.5 the offset is c = 0.8, so R(∅) is 0.8 against a maximum of 1.0, a ratio of 0.8 attained by doing nothing. The same algebra runs the other way in Section 6, where a nonnegative offset in the margin objective only improves the achieved ratio.

The reduction is the reason Section 3.5 defines Q as a coverage function rather than a modular one. Had Q been modular, the κ = 0 instance would be a linear objective over a matroid intersection, hence solvable exactly in polynomial time once logistics feasibility is relaxed, and no hardness would follow from the objective itself. The Λ(S) constraint of Section 3.2 is not matroidal and remains a separate source of difficulty. The overlap between the asset sets protected by different inductions is the entire source of difficulty in the benign regime.

Two consequences. First, the problem is hard even with no feedback. Second, under a cardinality constraint the 1 - 1/e of greedy [1] is optimal, so improvement must come from structure, not from a better algorithm for the same objective.

5. The structure of the readiness function

5.1 Readiness is a scalar response composed with a coverage function

R depends on S only through Q(S). Define the response function

h(q) = (n - X*(Q(G) - q)) / n,     so that     R(S) = h(Q(S))

All combinatorial difficulty sits in Q, and all nonlinearity sits in the scalar h. This separation is what makes the analysis tractable: a question about a set function over an exponentially large domain becomes a question about the curvature of a one-dimensional curve, and the curvature is something a bifurcation analysis can settle.

5.2 Concavity of the response transfers submodularity

Lemma 1. Let f(S) = h(ν(S)) with ν monotone, normalized and submodular, and let h be nondecreasing and concave on an interval containing the range of ν. Then f is monotone submodular.

Proof. Monotonicity is immediate. For submodularity take L ⊆ M and a ∉ M. Monotonicity of ν gives ν(L) ≤ ν(M), and submodularity of ν gives ν(L ∪ a) - ν(L) ≥ ν(M ∪ a) - ν(M) ≥ 0. Write δ_L and δ_M for these two increments. Then

f(L ∪ a) - f(L) = h(ν(L) + δL) - h(ν(L))f(M ∪ a) - f(M) = h(ν(M) + δM) - h(ν(M))

Since h is nondecreasing, its increment from a fixed left endpoint is nondecreasing in the length; since h is concave, its increment over a fixed length is nonincreasing in the left endpoint. Shorten the length first and move the endpoint second:

h(ν(L) + δL) - h(ν(L))  ≥  h(ν(L) + δM) - h(ν(L))  ≥  h(ν(M) + δM) - h(ν(M))

The order matters. Taken the other way round the argument would evaluate h at ν(M) + δ_L, which can exceed every value ν attains and so can fall outside the interval the hypothesis covers. In the order above every point lies in [ν(L), ν(M ∪ a)], and both endpoints are values of ν. ∎

Two cautions about the converse, which we do not claim. Concavity is sufficient, not necessary: on a finite range only increments of realizable lengths are tested, so a non-concave h can still produce a submodular f. Monotonicity of ν is also required, and nonnegativity of ν(S) is not a substitute. With ν(∅) = 10, ν_a = +1, ν_b = -3 and h = √·, every value of ν is positive and h is concave and increasing, yet f(a) + f(b) = 5.9624 < 5.9907 = f(ab) + f(∅), so submodularity fails. Monotonicity is the hypothesis doing the work here. Normalization is not used in the proof at all; we keep it so that f inherits f(∅) = h(0).

5.3 The submodularity ratio is bounded by the slope ratio

Recall the submodularity ratio of Das and Kempe [5]: for monotone f and a budget k,

γU,k = min over (L, S), S ∩ L = ∅, |S| ≤ k,   of   Σa ∈ S [f(L ∪ {a}) - f(L)]  /  [f(L ∪ S) - f(L)]

taken over pairs with f(L ∪ S) > f(L), so the ratio is defined; γ ∈ [0, 1], and γ = 1 when f is submodular.

Theorem 1. Let f(S) = h(ν(S)) with ν monotone, normalized and submodular, and h differentiable and strictly increasing on an interval containing the range of ν. Let ρ = inf h' / sup h' over that interval. Then γ ≥ ρ.

Proof. Fix L and disjoint S. For each a ∈ S, the mean value theorem gives some ξ_a between ν(L) and ν(L ∪ a) with

f(L ∪ a) - f(L) = [ν(L ∪ a) - ν(L)] · h'(ξa) ≥ [ν(L ∪ a) - ν(L)] · inf h'

Submodularity of ν gives Σ_{a ∈ S} [ν(L ∪ a) - ν(L)] ≥ ν(L ∪ S) - ν(L), so

Σa ∈ S [f(L ∪ {a}) - f(L)] ≥ [ν(L ∪ S) - ν(L)] · inf h'

Applying the mean value theorem once more, f(L ∪ S) - f(L) = [ν(L ∪ S) - ν(L)] · h'(ξ) ≤ [ν(L ∪ S) - ν(L)] · sup h'. Dividing gives a ratio of at least ρ for every admissible pair. ∎

Remark (discrete form). Section 5.6 applies Theorem 1 to an h defined on {0, 1, …, n}, where no derivative exists. The same argument runs with increments in place of derivatives: replace inf h' by the smallest unit increment min_j [h(j+1) - h(j)] and sup h' by the largest, and every step of the proof goes through unchanged, since h(l + s) - h(l) is a sum of s unit increments. We write ρ for either form and say which is meant where it matters.

Corollary 1. Under a cardinality constraint, greedy maximization of f returns at least (1 - e^−ρ) · OPT, combining Theorem 1 with [5]. We state this for cardinality because that is the setting in which the 1 - e^−γ guarantee is proved; it does not transfer to a matroid intersection, and we make no claim there.

The reading of Theorem 1 is that the guarantee is controlled by how much the marginal value of maintenance varies across the operating range. Sections 5.5 and 5.6 show the bound can be arbitrarily loose, so it is informative only where h is not concave.

5.4 The response near the tipping point

Substituting β(u) = β₀(1 + κ(1 - u)) and u = 1 - X/n into (1), writing x = X/n and π = P(S)/n:

x · (1 - β₀ - β₀ κ x) = π                                      (2)

Write g(x) for the left side, a downward parabola with maximum

πmax = (1 - β₀)² / (4 β₀ κ)        attained at    xc = (1 - β₀) / (2 β₀ κ)

Write Δ(π) = (1 - β₀)² - 4 β₀ κ π for the discriminant of (2), which is zero exactly at π_max.

(a) Existence threshold. For π > π_max equation (2) has no real root: above a critical uncovered mass the healthy equilibrium ceases to exist. The two equilibria collide and annihilate, which is a saddle-node bifurcation, and x_c - x*(π) = sqrt(π_max - π) / sqrt(β₀ κ) reproduces the generic normal-form scaling.

(b) Square-root divergence. The stable root is

x*(π) = [ (1 - β₀) - sqrt( Δ(π) ) ] / (2 β₀ κ),        dx*/dπ = Δ(π)−1/2

Since Δ(π) = 4 β₀ κ (π_max - π), the derivative diverges as (π_max - π)^−1/2.

(c) Slope ratio. With h(q) = 1 - x*(Q(G)/n - q/n) the chain rule gives h'(q) = (1/n) Δ^−1/2, so over an operating range from π_lo to π_hi < π_max,

ρ = inf h' / sup h' = sqrt( Δ(πhi) / Δ(πlo) ) = Θ( (πmax - πhi)1/2 )

Dynamics and stability. Equation (1) is an equilibrium condition, and stability belongs to a flow, not to an algebraic root, so we state the flow: ẋ = π - g(x), whose equilibria are exactly the roots of (2). Then ∂ẋ/∂x = -g'(x), and at the smaller root g'(x*) = sqrt(Δ(π)), giving ∂ẋ/∂x = -sqrt(Δ) < 0. The smaller root is therefore the stable equilibrium for all π < π_max, and it is the branch referred to throughout.

We call the point π = π_max the fold. One clarification is worth making, because Section 3.4 may suggest otherwise: at the fold the mean offspring number is β = β₀(1 + κ x_c) = (1 + β₀)/2 < 1. The collapse happens while the branching process is still strictly subcritical. It is a fold of the self-consistency equation (2), not branching criticality.

Numerics. The naive fixed-point iteration x ← π/(1 - β₀ - β₀ κ x) has |T'(x*)| = β₀ κ (x*)² / π, which stays below one for every π < π_max and reaches one exactly at the fold. Contraction is therefore lost at the fold itself, not before it. But it degrades steeply on approach: the modulus is 0.52 at 0.9 π_max and 0.94 at 0.999 π_max, and since it depends only on the ratio π/π_max those two values hold for every (β₀, κ). Near the tipping point, solve the quadratic directly or integrate the flow; do not iterate the map.

Physical range. These quantities are meaningful only where the fold is reachable with x* ∈ [0, 1]. Since x_c > 1 whenever κ < (1 - β₀)/(2 β₀), readiness would go negative before the tipping point in that region. The bifurcation is physically relevant for κ ≥ (1 - β₀)/(2 β₀), and statements about approaching it should be read with that restriction. Figure 2 shows the response and its curvature together, with the reparameterization that connects them.

5.5 The cascade preserves submodularity

Theorem 2. Adopt Assumption 1, and suppose Q(G)/n < π_max, so that every schedule including the empty one lies on the stable branch. Then in the model of Section 3.4 the response h is increasing and concave in q for every β₀ ∈ (0,1) and every κ ≥ 0. Consequently R is monotone submodular and γ = 1.

The hypothesis Q(G)/n < π_max is needed, not decorative. The worst case is the empty schedule, which leaves the whole failure mass uncovered at π = Q(G)/n; if that exceeds π_max then h is undefined there, R(∅) does not exist, and "R is monotone submodular" is not a statement about a function. Written out, the condition is κ < n(1 - β₀)² / (4 β₀ Q(G)).

Proof. From 5.4(b), h'(q) = (1/n) Δ^−1/2 > 0. Differentiating, with dΔ/dq = 4 β₀ κ / n > 0:

h''(q) = (1/n)(-1/2) Δ−3/2 (4 β₀ κ / n) = -2 β₀ κ / (n² Δ3/2) ≤ 0

strictly negative for κ > 0, and zero for κ = 0 where h is affine. So h is concave. Q is monotone, normalized and submodular by Section 3.5, so Lemma 1 gives submodularity of R, and a monotone submodular function has γ = 1. ∎

Consequences for the algorithm, stated by constraint type. The three constants below are different and the literature is often quoted loosely, so we state which applies where.

The feasible region of RCSS is M₁ ∩ M₂, so the applicable constant is 1/3 unless T = 1 and a single depot reduce M₂ to a cardinality bound. We are not aware of a 1 - 1/e result for two matroids and do not claim one.

This runs against the intuition that motivated the investigation. The feedback loop producing the collapse is genuine positive feedback and it nonetheless leaves the set function submodular. The reason is visible in the proof: positive feedback makes the disabled count convex in uncovered mass (d²x*/dπ² = 2 β₀ κ Δ^−3/2 > 0), and readiness is its negation under an affine decreasing reparameterization, which flips convexity into concavity.

What degrades instead is conditioning. The condition number 1/ρ diverges as (π_max - π)^−1/2. The objective is submodular but stiff: the marginal value of an induction varies by a large and growing factor across the operating range. Theorem 1 remains valid but is loose here, since the true γ is one. Figure 3 plots the slope ratio against the margin to the fold. Stiffness is not an optimization problem. Section 8.4 shows it is an estimation problem.

5.6 Where submodularity actually fails

Mission requirements are not fractional. An operator needs some number of assets simultaneously capable. Let N(S) be the number of capable assets and

Rm(S) = Pr[ N(S) ≥ m ]

Assume homogeneous failure probabilities so that coverage reduces to a count, that each induction protects exactly one previously unprotected asset so the count rises by one at a time, and take per-asset capability q_hi when covered and q_lo when not, independent across assets. Then N(S) is Poisson-binomial and R_m depends only on the covered count k, so the relevant h is defined on {0, ..., n} with unit increments, where concavity and the discrete increment condition coincide. The second assumption matters for the reading of the result: it removes the coverage overlap that Section 4 identifies as the source of difficulty in the benign regime, so the complementarity found below is separate from overlap, not a consequence of it.

Upgrading one asset from q_lo to q_hi gives the identity

h(k+1) - h(k) = (qhi - qlo) · Pr[ Mk = m - 1 ]

where M_k counts the other n - 1 assets. The marginal therefore increases at k exactly when Pr[M_k+1 = m - 1] > Pr[M_k = m - 1].

Proposition 2. With the assumptions above, and with n ≥ 2 and 1 ≤ m ≤ n, the marginal value of the first induction is increasing, hence R_m is not submodular and γ_U,k < 1 for every budget k ≥ 2, if and only if

m - 1 > (n - 1) · qlo

Proof sketch. Evaluating the condition at k = 0 with B ~ Bin(n - 2, q_lo) reduces it to Pr[B = m - 2] > Pr[B = m - 1], and the binomial mode inequality gives the stated form. ∎

The range 1 ≤ m ≤ n is required. For m > n the requirement is unmeetable, R_m is identically zero and no marginal increases, while the stated inequality still holds.

The weaker hypothesis n q_lo < m < n q_hi is not sufficient. For n = 12, q_lo = 0.55, q_hi = 0.95, m = 7, the expected capable counts are 6.60 and 11.40, so m lies strictly between them, yet the marginals decrease from the first step and R_m is exactly submodular with γ = 1. The gap between m > n q_lo and m - 1 > (n - 1) q_lo is precisely where such cases live.

Illustrative computation (not a measurement). For n = 24, m = 16, q_lo = 0.55, q_hi = 0.95, the condition holds since (n-1) q_lo + 1 = 13.65 < 16. Indexing the marginal by the covered count before the induction, as the identity above does, the gain from going from k to k + 1 rises for k from 0 to 6, peaks at k = 6, and first falls at k = 7. The Das-Kempe ratio depends on the budget k it is minimised over, so we give it by budget instead of quoting a single number. Table 3 lists it:

The ratio saturates at 0.665, attained at |L| = 0 and |S| = 10. The submodular case has γ = 1 and a greedy guarantee of 1 - 1/e = 0.632; this instance has γ = 0.665 and a guarantee of 0.485. The comparison to make is 0.485 against 0.632, since 0.665 and 0.632 are quantities of different kinds. These numbers are computed from the stated parameters and the stated budget, and are not observed on a fleet. Figure 4 plots the marginals for this instance.

Theorem 1 is vacuous here. In its discrete form the slope ratio over the full range is ρ ≈ 4.8 × 10⁻⁵, because the tail probability flattens almost completely at large k, against the full-range γ = 0.665. Restricting to the convex window k ≤ 6 gives ρ = 0.566, against the γ = 0.721 for the matching budget. Theorem 1 is a general sufficient bound and should not be expected to be tight; on this instance direct computation of γ is the right tool.

The complementarity has a plain reading. When the capable count is far below m, one more capable asset barely changes the probability of meeting the requirement. Several more change it considerably. That is increasing returns, and it is a property of the requirement, not of the degradation process.

5.7 Reading the result

Three statements, in order of how much they revise the starting intuition.

First, the cascade does not break the approximation guarantee. Readiness stays submodular on the stable branch regardless of feedback strength, and the applicable constant depends only on which constraints bind. The alarming dynamic and the hard optimization problem are not the same thing.

Second, the cascade makes the objective ill-conditioned, and ill-conditioning attacks the inputs. The binding constraint near collapse is the quality of the estimated model, not the quality of the scheduler.

Third, the genuine loss of submodularity comes from conjunctive mission requirements, is governed by an exact and checkable threshold, and would be present in a fleet with no coupling at all.

6. Algorithms

Theorem 2 settles the fractional case: the objective is submodular and the standard guarantees apply, with the constant determined by the binding constraints. The algorithmic question is therefore confined to the conjunctive objective of Section 5.6 and to the stiffness of Section 5.5.

Continuous greedy on the multilinear extension. Evaluating the multilinear extension requires the law of Q(S) under independent rounding. We flag a limitation that is easy to state wrongly: when failure probabilities are heterogeneous, Q(S) = Σ_i p_i Y_i, with Y_i the indicator that asset i is protected, is a weighted sum whose law has up to 2ⁿ atoms, and is not Poisson-binomial. Cheap evaluation via a one-dimensional integral is available only under homogeneous p_i, where Q reduces to a count, or through a discretization or central-limit approximation whose error would need to be controlled. Under the coverage structure of Section 3.5 the indicators are not independent in any case. We regard efficient evaluation of the multilinear extension for RCSS as open.

Target the bifurcation directly. If the practical obstruction is proximity to π_max, an alternative objective is to maximize the margin π_max - π(S). Because π(S) = (Q(G) - Q(S))/n, the margin equals π_max - Q(G)/n + Q(S)/n, an affine increasing function of Q(S), so maximizing it is maximizing the coverage Q(S), which is monotone submodular, so the same constants apply and no new machinery is required. Its appeal is not a better ratio but a better conditioned objective: it removes the Δ^−1/2 amplification from the optimization entirely, and the quantity it optimizes is the one Section 8.4 identifies as most worth estimating accurately. It is conservative when the fleet is healthy, since it ignores how much readiness a given margin actually buys.

Handle the conjunctive objective directly. For R_m, Proposition 2 identifies exactly when complementarity appears, and it appears at small k. A method that commits to blocks of inductions rather than single ones on the convex segment, then reverts to greedy once past the inflection, is the obvious response. We have not analyzed its guarantee.

6.1 Reference implementation

Every quantity in Sections 5 and 8 is a few lines of arithmetic. Listing 1 gives them in Python, so the claims can be checked instead of taken on trust.

1import math
2 
3def pi_max(b0, kappa):
4    "Critical uncovered mass. The fold of (2). No fold exists when kappa = 0."
5    if kappa == 0:
6        return math.inf                  # linear regime: never collapses
7    return (1 - b0) ** 2 / (4 * b0 * kappa)
8 
9def x_star(pi, b0, kappa):
10    "Stable disabled fraction: the smaller root of (2), or None past the fold."
11    if kappa == 0:
12        return pi / (1 - b0)             # the case Proposition 1 uses
13    disc = (1 - b0) ** 2 - 4 * b0 * kappa * pi
14    if disc < 0:
15        return None                      # no healthy equilibrium
16    return ((1 - b0) - math.sqrt(disc)) / (2 * b0 * kappa)
17 
18def slope_ratio(pi_lo, pi_hi, b0, kappa):
19    "rho = inf h' / sup h' over [pi_lo, pi_hi]. Tends to 0 at the fold."
20    if pi_hi < pi_lo:
21        raise ValueError("pi_hi must be the larger endpoint")
22    if kappa == 0:
23        return 1.0                       # h is affine, so the slopes agree
24    d = lambda pi: (1 - b0) ** 2 - 4 * b0 * kappa * pi
25    if d(pi_hi) <= 0:
26        raise ValueError("pi_hi is at or past the fold")
27    return math.sqrt(d(pi_hi) / d(pi_lo))   # lies in [0, 1] by construction
28 
29def sensitivity(pi, b0, kappa):
30    "|dR/dkappa| from Observation 1. Diverges as (pi_max - pi)^(-1/2)."
31    disc = (1 - b0) ** 2 - 4 * b0 * kappa * pi
32    if disc <= 0:
33        return math.inf                  # at or past the fold
34    x = x_star(pi, b0, kappa)
35    return b0 * x * x / math.sqrt(disc)
36 
37def tail_at_least(ps, m):
38    "Pr[N >= m] for independent Bernoulli ps: exact Poisson-binomial."
39    if m <= 0:
40        return 1.0                       # guard: dp[-1:] would be wrong
41    dp = [1.0] + [0.0] * len(ps)
42    for p in ps:
43        for k in range(len(dp) - 1, 0, -1):
44            dp[k] = dp[k] * (1 - p) + dp[k - 1] * p
45        dp[0] *= 1 - p
46    return sum(dp[m:])
47 
48def complementary(n, m, q_lo):
49    "Proposition 2: does the first induction show increasing returns?"
50    return (m - 1) > (n - 1) * q_lo

The last function, complementary, is the whole of Proposition 2. Checking it against a brute-force evaluation of tail_at_least over a parameter grid is the quickest way to confirm the threshold, and is what Figure 5 reports.

7. Quantum optimization: what would have to be true

7.1 What the hardware can and cannot do

The inner problem of assigning inducted assets to depot slots admits a standard quadratic unconstrained binary optimization (QUBO) encoding, and therefore an Ising form suitable for QAOA [16] or annealing hardware.

That does not mean quantum methods should be used. For n = 200 assets, |D| = 5 depots and T = 12 periods, the natural binary encoding has 200 × 5 × 12 = 12,000 variables before routing variables are added. Two obstacles apply. Annealing hardware with enough qubits exists, but its connectivity is sparse. Mapping a densely coupled problem onto that sparse graph, a step called minor-embedding, spends several physical qubits per logical variable, and that cost grows quadratically in the logical problem size. The usable logical size is therefore far below the nominal qubit count. Gate-based devices have passed a thousand qubits, so raw count is no longer the binding limit there either; coherence time and two-qubit gate error are, and they cap the circuit depth that QAOA at this problem size would require. We state these as the structural obstacles rather than quoting a device specification, because specifications change and the obstacles have not.

We also note that a careful benchmarking study of quantum annealing on randomly generated instances found no evidence of speedup [17]. That study concerns one device and one instance class, and it explicitly leaves open the possibility of speedup on structured instances, which is the only possibility the next section entertains.

7.2 Why degeneracy is the thing to look for

The motivation must come from somewhere the paper has actually established, so we are explicit that it cannot come from the fractional model. Theorem 2 proves h is concave on the stable branch, strictly so for κ > 0, with no convex segment anywhere, and stiffness separates optima better, not worse, since a small change in Q produces a large change in R. Nothing about the fractional objective suggests a rugged landscape.

The conjunctive objective of Section 5.6 is different. On its convex segment the response is nearly flat in readiness terms, and many distinct schedules reach similar covered counts. A large number of configurations therefore sit inside a narrow band of objective value, separated only by the block structure Section 6 describes. Degeneracy of that kind, where near-optimal configurations are numerous and single-element moves do not distinguish them, is the structural feature that motivates interest in quantum heuristics.

Hypothesis 1. For the conjunctive objective R_m in the parameter regime identified by Proposition 2, the classical time-to-target for the inner assignment problem grows faster with instance size than it does outside that regime, and a quantum heuristic exhibits a smaller growth exponent.

7.3 The test that would refute it

Sweep instances across the Proposition 2 threshold, holding everything else fixed, so the only varying quantity is whether the convex segment exists. For each instance measure classical time-to-target, the wall-clock time to first reach a fixed target objective value, with at least two solvers of different type, for example a constraint-programming solver such as CP-SAT and a tuned simulated-annealing baseline, and record the scaling exponent as a function of instance size. Then run the same instances on available quantum hardware and on a classical simulator of the same algorithm, comparing exponents rather than wall-clock times, following the methodology in [17].

The hypothesis is refuted if the classical exponent does not increase across the threshold, which would mean the conjectured hard regime is not hard. It is also refuted if the exponent increases but the quantum exponent increases at least as fast. We consider the second outcome more likely than a positive result, and the first outcome the more interesting one, because it would simplify the algorithmic picture of Section 6. Reporting either negative outcome is the point of specifying the test.

8. The learned layer

Sections 3 through 7 treat W, p, and (β₀, κ) as given. They are not, and the estimation problem does not sit beside the theory. It is inside it. Figure 6 shows where each learned component sits relative to the solver.

8.1 Language models build the graph

Most of what you need to populate W is written in prose, not recorded in telemetry, and the reason is specific: narratives carry coupling and sensors do not. A sensor channel reports that a temperature rose on one aircraft. A maintenance note reports that the same bracket cracks on every aircraft that operated from one location. Work orders, discrepancy reports (squawks), supply requisitions and technician free-text notes record what failed, what was done, and often what the technician believed caused it, at a specificity structured fields never reach.

The defensible use of a language model here is extraction, not decision. It parses narratives into typed tuples (component, failure mode, suspected cause, part lot, corrective action), resolves entities against the maintenance catalogue, and emits candidate edges for W. Every edge keeps the source span that produced it.

This matters for a specific reason. W appears in no equation in this paper: the analysis runs on the protection sets σ_a, the failure probabilities p, and the feedback parameters (β₀, κ). W is the record from which those are estimated, and it reaches the result only through them. That makes the extraction step the first place an error can enter, and also the only place an error can be audited, because an extracted edge can be checked against the span that produced it. A wrong edge is then a reviewable claim, not an unexplained number. Two requirements follow and should be treated as hard: every extracted edge carries a citation to its source span, and extraction confidence is retained rather than thresholded away, for the reason given in 8.4.

8.2 Graph neural networks estimate degradation

Given the heterogeneous graph of assets, components, part lots and depots, remaining useful life (RUL) estimation is node-level regression over a temporal graph. The motivation is direct: components sharing a lot or an environment have correlated degradation, which is what a graph model represents and a per-asset model cannot.

The benchmark starting point is the C-MAPSS turbofan data [10], whose generation methodology is documented separately [11].

Those last two rows are why C-MAPSS is not enough. C-MAPSS can validate the per-unit prediction component and nothing more, because units that never interact cannot exhibit the coupling this paper is about. We state that rather than let a reader infer a stronger claim from a familiar benchmark.

8.3 Policy confounding

Maintenance records are not an observational sample from the degradation process. They are filtered by the policy in force. Assets that were inducted did not fail, so the records systematically lack the counterfactual, and a model trained naively learns the policy as much as the physics. Its errors are then correlated with the decisions the optimizer is about to make. The record of which assets were inducted is a treatment assignment, and a model that consumes it as a feature has already gone wrong.

8.4 Calibration is a structural requirement

Here the learned layer rejoins the theory. The quantity of interest is how much an error in κ moves predicted readiness. Differentiating (2) implicitly with respect to κ at fixed π:

dx*/dκ = β₀ (x*)² / sqrt( Δ )

and since Δ = 4 β₀ κ (π_max - π), the sensitivity |dR/dκ| = β₀ (x*)² / sqrt(Δ) grows as (π_max - π)^−1/2.

Observation 1. The sensitivity of predicted readiness to error in the feedback parameters (β₀, κ) grows without bound as the margin to the bifurcation closes, with the same (π_max - π)^−1/2 exponent that governs the response slope. At any fixed operating point short of the fold the sensitivity is finite and computable; the statement is about the rate at which it grows as the margin shrinks.

A second and sharper failure mode deserves separate mention. π_max itself depends on κ, so an error in κ̂ does not merely scale the predicted readiness: it can place the true operating point beyond the fold, where the healthy equilibrium does not exist at all. Near collapse, a bad estimate does not give you a wrong answer. It gives you no answer. Figure 7 plots this sensitivity on a logarithmic scale, including the loss-of-solution regime past the fold.

This is where the corrected picture from Section 5 does its work. Theorem 2 removes optimization quality as the binding constraint in the fractional case. What remains is estimation quality, and Observation 1 says it degrades in the least convenient way: an error that is harmless for a healthy fleet is severe for a stressed one. Nothing in a point estimate tells you which fleet you have, because the amplification is a property of the equations and the data cannot show it to you.

Two consequences for practice. The margin to π_max is itself the quantity most worth estimating accurately, more than any individual asset's remaining life, and standard prognostics evaluation does not measure it. And the learned layer should emit calibrated intervals, not point predictions, so that a robust formulation can select against the worst case inside the interval. Conformal prediction supplies distribution-free coverage under exchangeability [12], [13]. Exchangeability fails under the confounding of 8.3, so the coverage guarantee weakens there, and that weakening should be stated and not assumed away.

8.5 Agents orchestrate; they do not optimize

The appropriate role for an agentic system here is narrow, and worth stating because the tempting role is wrong.

Appropriate:

• Monitor the estimated margin to π_max, and raise an alert when it narrows.
• Assemble the evidence behind a proposed plan, including the source spans that justify the coupling edges it relies on.
• Call the solver and present the tradeoffs between candidate schedules.
• Identify which assumption a recommendation is most sensitive to.
• Route the decision to a human with the authority to make it.

Not appropriate: producing the schedule. A language model asked to generate a maintenance plan will produce a fluent and plausible one. It will not respect depot capacity, it will not respect routing feasibility, and it has no access to the equilibrium of (1). The output will be well formed and wrong, which in a safety-relevant setting is worse than no output because it is harder to reject.

The boundary is that the agent owns evidence and orchestration and the solver owns the schedule. It should be enforced in the system design, not left to prompting.

9. Proposed experimental protocol

This protocol has not been executed. It is specified so that it can be.

Phase 1: response curve recovery (simulation). Build a discrete-event sustainment simulator implementing Section 3.4 with explicit inventory and cannibalization. Sweep κ within the physical range of 5.4 and measure the empirical response and the location of π_max. Success criterion: the measured dx*/dπ exhibits the (π_max - π)^−1/2 divergence of 5.4(b). A different exponent would indicate the bifurcation is not of saddle-node type and that Section 5.4 needs revision.

Phase 2: guarantee behavior (simulation). Compute the empirical submodularity ratio by sampling the defining pairs, and compare greedy against exact optima on instances small enough to solve exactly. Success criterion: under fractional readiness, greedy stays within the constant appropriate to the binding constraint at every κ, confirming that stiffness does not manifest as an optimality gap. Under R_m, the measured γ falls below one exactly when Proposition 2's threshold is crossed. Theorem 2 is a proved statement about the model, so a contrary simulation result would indicate that the simulator does not implement the model of Section 3.4, or a coding error, rather than falsifying the theorem.

Phase 3: sensitivity (simulation). Perturb κ by a fixed relative amount and measure the change in the chosen schedule's value as a function of margin. Success criterion: the (π_max - π)^−1/2 growth of Observation 1, and the appearance of the loss-of-solution regime. This phase tests the paper's main practical claim and should run before any learning work.

Phase 4: per-unit RUL (real data). Train and evaluate graph and non-graph RUL models on C-MAPSS [10], [11] with the standard split. This phase validates only the per-unit prediction component, for the reason given in 8.2.

Phase 5: coupling extraction (requires data we do not have). Validating W requires maintenance narratives with known shared-lot structure. This is the binding constraint on the program. Public corpora of this kind are scarce; the realistic paths are a partnership with an operator under a data agreement, or a synthetic narrative corpus with known ground-truth coupling, which tests the extraction pipeline but not its behavior on real prose.

Phase 6: the quantum sweep. As specified in 7.3, across the Proposition 2 threshold.

Phase 5 is stated as the limiting step deliberately. A reader should know which part of the program is blocked and why.

10. Limitations

The feedback model is a choice. β(u) = β₀(1 + κ(1 - u)) is the simplest parameterization producing the behavior. The square-root scaling of 5.4(b) is generic to saddle-node bifurcations and robust to the form, but π_max and the constants are not.

Theorem 2 holds on a bounded window of feedback strengths. Two conditions bracket κ from opposite sides. The fold is reachable with x* ∈ [0, 1] only for κ ≥ (1 - β₀)/(2 β₀); below that the bifurcation belongs to the equations and not to any fleet. And Theorem 2 needs κ < n(1 - β₀)² / (4 β₀ Q(G)), or the empty schedule already sits past the fold. Together:

(1 - β₀) / (2 β₀)  ≤  κ  <  n (1 - β₀)² / (4 β₀ Q(G))

The window is non-empty exactly when Q(G) < n(1 - β₀)/2, that is when the average primary failure probability is below half the baseline survival margin. A fleet failing faster than that is past the fold with nothing scheduled, which is a statement about the fleet and not about the theorem.

Branching approximates a finite system. Galton-Watson assumes unbounded population and independent offspring. A fleet is finite and cannibalization targets are not independent draws. The approximation is weakest exactly at the critical point.

Proposition 2 assumes homogeneity and independence. It requires homogeneous failure probabilities so coverage reduces to a count, and conditional independence of asset capability. Coupling violates the second. We expect the S-shape to survive because it comes from the threshold and not from independence, and we have not proved it under dependence.

Theorem 1 can be arbitrarily loose. Section 5.6 exhibits an instance where ρ ≈ 4.8 × 10⁻⁵ against a true γ = 0.665. The bound is a general sufficient condition, not a useful estimate.

Lemma 1 is one-directional. Concavity is sufficient for submodularity, not necessary. We do not characterize the non-concave responses that still yield submodular objectives.

Efficient evaluation of the multilinear extension is unresolved. See Section 6.

No measured fleet results. Every number here is a model parameter or a derived quantity.

11. Open problems

1. How should a fixed budget be split between estimation and optimization? Theorem 2 says a better scheduler buys nothing in the fractional case, and Observation 1 says better coupling estimates buy more the closer the fleet is to π_max. An allocation rule as a function of margin would be directly useful and follows from neither literature alone. This question follows from the corrected result, not from the one we originally anticipated.
2. A guarantee for block-greedy on the conjunctive objective. Proposition 2 localizes the complementarity to small k. Whether a block-then-greedy method beats 1 - e^−γ there is open.
3. Proposition 2 under dependence. Extend the threshold to coupled capability, where the Poisson-binomial structure is lost.
4. Multilinear evaluation for weighted coverage. Either an efficient scheme for heterogeneous p_i or a hardness result.
5. Does the degeneracy of 7.2 appear? Answerable by simulation alone, before any quantum hardware is involved, and it should be settled first.