Noam Goldberg
email: noam.goldberg@biu.ac.il

Michael Poss
email: michael.poss@lirmm.fr

Maximum Probabilistic All-or-Nothing Paths

Keywords: networks, dynamic programming, integer non-linear programming, FPTAS

We consider the problem of a maximum probabilistic all-or-nothing network path. Each arc is associated with a profit and a probability and the objective is to select a path with maximum value for the product of probabilities multiplied by the sum of arc profits. The problem can be motivated by applications including serial-system design or subcontracting of key project activities that may fail. When subcontracting such critical success activities, each must be completed on time, according to the specs, and in a satisfactory manner in order for the entire project to be deemed successful. We develop a dynamic programming (DP) method for this problem in the acyclic graph setting, under an independence assumption. Two different fully-polynomial approximation schemes are developed based on the DP formulations, one of which applies repeated rounding and scaling to the input data, while the other uses only rounding. In experiments we compare the DP approach with mixed-integer nonlinear programming (MINLP) using a branch-and-cut method, on synthetic randomly generated instances as well as realistic ones.

Introduction

Network optimization problems with an objective that involves a probability of the intersection of independent addtworandom events have been extensively studied. For example, in the reliability literature, some authors propose the objective of minimizing a ratio of cost to reliability [START_REF] Ravindra | Minimum cost-reliability ratio path problem[END_REF][START_REF] Katoh | A fully polynomial time approximation scheme for minimum cost-reliability ratio problems[END_REF]. The reliability of a subgraph of a given network graph is defined as the product of the edge probabilities, each of which corresponds to the probability that the edge remains functional. The closely related area of sequential system testing involves finding a least cost policy, which may correspond to a binary decision tree, of system components to test in order to determine whether the entire system is operational; see [START_REF] Ben-Dov | Optimal testing procedures for special structures of coherent systems[END_REF]; [START_REF] Boros | Diagnosing double regular systems[END_REF] as well as [START_REF] Daldal | Approximation algorithms for sequential batch-testing of series systems[END_REF] and the references therein.

Similar network optimization problems also arise in the network interdiction literature [START_REF] Pan | Minimizing a stochastic maximum-reliability path[END_REF][START_REF] Goldberg | Non-zero-sum nonlinear network path interdiction with an application to inspection in terror networks[END_REF] where the model may involve expected-value profit-probability product maximization (rather than minimization of a cost-reliability ratio). Probabilistic all-or-nothing expected-value maximization objectives have also been proposed in the kidney exchange game theory literature [START_REF] Dickerson | Failure-aware kidney exchange[END_REF], where they are termed discounted utility. These problems share the characteristic that value is only derived from a feasible solution (a subgraph such as a network path) if all of the underlying arcs are functional. Our problem extends probabilistic all-or-nothing subsets introduced by Goldberg and Rudolf (2017) to maximize a similar objective over network paths. The all-or-nothing subset problem involves selecting a subset of (unordered) activities such that the sum of activity payoffs multiplied by the product of their success probabilities is maximized.

An important application of our model is in designing series-connected subsystems of the power grid. In particular, in renewable energy generation it is quite common to use series-connected generators, for example in a string inverter layout, many photo-voltaic (PV) panel units may be connected in series; see for example [START_REF] Zhang | Reliability evaluation of grid-connected photovoltaic power systems[END_REF]. Although technical considerations may impose some bounds on the number of units to be connected using a single inverter (e.g., due to voltage requirements), generally a wide range of design and configuration choices may be available. In the subsystems being considered, a failure of one of the units would imply the failure of all units connected to the same inverter. Hence, the objectives of maximizing the subsystem's reliability and maximizing the operating state's power capacity (and/or associated profit) are antagonistic. Compared with bicriteria and single-objective constrained-maximization approaches, which : Series-connected power subsystem design. This example may illustrate a string array of 7 generators to be connected in series. In each position a generator is to be chosen given a choice of 5 generator types. Each generator j may correspond to a different power generation capacity c sj and reliability (one minus the probability of failure) p sj . Typically the generation capacity (accordingly revenue) and the failure probability for the same generator, j = 1, . . . , 5, would similar irrespective of the position. So that for all i = 1, . . . , 5, c sj = c i,j+5 and p sj = p i,j+5 . potentially leave a large set of candidate nondominatred solutions or require an arbitrary specification of a constraint parameter, our model maximizes the subsystem's expected profit, thereby it simultaneously accounts for both the system reliability and its generation capacity. The network corresponding to all feasible series subsystem can be represented as a directed acyclic graph (DAG). An example of a design problem of a certain series-connected power subsystem is illustrated in Figure 1. Note that in general the design network may not be a grid in cases where not all generator choices are available in a particular position and/or if the number of generators to be included is not a-priori fixed.

Our model can also be motivated by the important application of project activity networks. R&D Project activity scheduling when activities may fail has been considered by De Reyck and Leus (2008); [START_REF] Coolen | Scheudling modular projects on a bottleneck resource[END_REF].

These papers propose models for scheduling project activities in the case that activities may fail and the overall project success depends on the success of each and every activity. The objective is to maximize the expected profits where each activity incurs a negative payoff (i.e., a cost) and the project completion involves a positive payoff (revenue). In De [START_REF] De Reyck | R&D project scheduling when activities may fail[END_REF], the overall net present value is considered by time-discounting the Figure 2: A multigraph that illustrates activity precedence and subcontracting: An activity arc label pair (c a ij , p a ij ) along arc a ij indicates, respectively, the cost savings relative to a baseline activity arc (i -1, i) (for example, when the activity is carried out in-house) and the probability of successful on-time completion, using subcontractor j. Note that while this example is illustrated as a multigraph, it could be transformed into a directed graph (without parallel edges) using additional dummy vertices and 0-cost, probability-1 arcs).

project revenue and costs, which are associated with each of the project's underlying activities. In [START_REF] Coolen | Scheudling modular projects on a bottleneck resource[END_REF], the activities are partitioned into modules so that all modules must succeed in order for the project to be successful (while not all activities have to succeed in each module for the entire project to succeed).

In many industries such as construction, project activities are typically subcontracted. Complex engineering projects can be under significant pressures to be delivered at the lowest possible cost and consequently, costs are a major concern in procurement and subcontractor selection; see for example [START_REF] Damodara | Materials management: The key to successful project management[END_REF]; [START_REF] Abbasianjahromi | A new decision making model for subcontractor selection and its order allocation[END_REF]. When identifying the subcontractor to which a particular activity or task should be assigned, both cost and reliability considerations are taken into account. Reliability may be defined as the probability of completing a given task successfully and within an acceptable timeframe. Reliability considerations have been noted

as especially important for critical activities [START_REF] Icmeli | Ensuring quality in resource constrained project scheduling[END_REF][START_REF] Kim | A practical approach to project scheduling: considering the potential quality loss cost in the time-cost tradeoff problem[END_REF]. Every candidate subcontractor for each activity may be evaluated relative to a safe baseline alternative, for example, the alternative of completing the task in-house or that of using a highly reliable "premium"

subcontractor. Both of these alternatives are likely to incur higher costs but with the benefit of greater reliability. A multigraph that represents the critical path subcontracting problem is illustrated in Figure 2.

Assuming that arcs fail independent of one another, the problem that we model can be viewed as an optimization of a nonlinear utility function over Pareto efficient bicriteria optimal paths; the defined utility is the product of the sum of arc profits with the product of arc probabilities. The independence assumption is common in network reliability literature [START_REF] Ravindra | Minimum cost-reliability ratio path problem[END_REF][START_REF] Katoh | A fully polynomial time approximation scheme for minimum cost-reliability ratio problems[END_REF][START_REF] Michael | Network reliability[END_REF] as well in project management literature (see for example [START_REF] Hossein | The most critical path in a PERT network: A heuristic approach[END_REF]; De Reyck and Leus ( 2008)). Bicriteria shortest paths have been extensively studied with linear objectives, as have extensions with linear utility functions defined over the set of Pareto optimal paths. For references on approximation algorithms for multicriteria optimization problems, and in particular for shortest paths, see [START_REF] Hansen | Bicriterion path problems[END_REF]; [START_REF] Warburton | Approximation of pareto optima in multiple-objective, shortest-path problems[END_REF]; Henig (1994); [START_REF] Papadimitriou | On the approximability of trade-offs and optimal access of web sources[END_REF] and the references therein. A particular variant of a constrained shortest path has also been extensively studied [START_REF] Hassin | Approximation schemes for the restricted shortest path problem[END_REF][START_REF] Ergun | An improved FPTAS for restricted shortest path[END_REF][START_REF] Raz | A critical look at critical chain[END_REF]. In particular, these studies have improved on the computational complexity of general schemes for bicriteria shortest path [START_REF] Hansen | Bicriterion path problems[END_REF][START_REF] Warburton | Approximation of pareto optima in multiple-objective, shortest-path problems[END_REF].

In Section 2 we model the probabilistic all-or-nothing path problem.

We develop a dynamic program (DP) with a pseudopolynomial worst-case complexity in acyclic graphs in Section 3. Fully-polynomial time approximation schemes (FPTAS) are described in Section 5, which use scaling and/or rounding techniques together with our previously described DPs. Our problem is reformulated as a convex integer program in Section 6. In Section 7 we conduct experiments to compare the DP approaches with integer programming methods. We consider randomly generated instances and also onces that are based on real-life examples of IT and civil engineering projects.

Problem Definition

We now formally state the probabilistic all-or-nothing path problem. Let G = (V, E) be a directed graph, s, t ∈ V be the source and the sink, and objective function

