16.5 Formulating a Large-scale System Architecture Problem
We have examined six Patterns that appear when one is considering programmed decisions in system architecture: the DECISION-OPTION Pattern, the DOWN-SELECTING Pattern, the ASSIGNING Pattern, the PARTITIONING Pattern, the PERMUTING Pattern, and the CONNECTING Pattern. These Patterns can be used to formulate programmed decisions that appear when the system architect is conducting the recurring tasks that were identified earlier in the chapter and summarized in Table 16.1. Table 16.5 indicates which Patterns are usually more applicable for the various tasks.
Table 16.5 | Relationships of system architecture tasks and Patterns. X indicates the Pattern(s) that are usually more appropriate for each task.
| Decision-Option | Down-Selecting | Assigning | Partitioning | Permuting | Connecting | |
| Decomposition of Form and Function | X | |||||
| Mapping of Function to Form | X | X | ||||
| Specialization of Form and Function | X | X | ||||
| Characterization of Form and Function | X | |||||
| Connectivity of Form and Function | X | X | X | |||
| Definition of Scope and Selection of Goals | X |
One might think that one and only one of these Patterns will be appropriate for any particular system architecture problem and that choosing this Pattern will be straightforward. But that is not the case for real-life large-scale architecture optimization problems.
First, as suggested by the fact that Table 16.5 is not a one-to-one mapping, the Patterns are not mutually exclusive and there is sometimes ambiguity in the choice of a Pattern for a given task. For example, in the NEOSS example, the problem of choosing which instruments go into which spacecraft can be formulated either as an ASSIGNING problem, where instruments are assigned to spacecraft or orbits, or as a PARTITIONING problem, where instruments are simply partitioned into subsets, which then are the input to an orbit and spacecraft design. Note that the two formulations are different in that the ASSIGNING Pattern allows assigning instruments to zero or more than one spacecraft or orbit, which is not allowed in the PARTITIONING Pattern. One formulation will probably make more sense than the other, depending on the context; for example, budget constraints may preclude repeating instruments.
Second, real system architecture optimization problems usually have many decisions that are rarely homogeneous in terms of their structure. Often, a large problem can be effectively decomposed into sub-problems that fit one of the Patterns. This decomposition reduces the computational complexity of the overall problem, at the expense of a loss of global optimality if couplings exist between sub-problems.
These two points are discussed in the rest of this section.
Overlap between Patterns
Relationships between these Patterns were unveiled as the Patterns were introduced in the previous section. These relationships are summarized in Table 16.6.
Table 16.6 | Outstanding relationships between Patterns. Elements in the diagonal are not meaningful. Note that the matrix is symmetric, so only the upper triangular part is shown.
| Down- Selecting (DS) | Assigning (AS) | Partitioning (PT) | Permuting (PM) | Connecting (CN) | |
| Decision-Option (DO) | DS ~ DO with binary decisions (choose element yes or no) | AS ~ DO with binary decisions (assign element to bin yes or no) | PT ~ DO with 1 decision containing all possible partitions, or integer decisions (1 through ) with hard constraints to enforce partitioning structure | PM ~ DO with 1 decision containing all possible permutations, or integer decisions (1 through ) with hard constraints to enforce permutation structure | CN ~ DO with binary decisions (connect element to element yes or no) |
| Down-Selecting (DS) | AS ~ DS problems, one for each element | PT ~ DS with one decision for each possible subset of elements, and constraints to enforce partitioning structure. | PM ~ DS with one decision for each possible assignment of an element to a position, with hard constraints to enforce permutation structure | CN ~ DS problem where we choose a subset from a set of candidate connections | |
| Assigning (AS) | PT ~ AS with elements and indistinguishable bins, and each element must be assigned to 1 bin (empty bins are OK) | PM ~ AS with same number of elements and bins, and each element must be assigned to a different bin | AS ~ CN with two distinct groups of nodes, and each node from one set can be connected only to nodes from the other set | ||
| Partitioning (PT) | PM can be expressed as a traveling salesman problem, which is an NP-complete problem. PT can be expressed as a set-partitioning problem, also NP-complete. Since it has been proved that NP-complete problems are all interchangeable, PM can be expressed as PT. | PT ~ CN where connected nodes are considered to be in the same subset, but this is a degraded formulation because multiple CN architectures correspond to the same PT architecture | |||
| Permuting (PM) | PM ~ CN with two distinct groups of nodes, and each node from one set must be connected to exactly one node from the other set without repetition |
The relationships in Table 16.6 would seem to suggest that one can switch between some of these problem formulations but not others. In reality, although doing so requires more effort, it can be proved that one can switch between any two problem formulations. Intuitively, it is easy to see that every architectural problem can be formulated as a DECISION-OPTION problem. However, this requires explicitly enumerating what may be a large number of options for decisions that are more naturally expressed as ASSIGNING or PARTITIONING decisions. For instance, in the NEOSS example, it would be possible—though cumbersome—to express the instrument-packaging problem for 5 instruments as a single DECISION-OPTION decision with 52 options.
Proving that any architectural problem can be expressed as a DOWN-SELECTING problem is equally easy, because it suffices to assign binary codes to the options of each decision. For instance, if for a DECISION-OPTION decision we have m options, we can formulate that decision in the DOWN-SELECTING Pattern using binary decisions. This is similar to what was done in the Apollo example with the mission-mode decision, which was effectively decomposed into multiple decisions (such as EOR yes or no, LOR yes or no). Although this is possible in general, it often requires adding a large number of constraints to rule out binary combinations that do not correspond to any option, which will happen for any m that is not an exact power of 2.
It is also relatively easy (though less intuitive) to prove, using graph theory, that any architectural problem can be expressed as a CONNECTING problem, because any DECISION-OPTION problem can be represented as a bipartite graph* in which we have one set of nodes representing the decisions and another set representing the options. Each architecture can thus be uniquely associated with an adjacency matrix that connects these two partitions.
While this is possible in general, it also comes at the price of some extra constraints, because we have to ensure that options corresponding to a certain decision are not linked to other decisions, and that each decision is assigned to exactly one option.
Proving that any architecture optimization problem can be expressed by means of exclusively PERMUTING decisions or exclusively PARTITIONING decisions is a harder task. The idea for a possible proof is that two known NP-complete problems, namely the traveling salesman problem and the set partitioning problem, can be reduced to the PERMUTING and PARTITIONING problems. Since every problem in NP (including all NP-complete problems) is reducible to every other problem in NP-complete, this means that we can express permuting problems as partitioning problems, and vice versa. Moreover, any other architecture optimization problem (DOWN-SELECTING, ASSIGNING, CONNECTING) can also be reduced to an NP complete problem, and therefore can be reduced to a PARTITIONING or PERMUTING problem.
Although every architecting problem can be expressed using any Pattern, it is clear that some Patterns are more appropriate than others to express certain problems (for instance, expressing the NEOSS instrument-packaging problem as a DECISION-OPTION problem would be awkward). Furthermore, the Pattern that we choose will affect the time it takes to solve the problem with an optimization algorithm. For example, DOWN-SELECTING and ASSIGNING problems usually are easier to solve by optimization algorithms than PARTITIONING and PERMUTING problems are.
Decomposition into Sub-problems
It is important to note that the complete set of architectural decisions for a given system will naturally not entirely fall in any one of these Patterns. Instead, different parts of the problem (subsets of decisions) are likely to fit different Patterns. For example, the NEOSS example can effectively be decomposed into three sub-problems (instrument selection, packaging, and mission scheduling). These three sub-problems map directly to three Patterns: DOWN-SELECTING, PARTITIONING (or ASSIGNING if we assign instruments to orbits and allow for repetition of instruments), and PERMUTING.
This does not mean that a single optimization problem with all these different types of decisions cannot be written. However, in many cases, a global optimization problem will be extremely large in size, which will in general decrease the performance of the optimization algorithms.
Moreover, these different subsets of decisions are often relevant to different sets of metrics, or are relevant to the same set of metrics but operate at different scales (that is, the effect of one is much larger than the effect of the other). For example, in the NEOSS case, both the instrument selection problem and the instrument-packaging problem are fundamentally tradeoffs between cost and performance, but most of the cost and most of the performance are driven by the instrument selection problem. The instrument-packaging problem has a noticeable and important impact on both cost and performance, but this impact is still small compared to that of the instrument selection problem. Hence, in practice, decomposing the global architecture optimization problem into sub-problems that fit one of the Patterns presented in this chapter is often—but not always—the best way of decomposing the problem.
Note, however, that in the case of NEOSS, the three sub-problems are indeed clearly coupled. One cannot, for example, make an optimal decision in the instrument selection problem without thinking about the packaging of the selected instruments. This could lead to inefficiencies in the use of a certain satellite bus or launch vehicle. Similarly, it is hard to make the best packaging decision without thinking about the scheduling of the missions, since an instrument that closes an important data gap should perhaps fly in the spacecraft that is to be launched first. This is illustrated in the Figure 16.15.
Figure 16.15 Decomposition of the NEOSS architecture problem into three coupled sub-problems that map to the Patterns defined earlier.
As a consequence of this coupling, simply solving the individual sub-problems and combining the results will in general lead to suboptimal solutions. This problem can be alleviated by modeling the coupling between sub-problems explicitly—for example, in the form of constraints. For instance, in the instrument selection problem, a constraint can be used to ensure that an instrument that covers an important data gap is selected. These rules will guide the search process to favor architectures that are likely to be good when the other sub-problems are solved.
In summary, when formulating a large-scale system architecture problem, the architect must decompose the problem into sub-problems that are as loosely coupled as possible, using the six Patterns to formulate the sub-problems.