JP7526155B2 - Optimization problem solving device and optimization problem solving method - Google Patents

Description

This disclosure relates to an optimization problem solving device and an optimization problem solving method. In particular, this disclosure relates to an optimization problem solving device and an optimization problem solving method used for set packing problems such as material design problems in the steel industry.

Combinatorial optimization problems exist in various industrial fields. For example, when allocating one or more orders for multiple steel pieces (slabs, large plates) in a steel mill, a method for solving the optimization problem can be applied to provide a suitable plate selection method.

Patent Document 1 discloses a method for creating a large plate pattern using a branch-and-bound method and selecting a large plate using a 0-1 programming problem. Patent Document 2 discloses a method for rigorously formulating a set partitioning problem using an Ising model. Patent Document 3 discloses a method for finding a solution to a dual problem, creating a column generator problem represented by binary variables that includes the solution to the dual problem, and using a quantum computer to solve the column generator problem. Patent Document 4 discloses a method for using 0-1 programming to select a billet of steel that maximizes a target evaluation function from among the enumerated combinations, subject to the constraint of the number of orders.

JP 2004-276034 A JP 2017-151810 A JP 2021-043693 A JP 2020-181575 A

Here, when the problem of allocating one or more orders to multiple steel pieces involves a large number of orders, it becomes an integer programming problem rather than a 0-1 programming problem. In such cases, it is difficult to apply the method of Patent Document 1 as is.

In addition, in the problem of assigning one or more orders to multiple steel pieces, multiple orders may be included in different large plate patterns, which results in a set-packing problem. The method in Patent Document 2 is rigorously formulated, making it difficult to apply directly. In addition, the method in Patent Document 3 uses only equality constraints, making it difficult to apply directly.

The method in Patent Document 4 is applicable because it multiplies the constraints by a penalty term and includes it in the objective function, but the convergence is insufficient.

In general, when the number of factors to be determined increases in a combinatorial optimization problem, it becomes difficult to derive an optimal solution due to combinatorial explosion. As mentioned above, similar difficulties arise when applied to the problem of manufacturing intermediate products such as slabs in response to various orders for thick steel plates in the steel industry. In recent years, various approximation approaches have been proposed, such as mixed-integer programming problem (MIP), genetic algorithm (GA), simulated annealing (SA), and particle swarm optimization (PSO). In addition, a method has been proposed in which a combinatorial optimization problem is divided into subproblems to speed up individual searches and speed up the overall problem. However, even with these methods and improvements in computer calculation speed, it is difficult to obtain an optimal solution in a realistic amount of time when the problem is large-scale.

In recent years, quantum computers have begun to be used commercially, and an environment is being created in which they can be used relatively easily through cloud services over networks. As a result, there is a demand for methods of solving large-scale optimization problems that are also suitable for use with quantum computers.

In light of these circumstances, the purpose of this disclosure is to provide an optimization problem solving device and method that can efficiently solve combinatorial optimization problems and are also suitable for use with quantum computers.

An optimization problem solving device according to an embodiment of the present disclosure includes:
An optimization problem solving device that solves a combinatorial optimization problem in which a combination of a plurality of products is treated as one manufacturing unit and optimization is performed for one or more of the manufacturing units, the device comprising:
a model construction unit that lists candidate patterns that can be the combination and determines an evaluation value for each of the listed candidate patterns;
a calculation unit that selects the candidate pattern such that the constraint condition of the combination is satisfied and the value of the evaluation function is maximized or minimized, and adds the candidate pattern to a selected pattern;
a result presenting unit that presents the selected pattern when the evaluation function satisfies a criterion;
the evaluation function is configured by adding up the evaluation values of the candidate patterns included in the selected pattern,
The selected pattern may include multiple instances of the same candidate pattern.

A method for solving an optimization problem according to an embodiment of the present disclosure includes:
A method for solving an optimization problem, which solves a combinatorial optimization problem in which a combination of a plurality of products is treated as one manufacturing unit and optimization is performed for one or more of the manufacturing units, comprising the steps of:
listing candidate patterns that may be the combination, and determining an evaluation value for each of the listed candidate patterns;
selecting the candidate pattern such that the constraint condition of the combination is satisfied and the value of the evaluation function is maximized or minimized, and adding the candidate pattern to the selected patterns;
presenting the selected pattern if the evaluation function satisfies a criterion;
the evaluation function is configured by adding up the evaluation values of the candidate patterns included in the selected pattern,
The selected pattern may include multiple instances of the same candidate pattern.