let δ + (i) = {j ∈ V : (i, j) ∈ E} and δ -(i) = {j ∈ V : (j, i) ∈ E}
z(π) = e∈π c e f ∈π p f (1)
is maximized. Given any node i ∈ V , let us denote the set of all paths from s to i by P(i). Then, the optimization problem is to determine

z * ≡ max{z(π) : π ∈ P(t)}. (2)
When p e = 1 for each e ∈ E, problem (2) amounts to finding a longest path in G. Hence, in a general graph our problem is N P-hard in the strong sense (Garey and Johnson , 1979, pp. 199-200). We now show through a reduction from the unconstrained all-or-nothing problem that even in Directed Acyclic Graphs (DAGs), the problem is N P-hard (although in the ordinary sense).

Proposition 1. Problem (2) is N P-hard in DAGs with a node in-degree and out-degree of at most 2.

Proof. Consider an instance of the n-item all-or-nothing subset problem which, given item profits c ∈ Z n + and item probabilities p ∈ (0, 1) n , slightly determines a subset S ⊆ [n] that maximizes i∈S ci j∈S pj (over all subsets S ⊆ [n]). This problem is proved to be N P-hard in Goldberg and Rudolf (2017). Then, let G be defined as the directed graph with 2n + 1 vertices, as depicted in Figure 3. Let c (i-1)i = ci and p (i-1)i = pi for i = 1, . . . , n, and let c (i-1)i = c i i = 0 and p (i-1)i = p i i = 1. It follows that for every S ⊆ [n], there exists a path π in G so that i ∈ S if and only if (i -1, i) ∈ π.

Similarly, for every path π in G there exists a subset S ⊆ [n] so that every arc (i -1, i) ∈ π if and only if item i ∈ S. Further, it can be verified that in both cases (i,j)∈π p ij (k,l)∈π c kl = i∈S pi j∈S cj .

Note that the reduction in the proof of Proposition 1 uses a directed graph that is equivalent to the path network with parallel edges in Figure 2 with exactly two edges in parallel between each node pair along the chain. Also note that compared with the problem considered in De Reyck and [START_REF] De Reyck | R&D project scheduling when activities may fail[END_REF] each item/activity i is associated with a positive payoff c i . Although, some of our solution techniques may be extended to handle either positive or negative c i 's, compared with only negative payoffs (positive activity costs) in De Reyck and Leus ( 2008) and a positive project payoff for the last activity.

The NP-hardness result of Proposition 1 applies in the case that we consider when all of the c i 's are nonnegative. Finally, note that our objective (1) also resembles that of the minimum cost-to-reliability ratio problems for which negative computational complexity results remain open Ahuja (1988); [START_REF] Katoh | A fully polynomial time approximation scheme for minimum cost-reliability ratio problems[END_REF].

Dynamic Programming

We now develop DP algorithms to solve problem (2).

DP with State Space defined by the Profit Coefficient. Let Z c (C, i) denote the maximum objective value of a path from s to i with a realized total profit of (exactly) C for the arc profit vector c, so

Z c (C, i) = max z(π) : π ∈ P(i), e∈π c e = C .
(3)

Herein, when subscript c is omitted then Z by itself will refer to the given arc coefficients c. Let π(C, i) denote a path (a subset of arcs) that reaches the maximum in (3) (for the sake of unambiguity assume that ties are broken by selecting the lexicographically smallest path as a sequences of vertices).

Note that Z(C, i) satisfies the optimality condition

Z(C, i) =                  max j∈δ -(i) z(π(C -c ji , j) ∪ {(j, i)}) i ∈ V \ δ + (s) or c si < C max      c si p si , max j∈δ -(i)\{s}: c ji =C z(π(C -c ji , j) ∪ {(j, i)})      i ∈ δ + (s), C = c si -∞ C < 0. (4) It can be observed that for (j, i) ∈ π(C, i), z(π(C -c ji , j) ∪ {(j, i)}) = C • p ji f ∈π(C-c ji ,j) p f = C • p ji Z(C-c ji ,j) C-c ji if C -c ji > 0 C • p ji otherwise, (5)
where ( 5) follows directly from the definition of π(C -c ji , j), Z(C -c ji , j)

and z (note that the second line of ( 5) is needed when considering the direct successors of s). Plugging ( 5) into (4), for i ∈ V \ {s}, the DP equations are

Z(C, i) =                max j∈δ -(i) Cp ji Z(C-c ji ,j) C-c ji i ∈ V \ δ + (s) or c si < C max    c si p si , max j∈δ -(i)\{s}: c ji =C Cp ji Z(C-c ji ,j) C-c ji    i ∈ δ + (s), C = c si -∞ C < 0. (6)
To determine z * using the DP method given an upper bound on a∈π * c a ≤ C, (6) must be evaluated for C = 1, . . . , C. In particular

z * = max C=1,..., C Z(C, t). (7)
Let C * denote an optimal solution of (7). A straightforward upper bound C ≥ C * in a DAG is a∈E c a . A tighter upper bound, although its use may not affect the worst-case computational complexity of (7), is the longest path from s to t in the graph with arc profits c.

DP with State Space defined by the Probability Coefficient. In this case we first revise our DP formulation such that the product of probabilities is the state variable. Also, we must now assume that the probabilities are rational numbers, so for all e ∈ E, p e ∈ [0, 1] ∩ Q. Let Z p (P, i) denote the expected total profit of a path from s to i with a probability of (exactly)

P given probability vector p ∈ [0, 1] |E| . Thus for each i ∈ V Z p (P, i) =            max j∈δ -(i) {p ji Z p (P/p ji , j) + P • c ji } i = s, P ≤ 1 0 i = s, P = 1 -∞ i = s, P = 1. ( 8
)
Since the probabilities are rational, let us further suppose that they are given as p e = q e /d e for e ∈ E, where q e ,d e ∈ Z. Then, the DP ( 8) can be solved in finitely many steps with a maximum expected total profit from node s to node t given by max k=1,..., e∈E qe

Z p k e∈E d e , t . (9)
Now suppose that there exists some b > 0 such that for each e ∈ E, p e = b ke for some k e ∈ Z. Then, the next proposition establishes that the running time of DP ( 8) is polynomial in m, n and max e∈E k e under this assumption. Proof. The correctness of (8) follows by induction: For all π ∈ P(j) and (j, i) ∈ δ + (j), z(π ∪ {(j, i)}) = (z(π) + c ji )p ji . The maximizing path to i ∈ V is found by determining the maximum of z(π ∪ {(j, i)}) over the predecessors j ∈ δ -(i). The base case has π = {(s, i)}, z(π) = p si c si and trivially z(∅) = 0. Then, an optimal solution of ( 2) is determined by solving max k=0,1,...,n max e∈E ke

Z p b k , t ,
which has a running time complexity bound of O(mn max e∈E k e ).

We consider straightforward bounds on C * and z * as well as further tightening of these bounds in the following section.

4 Bounding z * and C *

The running time of the DP algorithm (7) directly depends on C as an upper bound on C * . Bounds on the optimal objective value may also be necessary to derive an approximation result. Some of the analysis that follows will be used to support the approximation results that appear in Section 5, while some will be used for the exact DP method experiments in Section 7. The following proposition establishes a lower bound on the optimal objective value.

Proposition 3. A lower bound on the optimal objective value is given by

z LB ≡ max π∈P(t) e∈π p e max f ∈π {c f } ≤ z * . (10)
Further, this bound satisfies z LB = max a∈E R(a).

It follows that z LB can be computed by solving at most m maximumreliability path problems, where each provides the value R(a) for a given a ∈ E. In a DAG the maximum-reliability path problem (similar to the shortest path problem) can be solved in O(m) running time using a topological sort algorithm [START_REF] Thomas H Cormen | Introduction to algorithms[END_REF].

Let H(v) denote the maximum number of hops, or the longest elementary path in terms of number of arcs, from s to v. The next proposition establishes an upper bound on the optimal solution value.

Proposition 4. z * ≤ H(t) • z LB .
Proof. Let π * denote a solution that is optimal for (2) and let π denote a solution that is optimal for (10). By the optimality of π,

z LB = e∈π p e max f ∈π c f ≥ e∈π * p e max f ∈π * c f . Since π * is an elementary path with |π * | ≤ H(t), H(t)z LB ≥ e∈π * p e H(t) max f ∈π * c f ≥ e∈π * p e f ∈π * c f = z * .
For convenience in the following, for a vector v ∈ R β , let v max = max β i=1 v i and v min = min β i=1 v i . The bounds on the optimal objective value do not necessarily imply bounds on C * ∈ argmax C {Z(C, t)}. However, given a lower bound on the optimal objective value, it may be possible in some cases to tighten the otherwise loose bounds on C * . The following proposition summarizes the bounds on C * .

Proposition 5. Suppose that C * ∈ argmax C {Z(C, t)}. Then, (i) C * ∈ [min π∈P(t) e:e⊆π c e , max π∈P(t) e:e⊆π c e ] ⊆ [c min , H(t)c max ]. (ii) C * ∈ e∈E [c e , H(t)c e ]. (iii) Let a * ∈ argmax a R(a). If for all a = a * satisfying H(t)R(a) > z LB , c a * ≥ c a , then [min a:(n-1)R(a)>z LB c a , H(t)c a * ] ∩ argmax C Z(C, t) = ∅.

Proof.

Proofs of (i) and (ii). Straightforward.

Proof of (iii). Suppose that c a * ≥ c a for all a = a * such that H(t)R(a) > z LB and suppose also that for all π * that are optimal to (2),

C * = a∈π * c a > H(t)c a * . Let f ∈ argmax e∈π * {c e }. Then, (n-1)R(f ) ≥ (n-1)c f e∈π * p e ≥ z(π * ) > z(π) ≥ z LB . Since H(t)R(f ) > z LB , it follows that c a * ≥ c f . But then H(t)c a * ≥ H(t)c f ≥ C * thereby establishing a contradiction.
Note that the tightening of the bounds in Proposition 5-(i), in particular the upper bound, relies on the computation of the longest path in a graph and so it can be determined in polynomial time in DAGs. This is while the straightforward upper bound H(t)c max ≤ (n-1)c max applies also in the case of general graphs. Also, note that although the bound of Proposition 5-(ii) corresponds to m intervals, the advantage of using this bounding set is that each interval has an upper bound that is only a (polynomial) factor of (n-1) times the lower bound.

We now describe a family of (deterministic) instances to illustrate the utility of tightening the bound on C * based on Proposition 5-(iii). Example 1 illustrates an application of Proposition 5-(iii). In practice the tightened bound can be used to make the DP more efficient or, perhaps, to preprocess a given graph more effectively by deleting arcs that cannot be a part of an optimal path. In particular, in Example 1 the graph can be reduced to the single path π * = {(s, 1), (1, 2), . . . , (k, t)}.

s 1 2 • • • k t v 1 v 2 • • • v k M, 1 M, 1 M, 1 M, 1 M, 1 L, 1/2 L, 1/2 L, 1/2 L, 1/2 L, 1/2 2L, 1 2•2 2 3L, 1 3•2 3 kL, 1 k2 k kL, 1 k2 k (k-1)L, 1 (k-1)2 k-1 2L, 1 2•2 2

Approximation Schemes

We now consider two different approximation schemes. First, a scaling and rounding scheme is applied to the c coefficients.

Profit coefficient scaling and rounding scheme. Consider Algorithm 1 as an approximation scheme given a relative error bound 0 < < 1 and an interval [ , u] so that there exists a

C * ∈ [ , u] where C * ∈ argmax C Z(C, t).
Following the discussion of the previous section, a straightforward ratio of bounds is given by u ∈ O(nc max /c min ). The computational complexity of our algorithm will depend on the magnitude of this ratio. Thus, we will also consider the repeated application of the algorithm when given a union of intervals of polynomially-bounded upper to lower bound ratios.

Algorithm 1 Profit Rounding and Scaling Approximation Scheme

Input: G = (V, E), p, c, 0 < < 1, , u {Bounds , u satisfy ≤ C * ≤ u.} 1: a * ← argmax a∈E R(a) 2: while q = 0, . . . , log u -log -1 do 3: K ← 2 q n-1 4: ce ← -∞ c e > 2 q+1 c e /K otherwise 5:
zq ← K • max C=0,..., 2(n-1) Z c(C, t); let π q = π(C, t) be the corresponding path. 6: end while 7: Select q * ∈ argmax{z q } Output: z(π q )

Following Algorithm 1, we define the scaled objective as

z c (π) = e∈π ce f ∈π p f ,
and the scaled problem is max{z c (π) : π ∈ P(t)}. The next lemma establishes an approximation relation between solutions of the scaled problem when 2 q ≤ z * e∈π * pe ≤ 2 q+1 in the main loop of Algorithm 1 and solutions that are optimal to (2).

Lemma 1. If K ≤ L (n-1) where L ≤ z * e∈π * pe , then π ≡ π q in the main loop of Algorithm 1 satisfies e∈π c e f ∈π p f ≥ (1 -)z * .
Proof. The result follows from the optimality of π for the rounded profits c and the assumption on K, specifically

e∈π c e f ∈π p f ≥ Kz c (π) (Rounding of c) ≥ e∈π * c e /K K f ∈π * p f (Optimality of π for c) ≥ ( e∈π * c e -(n -1)K) f ∈π * p f (Rounding of c) ≥ (1 -)z * (Assumed upper bound on K)
Intuitively, Lemma 1 shows that the desired approximation guarantee is attained as long as the scaling factor K is sufficiently small. It remains to show that such a "sufficiently small" scaling factor also allows for a polynomial running time complexity bound. The correctness and complexity bound of Algorithm 1 are established in the following proposition.

Proposition 6. The output z of Algorithm 1 satisfies z ≥ (1 -)z * . The complexity of Algorithm 1 is O( 1 mn log(u/ )).

Proof. The first part of the claim is evident from Lemma 1 and from the fact that the scaled DP is run over an interval that contains a maximizer C * . In particular, the main loop goes through q = 0, . . . , log u -log l -1 and the intervals [2 q , 2 q+1 ] partition the interval [ , u]. Each maximization using the DP with scaled profits in line 5 has a complexity bound of O(mn/ ), while the number of iterations of the main loop is bounded by O(log(u/ )). Together, these bounds imply an overall complexity bound of O( 1 mn log(u/ )).

Corollary 1. Algorithm 1 invoked with = c min , u = nc max outputs a solution with objective z ≥ (1 -)z * . The complexity of Algorithm 1 is

O( 1 mn log(nc max /c min )).
Observe that Proposition 6 establishes a polynomial complexity bound for Algorithm 1, although it is not strongly polynomial. The following proposition establishes a strongly polynomial time complexity at the cost of repeatedly invoking Algorithm 1 (m times).

Proposition 7. Algorithm 1 can be invoked repeatedly to output a solution with objective z ≥ (1 -)z * with a complexity bound of O( 1 m 2 n log n).

