DISTRIBUTION OF TYPICAL STRUCTURES OF A COMPUTING DEVICE ACROSS BLOCKS OF A UNIFIED SET

V. K. POGREBNOY

(Presented by the scientific and technical seminar of the Department of Automated Control Systems and the Control Laboratory)

The need to solve the problem of distributing typical structures among the blocks of a unified set arises in its practical use in the course of designing computing devices [1]. The result of solving the problem of covering the circuit of a computing device with blocks of a unified set is the vector \(X^*=\{x_1^*, x_2^*, \ldots, x_j^*, \ldots, x_{n'}^*\}\), whose nonzero components \(x_j^*\), \(j=1, 2, \ldots, n'\); \(n' < n\), indicate the number of blocks of the \(j\)-th kind required to implement the circuit under consideration. The number of typical structures (TS) of the given circuit is determined by the vector \(B=\{b_1, b_2, \ldots, b_r, b\}\), where \(\omega\) is the number of types of TS in the unified set, \(b_r\) \((r=1, 2, \ldots, \omega)\) is the number of TS of the \(r\)-th type contained in the circuit under consideration. The aggregate of TS contained in the blocks \(\{x_1^*, x_2^*, \ldots, x_{n'}^*\}\), by type and number, as a rule exceeds the set of TS of the circuit or coincides with it. Therefore, solving the problem of distributing the set of TS of the circuit among the blocks \(\{x_1^*, x_2^*, \ldots, x_{n'}^*\}\) without any optimization consists in the simple establishment of a correspondence between specific TS of the circuit and blocks, that is, the distribution of all TS of the circuit among the blocks.

If one takes into account that the TS of the circuit are connected with one another, then the problem arises of distributing the TS among the blocks in such a way that the total number of connections between blocks is minimal. Minimization of the total number of interblock connections, which are usually made by wire mounting, substantially improves the technical and economic characteristics of the computing device being designed. This problem is similar to the problem of arranging modules into blocks according to the criterion of the minimum of interblock connections, with the only essential difference that an arbitrary aggregate of modules (in this case TS) satisfying the structural parameters of a block cannot be included in it if it does not coincide with the a priori specified “image” of the block. This very substantial distinction of the present problem does not allow it to be considered as the problem of cutting a graph into minimally connected subgraphs.

In the present paper a mathematical formulation and a method are proposed for solving the problem of distributing TS among blocks according to the criterion of the minimum of the total number of interblock connections. The initial data for solving the distribution problem are the set of blocks \(\{x_1^*, x_2^*,\)

..., \(x_n'\}\) and the set of TS of the circuit \(\{b_1, b_2, \ldots, b_\omega\}\). Information on the connections between the TS of the circuit is represented by the incidence matrix \(C=\|c_{kl}\|\), \(k=1, 2, \ldots, s\), \(l=1, 2, \ldots, s\). The elements of the matrix \(c_{kl}\) characterize the number of connections between the \(k\)-th and \(l\)-th TS of the circuit. The matrix \(C\) is symmetric, and the elements \(c_{ll}=0\), \(l=1, 2, \ldots, s\), where \(s\) is the number of TS in the circuit.

Let us introduce the following notation:

\(A_j^0\) is the set of types of TS contained in the \(j\)-th block once each;

\(A_j'\) is the set of types of TS contained in the \(j\)-th block more than once;

\(A_j=A_j^0 \cup A_j'\) is the set of types of TS contained in the \(j\)-th block.

Table 1

Let us form all possible variants of arranging the TS of the circuit into a block of the \(j\)-th type. We shall illustrate the process of forming variants by the example of distributing TS among blocks for a circuit whose list of TS is presented in Table 1, and whose nonzero elements of the incidence matrix are presented in Table 2.

Table 2

To implement this circuit, 4 different blocks are used, each of which contains the following sets of TS: \(A_1=\{18, 20; 5; 12\}\); \(A_2=\{20; 3; 8\}\); \(A_3=\{2; 18; 18\}\); \(A_4=\{3; 2; 13\}\).

It is convenient to represent the variants of arranging the TS of the circuit into the \(j\)-th block by a tree, each branch of which contains the set \(M_{ij}\) of vertices of the TS of the circuit that forms the \(i\)-th variant of arranging the given block. The variants of arranging the TS in each of the four blocks of the example under consideration are presented in Fig. 1.

All vertices of the tree of block variants are arranged in levels, each of which corresponds to the \(r\)-th type of TS. Thus, for the 3rd variant of the 1st block, the set of vertices (TS numbers) is \(M_{3,1}=\{6, 3, 1, 2\}\), which corresponds to the set of TS of the 1st block \(A_1=\{18, 20, 5, 12\}\). When forming variants, it is necessary to take into account only those types of TS of the blocks that occur in the circuit under consideration. Let us also note that the tree of variants is constructed for blocks of all types used in implementing the circuit. Moreover, for blocks of the \(j\)-th type with \(x_j^*>1\), one tree of variants is constructed. In the adopted notation, it is not difficult to calculate the number of variants \(m_j\) when constructing the tree for the \(j\)-th block. In the case where all TS in the \(j\)-th block are distinct, that is, \(A_j=A_j^0\), the number of variants can be determined by the formula

\[ m_j=\prod_{r\in A_j^0} b_r,\quad \text{when } d_{rj}=1,\ \text{for all } r\in A_j, \tag{1} \]

where \(d_{rj}\) is the number of TS of the \(r\)-th type in the \(j\)-th block.

In the example under consideration, such blocks include the 1st, 2nd, and 4th. Thus, for the 1st block
\(m_1=b_{18}\cdot b_{20}\cdot b_5\cdot b_{12}=3\cdot2\cdot1\cdot1=6\).
For blocks containing only identical TS, or groups of TS of several types, in each of which there is more than one TS, the following formula is valid:

\[ m_j=\prod_{r\in A_j'} C_{b_r}^{d_{rj}},\quad \text{when } d_{rj}>1,\ \text{for all } r\in A_j', \tag{2} \]

where \(C_{b_r}^{d_{rj}}\) is the number of combinations of \(b_r\) taken \(d_{rj}\) at a time.

Fig. 1. \(a\) — variants of the 1st block; \(b\) — variants of the 2nd block; \(c\) — variants of the 3rd block; \(d\) — variants of the 4th block

There are blocks for which \(A_j^0\ne\varnothing\) and \(A_j'\ne\varnothing\), \(A_j=A_j^0\cup A_j'\). In this case the number of variants \(m_j\) is determined by the formula

\[ m_j=\prod_{r\in A_j^0} b_r \prod_{r\in A_j'} C_{b_r}^{d_{rj}},\quad \text{when } A_j^0\ne\varnothing,\ A_j'\ne\varnothing . \tag{3} \]

Thus, for the 3rd block \(A_j^0=\{2\}\); \(A_j'=\{18\}\); \(d_{18,3}=2\); \(m_3=b_2\cdot C_{b_{18}}^{d_{18,3}}=\)

\[ =2\cdot C_3^2=6. \]

The total number of variants over all types of blocks is equal to

\[ \sum_{j=1}^{n} m_j. \tag{4} \]

To each \(i\)-th variant of the \(j\)-th block one may assign a value \(c_{ij}\), which characterizes the number of connections between TS

of the \(i\)-th variant with the set \(M_{ij}\). The quantity \(c_{ij}\) is determined from the connectivity matrix \(C=\|c_l\|_{s\times s}\) by the formula

\[ c_{ij}=\sum_{k\in M_{ij}}\sum_{l\in M_{ij}} c_{kl}. \tag{5} \]

Thus, each \(i\)-th variant of the \(j\)-th block has an estimate \(c_{ij}\)—the sum of the internal connections between the TS of the set \(M_{ij}\). It is obvious that, in order to solve the problem of distributing TS among blocks according to the criterion of a minimum of interblock connections, it is necessary, from the entire set of variants of block layout, to choose such a collection of variants that contains all the TS of the circuit and has the maximum sum of the corresponding estimates \(c_{ij}\).

Introduce the variable \(x_{ij}\),

\[ x_{ij}= \begin{cases} 1, & \text{if the } i\text{-th variant of the } j\text{-th block is adopted for implementing the circuit;}\\ 0, & \text{otherwise.} \end{cases} \]

In the adopted notation, the problem of distributing TS among blocks according to the criterion of a minimum of interblock connections consists in maximizing the linear form

\[ P: \]

\[ \max Z=\sum_{i=1}^{m_j}\sum_{j=1}^{n'} c_{ij}x_{ij}, \tag{6} \]

subject to

\[ \sum_{i=1}^{m_j}\sum_{j=1}^{n'} a_{ijk}x_{ij}=1,\qquad k=1,2,\ldots,s, \tag{7} \]

\[ \sum_{i=1}^{m_j} x_{ij}=x_j^{*},\qquad j=1,2,\ldots,n', \tag{8} \]

\[ x_{ij}=0,1;\qquad i=1,2,\ldots,m_j;\quad j=1,2,\ldots,n', \tag{9} \]

where \(s\) is the number of TS in the circuit;

\[ a_{ijk}= \begin{cases} 1, & \text{if the } k\text{-th TS is contained in the } i\text{-th variant of the } j\text{-th block;}\\ 0, & \text{otherwise.} \end{cases} \]

Condition (7) in this case means that the set of variants constituting the solution of problem (6)—(9) must include, exactly once, all TS of the circuit. For the case when some TS of the blocks, when covering the circuit, prove to be redundant, condition (7) must be written in the form

\[ \sum_{i=1}^{m_j}\sum_{j=1}^{n'} a_{ijk}x_{ij}\ge 1,\qquad k=1,2,\ldots,s. \tag{7} \]

Condition (8) shows that, from among the set of variants of the \(j\)-th block, there must be selected a number of variants equal to the number of blocks of the \(j\)-th type obtained when covering the circuit.

If the blocks implementing the circuit occur once each, that is, \(x_j^{*}=1,\ j=1,2,\ldots,n'\), then condition (8) takes the form

\[ \sum_{i=1}^{m_j} x_{ij}=1,\qquad j=1,2,\ldots,n'. \tag{8'} \]

The problem obtained by replacing condition (8) with (8′) will be called problem \(P_1\). Let us dwell in more detail on conditions (7), (8′), (9) of problem \(P_1\).

The presence of condition \((8)'\) indicates that, among the set of variants of the \(j\)-th block, only one variant \(x_{ij}\) must enter into the solution of problem \(P_1\). Consequently, condition \((8)'\) partitions the entire set of variables of problem \(P_1\) into \(n'\) groups, each of which corresponds to the variants of the \(j\)-th block. The basic property of a group is that, among the set of its variables, only one of them enters into the solution of problem \(P_1\).

It is obvious that, in order to solve problem \(P_1\), it is sufficient to examine

\[ \prod_{j=1}^{n'} m_j \]

variants and, among the admissible ones, choose the solution corresponding to the maximum value of the objective function. When solving the problem of distributing TS for large circuits, the quantity

\[ \prod_{j=1}^{n'} m_j \]

may attain such values that enumeration of all solution variants proves impossible or irrational.

As applied to the problem under consideration, the number of enumerations can be substantially reduced if the search for the optimal solution is carried out according to the branch-and-bound method. We shall first show that the number of variables in problem \(P_1\) at the moment of searching for the optimal solution can be substantially reduced.

Replace condition \((7)'\) of problem \(P_1\) by the condition

\[ \sum_{i=1}^{m_j} \sum_{j=1}^{n'} a_{ijk} x_{ij} \leq 1, \qquad k = 1, 2, \ldots, s, \tag{7}'' \]

and condition \((8)'\) by the condition

\[ \sum_{i=1}^{m_j} x_{ij} \leq 1, \qquad j = 1, 2, \ldots, n'. \tag{8}'' \]

For problem \(P_2\), obtained by replacing conditions \((7)'\), \((8)'\) by \((7)''\), \((8)''\), we introduce the concept of a partial plan. By a partial plan \(R_h\) of problem \(P_2\) we shall mean any plan satisfying the conditions of problem \(P_2\) for which

\[ \sum_{i=1}^{m_p} x_{ip} = 1, \qquad p = 1, 2, \ldots, h, \quad h < n'. \]

It is obvious that the value of the objective function \(Z^*\) corresponding to the optimal plan of problem \(P_1\) coincides with the value of the objective function of the optimal plan of problem \(P_2\). Problem \(P_2\) is introduced in order to specify the concept of a partial plan and for the convenience of the subsequent reasoning.

Lemma 1. For any partial plan \(R_h\) of problem \(P_2\), in each \(t\)-th group, \(t = h+1, h+2, \ldots, n'\), there exists a variant \(x_{it}\) such that, when it is included in the partial plan \(R_h\), a new partial plan \(R_{h+1}\) of problem \(P_2\) is obtained.

Proof. Suppose there is a partial plan \(R_h\) of problem \(P_2\) for which

\[ \sum_{i=1}^{m_p} x_{ip} = 1, \qquad p = 1, 2, \ldots, h, \quad h < n'. \]

Choose one of the groups of the set \(\{h+1, h+2, \ldots, n'\}\), for example the \(t\)-th. Each variant \(x_{it}\) of the \(t\)-th group from the set \(m_t\) contains the set \(A_t\) of TS types of the \(t\)-th block. If the set

\[ A = \{A_1 \cup A_2 \cup \ldots \cup A_p\} \cap A_t = \varnothing, \]

then it is obvious that any variant \(x_{it}\) of the set \(m_t\) can be included in the partial plan \(R_h\) without violating conditions \((7)''\), \((8)''\).

Consider another case, when the set \(A=\{A_1\cup A_2\cup \ldots \cup A_p\}\cap A_t\ne\varnothing\). Let us single out in the set \(A\) the TS of the \(r\)-th type. Suppose that none of the variants \(x_{it}\), \(i=1,2,\ldots,m_t\), can be included in the partial plan \(R_h\) without violating the \(k\)-th inequality of condition \((7)''\). Suppose also that the \(k\)-th TS of the circuit is a TS of the \(r\)-th type. Note that violation of the \(k\)-th inequality of condition \((7)''\) is possible only if the variants of the partial plan \(R_h\) contain TS of the \(r\)-th type in the amount \(b_r\). This means that implementation of the TS of the \(r\)-th type of the circuit can be carried out without TS of the \(r\)-th type of the \(t\)-th block, which contradicts the initial assumption about the absence of redundancy in the blocks implementing the circuit. Taking into account the circumstance that the set of variants of the \(t\)-th group contains all possible layout variants of the \(t\)-th block, it remains to accept that in the \(t\)-th group there exists a variant \(x_{it}\) that can be included in the partial plan \(R_h\) without violating conditions \((7)''\), \((8)''\) of problem \(P_2\). Lemma 1 is proved.

In real problems of TS distribution, situations occur when, for all variants of some \(f\)-th group, \(c_{if}=c_f=\mathrm{const}\), \(i=1,2,\ldots,m_f\). Excluding from conditions \((7)''\), \((8)''\) of problem \(P_2\) such groups of variants, we obtain problem

\(P_3\):

\[ \max Z=\sum_{i=1}^{m_\nu}\sum_{\nu=1}^{\theta} c_{i\nu}x_{i\nu}, \tag{10} \]

subject to

\[ \sum_{i=1}^{m_\nu}\sum_{\nu=1}^{\theta} a_{i\nu k}x_{i\nu}\leq 1,\qquad k=1,2,\ldots,s, \tag{11} \]

\[ \sum_{i=1}^{m_\nu} x_{i\nu}\leq 1,\qquad \nu=1,2,\ldots,\theta, \tag{12} \]

\[ x_{i\nu}=0,1;\qquad i=1,2,\ldots,m_\nu;\qquad \nu=1,2,\ldots,\theta;\qquad \theta<n', \tag{13} \]

where \(\theta\) is the number of groups of problem \(P_2\) remaining after exclusion.

Theorem 1. Let \(Z_3^*\) be the value of the objective function corresponding to the optimal plan of problem \(P_3\), obtained from problem \(P_2\) after excluding the \(f\)-th groups with \(c_{if}=c_f=\mathrm{const}\), \(f=\theta+1,\theta+2,\ldots,n'\). Then

\[ Z_1^*=Z_3^*+\sum_{f=\theta+1}^{n'} c_f, \tag{14} \]

is valid.

Proof. Since in the conditions of problem \(P_2\) the groups with \(c_{if}=c_f=\mathrm{const}\), \(f=\theta+1,\theta+2,\ldots,n'\), are excluded, the optimal plan of problem \(P_3\) is a partial plan \(R_\theta\) of problem \(P_2\) with objective function \(Z_3^*\). According to Lemma 1, in each excluded group there exists a variant \(x_{if}\), \(i=1,2,\ldots,m_f\); \(f=\theta+1,\theta+2,\ldots,n'\), upon whose inclusion in the partial plan \(R_\theta\) a new partial plan \(R_{\theta+1}\) is obtained. The value of the objective function of the new partial plan will be determined by the sum \(Z_3^*+c_f\). After including in the partial plan \(R_\theta\) one variant \(x_{if}\) from each excluded \(f\)-th group, \(f=\theta+1,\theta+2,\ldots,n'\), the value of the objective function of the plan obtained will be equal to

\[ Z_3^*+\sum_{f=\theta+1}^{n'} c_f. \]

The obtained plan contains one variant from each group of problem \(P_2\) and satisfies its condition \((7)''\). Consequently, under conditions of absence of redundancy in the blocks, such a plan also satisfies the conditions of problem \(P_1\). It is obvious that the plan found in this way is optimal for problem \(P_2\), and since the values of the objective functions \(Z_2^*\) and \(Z_1^*\), corresponding to the optimal plans of problems \(P_2\) and \(P_1\), coincide, it follows that one may write

\[ Z_2^* = Z_3^* + \sum_{f=\theta+1}^{n'} c_f = Z_1^* . \]

Theorem 1 is proved.

In solving problem \(P_1\), at the stage of searching for the optimal partial plan, Theorem 1 makes it possible to reduce the dimensionality of the problem by \(n' - \theta\) groups, which substantially facilitates its solution. The use of Theorem 1 for such purposes is possible only when, in problem \(P_1\), there are groups of variants with estimates \(c_{ij}=\mathrm{const}\), \(i=1, 2, \ldots, m_j\). A more substantial reduction in dimensionality in solving real problems can be achieved by excluding from problem \(P_1\) all variants for which \(c_{ij}=0\). When variants with zero estimates are excluded, it is necessary to consider problem \(P_2\), since there is no guarantee that, for the remaining variants, a solution can be obtained in which one variant from all groups will be present, while conditions \((7)''\), \((8)''\) do not require obtaining precisely such a solution. Excluding from conditions \((7)''\), \((8)''\) the variables \(x_{ij}\) for which \(c_{ij}=0\), we obtain the reduced problem \(P_2\).

Theorem 2. Let the optimal plan of the reduced problem \(P_2\) correspond to the value of the objective function \(Z_2^*\); then

\[ Z_1^* = Z_2^* . \tag{16} \]

Proof. In the present case we are interested in variants with \(c_{ij}=0\) only in those groups that also contain variants with nonzero estimates. Groups all of whose variants have estimates \(c_{ij}=0\) may be assigned to groups with constant estimates of variants. The possibility of excluding such groups was proved by Theorem 1.

In problem \(P_2\), let us exclude from the \(j\)-th group the \(j\)-th variant with estimate \(c_{ij}=0\). After solving the reduced problem obtained in this way, two situations are possible. The optimal plan of the reduced problem contains a variant with nonzero estimate from the \(j\)-th group (case 1), or it contains no variant from the \(j\)-th group (case 2).

If problem \(P_2\) is solved without excluding the variant \(x_{ij}\) with zero estimate, then two cases are also possible. The optimal plan of problem \(P_2\) contains a variant of the \(j\)-th group with nonzero estimate (case 1), or it contains the variant \(x_{ij}\) with zero estimate (case 2). If, when solving problem \(P_2\), the first case occurs, then it is obvious that the value of the objective function \(Z_2^*\) obtained in this case does not depend on whether the variant \(x_{ij}\) with zero estimate is contained in problem \(P_2\) or not. Consequently, for the first case, the solution of the reduced problem \(P_2\) gives the value of the objective function \(Z_2^* = Z_2^{**}\). Suppose next that, when solving problem \(P_2\), the second case occurs. Excluding from the optimal plan obtained in this case the variant \(x_{ij}\) with zero estimate likewise will not change the value of the objective function \(Z_2^{**}\). Moreover, none of conditions \((7)''\), \((8)''\) will be violated, since these conditions do not require the presence in the optimal plan of variants from all groups. Consequently, in the second case as well the solution of the reduced problem \(P_2\) does not change the value of the objective function

Table 3

$Z^{**}_2$, obtained in solving problem $P_2$. Similar reasoning can be extended to all other variants with zero estimates.

The optimal plan of the reduced problem $P_2$ is a partial plan. Therefore, in order to obtain a plan for problem $P_1$, the partial plan, on the basis of Lemma 1, can be extended by means of variants with zero estimates. The value of the objective function of the optimal plan of problem $P_2$ will not change in this case and, consequently, expression (16) is valid. Theorem 2 is proved.

Before presenting the algorithm for solving problem $P_1$, let us specify the rule for constructing the branches of the tree, the method of computing the estimate for selecting a branch, and the process of moving along the vertices of the tree. The subsequent exposition will be illustrated by an example of the problem of distributing TS, the initial data for which are presented in Tables 1 and 2. The conditions of problem $P_1$ for the example under consideration will be presented in the form of Table 3.

Table 3 also presents the estimates of the variants $c_{ij}$, which are determined by formula (5) using the data of Table 2.

When constructing the tree, the variants of the 2nd group are not used, since all of them have estimates $c_{ij} = \mathrm{const}$. In the present case these variants may also be excluded as variants with zero estimates. The variants $x_{1,3}$, $x_{4,3}$, $x_{5,3}$, $x_{2,4}$ in the other groups, which have zero estimates, are also excluded from consideration when constructing the tree. To the remaining variants with nonzero estimates we assign corresponding variables $x^j_t$, $t = 1, 2, \ldots, v$ (the last row of Table 3). Here $v$ is the number of variants with nonzero estimates, and the index $j$ indicates that the $t$-th variant belongs to the $j$-th group. For convenience in constructing and organizing the traversal of the vertices of the tree, the variants are numbered by the index $t$ in the order of decreasing values of their estimates. The tree is constructed in such a way that each of its vertices corresponds to some variable $x^j_t$ (the exception is the zero vertex—the root of the tree). Each path starting at the zero vertex and ending at one of the vertices of the tree contains a set of vertices $x^j_t$, which is a partial plan of problem $P_2$. If the path ends at one of the dangling vertices of the tree, then the corresponding partial plan cannot be extended. Figure 2 shows the tree of partial plans for the example under consideration.

Fig. 2. Tree of partial plans

The process of constructing the tree consists in the sequential formation of mappings $F^f_{x^j_t}$ on the set of vertices $x^j_t$, where $f = 1, 2, \ldots, \mu$; $\mu \leq n'$, $f$ denotes the level of the mapping. The mapping of the first level

to the zero vertex \(F_0^1=\{x_1^j,x_2^j,\ldots,x_v^j\}\), includes the set of all \(x_t^j\) with nonzero estimates. The construction of the mapping of the second level for the vertex \(x_t^j\) is carried out on the set \(x_\gamma^z\in F_0^1\). A vertex \(x_\gamma^z\in F_{x_t^j}^2\) if the following conditions are satisfied:

\[ \begin{aligned} &\text{a) } x_\gamma^z\in F_0^1,\\ &\text{b) } \gamma>t;\\ &\text{c) } z\ne j;\\ &\text{d) } a_{kt}x_t^j+a_{k\gamma}x_\gamma^z\le 1,\quad k=1,2,\ldots,s. \end{aligned} \tag{17} \]

Here \(a_{kt}\) are the coefficients of condition (7) of problem \(P_2\) (for the example under consideration these are the elements of Table 3 located at the intersection of the \(k\)-th row and the \(t\)-th column). The indices \(\gamma,z\) have the same index sets as the indices \(t,j\), respectively.

The construction of the mappings of the \(f\)-th level \(F_{x_t^j}^f\) is also carried out according to conditions (17), except that instead of \(F_0^1\) one uses \(F_{x_\gamma^z}^{\,f-1}\), provided that \(x_t^j\in F_{x_\gamma^z}^{\,f-1}\).

An important factor that largely determines the efficiency of the branch-and-bound method is the way in which the estimate is computed. Let \(R_\gamma^z\) denote a partial plan containing the vertices of a tree route beginning at the zero vertex and ending at the vertex \(x_\gamma^z\), and let the corresponding value of the objective function be denoted by \(Z_\gamma^z\). Suppose that to the vertex \(x_t^j\) there corresponds the mapping \(F_{x_t^j}^f\). To each vertex \(x_\gamma^z\in F_{x_t^j}^f\) there corresponds an estimate \(c_{\gamma k}^z\), \(k=1,2,\ldots,\varphi\), where \(\varphi\) is the number of vertices in the mapping \(F_{x_t^j}^f\). The index \(k\) in the notation \(c_{\gamma k}^z\) indicates the position of the corresponding vertex \(x_\gamma^z\) in the sequence of vertices of the mapping \(F_{x_t^j}^f\). Note that the vertices \(x_\gamma^z\) in the mapping \(F_{x_t^j}^f\) are arranged in decreasing order of the corresponding estimates.

The estimate of the partial plan \(R_\gamma^z\) consists of two components: the value of the objective function of the given partial plan \(Z_\gamma^z\) and the maximum possible value of the objective function \(\overline{Z}_\gamma^z\), computed for its conditional extension. By conditional extension we mean here an extension composed of vertices \(x_\gamma^z\in F_{x_t^j}^f\) with distinct group numbers \(z\) and maximum values of the corresponding \(c_{\gamma k}^z\). Thus, the estimate \(R_\gamma^z\) of the partial plan \(R_\gamma^z\) is determined by the formula

\[ R_\gamma^z=Z_\gamma^z+\overline{Z}_\gamma^z. \tag{18} \]

The quantity \(\overline{Z}_\gamma^z\), in the notation adopted, is determined by the formula

\[ \overline{Z}_\gamma^z=\sum_{k=1}^{\varphi} c_{\gamma k}^z\omega_{\gamma k}^z. \tag{19} \]

where

\[ \omega_{\gamma k}^z= \begin{cases} 1, & \text{if for all estimates } c_\lambda^\nu \text{ of vertices } x_\gamma^\nu\in F_{x_t^j}^f \text{ with } \lambda<k,\text{ it is true that } z\ne \nu;\\ 0, & \text{if for one of the } c_\lambda^\nu \text{ with } \lambda<k,\text{ it is true that } z\ne \nu. \end{cases} \]

The process of moving through the vertices of the tree in searching for the optimal plan is carried out as follows. A mapping \(F'_0\) is formed; then, for the first vertex \(x^j_1\) of the mapping \(F^1_0\), the mapping \(F^2_{x^j_1}\) is formed, and so on. In the general case, for the vertex \(x^j_{t_1}\in F^f_{x^z_2}\), the mapping \(F^{f+1}_{x^j_{t_1}}\) is formed. The process of forming mappings continues until a terminal vertex of the tree is obtained, \(x^j_{t_1}\in F^f_{x^z_1}\), for which \(F^{f+1}_{x^j_{t_1}}=\varnothing\). For the partial plan \(R^j_{t_1}\), the value of the objective function \(Z^j_{t_1}\) is determined. We shall call the quantity \(Z^j_{t_1}\) the lower bound of the objective function and denote it by \(Z_0\). After this, the estimate \(Z_{R^j_{t_2}}\) is determined for the partial plan \(R^j_{t_2}\) corresponding to the vertex \(x^j_{t_2}\in F^f_{x^j_{t_1}}\), and the condition is checked

\[ Z_{R^j_{t_2}} > Z_0 . \tag{20} \]

If condition (20) is satisfied for the vertex \(x^j_{t_2}\in F^f_{x^z}\), the mapping \(F^{f+1}_{x^j_{t_2}}\) is formed and, if \(F^{f+1}_{x^j_{t_2}}\ne\varnothing\), an estimate is determined for its first vertex (the corresponding partial plan) and condition (20) is checked. The process of forming mappings, with determination of estimates of their first vertices and checking of condition (20), continues until a terminal vertex is reached, for example \(x^j_{t_k}\in F^f_{x^z_k}\), or until condition (20) is not satisfied for it. In the first case, the process of searching for the optimal plan continues in the same way as after determining the lower bound of the objective function. In the second case, the so-called backtracking is performed; that is, an estimate is determined and condition (20) is checked for the vertex \(x^z_{\gamma_{k+1}}\). Backtracking is also performed if the vertex under consideration is the last in the mapping.

If, at some step of the search, when determining the estimate for a vertex, the value \(Z^j_t\) turns out to be greater than \(Z_0\), then \(Z^j_t\) is accepted as \(Z_0\). The process of searching for the optimal plan ends if condition (20) is not satisfied for the vertex \(x^j_t\in R'_0\). The partial plan corresponding to the value of the objective function \(Z_0\) is the solution of problem \(P_2\). After this partial plan is expanded by variants with zero estimates and variants of groups containing variants with identical estimates, the optimal plan of problem \(P_1\) is obtained.

For the example under consideration, the search for the optimal plan proceeds as follows. The mappings are constructed:

\[ F'_0=\{x^1_1,\ x^1_2,\ x^4_3,\ x^3_4,\ x^3_5,\ x^4_6,\ x^1_7,\ x^4_8,\ x^1_9,\ x^1_{10},\ x^1_{11},\ x^3_{12}\}, \quad F^2_{x^1_1}=\{x^4_3,\ x^3_5,\ x^4_6,\ x^4_8\}, \quad F^3_{x^4_3}=\varnothing . \]

The partial plan

\[ R^4_3=\{x^1_1,\ x^4_3\} \]

corresponds to the value of the objective function

\[ Z^4_3=c^1_1+c^4_3=33+24=57, \]

which is taken as the lower bound \(Z_0\). Next, by formula (18), the estimate of the vertex \(x^3_5\in F^2_{x^1_1}\) (of the partial plan \(R^3_5\)) is determined:

\[ Z_{R^3_5}=Z^3_5+\overline{Z}^3_5=(c^1_1+c^3_5)+c^4_6=(33+17)+14=64 . \]

Since condition (20) is satisfied \((Z_{R^3_5}>Z_0)\), the mapping

\[ F^3_{x^3_5}=\{x^4_6\} \]

is constructed for the vertex \(x^3_5\). The partial plan

\[ R^4_6=\{x^1_1,\ x^3_5,\ x^4_6\} \]

corresponds to the value of the objective function

\[ Z^4_{t_i}=c^1_1+c^3_5+c^n_6=33+17+14=64, \]

which is taken as \(Z_0\). The estimate

\(Z_{R_6^4}\) of the vertex \(x_6^4 \in F_{x_1^1}^2\) is less than \(Z_0\); consequently, a backtracking step is made and an estimate is computed for the vertex \(x_2^1 \in R_0^1\),

\[ Z_{R_2^1}=Z_2^1+\overline{Z}_2^1=c_2^1+(c_3^4+c_4^3)=25+24+21=70. \]

The estimate \(Z_{R_2^1}>Z_0\) \((70>64)\); therefore we construct the mapping

\[ F_{x_2^1}^2=\{x_3^4,\ x_4^3,\ x_6^4,\ x_8^4,\ x_{12}^3\} \]

and determine the estimate of the vertex \(x_3^4 \in F_{x_2^1}^2\). The estimate \(Z_{R_3^4}=70>Z_0\); therefore \(F_{x_3^4}^3=\{x_{12}^3\}\) is constructed and \(R_{12}^3=53<Z_0\). The estimate \(Z_{R_4^3}\) of the vertex \(x_4^3 \in F_{x_2^1}^2\) is less than \(Z_0\); consequently, a backtracking step is made and the estimate \(Z_{R_3^4}\) of the vertex \(x_3^4 \in F_0^1\) is determined,

\[ Z_{R_3^4}=Z_3^4+\overline{Z}_3^4=c_3^4+(c_4^3+c_7^1)=24+(21+12)=57. \]

The estimate \(Z_{R_3^4}<Z_0\), and since \(x_3^4 \in F_0^1\), the search for the optimal partial plan ends here. The partial plan

\[ R_{x_6^4}=\{x_1^1,\ x_5^3,\ x_6^4\}, \]

corresponding to the estimate \(Z_0=64\), is optimal. The plan \(R_{x_6^4}\) contains variants from three groups and can be expanded by including the variant \(x_{1,2}\) of the excluded group. The resulting plan

\[ X^*=\{x_{6,1};\ x_{2,3};\ x_{4,4};\ x_{1,2}\} \]

with objective function \(Z_1^*=64\) is optimal for the example under consideration.

In Table 3, the variants of the optimal plan are marked with an asterisk. Figure 2 shows all the mappings that had to be constructed in determining the optimal plan. The vertices for which estimates were determined are marked with double circles.

The method described above was considered for the problem of distributing TS in the absence of redundancy, for the case when \(x_j^*=1,\ j=1,2,\ldots,n'\). A more general formulation of this problem takes into account redundancy and the presence of several blocks of one type. In this case, the problem of distributing TS among blocks is written in the form

\[ P:\qquad \max Z=\sum_{i=1}^{m_j}\sum_{j=1}^{n'} c_{ij}x_{ij}; \tag{21} \]

\[ \sum_{i=1}^{m_j}\sum_{j=1}^{n'} a_{ijk}x_{ij}\ge 1,\qquad k=1,2,\ldots,s; \tag{22} \]

with

\[ \sum_{i=1}^{m_j} x_{ij}=x_j^*,\qquad j=1,2,\ldots,n'; \tag{23} \]

\[ x_{ij}=0,1;\qquad i=1,2,\ldots,m_j;\quad j=1,2,\ldots,n'. \tag{24} \]

Condition (22) can easily be reduced to condition (7) of problem (6)–(9). To do this, for each \(r\)-th type of TS the condition is checked

\[ \sum_{j=1}^{n'} d_{rj}>b_r,\qquad r=1,2,\ldots,\omega. \tag{25} \]

If condition (25) is satisfied, then, consequently, there is redundancy, and \(b_r'\) conditional TS of the \(r\)-th type are introduced into the scheme*,

\[ b_r'=\sum_{j=1}^{n'} d_{rj}-b_r. \tag{26} \]

* It is assumed that the conditional TS have no connections either with one another or with the real TS of the scheme.

The total number of conditional TS included in the circuit is determined by the quantity \(h\)

\[ h=\sum_{r=1}^{\omega} b'_r . \tag{27} \]

After the inclusion of conditional TS, condition (22) may be written as follows:

\[ \sum_{i=1}^{m_j}\sum_{j=1}^{n'} a_{ijk} x_{ij}=1;\qquad k=1,2,\ldots,s,\ s+1,\ldots,s+h . \tag{28} \]

After replacing condition (22) by (28), problem \(P\) can be solved using the method set forth for problem \(P_1\). In searching for the optimal plan in this case, in the groups constructed for the \(j\)-th blocks with \(x_j^*>1\), not one variant is selected, as in problem \(P_1\), but \(x_j^*\) variants.

REFERENCES

1. V. K. Potrebnoi. Covering circuits of computing devices with blocks of a unified set. Izv. TPI, vol. 211, Tomsk, 1970.