betaFeedback

WorksComputer Science

Counting and Sampling Manufacturable Stacking Sequences

Abstract

Designing the stacking sequence of a composite laminate is a discrete optimisation problem: each ply takes one of a few orientations, each evaluation may cost a finite-element solve, and the design must obey manufacturing rules and design guidelines, which optimisers enforce by penalty, repair or rejection. We describe the admissible set exactly. The two manufacturing rules forbid a finite set of factors, so the sequences they admit form a regular language, recognised by an automaton that tracks the last orientation and the length of its run; balance and the ten per cent rule constrain the Parikh vector and are carried by a dynamic program over automaton state and counters. One table, polynomial in N, counts the admissible sequences without producing them, draws them uniformly, and tells whether a partial sequence can still be completed. We give pseudocode, exact counts for three orientation sets, closed-form ceilings on the composition, and four of the five single-rule entries a published table left uncomputed. At 48 plies, 99.8% of the nodes of a layer-wise search tree checking the rules locally have no admissible completion on eight orientations; the completion test removes them. A one-point crossover that cuts two admissible parents only where they share an automaton state and their child closes the counters returns admissible children by construction.

Introduction

A composite laminate is a stack of NN plies, each a sheet of parallel fibres laid at one of a finite set of orientations, and its stacking sequence lists those orientations from one surface to the other. We borrow the vocabulary of formal languages: the allowed orientations form an alphabet Σ\Sigma, a stacking sequence is a word over it, one letter per ply, and a set of stacking sequences is a language. The orientations determine the in-plane and bending stiffness of the laminate, hence its buckling load, natural frequencies and deflection under load, and the design problem is to maximise one of these responses, or to minimise NN subject to targets on them. It is a discrete optimisation problem over ΣN\Sigma^N, and each evaluation of the objective may cost a finite-element solve. It has been searched with genetic algorithms since the early 1990s [10, 39], with permutation encodings [40, 30], particle swarms [13], scatter search [49] and ant colonies [6], and with branch and bound: layer by layer from the outer surface inwards [34], in a modified form that starts from “ideal” layers and keeps one branch per level [12 Sec. 2], or in the space of lamination parameters, where the admissible laminates form a fractal set [56], non-symmetric laminates included [42]. It has been extended to blending across panels [52, 60], to lamination parameters as a continuous relaxation [41, 4], to variable-stiffness laminates [1, 50], to strength as well as buckling [6, 5], to multiple objectives [2], and to structures other than flat panels: cylindrical panels [2], laminated grid plates [20], a wind-turbine blade [3] and an aero-engine fan-blade-like structure [11].

Not every word is a laminate that can be built or certified. Two manufacturing rules are local: consecutive plies must not differ by more than 45∘45^\circ of orientation, and no more than three consecutive plies may share one. Designers add guidelines that are not local, namely mirror symmetry, balance between +θ+\theta and −θ-\theta, and a minimum share of ten per cent for each principal direction; symmetry and balance are dropped where a directional stiffness or a coupling is wanted, as in aeroelastic tailoring [51]. Each of these methods spends part of its effort on candidates outside the set these rules define: a genetic algorithm penalises the rules it does not build into its encoding [39] or repairs them [55], a sampler builds candidates and rejects the non-compliant, a branch and bound checks each partial sequence against the rules and learns only at the leaves that a branch had no admissible completion. The rules enter as a filter: as design rules to respect [27, 33] or to relax [57], as constraints on the fibre paths of tow-steered plies [9 Sec. 5], or as a coupled ply-order and ply-drop problem [3]. We describe the admissible set exactly and derive from the description algorithms that produce admissible sequences, and only those.

The set treated here is that of a single panel: blending between adjacent panels, ply drops [27] and damage tolerance are not part of it (§ 7).

Throughout the paper the reference size is N=48N = 48 plies. It is the ply count of the classical benchmark of Le Riche and Haftka [39], and it lies far beyond the ply counts at which we enumerate exhaustively (§ 3.6). Nothing in the construction depends on it: the counts are given from 24 to 54 plies, and every other quantity at 48.

Zein et al. [61], whose constraint-programming method searches a backtracking enumeration tree pruned as soon as a prefix breaks a rule, with rules of the same kind (no 90∘90^\circ jump, at most four identical consecutive plies, prescribed ply counts per orientation), write of it that “it does not give compute the number of admissible stacking sequences” [sic] [61 p. 57], and frame the cost in terms of enumerating 4164^{16} or 4324^{32} candidates [61 Sec. 4.2]. Irsarri [28] tabulates the number of realisable stacking sequences rule by rule at four, eight and sixteen plies, and leaves several cells marked as not computed. Fedon et al. [21] note that the number of admissible laminates grows exponentially with the ply count, which makes complete enumeration impossible; that is true of enumeration and does not follow for counting. A granted family assigned to Boeing builds a library of admissible sublaminates by growing an integer tree and pruning the branches that violate the rules [54], the rules being stated there as ranges of ply counts per orientation, a cap on consecutive plies of one orientation, and a list of sequences that are disallowed, a finite antidisctionary in all but the name; a companion patent bounds the ply counts of a laminate per orientation to decide feasibility before any optimisation is run [53]. That tree is the unfolding of the automaton used here, and it is stored: one node for every admissible prefix. Its specification puts the size of the unconstrained space at 4104^{10} sequences for a ten-layer sublaminate over four orientations and does not report how many of them survive the rules. Recent work maps the same design space onto a quantum state, or onto a tensor network, and carries the manufacturing rules as penalty terms in an objective [59].

Our results

We show that the two manufacturing rules forbid a finite set of factors, so that the sequences they admit form a regular language, recognised by an automaton whose state is the last orientation together with the length of the run it terminates (§ 2), while balance and the 10% rule constrain the Parikh vector and are carried exactly by a dynamic program over automaton state and counters. Symmetry reduces a laminate to its half-stack, and the mirror leaves only a condition on the last run. The construction therefore covers symmetric and non-symmetric, balanced and unbalanced laminates, over any finite set of orientations. We treat sets of four, eight and twelve orientations.

Algorithms. One dynamic program, built once per alphabet and ply count, supports three operations (§ 3, Algorithms 1–3): it returns the number of admissible sequences without producing any; it draws an admissible sequence uniformly at random in O(N)O(N), with no rejection; and it decides whether a partial sequence can still be completed, by a lookup after a walk of its length. A fourth operation, recombination of two admissible parents, returns an admissible child on every call, a fresh exact draw when no admissible cut exists (Algorithm 4).

Counts. We give exact counts for the three alphabets, for symmetric laminates at ply counts from 24 to 54, and for non-symmetric ones, balanced and unbalanced, verified against exhaustive enumeration (§ 3.6). Under the rules of [28] our methods reproduce five of the six rule columns of its table at four and eight plies, and fill four of the five single-rule entries it leaves uncomputed at sixteen (§ 3.7). At 48 plies the guidelines divide the symmetric language by 13 and by 832 on the four- and eight-orientation sets, so the size advantage of the larger set falls from 51 794 to 801 (Figure 1). We also give closed-form ceilings on the composition.

Image not extracted

Figure 1. The admissible set inside all stacking sequences, at N=48N = 48. Each bar counts the half-stacks of 24 plies that survive one restriction more than the bar above it. In the righthand column, the extended set is larger by a factor of 51 794 on the manufacturing language and of 801 once the guidelines are imposed. Exact counts, as in Table 1.

Tree search. At 48 plies, 90.8% of the nodes of a branch and bound that assigns plies from the surface inwards and checks the rules at each node have, on four orientations, no admissible completion, 99.8% on eight and more than 99.99% on twelve (§ 4). The completion test of the program removes them, and since two prefixes in the same cell have the same completions, the tree of completable prefixes collapses onto the cells: 1.3×1061.3 \times10^{6} of them against 2.9×10132.9 \times10^{13} prefixes on eight orientations.

Recombination. Two identical parents are in the same automaton state at every cut, so a population that has converged recombines only into copies of its members, and the diversity of a search inside the language has to come from outside the operator (§ 6). The exact sampler cannot fail and reports an empty language as empty (§ 5).

The techniques are classical and we claim none of them. Counting the words that avoid a finite set of factors is done by a transfer matrix [22 Ex. V.11] or by string correlations [25]; the forbidden-factor description we use, and the automaton that recognises the words avoiding a finite antidictionary, are those of [14 Sec. 2]; and transfer matrices have been used to enumerate and generate constrained configurations in other fields [36]. The sampler of Section 5 belongs to the line that generates combinatorial objects uniformly by counting them first [58, 23, 26, 29, 46], to which Boltzmann samplers are the standard alternative [19], and which meets constraint programming where a sequence is constrained by an automaton [48, 16] or by a Markov model [47]; conditioning it on prescribed letter counts is classical within that method as well [18, 17], and also done by holonomic methods [7]. What is new is that this set of industrial constraints is of that kind, a regular language conditioned on thresholds and signed differences of its letter counts rather than on a prescribed composition, together with a table that carries only what those conditions need.

The paper is organised as follows. In § 2 we define the language and the two kinds of constraint, and in § 3 we give the algorithms, the counts and the bounds, and verify the counts. In § 4 we compare the construction with branch and bound, in § 5 we sample uniformly, and in § 6 we give the recombination operator. § 7 discusses what is due to whom and the limitations, and § 8 concludes.