Proof. By invoking Algorithm 1 once for each arc a ∈ E, with = c a and u = (n -1)c a , and outputting the best solution value. This approach uses the straightforward observation that C * ∈ e∈E [c e , (n -1)c e ] (see also

Proposition 5-(ii). So, the analysis of the complexity bound is similar to that in the proof of Proposition 6 except that the algorithm is invoked m times and each invocation now involves O(log(u/ )) = O(log n) iterations.

Note that for every π * that is optimal to (2), the pair (C * , P * ) ≡

( e∈π * c e , e∈π * p e ) must be Pareto efficient: for all π ∈ P(t), if P C = P * C * then either C = e∈π c e < C * or P = e∈π p e < P * . It follows that approximation schemes for multicriteria shortest path problems could be adapted to determine an optimal solution for our problem. [START_REF] Hansen | Bicriterion path problems[END_REF] and [START_REF] Warburton | Approximation of pareto optima in multiple-objective, shortest-path problems[END_REF] developed a fully-polynomial time approximation scheme (FPTAS) for bicriteria and constant-number multicriteria path problems, respectively.

More efficient approximation schemes were developed by [START_REF] Hassin | Approximation schemes for the restricted shortest path problem[END_REF] for the related problem of the (linear) constrained shortest path. In contrast to the situation in the current problem, in the constrained shortest path case, it is possible to binary search a bounded interval of the logarithm of objective values. Subsequent improvements to Hassin's scaling-based approximation scheme for constrained shortest paths were developed by [START_REF] Dean | A simple efficient approximation scheme for the restricted shortest path problem[END_REF] and [START_REF] Ergun | An improved FPTAS for restricted shortest path[END_REF].

Probability-rounding scheme. We now consider a rounding scheme (without scaling) that is applied to the probability coefficients. Proposition 2 shows that under the assumption that the probabilities are powers of a common base, then the exact solution can be determined using DP (8) in polynomial time. In the absence of this assumption, we develop an approximation scheme that further exploits the result of Proposition 2. This rounding based scheme is given by Algorithm 2.

For convenience let z p (π) denote the objective value of path π (similar to Z p ) with probability vector p. The following proposition establishes that Algorithm 2 is an FPTAS.

Algorithm 2 Probability Rounding Approximation Scheme

Input: G = (V, E), p, c, 1: For each e ∈ E, let p e = (1 -)

log (1-) 1/n pe /n .

2: z = max k=1,...,n log (1-) 1/n (p min ) Z p (1 -) k/n , t . Let π be the corresponding path. Output: z(π) Proposition 8. Algorithm 2 computes a solution for (2) with an objective at least (1 -)z * in time O(-1 mn 2 log(p min )).

Proof. Consider π, which is the output of Algorithm 2, and π * , which is optimal to (2). By (i) the definition of p , (ii) the maximum number of arcs that form an elementary path and (iii) the optimality of π and π * for their respective problems, it follows that

z p (π) ≥ z (π) ≥ z (π * ) ≥ e∈π * p e (1 -) 1/n f ∈π * c f ≥ (1 -)z(π * ).
The complexity of the algorithm (recalling that for positive x,

log x ≤ x -1) is O(-m f ∈E log (1-) 1/n p f ) ⊆ O - 1 mn 2 log(p min ) .
Discussion. To summarize the approximation results of this section, our strongly polynomial profit scaling and rounding based FPTAS has a complexity of O( 1 m 2 n log n). Our alternative, simple probability rounding based FPTAS has a runtime complexity of O(-1 mn 2 ln p min ). The latter may be preferable if the probabilities are sufficiently large with respect to n, in particular, if p min ∈ Ω(e -n log n ). Also, note that using the directed graph reduction in the proof of Proposition 1, the all-or-nothing subset problem can be solved using our methods with m ∈ O(n). This implies a strongly polynomial runtime complexity of O( 1 n 3 log n) to solve the subset problem, which outperforms the O(n 4 / ) runtime complexity of the corresponding algorithm presented by Goldberg and Rudolf (2017).

A Convex Mixed-Integer Nonlinear Program (MINLP) Formulation

In this section we develop a MINLP model and a specialized MINLP method.

The latter will serve as a benchmark for empirically evaluating the efficiency of the DP as an exact solution technique in the following section. Introducing decision variables x ∈ {0, 1} m to indicate which arcs are selected to form a path, and accordingly the set of feasible paths

Π ≡ x ∈ R m (j,i)∈E x ji = (i,j)∈E x ij , i∈V \{s,t} (s,i)∈E x si =1, (j,t)∈E x jt =1
, the problem can be formulated as a MINLP. Following Goldberg and Rudolf (2017) we rewrite z(π) as

z(x) = e∈E c e x e f ∈E p x f f . (11)
Further, maximizing z(x) is equivalent to maximizing its logarithm, so ( 11) can be replaced by the concave objective function ln(z(x)) = ln

e∈E c e x e + f ∈E ln(p f )x f . ( 12
)
Then the derived MINLP formulation is

max {ln(z(x)) | x ∈ Π ∩ {0, 1} m } . ( 13
)
It can be observed that as a concave maximization problem with linear constraints, this formulation is a convex MINLP. In Section 7 we conduct experiments using this formulation and treat it as a benchmark for our proposed computational techniques.

To solve this model using state-of-the art linear integer programming solvers, we implement our own MINLP linearization and objective-based cutting plane techniques. While our convex MINLP method implementation is fairly standard, it specializes the general techniques for our problem. In particular, following the concavity of ln(z(x)), subgradient objective cuts can be derived for problem formulation (13). For any x that is feasible for formulation ( 13

subject to x ∈ Π (15b) g(x, x, u) ≤ 0 x ∈ Π 0 (15c) x ∈ {0, 1} m . (15d)
For a solution (x, u) that is feasible to (15), Algorithm 3 dynamically generates the cuts (14) required to solve (13) as a sequence of mixed-integer linear programs (MILPs) (15) to within a given relative-optimality gap γ ∈ [0, 1).

Note that although Algorithm 3 solves a sequence of MILPs, where each MILP may be solved to optimality, it can instead be implemented such that step 3 outputs any upper bound. Indeed, an approach that is usually more efficient in practice is to generate the inequalities (15c) dynamically and to "hot-start" the previous iteration's branch-and-bound tree in step 3 of the algorithm, or equivalently, to generate the inequalities (15c) as a part of a branch-and-cut algorithm. We conduct experiments using a branch-and-cut

Algorithm 3 Input: G = (V, E), c, p, 0 ≤ γ < 1 1: Π 0 ← {1} 2: while True do 3:
Solve (15) to determine a feasible solution x, u.

4:

if ln z(x) ≥ (1 -γ) u + e∈E ln(p e )x e then 5:

break.

6:

else 7:

Π 0 ← Π 0 ∪ {x} 8:
end if 9: end while Output: z(x) approach in Section 7.

Computational Results

In this experimental analysis, we compare our MINLP method (Algorithm 3) and DP (7) with a standard MINLP solver for solving problem (13), Bonmin. Algorithm 3 was implemented using Gurobi and was based on its cut generation routine. The next subsection contains further implementation details, while the following subsections detail our experiments using three sets of instances: random graph instances, specific types of graphs, and realistic instances based on project management.

Implementation details

All experiments were carried out on a CPU Intel i7-5500 3.0 GHz processor under the Ubuntu 16.04 operating system. Our algorithms were coded in Julia 5.1 using the package JuMP [START_REF] Dunning | Jump: A modeling language for mathematical optimization[END_REF] to interact with the MIP solvers. The MINLP (13) was solved in two different ways: using Bonmin 1.8.4 (with MUMPS as the linear solver) and using a branch-and-cut algorithm that generates the cuts ( 14) at the integer nodes found along the tree and interacts with Gurobi 7.02 through callbacks. It is essentially similar to Algorithm 3 (setting γ = 10 -4 ) but using Gurobi's callback facility to incorporate the generation of cuts within its branch-and-cut implementation.

General Random Graph Instances

We consider below two sets of random instances generated uniformly as topologically ordered DAGs, which means that for an ordering 1, ..., n ∈ V , all edges (i, j) ∈ V × V with i < j have the same probability of appearing in each graph. Furthermore, we consider s = 1 and t = n and ensure that there exists at least one path between s and t (otherwise the current graph is discarded and another one is generated). Similar to the random generation of knapsack instances (see for example [START_REF] Pisinger | A minimal algorithm for the 0-1 knapsack problem[END_REF]), as well as other constrained combinatorial optimization problems, we find that the degree of correlation between item profits and constraint coefficients may heavily affect the observed difficulty in solving the generated instances. Thus, we consider two different schemes for generating the probability coefficients (analogous to budget constraint coefficients in constrained settings):

Probabilities generated uniformly at random (independent of profits).

All graphs are generated given the following parameters: the number of vertices, the graph density, and the maximum edge profit. The number of vertices n ranges in {50, 100, 150, 200, 250, 300, 350, 400}, edge densities in {0.1, 0.2, 0.3, 0.4, 0.5}, maximum profit c max ∈ {50, 100, 150, 200}, and minimum probability p min ∈ {0.5, 0.6, 0.7, 0.8, 0.9}. The cost c e for each edge e is an integer uniformly generated between 1 and c max and the probability p e is uniformly generated in [p min , 1].

Probabilities inversely related with profits. For the second set of instances, we focus on smaller graphs (n = 50) with c max ranging in {50, 200, 400, 600, 800, 1000}. The cost c e is again uniformly generated between 1 and c max while the probability is now given by the relation p e = e -α ce cmax where α ranges in {1, 10, 20, 30}.

We now examine the results of our experiments. bound provided by the aforementioned longest path given arc length vector c (referred to as global UB in Figure 6), and C 2 = H(t)c a * with a * defined in Proposition 5-(iii) (referred to Prop 5. in Figure 6). It also appears the greatest improvement of the bound computed based on Proposition 5-(iii) is obtained with "small" correlated probability values corresponding to a large value of α. At the same time, it should be noted that for these instances Gurobi is much faster than the dynamic programming algorithms, which is explained by the larger bounds on C * used, which is consistent with the large ratios indicated by Figure 7 (in the experiments of Figure 5 with noncorrelated instances the corresponding ratios appeared to be significantly less than 400%).

Conclusion

In this paper we introduced a new probabilistic all-or-nothing path problem motivated by critical-path analysis and procurement applications. We developed the analysis and a suite of solution techniques to address this problem: approximation schemes with theoretical guarantees with respect to the quality of the solutions that are determined, as well as practical computational approaches. In our computational experiments we found that our specialized MINLP algorithm was most effective in general, in particular for large values of c max , although the DP method, including its variants that compute tightened state space parameter bounds, outperformed the MINLP algorithm in some cases. We showed that the MINLP method applied to networks constructed based on critical paths of real projects runs within less than a minute of CPU time. The observed optimal solutions show that increasing the variety of task subcontracting alternatives may result in somewhat riskier optimal solutions but with sufficiently higher profits to justify this risk.

In ongoing work we consider solution methods for a partial success model similar to the one considered in [START_REF] Dickerson | Failure-aware kidney exchange[END_REF], in which functional subpaths of a network path solution also yield a partial value. This extension may be useful for additional applications such as for the problem of determining optimal transplant-donation chains in kidney exchange compatibility graphs.

  Figure1: Series-connected power subsystem design. This example may illustrate a string array of 7 generators to be connected in series. In each position a generator is to be chosen given a choice of 5 generator types. Each generator j may correspond to a different power generation capacity c sj and reliability (one minus the probability of failure) p sj . Typically the generation capacity (accordingly revenue) and the failure probability for the same generator, j = 1, . . . , 5, would similar irrespective of the position. So that for all i = 1, . . . , 5, c sj = c i,j+5 and p sj = p i,j+5 .

Figure 3 :

 3 Figure 3: The instance used in the reduction of the all-or-nothing subset problem to the all-or-nothing path problem: Traversing an upper arc in the graph corresponds to selecting an item in the subset problem.

Proposition 2 .

 2 If there exists b > 0 such that for all e ∈ E, p e = b ke for some k e ∈ Z, then DP (8) can be applied to solve problem (2) with a running time complexity of O(mn max e∈E k e ).

  For convenience, for each a ∈ E define R(a) ≡ max π∈P(t) e∈π r e (a), where r e (a) =    c e p e e = a, p e otherwise. Note that as each π is an elementary path, then arc a ∈ A appears at most once in a path that is a maximizer in the definition of R(a). Denote such a maximizer by π. It follows that R(a) =    c a e∈π p e a ∈ π, e∈π p e otherwise.

Figure 4 :

 4 Figure 4: Deterministic instances that illustrate the utility of tightening the bound on C * using the result of 5-(iii).

  ), the following inequality ln(z(x)) ≤ ln(z(x)) + ∇ ln z(x) T (x -x) e ≤ ln e∈E c e xe + e∈E c e x e e∈E c e xe -1 is valid for the set of optimal solutions of (11). For convenience define, for x, x ∈ Π and 0 ≤ t ≤ ln e∈E c e , g(x, x, u) ≡ u -e∈E c e x e e∈E c e xe -ln e∈E c e xe + 1 ≤ 0. (14) Now consider a linearized subproblem given a set of inequalities (14) corresponding to a (finite) set of solutions Π 0 ⊂ Π ∪ {1}, also known as the relaxed master problem in the literature on decomposition algorithms. max

Figure 5 :

 5 Figure 5: Non-correlated probabilities: A comparison of solution times for the case where probabilities are independent of profits.

Figure 6 Figure 6 :

 66 Figure6reports the average solution times for the same algorithms, with the exception of Bonmin, on the second group of instances. These show that Proposition 5 now provides a worthwhile time reduction, especially when α ≥ 20. This is in-line with the bounds reported in Figure7, where we report the averages ratios C i /C * for i ∈ {1, 2} where C 1 is the upper

7. 3 Figure 7 :Figure 8 :Figure 9 :

 3789 Figure 7: Correlated probabilities: A comparison of bounds on C * for the case where probabilities are set to be inversely related to the profits.

Figure 10 :

 10 Figure 10: Non-correlated probabilities: A comparison of bounds on C * using the deterministic graphs from Figure 8.

Table 1 :

 1 Project subcontracting instances based on the IT-project criticalpath data of[START_REF] Batselier | Construction and evaluation framework for a real-life project database[END_REF]. The network was generated based on that project's original 22-arc critical path. Running times in seconds are indicated for solving the instances using the MINLP Algorithm 3.

	s	|V |	α Time	P *	z * Sub #
	5	133 0.6	0.0 0.49 1205.31	3
	10	243 0.6	0.0 0.45 1324.04	2
	20	463 0.6	2.0 0.45 1320.96	2
	50 1123 0.6	18.0 0.45 1323.76	2
	5	133 0.4	0.0 0.49 1454.29	3
	10	243 0.4	0.0 0.46 1638.98	3
	20	463 0.4	2.0 0.46 1591.61	3
	50 1123 0.4	27.0 0.45 1657.44	3
	s	|V |	α Time	P *	z * Sub #
	5	133	0.2	0.0 0.53 2134.87	5
	10	243	0.2	0.0 0.51 2285.07	5
	20	463	0.2	2.0 0.51 2279.60	5
	50 1123	0.2	32.0 0.50 2306.15	5
	5	133	0.1	2.0 0.62 2875.47	6
	10	243	0.1	1.0 0.61 2938.63	6
	20	463	0.1	2.0 0.61 2943.30	6
	50 1123	0.1	31.0 0.60 2995.01	6
	5	133 0.05	0.0 0.68 3161.81	8
	10	243 0.05	1.0 0.67 3361.73	8
	20	463 0.05	2.0 0.67 3320.29	8
	50 1123 0.05	22.0 0.67 3525.86	8

Table 2 :

 2 Project subcontracting instances based on the Tappan-Zee Bridge critical-path data of[START_REF] Batselier | Construction and evaluation framework for a real-life project database[END_REF]. The network was generated based on the 9-arc critical path of that project. Running times in seconds are indicated for solving the instances using the MINLP Algorithm 3.

	s	|V |	α Time	P *	z * Sub #
	5	55 0.6	0.0 0.57 3.40E8	2
	10	100 0.6	0.0 0.52 3.63E8	2
	20	190 0.6	0.0 0.53 3.59E8	2
	50	460 0.6	2.0 0.51 3.70E8	2
	100 910 0.6	9.0 0.51 3.71E8	2
	5	55 0.4	0.0 0.66 4.24E8	2
	10	100 0.4	0.0 0.63 4.49E8	2
	20	190 0.4	0.0 0.63 4.33E8	2
	50	460 0.4	2.0 0.62 4.51E8	2
	100 910 0.4	9.0 0.62 4.51E8	2
	s	|V |	α Time	P *	z * Sub #
	5	55	0.2	0.0 0.72 5.14E8	3
	10	100	0.2	0.0 0.70 5.51E8	3
	20	190	0.2	0.0 0.70 5.69E8	3
	50	460	0.2	2.0 0.69 5.60E8	3
	100 910	0.2	12.0 0.68 5.73E8	3
	5	55	0.1	0.0 0.72 6.56E8	6
	10	100	0.1	0.0 0.71 6.62E8	6
	20	190	0.1	0.0 0.69 6.81E8	6
	50	460	0.1	2.0 0.69 6.81E8	6
	100 910	0.1	10.0 0.69 6.89E8	6
	5	55 0.05	0.0 0.82 7.12E8	6
	10	100 0.05	0.0 0.81 7.07E8	6
	20	190 0.05	0.0 0.80 7.71E8	6
	50	460 0.05	2.0 0.80 7.88E8	6
	100 910 0.05	10.0 0.80 8.00E8	6
				27

Real Project Critical Path Experiments

In this subsection we perform experiments using the critical paths of real projects appearing in [START_REF] Batselier | Construction and evaluation framework for a real-life project database[END_REF]. In particular, for each project, an activity-on-arc network is created in order to determine the critical path given the planned activity durations. Then, for each arc a on the critical path, an arc a 0 is created in the subcontracting chain graph with c a 0 = 0 and p a 0 = p max = 0.99. In addition, s ∈ {5, 10, 20, 50, 100} "parallel arcs" are created, with c a 1 , . . . , c as , each joined with a dummy vertex and additional arc with cost 0 and probability 1, which correspond to the alternatives to subcontracting activity a (similar to the multigraph in Figure 2 but converted into an equivalent graph). For i = 1, . . . , s, c a i is assigned r/2 of the total budgeted cost of activity a i , where r is generated uniformly at random from [0, 1]. Then, for a given α > 0, the success probability of subcontract arc a i is set to p a i = p max e -αr .

Based on the results with random probabilities in Section 7.2, it is evident that the MINLP algorithm outperforms the DP method for all but negligible values of the cost parameter. In the current experiments, we ran MINLP algorithm 3. The results are shown in Tables 1 and2. For each experiment with different values of the parameters s (accordingly |V |) and α, the results of the running time, the optimal solution probability and the objective (expected) value are indicated. The number of subcontracted activities is also reported. The results confirm the running time efficiency of the MINLP algorithm in practice for actual project network instances. It can be observed overall that the number of activities that are subcontracted, as well as the probability P * and the objective value of the optimal solution, increase as α decreases. Further, as would be expected, for a given value of α, as s (the number of subcontracting alternatives) increases, the optimal objective value also tends to increase. Perhaps less intuitive is the finding that P * tends to decrease rather than increase under the same circumstances.

Therefore, it appears that a greater variety of subcontracting alternatives results in somewhat riskier optimal solutions with higher returns to justify the increased risk.


Dave Hewitt
email: d.p.hewitt@lboro.ac.uk

"Never carry out any arithmetic": the importance of structure in developing algebraic thinking

Keywords: Early algebra, pattern spotting, algebraic thinking, structure

The use of tasks which ask learners to find general rules for growing figural patterns is widely reported in the algebra research literature. Such tasks are sometimes seen as a way to develop early algebra thinking. This paper looks at examples of such activities from the literature and presents a theoretical argument against the common practice of learners creating a table of values and seeking patterns within the numbers. Instead an argument is made for learners to focus on more complex examples where learners are discouraged from counting and turning the original figures into numbers. Instead, it is suggested that learners seek structure within complex examples and express what they see without carrying out any arithmetic but instead just writing down what arithmetic they would do.

Introduction

The difference between arithmetic and algebra has been discussed at some length in the literature. For example, [START_REF] Filloy | Solving equations, the transition from arithmetic to algebra[END_REF] talked about a didactic cut existing when a letter appears on both sides of an equation. This is, of course, an attribute of the equation rather than a statement about ways of thinking which might differentiate between arithmetic and algebraic thinking. [START_REF] Herscovics | A cognitive gap between arithmetic and algebra[END_REF] spoke about the need for learners to work with the unknown for something to be considered as algebraic activity. This places a greater emphasis on the learner rather than the object, such as the form of an equation, with which they are working. With the emphasis on a learner, Radford (2010a) talked of a zone of emergence of algebraic thinking where expressions of generalisation can be expressed in a variety of forms such as gesturing and actions as well as writing. For Radford, there was not a need for letters to be present for algebraic thinking to be emerging. [START_REF] Kieran | Algebraic thinking in the early grades: what is it?[END_REF] allowed the possibility of thinking algebraically about something even if that something is not explicitly on the list of algebra content within the curriculum. This allows for algebraic thinking to happen in many different areas of the curriculum, one of which is number. In this paper I argue for the case to place structure at the forefront of developing the algebraic thinking of learners. Several researchers have included structure as a key aspect of algebra work, including [START_REF] Kieran | Algebraic thinking in the early grades: what is it?[END_REF]. [START_REF] Usiskin | Conceptions of school algebra and uses of variables[END_REF] included the study of structures within his four conceptions of algebra; [START_REF] Kaput | A research base supporting long term algebra reform[END_REF] did the same within his five aspects of algebra; and NCTM's (1998) discussion document included structure within four organizing themes for school algebra. Yet, I will argue that a number of reported teaching practices do not assist learners in placing their attention on structure; indeed often practices do the opposite and turn attention away from structure and onto what I would consider to be more arithmetic thinking. [START_REF] Radford | Signs and meanings in students' emergent algebraic thinking: a semiotic analysis[END_REF] posited that algebraic thinking differed from arithmetic thinking in the form of the mathematical practice in which learners were engaged. For him it was about the focus being on, for example, investigating and expressing the general term of a pattern. At one level, arithmetic is involved in generality in that 3+4=7 is an expression of generality: it does not matter what we are talking about, 3 things plus 4 more of the same things result in 7 of those things. This is true no matter what those things are. However, algebra, as generalised arithmetic, requires a second level of generalisation. It stresses the structure of the given situation rather than a 'result'. Thus, 3+4=4+3 can be judged to be correct through arithmetic thinking, by carrying out calculations and stressing the similarity of the results from both sides of the equation (both sides result in 7). Algebraic thinking will stress the structure inherent within the operation of addition, that of commutativity; the two sides are the same because it does not matter which way round you do addition. Thus algebraic thinking stresses operations as objects of attention and structure whereas arithmetic thinking stresses processes and with the results being the object of attention. [START_REF] Linchevski | Structure sense: The relationship between algebraic and numerical contexts[END_REF] introduced the notion of structure sense and since then other authors have developed the notion further (e.g., [START_REF] Hoch | Structure sense in high school algebra: the effect of brackets[END_REF][START_REF] Mulligan | Awareness of pattern and structure in early mathematical development[END_REF]. In particular, they have in common the idea of pattern, connections and relationships. [START_REF] Mulligan | Awareness of pattern and structure in early mathematical development[END_REF] offered an example of seeing a 3 by 5 rectangle as three rows of five columns or as five columns of three rows. Each of these views placed a structured way of seeing the object rather than seeing it just as a whole. My own definition of algebraic structure which will be used in this paper is:

A way of viewing an object or expression such that it is seen as a combination of recognizable parts along with recognizable patterns which connect those parts together. Such a way of viewing results in an expression of the object in terms of the parts and connections which places the object as a particular example of a more general type.

The use of figural patterns (either based upon quasi-real life situations, such as the number of chairs around a line of tables, or purely geometrical, such as the length of the perimeter of a line of regular hexagons joined together) is widely reported in the literature (e.g., [START_REF] Montenegro | Transformations in the visual representation of a figural pattern[END_REF][START_REF] Blanton | The development of children's algebraic thinking: The impact of a comprehensive early algebra intervention in third grade[END_REF]. I will analyse some examples of such tasks and consider ways in which the students have worked towards trying to find a functional rule for a given initial figural growth pattern. I will argue that taking students' attention away from the original figural situation and onto numbers generated from those patterns reduces the likelihood of students finding functional rules. A key to generalising is to keep attention with the figurative context and to focus on noticing structure. Carrying out arithmetic hides any inherent structure which had been noticed and thus reduces still further the opportunity to express generality. I start off by looking at the common practice of looking at the first few cases of a figural grown pattern and creating a table of values.

Tables of values

Asking learners to create a table of values for the first few cases is a common strategy which is either suggested by teachers or included in the task instructions. Transferring learners' attention from the original problem situation to a table of values means that they can lose contact with three important elements to assist with generality. Firstly the structural properties inherent within the original situation can be lost as learners stare only at numbers. Secondly, the nature of a classic table of values is that it is structured to be in term order from 1 onwards. This brings a natural temporal aspect where recursive rules are more likely to be articulated. Thirdly, if a functional rule is found for the numbers, there can never be certainty by looking at the table of values that the rule will apply to the original situation. I will now consider each of these three elements in turn.

Losing connection with the context

In Blandon et al.'s (2015b) study, one task involved finding the number of people sitting round a certain number of square tables which were joined in a line. Drawings of the first two cases were given and then the learners were asked to record their results in a table of values.

They were asked to find patterns in the table. One 1 st grade learner noticed a pattern in their table of values (Figure 3) where the numbers were the same along diagonals. Whilst this is, indeed, a pattern in the table, Blanton, Brizuela, Gardiner, Sawrey, and Newman-Owens (2015a) report that this could have been any symbol set where the symbols were the same along a diagonal and was not an observation which necessarily related to a sense of number let alone the contextual situation. Indeed, the creation of a table of values takes away the context within which those numbers were generated.

I observed a group of lower attaining 12-13 year olds spending half an hour building examples of the first few cases of a ring of tiles surrounding a 1 by n rectangle. The task was to find a general rule for how many tiles would be needed to surround such a rectangle. They began by making the first few cases with multi-link cubes and constructed a table of values for these first few cases. They then spent a long time looking at the numbers in the table and not getting further than noticing the recursive rule of the numbers going up in twos. They did not turn their attention back to the multi-link cubes but instead kept staring at the numbers in the table of values. I will say more about how this activity was concluded in a later section. The point here is that they no longer paid attention to the original situation.

These examples are in contrast to when learners' attention remains with the original context and where a structured way of viewing that context can lead to finding a functional rule, as can be seen from the following example. For example, [START_REF] Ferrara | Agency and assemblage in pattern generalisation: a materialist approach to learning[END_REF] discussed a group of 10-11 year olds working on finding the number of circles in further terms of the sequence shown in Figure 1. They were also asked to explain to someone from another class how to find the number of circles in any term in this sequence. An example of work from a group of three students showed how they justified their rule by seeing the figural patterns in a structured way. For example, Figure 2 shows a link between the notational expression and the pictorial situation for the 6 th term. They also showed an alternative way of structuring the geometric figure when one of them explained that "The figure is made of two rows: First row, second row, which, the second row is equal to the first row, plus 1" (p. 28). The written explanation for the 6 th term (Figure 2) and the more verbal articulation in terms of the two rows, reveal two ways of imposing a structured way of viewing the geometric figure rather than seeing it as a single collection of circles. Both of these ways of viewing reveal a sense of generality where I feel confident they would be able to calculate the number of circles for any term in this sequence.

The seduction towards finding recursive rules

The second concern I have about tables of values is that their usual sequential nature can seduce students into noticing recursive rules rather than functional rules. Recursive rules give a way in which the next term can be generated from the previous term. This can involve the carrying out of a long series of arithmetic operations if a 'far' term in a sequence is to be found. Learners can also find it difficult to make use of a recursive rule in order to generate a functional rule; recall, for example, the case of the learners trying to find a rule for a ring of tiles surrounding a 1 by n rectangle. They had a recursive rule but this did not help them towards finding a functional rule. [START_REF] Montenegro | Transformations in the visual representation of a figural pattern[END_REF] described a class of 18 Portuguese students aged between 10 and 13 working on a sequence of growing geometric figures in the shape of an 'L'. Two of the four groups were not able to find a functional rule even though they had found a recursive rule. All groups had turned their attention to working with numbers from the first six cases as this had been encouraged from the questioning of the task. The teacher decided that the students had missed the potential within the visual representation of the 'L' shapes and focused their attention on the shapes; asking students to say what was the same and what was different about the figurative representations. This led to students making comments such as "Figure 15 has one common square and 15 on each side" and "figure n will have a common square and n squares on each side". This led to an exclamation of "Ahhhhh!" (p. 102) and the students were able to quickly find the functional rule. The focus being turned from trying to find patterns in numbers to looking for structure within the original geometric context was significant in the success obtained by those students.

The sequential nature of a table of values encourages learners to see a recursive rule, which is often 'easier' than a functional rule as it is usually additive rather than multiplicative, linear rather than quadratic, etc. It also does not always help with finding a functional rule.

Is the rule correct?

The third concern I have about tables of values is that even if a functional rule is found for the data in the table, students can never know from the table alone if that rule is correct for the original contextual situation. For example, without me telling you, you would not know the context which the table in Figure 4 represented. The contextual situation has disappeared and the activity becomes one of pure number pattern spotting. There is a danger that this can lead to little awareness of the mathematical situation from which those numbers originated [START_REF] Hewitt | Train spotters' paradise[END_REF]. Some patterns spotted may not actually apply to the general situation from which the numbers originated. The table in Figure 4 gives a strong sense of the rule 2 n-1 , however if the numbers came from the first five cases of looking at the maximum number of regions formed within a circle when n points on the circumference are joined to each other by chords, then this rule would not be correct. The case for six points produces a maximum number of 31 regions and not the 32 which might be expected from looking only at the table of values. Justification or proof is never possible when attention is solely with a table of values. [START_REF] Palatnik | Four-component decomposition of sense making in algebra[END_REF] reported a pair of 9 th grade students who obtained formulae connected with the problem of finding the maximum number of pieces a pizza can be cut into with n straight 'cut' lines. The students had a sense that their formulae were correct as they fitted with the numbers in the table of values. However, when challenged to work on why the formulae worked, the students had to return to the context of the problem to articulate reasons for why they were correct. So, the common practice of encouraging learners to construct a table of values (e.g., Blanton et al., 2015a;[START_REF] Blanton | The development of children's algebraic thinking: The impact of a comprehensive early algebra intervention in third grade[END_REF] restricts any pattern spotting to the level of conjecture at best. Any sense of certainty of generality requires attention to be on the structure of the original problem situation, not a table of numbers. Never carry out any arithmetic I will now return to the story of the lower attaining students who were trying to find a functional rule for the number of tiles surrounding a 1 by n rectangle. They spent a long time looking at their table of values without getting anywhere towards finding a functional rule. After a long while observing them, I asked them how many tiles there would be in a situation where the rectangle was 47 long. They replied quickly that it would be two lots of 47 plus 3 for each end. Within one minute they had expressed the rule of 2n+3+3. The articulation of 2x47+3+3 rather than the single number of 100, which would be the result of carrying out the arithmetic of that expression, meant that the structured way in which they viewed the tiles was contained within that expression. The stressing of the structure allowed them to see the generality that, however long the rectangle was, they needed two lots of that length plus another two sets of three tiles. A significant aspect of this anecdote is that the rectangle was long enough so that they would not attempt to build this and count the number of tiles. As Radford (2010b) noted, it is important to work with a case where the numbers involved are too big for a learner to carry out arithmetic or to count. This forces the need to seek structure. Indeed I go further and say that in order to head towards algebra in such situations, all arithmetic should be avoided. [START_REF] Chimoni | Examining early algebraic thinking: insights from empirical data[END_REF] give an indicative answer from a group of 10-13 year olds who were successful in solving all the tasks given to them. In this case they were asked to find how many children could be seated around a group of 10 trapezoidal tables (see Figure 5 for the first two cases). The answer was presented similar to N 10 = 5+(9x3) = 32. The number 32 may be seen as the answer to the question but it is the expression 5+(9x3) which reveals the structural way of seeing the situation. It is this expression, not the 32, which offers the insight to go on to express a general rule of 5+((n-1)x3), which may be written in the conventional form of 5+3(n-1). I argue that in order to head towards general algebraic statements learners should never do any arithmetic, just write down the arithmetic they would do. This is another reason why a table of values is often not as helpful as it might initially be considered to be; arithmetic is carried out in order to enter each value into the table. This means that any structural insights obtained are lost. [START_REF] Ferrara | An early algebra approach to pattern generalisation: Actualising the virtual through words, gestures and toilet paper[END_REF] describe a teacher who worked with a class of grade 3 learners to see if they could work out the position number of 26 in the sequence 2, 4, 6,… The teacher stressed that this was not to be done by counting. After a while several children were clear that doubling was involved. The teacher asked what number would be in position 99. One learner answered "Hum, I don't know the double of 99" (p. 13). For algebra, I argue that you do not need to know the double of 99, you just need to express the arithmetic you would do (i.e. 2 x 99). This then leads towards an articulation of 2xn, or 2n. In some ways a learner might struggle to carry out some arithmetic whilst just writing down what arithmetic they would do can feel easier. In that sense expressing an algebraic structure in written form can feel easier than having to carry out any arithmetic involved.

Summary and implications

The research literature has shown a frequent practice of presenting learners with figural diagrams and encouraging them to construct a table of values for the first few terms. This results in learners' attention being focused on to numbers rather than the context from which those numbers arose. The activity for learners then becomes number pattern spotting and there are examples of students finding patterns in the numbers which can be detached from the contextual situation. The nature of a table of values is such that recursive rules are likely to be found and students do not always find it easy to translate such rules into a general functional rule. The argument I have made is that it may be preferable to stay with the contextual situation and encourage learners to find 'structural ways of seeing'. This is supported by [START_REF] Strømskag | A pattern-based approach to elementary algebra[END_REF], who identified staying with the context as important for a successful pattern-based approach to algebra. Indeed, learners who stayed focused on the original figures were more likely to take a functional approach (El Mouhayar & Jurdak, 2016) and find several important connected features [START_REF] El Mouhayar | Trends of progression of student level of reasoning and generalization in numerical and figural reasoning approaches in pattern generalization[END_REF], whereas those who focused on numbers were more likely to take a recursive approach and noticed features which were disconnected with each other.

The principle of never carrying out any arithmetic but just writing down what arithmetic you would do can allow the structured way of seeing to be expressed within a written expression. Such expressions, and their associated ways of seeing, are a step towards seeing generality through a particular example [START_REF] Mason | What do symbols represent?[END_REF]. To aid this process of not carrying out any arithmetic and stressing structure instead, it is worth teachers considering offering just one example for learners to work on. This example should be one which is sufficiently complex so that learners are not able to count and are unlikely to be able to do any necessary arithmetic [START_REF] Radford | Signs and meanings in students' emergent algebraic thinking: a semiotic analysis[END_REF]. This will increase the likelihood of learners expressing the structure they observe and writing it in a form which preserves that structure. Since a large number will be involved, this acts as a quasi-variable [START_REF] Fujii | Fostering an understanding of algebraic generalisation through numerical expressions: the role of quasi-variables[END_REF] in which the number acts as if it were a variable as learners have a sense that this could be any other number and the expression would still be true.

Figure 1 :

 1 Figure 1: A figural pattern of dots

Figure 2 :

 2 Figure 2: Re-drawn version of a learner's response from Ferrara & Ferrari (2017, p. 28)

Figure 4 :

 4 Figure 3: Numbers on a diagonal are the same

Figure 5 :

 5 Figure 5: Chairs round tables


Iveta Kohanová
email: iveta.kohanova@ntnu.no

Trygve Solstad
email: trygve.solstad@ntnu.no

Linear figural patterns as a teaching tool for preservice elementary teachersthe role of symbolic expressions

Keywords: generalization, prospective elementary teachers, algebraic thinking, figural patterns

Figural patterns connect several aspects of mathematical activity central to the work of teaching mathematics. In this pilot study, we investigated the solutions of 16 preservice elementary teachers to linear figural patterns of different levels of complexity after the completion of a series of six teaching sessions of a course in mathematics education. We found that a) most students were able to generalize and find the figural number of an arbitrary figure in the sequence; b) about half of the students produced mathematically imprecise formulas when translating from an arbitrary number into a general algebraic expression; c) the formulas students produced frequently lacked structural correspondence with the figural patterns and d) students had difficulties in interpreting figural patterns that are more complex. These results indicate that although the course successfully trains students to generalize with linear figural patterns, more attention to precisely formulating mathematical ideas and to interpretation of more difficult patterns can further improve the training of preservice elementary teachers.

Introduction

Research on students' algebraic thinking has drawn considerable interest over the past decades. For [START_REF] Blanton | Functional Thinking as a Route Into Algebra in the Elementary Grades[END_REF], experiences in building, expressing and justifying mathematical generalizations constitute the heart of algebra and algebraic thinking. [START_REF] Mason | Thinking Mathematically[END_REF] highlight the importance of the generalization process in mathematics when stating that "generalizations are the life-blood of mathematics. Whereas specific results may in themselves be useful, the characteristically mathematical result is the general one" (p.8). The placement of algebraic content within the mathematics curriculum has received considerable attention. For example, documents from the National Council of Teachers of Mathematics (2000) in the United States, the Department for Education (2014) in England and The Norwegian Directorate for Education and Training (2013) recommend the development of algebraic ideas at elementary and middle school levels through activities such as generalizing number and figural patterns. Several authors have researched algebraic generalizations, but in most cases the target group were pupils in primary or middle school (e.g. [START_REF] Carpenter | Thinking mathematically[END_REF][START_REF] Becker | Generalization strategies of beginning high school algebra students[END_REF][START_REF] Rivera | Algebraic reasoning through patterns[END_REF][START_REF] Rivera | Visual templates in pattern generalization activity[END_REF]. There is less research on generalization of pre-service elementary teachers (PSETs). A study by [START_REF] Yeúilderea | Algebraic generalization strategies of number patterns used by pre-service elementary mathematics teachers[END_REF] indicated that PSETs, when trying to find the general term of number patterns, described number pattern rules in relation to differences between terms and used visual models without a purpose. The study of [START_REF] Rivera | The Effects of Numerical and Figural Cues on the Induction Processes of Preservice Elementary Teachers[END_REF] suggests that PSETs who used figural reasoning acquired a better understanding of the generalizations they constructed than PSETs who reasoned numerically, even if relationships among numerical values had greater contribution to similarity between the compared entities than the figural patterns. [START_REF] Måsøval | Factors constraining students' establishment of algebraic generality in shape patterns: A case study of didactical situations in mathematics at a university college[END_REF] studied the factors that constrain PSETs' establishment and justification of formulae and mathematical statements that represent generality in different quadratic shape patterns. Her findings indicate three such constraints: The first constraint is related to a limited feedback potential in situations where the students are supposed to solve the mathematical tasks without teacher intervention. The second constraint is related to obstacles the students face when they transform informal mathematical statements expressed in natural language into formal algebraic notation. The third constraint is related to challenges with justification of formulae and mathematical statements that the students have proposed. [START_REF] Hallagan | Elementary school pre-service teachers' understanding of algebraic generalizations[END_REF] found that after a problem solving-based teaching intervention, PSETs improved in their ability to generalize, however, they encountered more difficulty with determining the algebraic generalization for items arranged in squares with additional single items as exemplified by x 2 +1, than with multiple sets of items, as exemplified by 4x. [START_REF] Callejo | Prospective primary teachers' noticing of students' understanding of pattern generalization[END_REF] characterised profiles of the teaching competence "noticing students' mathematical thinking" in the context of pattern generalization. PSETs named various mathematical elements to describe the students' answers but did not always use them to interpret the understanding of pattern generalization of each student. Their findings allow one to generate descriptors of the development of this teaching competence and provide information for the design of interventions in teacher education addressed to support the recognition of evidence of students' mathematical understanding.

To meet the goals of teaching in the elementary school curriculum, we need to understand more about how to better prepare PSETs for this undertaking. As part of a formative evaluation of the mathematics education course design, we set out to identify aspects within the course module about generalization that require increased attention and emphasis. Specifically, we asked: Which are the most common challenges that PSETs still face when solving problems with generalizations of linear figural patterns after completing our six-session course module about algebraic generalization?

Theoretical framework

According to [START_REF] Radford | Some reflections on teaching algebra through generalization[END_REF], the goal of generalizing spatial or numerical patterns is to find an expression representing the conclusion derived from the observed facts (concrete numbers). Radford claims that the obtained expression is in fact a formula, which is constructed on the basis, not of the concrete numbers in the sequence, but on the idea of a general number. Radford asserts that "general number" appears as preconcepts to the concept of variable. Hence, he claims that the notion of letter as variable is consistent with a generalizing approach to algebra, aiming at establishment of relations between numbers. The point is constructing formulae where the symbols represent generalized numbers [START_REF] Radford | Some reflections on teaching algebra through generalization[END_REF]. He highlights that one of the most significant characteristics of generalization is its logical nature, which makes the conclusion possible. This means that the process of generalization is closely connected to that of justification and proof. The underlying logic of generalization can be of various types, depending on the student's mathematical thinking. [START_REF] Radford | Iconicity and construction: A semiotic investigation of forms of algebraic generalizations of patterns in different contexts[END_REF] distinguish between arithmetic and algebraic generalization of the pattern. While in both domains some generalizations do certainly occur, in algebra, a generalization will lead to results that cannot be reached within the arithmetic domain. Algebraic pattern generalization involves the students in (1) grasping a commonality, (2) generalizing this commonality to all the terms of the sequence, and (3) providing a rule that allows them to directly determine any term of the sequence (Figure 1; [START_REF] Radford | Iconicity and construction: A semiotic investigation of forms of algebraic generalizations of patterns in different contexts[END_REF].

Methodological approach

After a six-session module on algebraic generalization as part of a course in mathematics education, 16 PSETs completed a digital survey with six tasks about generalization of figural patterns. Before data collection, the background of the study and research questions were presented to the PSETs. Participation was voluntary and anonymous. Answers were in the form of multimodal digital texts including text and freehand drawings. Subsequent to data collection, PSETs' responses were downloaded from the server and sorted according to task. A content analysis was performed independently by both authors in order to identify categories of common challenges in the PSETs' algebraic pattern generalization process.

Course content

The Mathematics 2 course is an optional course which integrates mathematics and didactics. The content of the course previous to data collection was: Rich mathematics conversations, Argumentation and proof, Representations, Algebraic thinking, Generalization, Figural numbers, Equality, Relational thinking, Models for negative numbers, Realistic Mathematics Education, Fractionsmultiplication and division, Decimal numbers, Percent, Difficulties in Mathematics.

A module with six sessions of 180 minutes was devoted to these topics: algebraic thinking, generalization, figural numbers, equality and relational thinking. These six sessions were taught in English and gave the PSETs the opportunity to discuss several tasks about generalization (not only with figural patterns), their different solutions, and challenges for pupils. PSETs also discussed several research papers on generalization, equality and relational thinking (e.g. [START_REF] Carpenter | Thinking mathematically[END_REF][START_REF] Kaput | Algebrafying the elementary mathematics experience in a teachercentered, systemic way[END_REF][START_REF] Becker | Establishing and Justifying Algebraic Generalization at the Sixth Grade Level[END_REF][START_REF] Mason | Expressing Generality and Roots of Algebra[END_REF] under the guidance of the course instructor.

Prior to the Mathematics 2 course, in 2016, the PSETs had completed a two-semester compulsory Mathematics 1 course whose main content was: Numbers and the number line; Counting; The position system; Addition and subtraction; Multiplication and division; Fractionsmodels, comparison, estimation, addition, subtraction; Probability and statistics in primary school.

Survey

The survey consisted of six tasks; for the purpose of this paper we focus only on three of them (Figures 2,3,4). at Department of Teacher Education, NTNU in Trondheim, Norway. The whole group consisted of 67 students, but only 20 were present in the last session. For technical reasons we only received answers from 16 students. In the third teaching session, PSETs were given a figural pattern task to solve on their own. Most PSETs did not complete an answer to the first question about near generalization, and all of them gave up answering any of the following questions. All PSETs who answered the survey were present at almost all teaching sessions and the majority of them was participating quite actively during the course. Hence, the subjects in this study were likely among the most highly motivated students in the class.

Findings Pattern generalization

The majority of students gave satisfactory answers to most of the figural pattern questions, requiring both finding the first few figural numbers (near generalization), as well as generalizing to figure number 50 or 100 (far generalization). This requires successful abductive-inductive action and shows that the PSETs in the study had learned to generalize the figural patterns. This is indeed an encouraging result considering that none of the PSETs could solve figural pattern tasks at the beginning of the course. At the same time, it is likely that the sixteen PSETs who participated in the survey were also among the highest attaining students in the class.

Imprecise symbolic action

For items involving the construction of formulas, typically around half of the subjects formed symbolic expressions containing mathematical imprecisions, indicating a potential for improvement in symbolic action.

Answers from task 1 illustrate this point well. While in task 1 (Figure 2) 75 % of PSETs provided valid generalizations to pattern number 100, only 50 % of PSETs wrote accurate algebraic formulas. Answers from the subjects who did not provide mathematically precise formulas fell into two categories: a) inaccurate use of variables, and b) improper use of the equal sign.