The present disclosure provides an optimization problem solving device and method that can efficiently solve combinatorial optimization problems and are suitable for use with quantum computers.

FIG. 1 is a diagram illustrating an example of the configuration of an optimization problem solving device according to an embodiment. FIG. 2 is a diagram for explaining the thick plate material design problem. FIG. 3 is a diagram illustrating an example of a division form of a thick plate blank design problem. FIG. 4 is a diagram for explaining the selection of a large plate pattern in a thick plate material design problem. FIG. 5 is a diagram for explaining the expansion of the pattern matrix. FIG. 6 is a diagram illustrating the results when slack variables are used. FIG. 7 is a diagram illustrating the results when the augmented Lagrangian method is used. FIG. 8 is a diagram illustrating another example of the configuration of an optimization problem solving device according to an embodiment.

Below, an optimization problem solving device and an optimization problem solving method according to an embodiment of the present disclosure will be described with reference to the drawings.

Fig. 1 is a diagram showing an example of the configuration of an optimization problem solving device 10 according to this embodiment. The optimization problem solving device 10 is a device that solves a combinatorial optimization problem in which a combination of multiple products is treated as one manufacturing unit and optimization is performed for one or more manufacturing units. The optimization problem solving device 10 may be connected to a business computer, which is a host computer, and may acquire various data stored as order data 121 and constraint condition data 122, which will be described later, from the business computer.

The optimization problem solving device 10 includes an input/output control unit 11, a storage unit 12, and a production planning unit 13. The production planning unit 13 includes a solution search unit 14 and a result presentation unit 15. The solution search unit 14 includes a model construction unit 141, a calculation unit 142, a condition determination unit 143, and a parameter update unit 144. The optimization problem solving device 10 may be, for example, a computer as a hardware configuration. The computer includes, for example, a storage device such as a memory and a hard disk drive, a processing device such as a CPU, and a display device such as a display. The storage unit 12 may be realized, for example, by a storage device. The input/output control unit 11 and the solution search unit 14 may be realized, for example, by a processing device. The result presentation unit 15 may be realized, for example, by a display device. The computer may also include input devices such as a keyboard and a mouse that accept input from a user.

The input/output control unit 11 controls the input and output of data, etc., of the optimization problem solving device 10. The input/output control unit 11 may, for example, obtain a command to execute a calculation from a user or various data from a business computer, and output the data to the production planning unit 13 or the memory unit 12.

The storage unit 12 stores data used in various calculations executed by the production planning unit 13, calculation results, intermediate data, etc. The storage unit 12 is, for example, built into the optimization problem solving device 10, but can also be configured to be accessed from outside the optimization problem solving device 10 via any interface.

In this embodiment, the storage unit 12 includes order data 121 and constraint condition data 122. As described above, the optimization problem solving device 10 solves a combinatorial optimization problem in which a combination of multiple products is treated as one production unit and one or more production units are optimized. The order data 121 is information such as the size, quantity, and delivery date of each of the multiple products in this optimization problem. The size may include thickness, width, length, etc. The order data 121 may further include product specifications such as components and required mechanical properties. The constraint condition data 122 is a constraint condition when manufacturing by setting a production unit. The constraint condition may include a condition regarding the quantity of multiple products to be manufactured by a specified period, such as "three products a, one product b, and two products c."

The production planning unit 13 uses data from the input/output control unit 11 and the memory unit 12 to calculate a solution to the optimization problem. The arrows shown in FIG. 1 simply indicate the processes corresponding to the optimization problem solving method executed by the optimization problem solving device 10. Below, the components of the production planning unit 13 will be explained in accordance with this processing order.

The model construction unit 141 lists candidate patterns that are combinations of multiple products, and determines an evaluation value for each of the listed candidate patterns. When there are many orders, there are many patterns of combinations of multiple products. A candidate pattern is a combination pattern that can be adopted as one manufacturing unit. The evaluation value is a numerical value that indicates the desirability (or unsuitability) of the combination of multiple products in the candidate pattern for manufacturing. The evaluation value may be calculated based on, for example, the time required for production, the yield, and the ease of processing. Specific examples of the listed candidate patterns and evaluation values will be described later.

The calculation unit 142 selects a candidate pattern so that the constraint conditions of the combination are satisfied and the value of the evaluation function is maximized or minimized, and adds it to the selected pattern. The constraint conditions may be the manufacturing conditions stored in the constraint condition data 122. The calculation unit 142 selects an appropriate candidate pattern from the listed candidate patterns and adds it to the selected pattern. The selected pattern corresponds to a set of appropriate candidate patterns. The evaluation function is a function used to select an appropriate candidate pattern, and is configured by adding up the evaluation values of the candidate patterns included in the selected pattern. Specific examples of the evaluation function will be described later.

The selected patterns generated by the calculation unit 142 can include multiple instances of the same candidate pattern. Therefore, even if the selection or non-selection of a candidate pattern is expressed by a binary variable of 0 or 1, it is possible to handle integers (select an integer number of patterns) by allowing multiple instances of the same candidate pattern. In other words, even if the parameters are configured as binary variables of 0 and 1 so as to be suitable for calculations on the quantum computer 16 (see FIG. 8), a solution to an integer programming problem can be obtained.

The condition determination unit 143 determines whether the evaluation function satisfies the criterion. For example, in the case of a minimization problem in which the evaluation function includes a penalty term related to the constraint condition, the condition determination unit 143 may determine that the criterion is satisfied when the value of the evaluation function is equal to or less than a reference value, the change range of the evaluation function is equal to or less than a predetermined value, and an upper limit is set for the number of calculations of the iterative calculation or the calculation time, and the upper limit is reached. In other words, the calculation result may be a suboptimal solution. In the case of a maximization problem, the evaluation function value is equal to or greater than the reference value, but the concept is the same as in the minimization problem. In addition, the absence of a reference value is also acceptable. The process branches depending on the result of the determination by the condition determination unit 143. When the evaluation function satisfies the criterion, the calculation unit 142 outputs the selected pattern as a solution to the result presentation unit 15. In addition, when the evaluation function does not satisfy the criterion, the parameter update unit 144 executes the process.

The parameter update unit 144 updates the parameters included in the evaluation function. For example, if the evaluation function includes a Lagrangian multiplier, the parameter update unit 144 updates the Lagrangian multiplier. Here, if the evaluation function is configured not to update parameters, the parameter update unit 144 may be omitted.

When the condition determination unit 143 determines that the evaluation function does not satisfy the criteria, the model construction unit 141 executes processing again. The model construction unit 141 adds the candidate patterns to be enumerated. As described below, the candidate patterns may be simply added (see the first method in FIG. 5), or may be added after deleting the candidate patterns that were not selected by the calculation unit 142 from the candidate patterns added immediately before (see the second method in FIG. 5).

The result presentation unit 15 presents the calculation results (solutions) of the solution search unit 14 to the user. The user can improve production efficiency and yield by reflecting the solutions presented by the result presentation unit 15 in the production plan.

Here, as shown in FIG. 8, the calculation unit 142 may be realized by a quantum computer 16 connected via a network such as the Internet. By using a quantum computer 16 as the calculation unit 142, it is possible to speed up calculations. Here, the optimization problem solving device 10 configured as shown in FIG. 8 may be referred to as an optimization problem solving system. Furthermore, the optimization problem solving device 10 of FIG. 1 or FIG. 8 may constitute an optimization problem solving system together with a business computer.

The optimization problem solving device 10 and the optimization problem solving method are described in more detail below as being used for a thick plate material design problem in the steel industry, where one or more orders are placed for multiple steel pieces (slabs, large plates). Here, the term order is also used to refer to a steel plate product whose size, quantity, delivery date, etc. are specified by the customer.

The material design problem is to determine the allocation of multiple order groups (steel grades, plate thicknesses, lots) to large plates in a way that satisfies manufacturing constraints and is production efficient. As shown in Figure 2, order groups are determined, for example, based on delivery dates. The allocation is determined so that cutting losses and leftovers are reduced while combining several orders contained in an order group into large plates.

Such problems are well known in the field of mathematical optimization, and are classified as set packing problems, in which a group of orders is compiled to create materials, and cutting stock problems, in which products are cut from manufactured stock. The above problems belong to the class of NP-hard problems, and the required calculation time increases exponentially as the number of orders increases, so they may not be solvable in a realistic amount of time.