The language of admissible stacking sequences

Words, forbidden factors, and the manufacturing rules

A stacking sequence of NN plies is a word of length NN over a finite alphabet Σ\Sigma of ply orientations. We consider the conventional set, its extension by ±30\pm30 and ±60\pm60, and a finer one,

Σ4={0,±45,90},Σ8={0,±30,±45,±60,90},\Sigma_{4} = \{0, \pm45, 90\}, \qquad\Sigma_{8} = \{0, \pm30, \pm45, \pm60, 90\},
Σ12={0,±15,±30,±45,±60,±75,90},\Sigma_{12} = \{0, \pm15, \pm30, \pm45, \pm60, \pm75, 90\},

angles being measured in degrees; Σ8\Sigma_{8} is also called the extended alphabet.

Recall that a word uu is a factor of ww if w=xuyw = xuy for some words x,yx,y, and that a set of words A\mathcal{A} is an antidictionary for the language L(A)={w∈Σ∗:no factor of w belongs to A}\mathcal{L}(\mathcal{A}) = \{w \in\Sigma^{*} : \text{no factor of }w\text{ belongs to }\mathcal{A}\}, the words that avoid A\mathcal{A} [14 Sec. 2], [15]. When A\mathcal{A} is finite, L(A)\mathcal{L}(\mathcal{A}) is regular [14 Sec. 2].

The disorientation between two orientations is

δ(a,b)=min⁡(∣a−b∣mod⁡180,180−(∣a−b∣mod⁡180)),(1)\delta(a,b) = \min\left(\lvert a-b\rvert\mathbin{\operatorname{mod}} 180, 180 - \left(\lvert a-b\rvert\mathbin{\operatorname{mod}} 180\right)\right), \tag*{(1)}

and the two manufacturing rules read as follows (Figure 2).

Image not extracted

Figure 2. A stacking sequence and the two manufacturing rules. (a) An eight-ply symmetric laminate in exploded view, each ply carrying its fibre direction; the mid-plane is the axis of the mirror. (b) The laminate of (a) as a column of plies, admissible, and two sequences that are not, one against (M1) and one against (M2). Colour encodes ∣θ∣|\theta|; the sign is carried by the fibres and by the lean of the stroke.

(M1) Disorientation. No two consecutive plies differ by more than 45∘45^\circ, that is, δ(wi,wi+1)≤45\delta(w_i,w_{i+1}) \le45 for every ii.

(M2) Contiguity. No more than three consecutive plies share the same orientation.

Proposition 2.1. Rules (M1) and (M2) forbid exactly the finite set

A={ab:a,b∈Σ, δ(a,b)>45}∪{aaaa:a∈Σ},(2)\mathcal{A} = \{ab : a,b \in\Sigma,\ \delta(a,b) > 45\} \cup\{aaaa : a \in\Sigma\}, \tag*{(2)}

and the set of stacking sequences satisfying both rules is L(A)\mathcal{L}(\mathcal{A}). In particular ∣A∣=8\lvert\mathcal{A}\rvert= 8 for Σ4\Sigma_{4} (four forbidden pairs, namely 090090, 90090 0, 45−4545 -45 and −4545-45 45, and four forbidden quadruples), ∣A∣=36\lvert\mathcal{A}\rvert= 36 for Σ8\Sigma_{8} (twenty-eight pairs and eight quadruples) and ∣A∣=72\lvert\mathcal{A}\rvert= 72 for Σ12\Sigma_{12} (sixty pairs and twelve quadruples).

Proof. Both rules are stated on windows of fixed length, two consecutive plies for (M1) and four for (M2), so a sequence violates them if and only if it contains one of the corresponding windows as a factor. Enumerating the violating windows gives (2). The cardinalities follow by inspection of δ\delta on Σ×Σ\Sigma\times\Sigma.

Theorem 2.2. The set of stacking sequences satisfying (M1) and (M2) is a regular language, recognised by a finite automaton with 3∣Σ∣3|\Sigma| states besides the initial one, in which the state reached is a function of the prefix read.

Proof. By Proposition 2.1 it suffices to recognise L(A)\mathcal{L}(\mathcal{A}). Take

Q={(a,r):a∈Σ, 1≤r≤3},(3)Q = \{(a,r) : a \in\Sigma,\ 1 \le r \le3\}, \tag*{(3)}

where aa is the last orientation read and rr the length of the run it terminates, with transitions