Although the problem text specified that the letter n denotes the figure number, 4 PSETs chose to use the letter x for their formula without defining what x denotes. As for subject 3:

S3:

General formula: N=3*x+1; Because we always want to start with 3 since this is the "bush" [that makes up the base of the continuing pattern], then we have to multiply this "bush" with x since we do not know which day we want to find. Finally we must add 1 since all these shapes have only one "stem".

The notation F(n) could be used to denote the figural number while the letter x was used instead of n to denote the figure number. Subject 11: S11: 100* 3 + 1 Corresponding formula: fn= x*3 +1

These inaccuracies indicate an inflexibility in the students' appropriation of variables, which might be rooted in an experience with solving equations where x stands for the unknown.

In some answers, PSETs gave the same variable name to the figural number and the figure number, as for subjects 5 and 10 below: S5: General formula: N = (Nx3)+1; This expression is correct because figure number N will have N number of triangles. These triangles have to be multiplied by 3, since each triangle consists of three sticks. Then one has to add 1, which corresponds to the stick at the bottom.

S10:

General formula: n = n x 3 + 1; Because in each triangle one needs 3 matches, so to make 4 triangles one needs 4x3 (12) matches, and to make 100 triangles one needs 100x3 (300) matches. Therefore n x 3. In the end one needs to add the one match which stands, and then it finally becomes +1.

These responses indicate a lack of attention to equality and the meaning of the equal sign. It appeared not only in solutions of task 1, but also in task 4, as shown in the example below for subject 15 (task 4c, Figure 4).

S15

Here he divides into parts where he circles the same dot twice. n = n + ((n + 1) x 4) -2. Have to subtract 2 since this is counted twice.

Lack of structural correspondence with figural pattern

Finally, both for correct and incorrect answers, the structure of the formulas given by the PSETs often did not correspond to the figural pattern.

For instance, subjects 5 and 13 responded with the same formula for all three different decompositions of the figure in task 4 (Figure 4):

S13: N = n+2+(nx4); n+2 is the body; nx4 is the arms Decomposition c) in task 4 contained overlapping regions that were to be subtracted. Still, subject 7 provided the formula in reduced form, reinterpreting the figure from the second decomposition of the same figure: S7: n*5+2; n is the figural number, 5 is the number that it increases by for each figure, + 2 are the circles that are overlapping encircled, that are constant While all students wrote some formula for decompositions in task 4a) and 4b), in task 4c) six students wrote "I don't know". We could see a similar phenomenon in task 2 (Figure 3). While all students gave adequate answers to tasks 2a) and 2b), five students answered task 2c with "I don't know". Slightly more difficult structures of figural patterns (overlapping regions or the two colors, which add a layer of complexity) seem to be challenging for PSETs.

Discussion and conclusion

In this paper we investigated sixteen preservice elementary teachers' solutions to linear figural pattern generalization tasks. The analysis of these solutions showed that although PSETs typically recognized the underlying structure of linear figural patterns, their algebraic notation and syntax of algebra was often imprecise. This observation corresponds to the second constraining factor identified in [START_REF] Måsøval | Factors constraining students' establishment of algebraic generality in shape patterns: A case study of didactical situations in mathematics at a university college[END_REF], related to formalizing mathematical ideas expressed in natural language. Most of the formulas that PSETs provided were meaningful, i.e. the formulas conveyed the underlying structure in the figural patterns. However, several solutions were characterized by imprecise mathematical language. Variable names commonly were not defined or not used consistently, and indicated a lack of attention to equality and to what a variable represented. The fact that it wasn't an interview, where PSETs were not asked for further and detailed explanations of their answers, might support the assumption that this is how their notation and argumentation will look like in the classroom.

A meaningful pattern generalization must be accompanied by a symbolic action [START_REF] Rivera | Visual templates in pattern generalization activity[END_REF]. In the study of [START_REF] Hill | Mathematical Knowledge for Teaching and the Mathematical Quality of Instruction: An Exploratory Study[END_REF], mathematical errors, including errors in language (conventional notation, technical language, general language for expressing mathematical ideas), proved the most strongly related to teacher knowledge. In further research we will investigate whether increased attention to equivalence, symbolic notation, dependent and independent variables, variable names and the accuracy of the mathematical language during teaching sessions on generalization might benefit the development of PSETs' teacher knowledge and better prepare PSETs for teaching generalization in real classrooms. The recent decision to incorporate programming into the Norwegian mathematics curriculum is also an invitation to investigate the role of programming in developing the concept of variables and symbolic action in pattern generalization.

Figure 1 :

 1 Figure 1: Radford's (2008) architecture of algebraic pattern generalizations[START_REF] Rivera | Algebraic reasoning through patterns[END_REF] extended Radford's definition by including the necessity of justification at the middle school level. "Students have to provide some kind of explanation that their algebraic generalization is valid by a visual demonstration that provides insights into why they think their generalization is true." (p.213-214) Rivera (2010) claims that meaningful pattern generalization involves the coordination of two interdependent actions, as follows: (1) abductive-inductive action on objects, which involves employing different ways of counting and structuring discrete objects or parts in a pattern in an algebraically useful manner; and (2) symbolic action, which involves translating (1) in the form of an algebraic generalization.

Figure

  Figure 2: Task 1