For material design problems, various efforts have been made to improve efficiency by dividing the problem into multiple stages. For example, as shown in FIG. 3, a two-stage configuration has been proposed in which possible patterns (candidate patterns) that can be combined with order groups while taking into account constraints are enumerated in advance, and an optimal pattern group that includes as many order groups as possible and is optimal in terms of production efficiency and truncation loss is selected from the candidate patterns (Patent Document 1). The optimization problem solving device 10 according to this embodiment can also use the method described in Patent Document 1 for the process up to "pattern enumeration" in FIG. 3, that is, the process up to the process of enumerating candidate patterns before selection. After the process of enumerating candidate patterns, the optimization problem solving device 10 according to this embodiment executes a pattern selection process that is suitable for high-speed calculations using, for example, a quantum computer 16, as described below.

Figure 4 is a diagram for explaining the selection of a large plate pattern in a thick plate material design problem. The vertical axis of the first data indicates the order (subscript i = 1 to N). The horizontal axis indicates the large plate pattern (subscript j = 1 to M). The M large plate patterns correspond to the candidate patterns enumerated by the model construction unit 141. Enumeration of candidate patterns refers to the specific process in which the model construction unit 141 generates the first data and stores it in the memory unit 12. Also, since the candidate patterns enumerated as described above are added, M shown in the first data changes.

The numerical value at the intersection between the order of the first data and the large board pattern indicates the number of sheets (P _ij ) included in the large board pattern. Also, a score (c _j ) is set, which is an evaluation value taking into account the time and yield required for the production of each large board. In this embodiment, the higher the score, the better.

The second data defines the number of orders (d _i ) and the remaining penalty (b _i ) for each order. The model construction unit 141 may generate the second data based on the order data 121 and the constraint condition data 122. In this embodiment, the constraint condition is that the total number of incorporations of each order (#1 to #N) into the large board pattern group does not exceed the number of orders. In addition, the evaluation function as a minimization problem includes terms corresponding to the "sum of scores of the selected large board patterns" and the "sum of shortage penalties in the case where the order number of orders cannot be fulfilled."

When selecting an appropriate candidate pattern from the enumerated candidate patterns, the process of minimizing the evaluation function performed by the calculation unit 142 can be expressed by the following formula (1).

Here, x _j is the number of large board patterns selected, and is assumed to be an integer equal to or greater than 0. Also, y _i is the number of shortages relative to the number of orders (d _i ), and is expressed by formula (2). c _j is the score as described above. b _i is the penalty for remaining in the set as described above. P _ij is a pattern matrix, and corresponds to the enumerated candidate patterns. The first term corresponds to the "total score of the selected large board patterns". The second term corresponds to the "total shortage penalty when the number of orders cannot be fulfilled". The third term corresponds to a penalty term related to the inequality constraint that the number of pieces to be incorporated does not exceed the number of pieces ordered, and is obtained by squaring the difference with the number of pieces ordered and multiplying it by a coefficient. When it matches the number of pieces ordered, the penalty is zero. However, since the difference is taken and squared, the constraint of not exceeding the number of pieces ordered is not strictly expressed in the sense that an excess or shortage is equivalent to the number of pieces ordered. Here, in this embodiment, the minimization of the evaluation function is calculated, but as another example, the maximization of the evaluation function may be calculated.

In this formulation, _xj is an integer equal to or greater than 0, but there are the following points to consider: First, since _xj is the selection number of large board patterns, if it is expressed only as 0 or 1, a large number of variables will be used.

For example, in quantum annealing (QUBO (Quadratic Unconstrained Binary Optimization) model), which can only express binary values of 0 or 1, it is necessary to handle integer values by summing several variables to represent integer values. As a typical example of expression, _xj is expressed by binary expression as shown in the following formula (3).

Here, q _i,k in formula (3) is 0 or 1. However, when the number of variables is N and K variables are further required to represent each integer, the effective number of variables is NK. Therefore, when solving a problem with N variables, it is essentially solving a problem of the scale of NK variables, which leads to a waste of limited quantum bits.

Therefore, in order to make it easier to formulate using quantum annealing, _xj is set as a binary variable of 0 or 1, and the adopted large plate pattern (selected candidate pattern) is considered to be highly useful, so that a solution can be calculated without using binary representation by using a new method of expanding the matrix P and solving it again. The optimization problem solving device 10 according to this embodiment can execute this new method by executing a process of adding candidate patterns listed by the model construction unit 141 and by allowing the selected pattern generated by the calculation unit 142 to include multiple identical candidate patterns.

The formula modified to correspond to the above new method is as shown in the following formula (4). _{x j} is a binary variable of 0 or 1, and the difference from the original formula is that the pattern matrix is expanded. The other parameters are the same as formulas (1) and (2).

FIG. 5 is a diagram for explaining the expansion of a pattern matrix. The pattern matrix corresponds to the candidate patterns listed as above. The pattern matrix is shown as a horizontally long rectangle drawn with a solid line. In the first method of FIG. 5, the upper row corresponds to the previous (immediately preceding) pattern matrix, and the lower row corresponds to the current pattern matrix. In the first method, an addition is also made to the pattern matrix immediately before, and the current addition is further made to the pattern matrix after the immediately preceding addition. Here, the dashed lines indicate the patterns used (corresponding to x _j , which is 1). The used patterns correspond to the candidate patterns selected from the candidate patterns listed by the calculation unit 142. The set of patterns indicated by the dashed lines corresponds to the selected patterns generated by the calculation unit 142.

The pattern matrix may be expanded by a second method. As shown in FIG. 5, in the second method, unused patterns from the previously added patterns are deleted before the current addition is performed. The second method can save variables compared to the first method.

Here, in order to improve convergence, it is necessary to properly handle the case where the quantity of received orders (d _i ) of each order is not completely satisfied in formulas (1) and (4), in other words, to properly handle inequality constraints. In the method for solving the optimization problem according to this embodiment, it is possible to further improve convergence by introducing another variable into formula (4).

For example, an inequality constraint is converted into an equality constraint by introducing a slack variable z _i . In the optimization problem solving method according to the present embodiment, the formula when the slack variable z _i is introduced is as shown in the following formula (5). In formula (5), the penalty term of the evaluation function includes the slack variable z _i . The slack variable z _i is a decision variable that takes a value from 0 to d _i , and plays a role in converting the inequality constraint into an equality constraint. Here, the other parameters of formula (5) are the same as those of formulas (1) and (2).

Here, the slack variable z _i is each value from 0 to d _i (normal integer), so it is treated as a binary variable of 0 or 1, and the binary representation expressed in the form of formula (3) is used. Therefore, when the slack variable z _i is introduced, there may be a disadvantage that the number of variables increases. On the other hand, for example, on the premise that the number of orders (d _i ) of each order is satisfied to a certain extent, the increase can be suppressed by limiting the range of values that the slack variable z _i takes to 0 to d _i -A. Here, A is a fixed value less than d _i . In general, since the number of large board patterns (M) is larger than the number of orders (N) (see FIG. 4), the merit of introducing the binary slack variable z _i is large even if the number of variables increases.

Figure 6 shows the results of a formulation using slack variables z _i . As can be seen from the upper diagram of Figure 6, a constraint satisfaction solution can be derived with a small number of calculation steps. Also, as shown in the lower diagram of Figure 6, there is a high degree of agreement between the order quantity (d _i , solid line) and the planned quantity (dashed line), and good results were obtained.

As another method, iterative calculation can be performed by introducing a Lagrangian multiplier instead of the slack variable z _i . That is, an extended Lagrangian method is configured in which the Lagrangian multiplier is updated so as to satisfy the inequality constraint condition. The mathematical expression when the Lagrangian multiplier is introduced is as shown in the following formula (6). In formula (6), the penalty term (cost function) of the evaluation function includes the Lagrangian multiplier. The Lagrangian multiplier is updated by the parameter update unit 144 so as to minimize the cost function.

Here, v _i is a Lagrange multiplier. The other parameters are the same as those in equations (1) and (2). When a solution that satisfies the following equation (7) is selected, the cost function is minimized.

Here, the constraint is that each order does not exceed the quantity received (d _i ). When the inequality constraint is satisfied, (d _i -ΣP _ij x _j ) ≥ 0, so (ν _i /λ) ≤ 0. When the inequality constraint is satisfied, the Lagrange multiplier is not updated, and when the inequality constraint is not satisfied, it is updated according to the following formula (8) (ν _i becomes large).

Figure 7 shows the results of a formulation using Lagrange multipliers. As shown in the upper diagram of Figure 7, the constraint violations, which had exceeded 140, dropped to 0 in a dozen or so steps, and a constraint satisfying solution was obtained. Also, as shown in the lower diagram of Figure 7, there was no planned number (dashed line) that exceeded the number of orders (d _i , solid line), and good results were obtained.

Here, since the method using the slack variable z _i and the augmented Lagrangian method involve a trade-off between the number of variables and the number of calculation steps, one of them may be selected according to the nature of the optimization problem.

As described above, the optimization problem solving device 10 and optimization problem solving method according to this embodiment can solve manufacturing optimization problems, including large board pattern selection problems, as 0-1 plans with inequality constraints, using the above-mentioned configuration and process. Therefore, the optimization problem solving device 10 and optimization problem solving method according to this embodiment can efficiently solve combinatorial optimization problems and are also suitable for use with a quantum computer 16. Furthermore, by applying the optimization problem solving device 10 and optimization problem solving method according to this embodiment to solving production planning problems, production efficiency and yield can be improved.

Although the embodiments of the present disclosure have been described based on the drawings and examples, it should be noted that those skilled in the art would easily be able to make various modifications or amendments based on the present disclosure. Therefore, it should be noted that these modifications or amendments are included in the scope of the present disclosure. For example, the functions included in each component or step can be rearranged so as not to cause logical inconsistencies, and multiple components or steps can be combined into one or divided. The embodiments of the present disclosure can also be realized as a program executed by a processor included in the device or a storage medium having a program recorded thereon. It should be understood that these are also included in the scope of the present disclosure.

In the above embodiment, the optimization problem solving device 10 and the optimization problem solving method are applied to a material design problem for thick steel plates, but are not limited to this. The optimization problem solving device 10 and the optimization problem solving method can be applied to various combinatorial optimization problems in which a combination of multiple products is one manufacturing unit.

REFERENCE SIGNS LIST 10 Optimization problem solving device 11 Input/output control unit 12 Memory unit 13 Production planning unit 14 Solution search unit 15 Result presentation unit 16 Quantum computer 121 Order data 122 Constraint condition data 141 Model construction unit 142 Calculation unit 143 Condition determination unit 144 Parameter update unit

Claims (5)

An optimization problem solving device that solves a combinatorial optimization problem for optimizing one or more manufacturing units, the manufacturing unit being a combination of a plurality of products, comprising:
a model construction unit that lists candidate patterns that can be the combination and determines an evaluation value for each of the listed candidate patterns;
a calculation unit that selects the candidate pattern such that the constraint condition of the combination is satisfied and the value of the evaluation function is maximized or minimized, and adds the candidate pattern to a selected pattern;
a result presenting unit that presents the selected pattern when the evaluation function satisfies a criterion;
the evaluation function is configured by adding up the evaluation values of the candidate patterns included in the selected pattern,
The selected pattern may include a plurality of the same candidate patterns;
The model construction unit adds the listed candidate patterns when the evaluation function does not satisfy a criterion. 2. The optimization problem solving device according to claim 1, wherein, when the evaluation function does not satisfy a criterion, the model construction unit deletes the candidate patterns that were not selected by the calculation unit from among the candidate patterns added immediately before, and then adds the candidate patterns to be listed . the evaluation function includes a penalty term related to the constraint condition,
3. The apparatus for solving an optimization problem according to claim 1 , wherein the penalty term includes a slack variable. The optimization problem solving device according to claim 1 , further comprising a parameter updating unit that updates parameters included in the evaluation function. A method for solving an optimization problem, in which a combination of a plurality of products is treated as one manufacturing unit and a combinatorial optimization problem is solved by a computer to optimize one or more of the manufacturing units, comprising the steps of:
listing candidate patterns that may be the combination, and determining an evaluation value for each of the listed candidate patterns;
selecting the candidate pattern such that the constraint condition of the combination is satisfied and the value of the evaluation function is maximized or minimized, and adding the candidate pattern to the selected patterns;
presenting the selected pattern if the evaluation function satisfies a criterion ; and
adding the candidate patterns to the list when the evaluation function does not satisfy a criterion;
the evaluation function is configured by adding up the evaluation values of the candidate patterns included in the selected pattern,
The selected pattern may include a plurality of the same candidate patterns.

Images