δQ((a,r),b)={(a,r+1)if b=a and r<3,(b,1)if b≠a and δ(a,b)≤45,undefinedotherwise.(4)\delta_Q((a,r),b) = \begin{cases} (a,r+1) & \text{if } b=a \text{ and } r<3,\\ (b,1) & \text{if } b\ne a \text{ and } \delta(a,b)\le45,\\ \text{undefined} & \text{otherwise.} \end{cases} \tag*{(4)}

Every state is accepting, and the states reachable by a single ply are those with r=1r=1; prefixing a state q0q_0 for the empty word, with δQ(q0,a)=(a,1)\delta_Q(q_0,a)=(a,1), gives a deterministic automaton in the usual sense. A transition is undefined exactly when it would complete a factor of A\mathcal{A}, by (2): the second case of (4) rules out the forbidden pairs and the first the quadruples. Hence the automaton accepts L(A)\mathcal{L}(\mathcal{A}).

Figure 3 shows the automaton for Σ4\Sigma_4, where ∣Q∣=12|Q|=12 and there are 32 transitions; on Σ8\Sigma_8 it has 24 states and 100 transitions, on Σ12\Sigma_{12} 36 and 240. It is, up to its sink state, the automaton that [14 Sec. 2] build from a finite antidictionary, whose states are the proper prefixes of forbidden words; here those prefixes are the empty word and the runs of one, two and three identical plies. In Figure 3 the missing cross transitions are exactly the forbidden pairs, 0↔900 \leftrightarrow90 and 45↔−4545 \leftrightarrow-45, so that what remains is a cycle on the four orientations.

Image not extracted

Figure 3. The automaton of the manufacturing rules on Σ4\Sigma_4. A state θr\theta_r is the pair (last orientation, run length). Horizontal arrows repeat the last ply and advance the run, which stops at three; returning arrows change orientation and reset the run to one; the three states of an orientation are drawn as one dashed box, and each returning arrow stands for three transitions. Double circles mark the states with run one; the initial state q0q_0 is not drawn.

The design guidelines as Parikh constraints

The remaining guidelines do not forbid factors: they constrain how many plies of each orientation the laminate contains. Let c(w)c(w) denote the Parikh vector of ww, whose entry ca(w)c_a(w) counts the occurrences of aa in ww. For a laminate of NN plies they read

c+θ(w)=c−θ(w)for every θ with ±θ∈Σ,(5)c_{+\theta}(w) = c_{-\theta}(w) \qquad\text{for every } \theta\text{ with } \pm\theta\in\Sigma, \tag*{(5)}

(balance)

ca(w)≥0.1Nfor every a∈{0,45,−45,90},(6)c_a(w) \ge0.1N \qquad\text{for every } a \in\{0,45,-45,90\}, \tag*{(6)}

(10% rule)

and, where it is required, mirror symmetry about the mid-plane. The constructions below take each guideline as an option.

Proposition 2.3. The words of all lengths over Σ⊇Σ4\Sigma\supseteq\Sigma_4 that satisfy (M1), (M2) and (5) do not form a regular language, and neither do those that satisfy (6) as well.

Proof. Intersect with the regular language R=(45 90)∗(−45 0)∗R = (45\ 90)^*(-45\ 0)^*. In a word of RR consecutive plies differ by 45∘45^\circ and no orientation is repeated, so (M1) and (M2) hold, and c45=c90=nc_{45} = c_{90} = n, c−45=c0=kc_{-45} = c_0 = k for some n,k≥0n,k \ge0. Balance holds exactly when n=kn = k, and then each of the four directions is a quarter of the plies, so (6) holds too. The intersection is {(45 90)n(−45 0)n:n≥0}\{(45\ 90)^n(-45\ 0)^n : n \ge0\} in both cases, which is not regular by the pumping lemma; since regular languages are closed under intersection, neither set is regular.

Since (5) and (6) depend on ww only through c(w)c(w), they are carried exactly by a dynamic program over pairs (automaton state, partial Parikh vector), developed in § 3. The same construction accommodates any constraint that depends on the word only through its Parikh vector, given counters that carry what that constraint needs.

Symmetric and non-symmetric laminates

A symmetric laminate of N=2mN = 2m plies is written w=hhRw = h h^{R}, where hh is the half-stack of mm plies and hRh^{R} its reversal.

Lemma 2.4. Let N=2mN = 2m and w=hhRw = h h^{R}. Then ww satisfies (M1) and (M2) if and only if hh does and hh ends with a run of length one.

Proof. The factors of ww that are not factors of hh or of hRh^{R} are those straddling the mid-plane, where the last ply of hh is immediately followed by its own copy. Rule (M1) is satisfied there because δ(a,a)=0\delta(a,a) = 0. Rule (M2) is satisfied there if and only if the run ending hh, of length rr, does not become a run of length 2r>32r > 3, that is if and only if r=1r = 1. Reversal preserves both rules, since A\mathcal{A} is closed under reversal.

Remark 2.5. For odd NN the mid-plane carries a single ply that its own reflection does not duplicate, so the run condition of Lemma 2.4 is replaced by one on the run that ply terminates. The Parikh vector becomes 2c(h)+ec2c(h) + e_c, where cc is the central ply, so balance forces c∈{0,90}c \in\{0, 90\} and the thresholds depend on cc. We treat only even NN below.

Lemma 2.6. With w=hhRw = h h^{R} we have c(w)=2c(h)c(w) = 2c(h), so (5) and (6) hold for ww if and only if c+θ(h)=c−θ(h)c_{+\theta}(h) = c_{-\theta}(h) for every θ\theta and 2ca(h)≥0.1N2c_a(h) \ge0.1N for every a∈{0,45,−45,90}a \in\{0, 45, -45, 90\}.

Proof. Immediate, since hRh^{R} is a permutation of hh.

Lemma 2.4 turns symmetry into a choice of accepting states, those with run one (the double circles of Figure 3), and Lemma 2.6 halves the counters.

A non-symmetric laminate is read whole; “non-symmetric” means here that symmetry is not imposed, so the class contains the symmetric laminates, a share below 2×10−62 \times10^{-6} of it at every ply count tabulated. Rules (M1) and (M2) apply to the word of NN plies, balance and the 10% rule to its Parikh vector, and every state is accepting. We write LL for the length of the word the automaton reads, L=m=N/2L = m = N/2 for a symmetric laminate and L=NL = N otherwise, and tt for the smallest value of a counter of that word that satisfies the 10% rule, that is the least integer with 2t≥0.1N2t \ge0.1N in the symmetric case and t≥0.1Nt \ge0.1N otherwise. Everything that follows holds for both unless stated otherwise.

Definition 2.7. Fix NN and the guidelines imposed, a subset GG of symmetry, balance (5) and the 10% rule (6). A laminate is admissible if it satisfies (M1), (M2) and every guideline in GG, and compliant if it is admissible with balance and the 10% rule in GG, the setting of § 5 and § 6. A word read by the automaton, hh or ww, is admissible or compliant when its laminate is. A completion of a word uu of length j<Lj < L is a word vv of length L−jL - j such that uvuv is admissible. With GG empty the admissible words are the manufacturing language L(A)∩ΣL\mathcal{L}(\mathcal{A}) \cap\Sigma^{L}.

The statements of § 3 hold for every GG.

Counting

The transfer matrix

The term is meant in its combinatorial sense [22 Ex. V.11], unrelated to the transfer-matrix method of laminate mechanics.

Let AA be the ∣Q∣×∣Q∣|Q| \times|Q| adjacency matrix of the automaton of Theorem 2.2, Aqq′=1A_{qq'} = 1 if δQ(q,b)=q′\delta_Q(q,b) = q' for some b∈Σb \in\Sigma and 0 otherwise; since the state reached determines the ply read, walks and words correspond one to one. By Lemma 2.4 the admissible half-stacks of mm plies are the walks of length m−1m-1 that start and end in a state with run one, so their number is

∣Lm∣=uTAm−1u,uq={1if q=(a,1) for some a∈Σ,0otherwise.(7)|\mathcal{L}_m| = \mathbf{u}^{\mathsf{T}} A^{m-1}\mathbf{u}, \qquad u_q = \begin{cases} 1 & \text{if } q=(a,1)\text{ for some }a\in\Sigma,\\ 0 & \text{otherwise.} \end{cases} \tag*{(7)}

For a non-symmetric laminate the count is uTAN−11\mathbf{u}^{\mathsf{T}}A^{N-1}\mathbf{1}. (7) is an exact integer computation whose cost grows with the number of digits of the count and not with the count, and produces no sequence.

The dynamic program on the Parikh counters

We work on cells (q,κ)(q,\kappa), where qq is an automaton state and κ\kappa a vector of counters holding what the guidelines need to know of the Parikh vector read so far:

  • for each principal direction a∈{0,±45,90}∩Σa\in\{0,\pm45,90\}\cap\Sigma, the count min⁡(ca,t)\min(c_a,t), since beyond tt the 10% rule is indifferent;

  • for each pair ±θ⊆Σ\pm\theta\subseteq\Sigma with θ>0\theta>0, when balance is imposed, the difference dθ=c+θ−c−θd_\theta=c_{+\theta}-c_{-\theta}.

Reading a ply bb updates κ\kappa to a vector κ⊕b\kappa\oplus b that depends on κ\kappa and bb only. Let need⁡(κ)\operatorname{need}(\kappa) be the least number of plies that, appended to a word with counters κ\kappa, satisfy every imposed guideline, ignoring the automaton: the deficits t−min⁡(ca,t)t-\min(c_a,t) of the thresholded directions that belong to no pair, ∣dθ∣|d_\theta| for the pairs without threshold, and 2max⁡(c45,c−45,t)−c45−c−452\max(c_{45},c_{-45},t)-c_{45}-c_{-45} for ±45\pm45 when both are imposed, which the capped counts and d45d_{45} determine; a guideline that is not imposed contributes nothing, and with the 10% rule off t=0t=0. A cell is accepting when need⁡(κ)=0\operatorname{need}(\kappa)=0 and, for a symmetric laminate, qq has run one (Lemma 2.4).

Lemma 3.1. Two words of the same length that satisfy (M1) and (M2) and reach the same cell have the same completions (Definition 2.7). Moreover need⁡(κ⊕b)≥need⁡(κ)−1\operatorname{need}(\kappa\oplus b)\ge\operatorname{need}(\kappa)-1 for every bb, so a word of length jj whose cell has need⁡(κ)>L−j\operatorname{need}(\kappa)>L-j has no completion, and neither has any of its extensions.

Proof. By (4) the continuations readable after a prefix depend on it only through qq, and whether a completion satisfies the guidelines depends on the prefix only through κ\kappa, which ⊕\oplus updates without reference to anything else. A ply raises one entry of the Parikh vector by one, so it moves a single term of need, that of its direction or of its pair, and lowers it by at most one; the remaining L−jL-j plies can therefore close at most L−jL-j units of deficit. □\square

The program has two passes (Algorithm 2). The forward pass generates the reachable cells level by level, discarding by need; the backward pass assigns to each cell Fj(q,κ)F_j(q,\kappa), the number of admissible completions of any prefix of length jj that reaches it. The number of admissible words is the sum of F1F_1 over the first level. The threshold tt is computed in integer arithmetic, as the least integer with 10t≥N10t\ge N, or 20t≥N20t\ge N for a half-stack.

Theorem 3.2. Let Σ\Sigma be fixed, with pp principal directions and kk sign pairs. Algorithm 2 computes the number ∣L∣|\mathcal{L}| of admissible words of length LL exactly, in

O(∣Σ∣∣Q∣L(t+1)p(2L+1)k)O\left(|\Sigma||Q|L(t+1)^p(2L+1)^k\right)

arithmetic operations on integers of O(Llog⁡∣Σ∣)O(L\log|\Sigma|) bits, hence in time polynomial in NN. After it, Algorithm 3 draws a uniformly distributed admissible word in O(∣Σ∣L)O(|\Sigma|L) operations and decides whether a prefix of length jj is completable in O(j)O(j).

Algorithm 1 Automaton(Σ\Sigma): the manufacturing rules (M1)–(M2).

  1. Q←{(a,r):a∈Σ, 1≤r≤3}Q \leftarrow\{(a,r):a \in\Sigma,\ 1 \le r \le3\}

  2. for (a,r)∈Q(a,r) \in Q and b∈Σb \in\Sigma do

  3. &nbsp;&nbsp;if b=ab=a and r<3r<3 then

  4. &nbsp;&nbsp;&nbsp;&nbsp;δQ((a,r),b)←(a,r+1)\delta_Q((a,r),b) \leftarrow(a,r+1) ▷ extend the run

  5. &nbsp;&nbsp;else if b≠ab \ne a and δ(a,b)≤45\delta(a,b) \le45 then

  6. &nbsp;&nbsp;&nbsp;&nbsp;δQ((a,r),b)←(b,1)\delta_Q((a,r),b) \leftarrow(b,1) ▷ open a new run &nbsp;&nbsp;&nbsp;&nbsp;▷ otherwise undefined: bb completes a factor of A\mathcal{A}

  7. return (Q,δQ)(Q,\delta_Q)

Algorithm 2 Table(Σ,N,options\Sigma,N,\mathit{options}): completion counts on the cells.

Require: options: symmetric or not, balance on or off, 10% rule on or off

  1. (Q,δQ)←Automaton⁡(Σ)(Q,\delta_Q) \leftarrow\operatorname{Automaton}(\Sigma); L←N/2L \leftarrow N/2 if symmetric, else NN

  2. C1←{((a,1),0⊕a):a∈Σ, need⁡(0⊕a)≤L−1}C_1 \leftarrow\{((a,1),0 \mathbin{\oplus} a):a \in\Sigma,\ \operatorname{need}(0 \mathbin{\oplus} a) \le L-1\}

  3. for j=1,…,L−1j=1,\ldots,L-1 do ▷ forward: reachable cells

  4. &nbsp;&nbsp;for (q,κ)∈Cj(q,\kappa) \in C_j and bb with δQ(q,b)\delta_Q(q,b) defined do

  5. &nbsp;&nbsp;&nbsp;&nbsp;if need⁡(κ⊕b)≤L−j−1\operatorname{need}(\kappa\mathbin{\oplus} b) \le L-j-1 then

  6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;add (δQ(q,b),κ⊕b)(\delta_Q(q,b),\kappa\mathbin{\oplus} b) to Cj+1C_{j+1}

  7. for (q,κ)∈CL(q,\kappa) \in C_L do

  8. &nbsp;&nbsp;FL(q,κ)←1F_L(q,\kappa) \leftarrow1 if need⁡(κ)=0\operatorname{need}(\kappa)=0 and (q(q has run one or not symmetric)), else 00

  9. for j=L−1,…,1j=L-1,\ldots,1 do ▷ backward: completions

  10. &nbsp;&nbsp;for (q,κ)∈Cj(q,\kappa) \in C_j do

  11. &nbsp;&nbsp;&nbsp;&nbsp;Fj(q,κ)←∑bFj+1(δQ(q,b),κ⊕b)F_j(q,\kappa) \leftarrow\sum_b F_{j+1}(\delta_Q(q,b),\kappa\mathbin{\oplus} b) ▷ over defined δQ\delta_Q; absent cells count 0

  12. return FF, and ∣L∣=∑c∈C1F1(c)|\mathcal{L}|=\sum_{c\in C_1}F_1(c)

Algorithm 3 Sample(FF) and Completable(F,pF,p).

  1. if ∣L∣=0|\mathcal{L}|=0 then

  2. &nbsp;&nbsp;return none ▷ the empty set, certified

  3. draw c∈C1c \in C_1 with probability F1(c)/∣L∣F_1(c)/|\mathcal{L}|; w←w \leftarrow the ply of cc

  4. for j=1,…,L−1j=1,\ldots,L-1 do

  5. &nbsp;&nbsp;draw bb with probability Fj+1(δQ(q,b),κ⊕b)/Fj(q,κ)F_{j+1}(\delta_Q(q,b),\kappa\mathbin{\oplus} b)/F_j(q,\kappa), where c=(q,κ)c=(q,\kappa)

  6. &nbsp;&nbsp;c←(δQ(q,b),κ⊕b)c \leftarrow(\delta_Q(q,b),\kappa\mathbin{\oplus} b); append bb to ww

  7. return ww ▷ uniform on L\mathcal{L}; mirror it if symmetric

  8. function Completable(F,pF,p) ▷ pp a prefix of length jj

  9. &nbsp;&nbsp;if j=0j=0 then return ∣L∣>0|\mathcal{L}|>0

  10. &nbsp;&nbsp;walk pp through δQ\delta_Q from q0q_0 and ⊕\oplus from 00 (Theorem 2.2); return false if a transition is undefined

  11. &nbsp;&nbsp;return Fj(q,κ)>0F_j(q,\kappa)>0 for the cell (q,κ)(q,\kappa) reached

Proof. Correctness: by Lemma 3.1 the prefixes that reach a cell share their completions, so FjF_j is well defined, the recursion of the backward pass counts each admissible completion exactly once by its next ply, and the discarded cells contribute nothing. Each level holds at most ∣Q∣|Q| states times (t+1)p(t+1)^p capped counts times (2L+1)k(2L+1)^k differences, and each cell has at most ∣Σ∣|\Sigma| successors. A count never exceeds ∣Σ∣L|\Sigma|^L. The walk of Algorithm 3 chooses each ply with probability equal to the share of completions it keeps, so the product telescopes to 1/∣L∣1/|\mathcal{L}| for every admissible word.

The operations counted are additions and comparisons of integers of that size; a draw takes a uniform integer below FjF_j, and the cells are kept in hash tables with constant expected access.

With the discarding by need, the largest level at N=48N=48 on Σ8\Sigma_8 holds 213 202 cells. When the distribution over compositions is wanted, as below, the counters are carried uncapped, at a cost in cells.

Cost of the design guidelines

At N=48N=48 the guidelines divide the language by 13 on Σ4\Sigma_4 and by 832 on Σ8\Sigma_8 (Table 1). On Σ8\Sigma_8 balance acts on three pairs instead of one, and the 10% rule demands that 0, ±45\pm45 and 90 all be present in a laminate whose plies may also be spent on ±30\pm30 and ±60\pm60, which do not help to satisfy it.

NNΣ4\Sigma_4Σ8\Sigma_8Σ12\Sigma_{12}
24376 704102 102 3681.99×10101.99 \times10^{10}
401 988 997 12017 885 340 482 8001.13×10171.13 \times10^{17}
4416 954 798 592365 900 128 074 1965.49×10185.49 \times10^{18}
48144 527 708 1607 485 622 309 145 5522.68×10202.68 \times10^{20}
543 596 986 742 784692 669 292 246 653 8489.11×10229.11 \times10^{22}
NNΣ4\Sigma_4Σ8\Sigma_8Σ12\Sigma_{12}Σ8/Σ4\Sigma_8/\Sigma_4Σ12/Σ8\Sigma_{12}/\Sigma_8
2429 560182 020782 3486.2×6.2\times4.3×4.3\times
40175 964 26839 709 914 0886.32×10126.32 \times10^{12}226×226\times159×159\times
441 302 502 076398 548 747 3723.46×10133.46 \times10^{13}306×306\times87×87\times
4811 236 189 6448 999 374 621 9602.18×10152.18 \times10^{15}801×801\times243×243\times
54277 909 460 780881 013 334 451 0808.49×10178.49 \times10^{17}3 170×3\,170\times964×964\times

Table 1. Exact number of admissible symmetric half-stacks of N/2N/2 plies on the three alphabets: (a) under the manufacturing rules alone, (b) under the rules together with the design guidelines, with the ratios between alphabets. In the Σ12\Sigma_{12} columns values of 10710^7 and above are rounded to three significant figures; the deposited code returns the integers.

Hence the size advantage of the extended alphabet falls from 51 794×51\,794\times on the manufacturing language to 801×801\times under the guidelines. On Σ12\Sigma_{12} the guidelines divide the language by 1.2×1051.2\times10^5, and its advantage over Σ8\Sigma_8 falls from 35 700×35\,700\times to 243×243\times.

Non-symmetric and unbalanced laminates

An unbalanced laminate couples extension with shear and strengthens the coupling of bending with twisting, a non-symmetric one couples extension with bending [51]. Algorithm 2 counts every class with the corresponding options (§ 2.3); for the non-symmetric balanced class, which carries a difference for every sign pair over the whole length, we count by meeting in the middle.

Proposition 3.3. Let NN be even and let G(q,κ)G(q,\kappa) be the number of words of N/2N/2 plies satisfying (M1)–(M2) that reach the cell (q,κ)(q,\kappa), obtained by carrying these counts through the forward pass of Algorithm 2 for non-symmetric words of length NN. Then the number of admissible non-symmetric laminates of NN plies is

∑G(q,κ)G(q′,κ′),\sum G(q,\kappa)G(q',\kappa'),

over the pairs of cells such that the junction is admissible (if q=(a,r)q=(a,r) and q′=(b,r′)q'=(b,r'), then r+r′≤3r+r' \le3 when a=ba=b and δ(a,b)≤45\delta(a,b)\le45 otherwise), every sign-pair difference of κ′\kappa' is the opposite of that of κ\kappa, and min⁡(ca,t)+min⁡(ca′,t)≥t\min(c_a,t)+\min(c'_a,t)\ge t for every principal direction aa.

Proof. Write the laminate as uvuv with ∣u∣=∣v∣=N/2|u|=|v|=N/2. The antidictionary (2) is closed under reversal, and the Parikh constraints do not depend on the order, so vv is admissible exactly when its reversal vRv^{R} is an admissible prefix of the same length; the state reached by vRv^{R} is the pair (first ply of vv, length of its first run). The factors of uvuv that are factors of neither uu nor vv straddle the junction; they break (M1) exactly when δ(a,b)>45\delta(a,b)>45, and (M2) exactly when a=ba=b and the two runs together exceed three. The Parikh vector of uvuv is the sum of those of uu and vv, so balance holds iff the differences are opposite, and a threshold holds iff the sum of the counts reaches tt, which the capped counts decide. The pruning of the forward pass removes only prefixes that no completion of length NN can save (Lemma 3.1), hence none that the sum needs.

Proposition 3.3 needs only the middle level, one table serving both halves. With the counts of each half exact and the sum taken modulo four primes of 61 bits and rebuilt by the Chinese remainder theorem, it reproduces all 56 non-symmetric counts obtained with Algorithm 2, and reaches N=54N=54 on Σ12\Sigma_{12} with 1.1×1091.1 \times10^{9} cells at the middle level (Table 2).

Table 2: Exact number of admissible laminates of NN plies under the manufacturing rules and the 10% rule, for the three classes other than symmetric and balanced (Table 1): symmetric unbalanced, non-symmetric balanced, non-symmetric unbalanced. Values of 10710^7 and above are rounded to three significant figures; the deposited code returns the integers.

NNsymmetric unbalancednon-symmetric balancednon-symmetric unbalanced
Σ4\Sigma_424147 1121.62×10101.62 \times10^{10}1.63×10111.63 \times10^{11}
401.69×1091.69 \times10^93.91×10173.91 \times10^{17}5.64×10185.64 \times10^{18}
441.18×10101.18 \times10^{10}2.69×10192.69 \times10^{19}4.02×10204.02 \times10^{20}
481.13×10111.13 \times10^{11}1.90×10211.90 \times10^{21}3.01×10223.01 \times10^{22}
543.12×10123.12 \times10^{12}1.11×10241.11 \times10^{24}1.87×10251.87 \times10^{25}
Σ8\Sigma_8244 128 9681.11×10131.11 \times10^{13}1.64×10151.64 \times10^{15}
406.05×10126.05 \times10^{12}2.51×10232.51 \times10^{23}1.32×10261.32 \times10^{26}
444.15×10134.15 \times10^{13}7.75×10257.75 \times10^{25}3.98×10283.98 \times10^{28}
481.32×10151.32 \times10^{15}3.32×10283.32 \times10^{28}2.30×10312.30 \times10^{31}
541.98×10171.98 \times10^{17}2.23×10322.23 \times10^{32}1.72×10351.72 \times10^{35}
Σ12\Sigma_{12}243.33×1073.33 \times10^72.49×10152.49 \times10^{15}1.57×10181.57 \times10^{18}
404.27×10154.27 \times10^{15}4.80×10284.80 \times10^{28}1.91×10321.91 \times10^{32}
441.31×10161.31 \times10^{16}2.67×10312.67 \times10^{31}9.63×10349.63 \times10^{34}
481.35×10181.35 \times10^{18}1.01×10351.01 \times10^{35}5.68×10385.68 \times10^{38}
541.14×10211.14 \times10^{21}3.69×10393.69 \times10^{39}2.32×10432.32 \times10^{43}

Table 2.

At N=48N=48 the balanced non-symmetric laminates outnumber the symmetric ones by 1.7×10111.7 \times10^{11} on Σ4\Sigma_4, 3.7×10153.7 \times10^{15} on Σ8\Sigma_8 and 4.6×10194.6 \times10^{19} on Σ12\Sigma_{12}. Dropping balance multiplies the non-symmetric set by 16, 691 and 5 648. The symmetric unbalanced class is 10.0, 147 and 619 times the symmetric balanced one. Every algorithm of this paper applies to these sets wherever their full table fits in memory: sampling and the completion test use it as it is, and the crossover of Section 6 is used without the run-one condition that a symmetric laminate imposes at its mid-plane (Lemma 2.4). The balanced non-symmetric class on Σ12\Sigma_{12} is counted beyond that point, from N=40N=40, by Proposition 3.3 alone, and is not sampled here.

Ceilings on the composition

Proposition 3.4. Let tt be the smallest half-stack counter satisfying the 10% rule, and let hh be a compliant half-stack of mm plies. Then

ca(h)≤{m−3t,a∈{0,90},⌊(m−2t)/2⌋,a∈{45,−45},⌊(m−4t)/2⌋,a in a sign pair without threshold.(8)c_a(h) \le \begin{cases} m-3t, & a \in\{0,90\},\\ \lfloor(m-2t)/2\rfloor, & a \in\{45,-45\},\\ \lfloor(m-4t)/2\rfloor, & a \text{ in a sign pair without threshold.} \end{cases} \tag*{(8)}

Proof. By Lemma 2.6 the 10% rule reads cb(h)≥tc_b(h) \ge t for each of the four directions b∈{0,45,−45,90}b \in\{0, 45, -45, 90\}, and balance reads c+θ(h)=c−θ(h)c_{+\theta}(h) = c_{-\theta}(h). Fix aa and bound the plies that cannot be spent on it. If a∈{0,90}a \in\{0, 90\}, which have no distinct partner, the other three thresholded directions consume at least 3t3t, whence ca≤m−3tc_a \le m - 3t. If a∈{45,−45}a \in\{45, -45\}, balance forces c−a=cac_{-a} = c_a, so the pair consumes 2ca2c_a, while 0 and 90 consume at least 2t2t; hence 2ca≤m−2t2c_a \le m - 2t. If aa belongs to a sign pair that carries no threshold (±30\pm30 and ±60\pm60, and on Σ12\Sigma_{12} also ±15\pm15 and ±75\pm75), the pair again consumes 2ca2c_a while all four thresholded directions consume at least 4t4t, hence 2ca≤m−4t2c_a \le m - 4t.

At N=48N = 48, where m=24m = 24 and t=3t = 3, (8) gives c0≤15c_0 \le15. That bound is attained: the dynamic program finds 840 compliant half-stacks with exactly 15, on Σ4\Sigma_4 and on Σ8\Sigma_8.

It is not tight in general. At N=20N = 20 on Σ4\Sigma_4 the bound gives c0≤7c_0 \le7, while exhaustive enumeration shows the true maximum is 5. The bound ignores adjacency: a half-stack rich in 0° must break its runs every three plies, the only orientations adjacent to 0° are ±45\pm45, and the 90° ply that the 10% rule demands cannot sit next to a 0° one. The exact maximum needs the joint state of automaton and counters, which the dynamic program carries.

Against exhaustive enumeration for every orientation at N=12,16,20N = 12, 16, 20 on Σ4\Sigma_4 and N=12,14N = 12, 14 on Σ8\Sigma_8, (8) is attained everywhere except at N=20N = 20 on Σ4\Sigma_4, where the maxima fall short of it also for 90 (5 against 7) and for ±45\pm45 (3 against 4).

On Σ8\Sigma_8 at N=48N = 48 the compliant language has mode c0=3c_0 = 3 and mean 4.42, and 0.00058% of it lies at c0≥12c_0 \ge12, half the half-stack.

Verification of the counts

Internally, we compared the counts with exhaustive enumeration filtered by rule checkers written separately from the dynamic program, on totals and on the whole distribution by Table 3: Table II-1 of [28] completed. The columns at four and eight plies are the published values, which our methods reproduce exactly except in the 10% row; at sixteen plies the symmetry row is published and the other entries are the cells the table leaves uncomputed.

rule4 plies8 plies16 pliesclosed form
Sym.1625665 5364n/24^{n/2}, nn even
Eq.7012 870601 080 390(2nn)\binom{2n}{n}
Group.22847 0882 010 036 708an=3(an−1+an−2)a_n = 3(a_{n-1} + a_{n-2})
Des.1088 74857 395 6284⋅3n−14 \cdot3^{n-1}
TolDom.14436 8642 415 919 1049⋅4n−29 \cdot4^{n-2}, n≥2n \ge2
10%19262 720not reproducible: see text

Table 3. Table II-1 of [28] completed.

composition. The nine cases are N=8,12,…,24N = 8, 12, \ldots, 24 on Σ4\Sigma_4 and N=8,10,…,14N = 8, 10, \ldots, 14 on Σ8\Sigma_8, and all coincide. The ten manufacturing counts of Table 1(a) on Σ4\Sigma_4 and Σ8\Sigma_8 agree with the matrix powers of (7), computed in exact integer arithmetic. We checked the general program of Algorithm 2, with capped counters, separately: against exhaustive enumeration on 80 cases that cover the three alphabets, symmetric and non-symmetric words, balance on and off and the 10% rule on and off; against every Σ4\Sigma_4 and Σ8\Sigma_8 entry of Table 1; by 2000 draws of Algorithm 3 in each of three settings, all compliant; and by Completable on every one of the ∑j≤84j\sum_{j \le8}4^j prefixes at N=16N = 16 on Σ4\Sigma_4, with no disagreement.

Externally, Table II-1 of [28] tabulates the number of realisable stacking sequences on {0,±45,90}\{0, \pm45, 90\} rule by rule at 4, 8 and 16 plies. We recover five of its six rule columns at both 4 and 8 plies, and with them the definitions he used. Two differences forbid a column-by-column comparison with our own counts. His rules are symmetry (Sym.), balance of ±45\pm45 (Eq.), contiguity (Group.), disorientation (Des., our (M1)), no 0∘0^\circ ply on either outer surface (TolDom.) and a 10% rule. His contiguity rule allows two identical consecutive plies where ours allows three; and his 10% rule is not a counting rule but a membrane-stiffness criterion, chosen to remain applicable to arbitrary orientations and, as he notes, less restrictive for thin laminates.

Completion of a published table

At sixteen plies Table II-1 leaves five of its six single-rule entries uncomputed [28 p. 59]: only the symmetry entry, which it deduces from the eight-ply enumeration, is filled. Four cumulative entries are also uncomputed; each combines rules with the 10% criterion. Each of the five combinatorial rules is counted by a transfer matrix or in closed form, so we fill four of the five blank cells in the sixteen-ply column of Table 3; the fifth, the 10% row, rests on a reading of a membrane-stiffness criterion that the thesis does not spell out and we cannot reconstruct.

Every entry at sixteen plies comes from a computation that first returns the published values at four and eight plies; the four other than symmetry, which is a formula, also agree with an independent exhaustive enumeration at eight plies.

Four of the five combinatorial rows are closed forms, and the fifth, contiguity, satisfies a two-term linear recurrence,

an=3(an−1+an−2),a1=4, a2=16,(9)a_n = 3(a_{n-1} + a_{n-2}), \qquad a_1 = 4,\ a_2 = 16, \tag*{(9)}

which returns the published values at four and eight plies [45]. Balance, for its part, is the central binomial coefficient:

∑k=0⌊n/2⌋(nk)(n−kk)2n−2k=(2nn).(10)\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n}{k}\binom{n-k}{k}2^{n-2k} = \binom{2n}{n}. \tag*{(10)}

It is the coefficient identity ∑k(nk)(n−kk)2n−2k=[xn](1+2x+x2)n=[xn](1+x)2n\sum_k \binom{n}{k}\binom{n-k}{k}2^{n-2k} = [x^n](1+2x+x^2)^n = [x^n](1+x)^{2n}, and the values are those of [44].

The criterion behind that row requires the extensional stiffnesses A11A_{11}, A22A_{22} and A66A_{66} of classical lamination theory [31] to be at least those of a virtual quasi-isotropic laminate [45/0/−45/90]s[45/0/-45/90]_s of 40% the thickness. With plies of one thickness it depends on the sequence only through its counts and enters the program as three linear inequalities on uncapped counters; as stated, it gives 224 and 64 128 admissible sequences at 4 and 8 plies, against the published 192 and 62 720, for any carbon-epoxy ply.

Branch and bound

A branch and bound for the stacking sequence [34] assigns plies one at a time from the outer surface towards the mid-plane, since the outer plies weigh most in bending. Each node of its tree is a prefix, discarded when a bound on the objective over its completions cannot beat the incumbent [43]. The manufacturing rules are local, so a node that breaks one is discarded on the spot. The guidelines are not, and a prefix that obeys the rules may have no admissible completion; the tree learns it only after generating and rejecting every leaf below, unless the bound happens to discard the branch first for another reason.

The prefixes of length jj that obey the rules number Tloc(j)=u⊤Aj−11T_{\mathrm{loc}}(j) = u^{\top}A^{j-1}\mathbf{1}, by the transfer matrix of § 3. Those with at least one admissible completion number Tex(j)=∑Gj(q,κ)T_{\mathrm{ex}}(j) = \sum G_j(q,\kappa) over the cells of level jj with Fj(q,κ)>0F_j(q,\kappa) > 0, where GjG_j counts the prefixes that reach a cell and is obtained by carrying counts through the forward pass of Algorithm 2. Their difference is the part of a locally checked tree that leads nowhere. Table 4 gives it for the three alphabets; the values are exact and agree with an explicit tree at N=16N = 16 on Σ4\Sigma_4, N=12N = 12 on Σ8\Sigma_8 and on a non-symmetric case.

Table 4: A layer-wise tree over symmetric half-stacks against the cells of Algorithm 2, rules and guidelines imposed; sizes summed over the depths j=1,…,N/2j = 1, \ldots, N/2. “Local” keeps every prefix that obeys the manufacturing rules, “exact” those with an admissible completion; “dead” is the share of the first not in the second; “cells” counts the cells with Fj>0F_j > 0.

NNadmissibletree, localtree, exactdeadcellstree / cells
Σ4\Sigma_42429 560836 38885 55689.8%1 65052
481.12×10101.12 \times10^{10}3.21×10113.21 \times10^{11}2.96×10102.96 \times10^{10}90.8%21 3701.4×1061.4 \times10^{6}
Σ8\Sigma_824182 0201.66×1081.66 \times10^{8}614 12499.63%8 72670
489.00×10129.00 \times10^{12}1.22×10161.22 \times10^{16}2.90×10132.90 \times10^{13}99.76%1 257 7742.3×1072.3 \times10^{7}
Σ12\Sigma_{12}24782 3482.71×10102.71 \times10^{10}2.70×1062.70 \times10^{6}99.990%21 574125
482.18×10152.18 \times10^{15}3.63×10203.63 \times10^{20}7.30×10157.30 \times10^{15}99.998%1.40×1071.40 \times10^{7}5.2×1085.2 \times10^{8}

Table 4.

At N=48N = 48 on Σ8\Sigma_8 the dead share is zero at depth 6, 2% at depth 9, 14% at 12, 75% at 18 and 97% at 21 of 24: the dead branches sit near the mid-plane, where the tree is widest.

Three things follow.

First, counting with a tree means reaching every admissible leaf. By Lemma 3.1 a tree that never enters a dead branch is the unfolding of the cells: two prefixes in the same cell root identical subtrees, so the program keeps one copy of each. The tree grows exponentially with the depth, the cells polynomially (Theorem 3.2).

Second, a branch and bound that calls COMPLETABLE, a lookup, at each node never enters a dead branch, and its branching, its bound and its incumbent are untouched. On the eight- and twelve-orientation sets the test removes more than 99% of what a locally checked tree would visit before its bound acts.

Third, with the counters uncapped, the cells reachable from a node are the compositions its admissible completions can still attain, so a bound on a quantity that depends on the plies only through their counts, such as the membrane stiffness, can be taken over those compositions alone.

Exact uniform sampling

Algorithm 3 draws every admissible word with probability 1/∣L∣1/|L|, in L−1L-1 steps with no rejection (Theorem 3.2). The sampler never fails: it either returns a compliant laminate or reports that the language is empty, which it knows from the count.

A crossover valid by construction

Proposition 6.1 gives two conditions under which a one-point cut of two compliant half-stacks yields a compliant child. The Parikh vector of the child is a difference of prefix and suffix counters, so both conditions, equality of states and the Parikh test, are integer tests of cost O(1)O(1) per candidate cut, and a child costs O(m)O(m) once the prefix states and counters of the two parents are in hand.

Proposition 6.1. Let hAh_A and hBh_B be compliant half-stacks of mm plies and let 1≤i<m1 \le i < m. If the automaton state after hA[1..i]h_A[1..i] equals the state after hB[1..i]h_B[1..i], and if the Parikh vector of hA[1..i]hB[i+1..m]h_A[1..i]h_B[i+1..m] satisfies the conditions of Lemma 2.6, then that word is a compliant half-stack.

Proof. The state (a,r)(a,r) of Theorem 2.2 determines which continuations are admissible, since (4) depends on the prefix only through it. The prefix hA[1..i]h_A[1..i] is admissible because hAh_A is, and it leaves the automaton in the state from which hBh_B read its own suffix; that suffix is therefore readable, and the child satisfies (M1) and (M2). Its final state is the final state of hBh_B, which has run one because hBh_B is compliant, so Lemma 2.4 applies. The composition conditions hold by hypothesis. □

Algorithm 4 Cut(h_A, h_B): recombination inside the compliant language.
1: q_i^A, q_i^B ← automaton states after h_A[1..i], h_B[1..i], for 1 ≤ i < m
2: c_i^A, c_i^B ← Parikh vectors of the same prefixes
3: I ← { i : q_i^A = q_i^B and c_i^A + c(h_B) − c_i^B satisfies Lemma 2.6 }
4: if I ≠ ∅ then
5:     choose i ∈ I; return h_A[1..i] h_B[i+1..m] ▷ compliant by Prop. 6.1
6: else
7:     return Sample(F) ▷ no admissible cut: fresh exact draw

At N=48N=48 an admissible cut exists for 49.0% of 3000 independent pairs on Σ4\Sigma_4 and 18.0% on Σ8\Sigma_8. We verified compliance on the 2008 children with rule checkers written separately from the dynamic program, and the sufficiency of the condition by brute force over 3600 pairs and all their cuts, at N=16N=16 and 20 on Σ4\Sigma_4 and N=12N=12 and 14 on Σ8\Sigma_8.

Proposition 6.2. Let hh be a compliant half-stack of mm plies. Every cut of hh with itself is admissible under Proposition 6.1, and every child it produces equals hh.

Proof. Take hA=hB=hh_A=h_B=h and any 1≤i<m1 \le i < m. The automaton state after h[1..i]h[1..i] equals itself, so the state condition of Proposition 6.1 holds at every ii; and the child h[1..i]h[i+1..m]h[1..i]h[i+1..m] is hh, whose Parikh vector satisfies the conditions of Lemma 2.6 because hh is compliant. □

The fallback to the exact sampler, which is the only source of new material, fires exactly when no cut exists, and therefore never fires once the population has converged.

The proofs of Propositions 6.1 and 6.2 use only that the automaton state determines the admissible continuations and that acceptance depends on the final state and the counters; both therefore hold for any operator that joins a prefix and a suffix meeting in one state and closing the counters together. A diversity guard has to come from outside the operator.

Discussion

No result of this paper evaluates the response of a laminate: the counts, the sampler, the completion test and the recombination concern the admissible set. Closed-form responses exist for simple geometries under elementary loads, such as the buckling load and the natural frequencies of a simply supported rectangular plate of a symmetric and balanced laminate, exact when the bending-twisting terms D16D_{16} and D26D_{26} vanish. They do not exist for the geometries and load cases of an industrial component, nor, beyond a few antisymmetric lay-ups, for laminates whose couplings cannot be neglected, B ≠0\ne0 in a non-symmetric laminate and A16,A26≠0A_{16}, A_{26} \ne0 in an unbalanced one; there each evaluation is a finite-element solve, and a search that spends evaluations on designs that cannot be built pays for them in solves.

Stacking-sequence optimisation is surveyed in [24]. Four things this paper uses are not ours. Treating the manufacturing constraints exactly is [61]. Expressing the manufacturing rules as forbidden factors and pruning a prefix tree by them is recited in a granted patent [54]. An evolutionary operator that preserves a design guideline is not new either: [28] has crossover and mutation preserving symmetry and balance, and what is new is preserving the whole modelled set in a single cut, each cut decided in O(1)O(1). Nor is the sampling method ours. The backward walk proportional to the counts is the recursive method [23]; an automaton accepting under a semilinear condition on counters is a Parikh automaton [35]; and conditioning the recursive method on an exact composition is older still [18, 7], with a Boltzmann counterpart [8]. What is new is therefore narrow: exact conditioning on thresholds and signed differences of the letter counts, rather than on a prescribed composition, realised as one explicit product automaton of size polynomial in NN that serves every composition at once and decides completability.

Four limitations bound the scope. First, the guidelines modelled are symmetry, balance and the ten per cent rule: damage tolerance, ply drops and blending between adjacent panels are not represented, and blending is not a function of one laminate’s Parikh vector, so it would not fit this construction without extension. The patent family cited above handles blending by choosing each panel’s sublaminate from the pre-generated library so as to couple adjacent panels [32]. Second, the dynamic program tracks the sign pairs without a threshold, ±30\pm30 and ±60\pm60 and on Σ12\Sigma_{12} also ±15\pm15 and ±75\pm75, through their difference alone, which suffices for balance but not for constraints that weigh those orientations individually, such as the membrane-stiffness criterion of [28] on Σ8\Sigma_{8}. Third, this paper measures no search: what the operations save a heuristic in evaluations and in generation time is not quantified here. Fourth, the program is polynomial for a fixed alphabet but its degree grows with the number of sign pairs: the non-symmetric balanced count on Σ12\Sigma_{12}, which carries five differences, needs 1.1×1091.1 \times10^{9} cells at the middle level, 69 GB and an hour and a half at N=54N = 54.

Conclusions

The manufacturing rules and guidelines treated here form a regular language conditioned on thresholds and signed differences of its letter counts, so one table per ply count, polynomial in NN, counts the admissible sequences exactly, draws them uniformly and tells whether a partial sequence can still be completed. In a branch and bound it supplies the completion test without which 99.8% of a locally checked tree is dead at 48 plies on eight orientations, and in a genetic algorithm a recombination that returns admissible children by construction. Blending across panels, ply drops and damage tolerance are the constraints this construction does not yet carry.

Funding

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Data availability

The program of Algorithms 1–4 and the meet-in-the-middle counter are available on Zenodo [38]. The rule checkers of § 3.6, written separately from the dynamic program, are those of the open-source design workflow of [37], also on Zenodo. The scripts were written and run with the assistance of Claude (Anthropic), and every number reported was recomputed by a separate verification script.

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

During the preparation of this work the authors used Anthropic’s Claude, through the Claude Code interface, in order to draft and edit manuscript text, to write and run the counting, sampling and search scripts, and to check the cited sources against the statements that cite them. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the content of the published article.

References

  1. [1]Abdalla M. Abdalla, Shahriar Setoodeh, and Zafer Gürdal. Design of variable stiffness composite panels for maximum fundamental frequency using lamination parameters. Composite Structures, 81(2):283–291, 2007. doi:10.1016/j.compstruct.2006.08.018.DOI
  2. [2]M. Abouhamze and M. Shakeri. Multi-objective stacking sequence optimization of laminated cylindrical panels using a genetic algorithm and neural networks. Composite Structures, 81(2):253–263, 2007. doi:10.1016/j.compstruct.2006.08.015.
  3. [3]Alejandro Albanesi, Facundo Bre, Victor Fachinotti, and Cristian Gebhardt. Simultaneous ply-order, ply-number and ply-drop optimization of laminate wind turbine blades using the inverse finite element method. Composite Structures, 184:894–903, 2018. doi:10.1016/j.compstruct.2017.10.051.DOI
  4. [4]Mazen A. Albazzan, Ramy Harik, Brian F. Tatting, and Zafer Gürdal. Efficient design optimization of nonconventional laminated composites using lamination parameters: A state of the art. Composite Structures, 209:362–374, 2019. doi:10.1016/j.compstruct.2018.10.095.DOI
  5. [5]Haichao An, Shenyan Chen, and Hai Huang. Laminate stacking sequence optimization with strength constraints using two-level approximations and adaptive genetic algorithm. Structural and Multidisciplinary Optimization, 51(4):903–918, 2015. doi: 10.1007/s00158-014-1181-0.DOI
  6. [6]F. Aymerich and M. Serra. Optimization of laminate stacking sequence for maximum buckling load using the ant colony optimization (ACO) metaheuristic. Composites Part A: Applied Science and Manufacturing, 39(2):262–272, 2008. doi:10.1016/j.compositesa.2007.10.011.DOI
  7. [7]Alberto Bertoni, Paolo Massazza, and Roberto Radicioni. Random generation of words in regular languages with fixed occurrences of symbols. In Proceedings of WORDS’03, 4th International Conference on Combinatorics on Words, TUCS General Publication 27, pages 332–343, Turku, Finland, 2003. Turku Centre for Computer Science.
  8. [8]Olivier Bodini and Yann Ponty. Multi-dimensional Boltzmann sampling of languages. In DMTCS Proceedings, 21st International Meeting on Probabilistic, Combinatorial and Asymptotic Methods in the Analysis of Algorithms (AofA’10), 2010. Article 2793. doi: 10.46298/dmtcs.2793.DOI
  9. [9]Timothy R. Brooks and Joaquim R.R.A. Martins. On manufacturing constraints for tow-steered composite design optimization. Composite Structures, 204:548–559, 2018. doi:10.1016/j.compstruct.2018.07.100.DOI
  10. [10]Kelvin J. Callahan and George E. Weeks. Optimum design of composite laminates using genetic algorithms. Composites Engineering, 2(3):149–160, 1992. doi:10.1016/0961-9526(92)90001-M.DOI
  11. [11]Giacomo Canale, Stuart Andrews, Felice Rubino, Angelo Maligno, Roberto Citarella, and Paul M. Weaver. Realistic stacking sequence optimisation of an aero-engine fan blade-like structure subjected to frequency, deformation and manufacturing constraints. The Open Mechanical Engineering Journal, 12(1):151–163, 2018. doi:10.2174/1874155X01812010151.DOI
  12. [12]Giacomo Canale, Paul M. Weaver, Felice Rubino, Angelo Maligno, and Roberto Citarella. Lay-up optimization of laminated composites using a modified branch and bound method. The Open Mechanical Engineering Journal, 12(1):138–150, 2018. doi:10.2174/1874155X01812010138.DOI
  13. [13]Nan Chang, Wei Wang, Wei Yang, and Jian Wang. Ply stacking sequence optimization of composite laminate by permutation discrete particle swarm optimization. Structural and Multidisciplinary Optimization, 41(2):179–187, 2010. doi:10.1007/s00158-009-0417-x.DOI
  14. [14]M. Crochemore, F. Mignosi, and A. Restivo. Automata and forbidden words. Information Processing Letters, 67(3):111–117, 1998. doi:10.1016/S0020-0190(98)00104-5.
  15. [15]Maxime Crochemore, Filippo Mignosi, Antonio Restivo, and Sergio Salemi. Data compression using antidictionaries. Proceedings of the IEEE, 88(11):1756–1768, 2000. doi:10.1109/5.892711.
  16. [16]Sophie Demassey, Gilles Pesant, and Louis-Martin Rousseau. A cost-regular based hybrid column generation approach. Constraints, 11(4):315–333, 2006. doi:10.1007/s10601-006-9003-7.DOI
  17. [17]Alain Denise, Yann Ponty, and Michel Termier. Controlled non-uniform random generation of decomposable structures. Theoretical Computer Science, 411(40–42):3527–3552, 2010. doi:10.1016/j.tcs.2010.05.010.DOI
  18. [18]Alain Denise, Olivier Roques, and Michel Termier. Random generation of words of context-free languages according to the frequencies of letters. In Danièle Gardy and Abdelkader Mokdad, editors, Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Trends in Mathematics, pages 113–125. Birkhäuser, 2000. doi:10.1007/978-3-0348-8405-1_10.DOI
  19. [19]Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. Boltzmann samplers for the random generation of combinatorial structures. Combinatorics, Probability and Computing, 13(4–5):577–625, 2004. doi:10.1017/S0963548304006315.DOI
  20. [20]Amir Ehsani and Jalil Rezaeepazhand. Stacking sequence optimization of laminated composite grid plates for maximum buckling load using genetic algorithm. International Journal of Mechanical Sciences, 119:97–106, 2016. doi:10.1016/j.ijmecsci.2016.09.028.
  21. [21]Noémie Fedon, Paul M. Weaver, Alberto Pirrera, and Terence Macquart. A method using beam search to design the lay-ups of composite laminates with many plies. Composites Part C: Open Access, 4:100072, 2021. doi:10.1016/j.jcomc.2020.100072.DOI
  22. [22]Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, Cambridge, 2009. doi:10.1017/CBO9780511801655.DOI
  23. [23]Philippe Flajolet, Paul Zimmermann, and Bernard Van Cutsem. A calculus for the random generation of labelled combinatorial structures. Theoretical Computer Science, 132(1–2):1–35, 1994. doi:10.1016/0304-3975(94)90226-7.DOI
  24. [24]Hossein Ghiasi, Damiano Pasini, and Larry Lessard. Optimum stacking sequence design of composite materials. Part I: Constant stiffness design. Composite Structures, 90(1):1–11, 2009. doi:10.1016/j.compstruct.2009.01.006.DOI
  25. [25]L. J. Guibas and A. M. Odlyzko. String overlaps, pattern matching, and nontransitive games. Journal of Combinatorial Theory, Series A, 30(2):183–208, 1981. doi:10.1016/0097-3165(81)90005-4.DOI
  26. [26]Timothy Hickey and Jacques Cohen. Uniform random generation of strings in a context-free language. SIAM Journal on Computing, 12(4):645–655, 1983. doi:10.1137/0212044.DOI
  27. [27]F.-X. Irisarri, A. Lasseigne, F.-H. Leroy, and R. Le Riche. Optimal design of laminated composite structures with ply drops using stacking sequence tables. Composite Structures, 107:559–569, 2014. doi:10.1016/j.compstruct.2013.08.030.DOI
  28. [28]François-Xavier Irisarri. Stratégies de calcul pour l’optimisation multiobjectif des structures composites. Thèse de doctorat, Université Paul Sabatier — Toulouse III, Toulouse, France, 2009. HAL: tel-00514120. URL: https://theses.hal.science/tel-00514120v1.
  29. [29]Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169–188, 1986. doi:10.1016/0304-3975(86)90174–x.DOI
  30. [30]Zhao Jing, Xueling Fan, and Qin Sun. Stacking sequence optimization of composite laminates for maximum buckling load using permutation search algorithm. Composite Structures, 121:225–236, 2015. doi:10.1016/j.compstruct.2014.10.031.DOI
  31. [31]Robert M. Jones. Mechanics of Composite Materials. CRC Press, Boca Raton, 2nd edition, 2018. doi:10.1201/9781498711067.DOI
  32. [32]Laura Sumi Kang and Adriana Willem pje Blom. Optimization of ply orientations for multi-layer composite parts. U.S. Patent 10,467,350 B2, assigned to The Boeing Company, 2019. Filed 8 February 2016; granted 5 November 2019.
  33. [33]Jung-Seok Kim. Development of a user-friendly expert system for composite laminate design. Composite Structures, 79(1):76–83, 2007. doi:10.1016/j.compstruct.2005.11.030.DOI
  34. [34]Tae-Uk Kim and In Hee Hwang. Optimal design of composite wing subjected to gust loads. Computers & Structures, 83(19–20):1546–1554, 2005. doi:10.1016/j.compstruc.2005.02.002.DOI
  35. [35]Felix Klaedtke and Harald Rueß. Monadic second-order logics with cardinalities. In Automata, Languages and Programming (ICALP 2003), volume 2719 of Lecture Notes in Computer Science, pages 681–696, 2003. doi:10.1007/3-540-45061-0_54.DOI
  36. [36]A. Kloczkowski and R. L. Jernigan. Transfer matrix method for enumeration and generation of compact self-avoiding walks. I. Square lattices. The Journal of Chemical Physics, 109(12):5134–5146, 1998. doi:10.1063/1.477128.DOI
  37. [37]Alessio Langiu, Felice Rubino, and Giacomo Canale. composite-minply: an open-source validated workflow for minimum-thickness composite laminate design under buckling constraints, 2026. doi:10.5281/zenodo.22109868.DOI
  38. [38]Alessio Langiu, Felice Rubino, and Giacomo Canale. Counting and sampling manufacturable stacking sequences: code. Version 1.0.0 [software]. Zenodo, 2026. doi:10.5281/zenodo.23391635.arxiv.org/abs/2610.23146
  39. [39]Rodolphe Le Riche and Raphael T. Haftka. Optimization of laminate stacking sequence for buckling load maximization by genetic algorithm. AIAA Journal, 31(5):951–956, 1993. doi:10.2514/3.11710.DOI
  40. [40]Boyang Liu, Raphael T. Haftka, Mehmet A. Akgün, and Akira Todoroki. Permutation genetic algorithm for stacking sequence design of composite laminates. Computer Methods in Applied Mechanics and Engineering, 186(2–4):357–372, 2000. doi:10.1016/S0045-7825(99)90391–2.DOI
  41. [41]Xiaoyang Liu, Carol A. Featherston, and David Kennedy. Two-level layup optimization of composite laminate using lamination parameters. Composite Structures, 211:337–350, 2019. doi:10.1016/j.compstruct.2018.12.054.DOI
  42. [42]Ryosuke Matsuzaki and Akira Todoroki. Stacking-sequence optimization using fractal branch-and-bound method for unsymmetrical laminates. Composite Structures, 78(4):537–550, 2007. doi:10.1016/j.compstruct.2005.11.015.
  43. [43]David R. Morrison, Sheldon H. Jacobson, Jason J. Sauppe, and Edward C. Sewell. Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning. Discrete Optimization, 19:79–102, 2016. doi:10.1016/j.disopt.2016.01.005.
  44. [44]OEIS Foundation Inc. Entry A000984: central binomial coefficients. The On-Line Encyclopedia of Integer Sequences, 2026. https://oeis.org/A000984.
  45. [45]OEIS Foundation Inc. Entry A123620: Expansion of (1 + x + x²)/(1 − 3x − 3x²). The On-Line Encyclopedia of Integer Sequences, 2026. https://oeis.org/A123620.
  46. [46]Johan Oudinet, Alain Denise, and Marie-Claude Gaudel. A new dichotomic algorithm for the uniform random generation of words in regular languages. Theoretical Computer Science, 502:165–176, 2013. doi:10.1016/j.tcs.2012.07.025.DOI
  47. [47]François Pachet and Pierre Roy. Markov constraints: steerable generation of Markov sequences. Constraints, 16(2):148–172, 2011. doi:10.1007/s10601-010-9101-4.
  48. [48]Gilles Pesant. A regular language membership constraint for finite sequences of variables. In Principles and Practice of Constraint Programming – CP 2004, Lecture Notes in Computer Science, pages 482–495, 2004. doi:10.1007/978-3-540-30201-8_36.DOI
  49. [49]A. Rama Mohan Rao and N. Arvind. A scatter search algorithm for stacking sequence optimisation of laminate composites. Composite Structures, 70(4):383–402, 2005. doi:10.1016/j.compstruct.2004.09.031.DOI
  50. [50]Ali Rashed and Eralp Demir. Design of variable stiffness composites for maximum fundamental frequency considering manufacturing constraints of tow steering. Composite Structures, 284:115151, 2022. doi:10.1016/j.compstruct.2021.115151.DOI
  51. [51]Michael H. Shirk, Terrence J. Hertz, and Terrence A. Weisshaar. Aeroelastic tailoring – theory, practice, and promise. Journal of Aircraft, 23(1):6–18, 1986. doi:10.2514/3.45260.DOI
  52. [52]Grant Soremekun, Zafer Gürdal, Christos Kassapoglou, and Darryl Toni. Stacking sequence blending of multiple composite laminates using genetic algorithms. Composite Structures, 56(1):53–62, 2002. doi:10.1016/S0263-8223(01)00185-4.DOI
  53. [53]Richard Joel Thompson and Adriana Willempe Blom-Schieber. Ply optimization feasibility analysis for multi-layer composite parts. U.S. Patent 10,322,792 B2, assigned to The Boeing Company, 2019. Priority 8 February 2016; granted 18 June 2019.
  54. [54]Richard Joel Thompson and Adriana Willempe Blom-Schieber. Sublaminate library generation for optimization of multi-panel composite parts. U.S. Patent 10,380,319 B2, assigned to The Boeing Company, 2019. Filed 5 January 2017 as a continuation-in-part of application 15/018,075 (priority 8 February 2016); granted 13 August 2019.
  55. [55]Akira Todoroki and Raphael T. Haftka. Stacking sequence optimization by a genetic algorithm with a new recessive gene like repair strategy. Composites Part B: Engineering, 29(3):277–285, 1998. doi:10.1016/S1359-8368(97)00030-9.DOI
  56. [56]Akira Todoroki and Yuichiro Terada. Improved fractal branch and bound method for stacking-sequence optimizations of laminates. AIAA Journal, 42(1):141–148, 2004. doi:10.2514/1.9038.DOI
  57. [57]G. Verchery. Design rules for the laminate stiffness. Mechanics of Composite Materials, 47(1):47–58, 2011. doi:10.1007/s11029-011-9186-x.DOI
  58. [58]Herbert S. Wilf. A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects. Advances in Mathematics, 24(3):281–291, 1977. doi:10.1016/0001-8708(77)90059-7.DOI
  59. [59]Arne Wulff, Boyang Chen, Matthew Steinberg, Yinglu Tang, Matthias Möller, and Sebastian Feld. Quantum computing and tensor networks for laminate design: a novel approach to stacking sequence retrieval. Computer Methods in Applied Mechanics and Engineering, 432:117380, 2024. doi:10.1016/j.cma.2024.117380.DOI
  60. [60]Junbo Yang, Bifeng Song, Xiaoping Zhong, and Peng Jin. Optimal design of blended composite laminate structures using ply drop sequence. Composite Structures, 135:30–37, 2016. doi:10.1016/j.compstruct.2015.08.101.DOI
  61. [61]S. Zein, P. Basso, and S. Grihon. A constraint satisfaction programming approach for computing manufacturable stacking sequences. Computers & Structures, 136:56–63, 2014. doi:10.1016/j.compstruc.2014.01.016.DOI

Paper details

vlnc:W_n8meaf58
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents