JP7024580B2 - Mountain division plan creation device, mountain division plan creation method, and program - Google Patents

Description

The present invention relates to a mountain division plan creation device, a mountain division plan creation method, and a program, and is particularly suitable for use in creating a mountain division plan.

In the steel process, for example, when a steel material such as a slab is transported from the steelmaking process to the rolling process of the next process, the steel material is once carried into a temporary storage place called a yard and then placed in the rolling process (heating) which is the next process. It is carried out from the yard according to the processing time of the furnace). An example of the layout of the yard is shown in FIG. As shown in FIG. 11, the yard is composed of storage areas 1101 to 1104 partitioned vertically and horizontally as a buffer area for supplying steel materials and the like discharged from the upstream process to the downstream process. The vertical divisions are often referred to as "buildings" and the horizontal divisions are often referred to as "columns". Cranes (1A, 1B, 2A, 2B) are movable within the building and transfer steel materials between different rows within the same building. In addition, steel materials will be transferred between buildings using a transfer table. By specifying the "building" and "row" when creating a transport command, it is possible to command where to transport the steel material.

FIG. 11 shows a basic work flow in the yard as an example. First, the steel material carried out from the continuous casting machine 1110 in the steelmaking process, which is the previous process, is carried into the yard at the receiving table X via the piler 1111, and is partitioned by the cranes 1A, 1B, 2A, and 2B. It is transported to any of 1104 and placed in piles. Then, according to the production schedule of the rolling process, which is the next process, the cranes 1A, 1B, 2A, and 2B are placed on the payout table Z again and transported to the rolling process. Generally, steel materials are placed in a pile as described above in a yard. This is to make effective use of the limited yard area. On the other hand, when stacking steel materials, it is necessary to stack the steel materials from the top in the processing order of the next process so that they can be easily supplied to the next process. Furthermore, it is necessary to prevent steel materials from being stacked in an inverted pyramid shape, which is unstable in stacking. In this way, dividing the steel material into a plurality of optimum mountains (= payout mountain: the mountain that has become the final mountain shape to be paid out to the next process) is called mountain division.

Here, in order to reduce the fuel intensity of the heating furnace in the rolling process, which is the next process, it is required to dispense (charge) the steel material having the highest possible temperature into the heating furnace. For this reason, in recent years, heat insulating equipment has been installed in the yard, and steel materials are stored in a pile in the heat insulating equipment as described above. Even when the heat insulating equipment is used in this way, in order to make effective use of the heat insulating equipment, as in the case of directly stacking steel materials in the storage areas 1101 to 1104, the height of the payout mountain is as high as possible. It is necessary to create.

On the other hand, when stacking steel materials, the steel materials must be stacked from the top in the processing order of the next process so that they can be easily supplied to the next process, and the steel materials cannot be stacked in an inverted pyramid shape with an unstable stacking shape. There is a constraint (this is called a "stacking constraint"). Furthermore, the work load when piling up (this work load is called the heap load (load for transshipment of steel materials in the order of delivery from the top)) is also an element that cannot be overlooked. That is, in order to divide into piles, it is required that the number of transport operations for stacking is as small as possible due to the problem of work space and the capacity of transport equipment such as cranes for performing the work. In the case of mountain division, it would be ideal if steel materials could be piled up in the order of arrival at the yard. On the other hand, in order to eliminate the temporary placement (mountain rolling) at the time of paying out to the rolling process and to perform the payout work quickly, in the payout mountain, it is better to stack the ones that are quickly paid out to the heating furnace in the rolling process. It's basic. Therefore, in reality, the order of arrival at the yard and the order of product at the payout mountain may be different. That is, it may be necessary to stack the steel material with the earliest arrival in the yard on the upper stage of the same payout pile than the steel material with the slower arrival order. In that case, the steel materials that arrived in the yard first are temporarily placed in the temporary storage area until the steel materials that are relatively piled up in the lower tier arrive at the yard, and the steel materials that are relatively piled up in the lower tier arrive at the yard and pile up. After that, it is necessary to load the steel material of the temporary storage site on the steel material. Therefore, it is desirable to make a pile so that such work is reduced as much as possible.

As described above, in yard control, it is desirable to formulate a work plan for as high a mountain as possible with as little work load as possible under the above restrictions.
To solve the problem of stacking multiple sheets of steel with different sizes and processing orders in the next process (rolling process heating furnace) at the steel storage site, dividing them into multiple piles, all the piles that can be generated by the target steel are divided. From the candidates, it is indispensable to find a combination of mountain divisions that optimizes the evaluation function such as the mountain division load at the time of acceptance into the yard and the work load at the time of delivery to the heating furnace in the rolling process.

As a method for dealing with such a large-scale problem, Patent Document 1 states that none of the target steel materials must be used in a plurality of piles and must be used in any of the piles. , A method of creating a mountain division plan by finding the optimum combination of feasible mountains as a partition of a set problem is disclosed under the objective function that minimizes the total number of mountains and the mountain rolling load. Here, the feasible pile is a subset of the whole set whose elements are the target steel materials, and is a subset that satisfies the pile constraint. The stacking constraint is a constraint imposed when stacking steel materials. The stacking constraint includes the constraint that steel materials with a faster payout order must be placed on the upper side of the pile.

Since the method described in Patent Document 1 is an exact solution method, it can be expected to create an optimum mountain division plan for the total number of mountains set as the objective function and the mountain rolling load. Further, in Patent Document 1, only feasible piles are piled up (branched) from the bottom to the top in order so that the check of subsets that are unlikely to be feasible can be efficiently omitted. To generate.

However, when the technique described in Patent Document 1 is applied to a large-scale problem in which the number of steel element elements for which a mountain division plan is created is about 50 to 80, the number of feasible mountains often exceeds 100 million. In that case, the capacity of computer resources (mainly main memory) is limited, and the feasible mountains cannot be listed. In addition, even if the scale is not so large and the enumeration of feasible mountains is barely possible, the number of determinants will be the number of feasible mountains when optimally calculating the subsequent set partitioning problem. The memory capacity is exceeded on the way, or the situation cannot be solved within the practical time.

As a method of applying a set partitioning problem to obtain an optimum solution for such a large-scale problem in which feasible solutions cannot be enumerated, Patent Document 2 provides an alignment problem in natural language processing (two sequences are given). A method of using a column generation method is disclosed for the problem of finding which element of one series corresponds to which element of the other series when the problem is solved. The column generation method is a method of finding the optimum solution of the original problem by solving the partial problem of the original problem while sequentially adding variables instead of solving a large-scale linear programming problem at once. Therefore, it is conceivable to apply this method to the problem of mountain division in the yard.

Japanese Unexamined Patent Publication No. 2016-81186 JP-A-2015-170131 Japanese Unexamined Patent Publication No. 2011-105483

Mikio Kubo, Akihisa Tamura, Tomomi Matsui, "Applied Mathematical Planning Handbook", Asakura Shoten Co., Ltd., May 2002, p.133, 337, 621, 634

However, the technique described in Patent Document 2 only provides the framework of the solution method, and does not provide the solution method itself. Therefore, it is necessary to devise an application method according to the application target. Further, since the technique described in Patent Document 2 is premised on the alignment problem, it is not easy to apply the technique described in Patent Document 2 to the mountain division problem.
Further, although the column generation method is guaranteed to obtain the optimum solution of the linear programming problem by using it, it is applied to the 0-1 planning problem such as the partition of a set problem to be applied in the present invention. Can obtain a feasible solution (in the case of a minimization problem, the upper limit of the solution can be obtained), but it is not always guaranteed that the optimum solution can be obtained. This point remains an issue even in the factual Patent Document 2.

The present invention has been made in view of the above problems, and even when there are many target materials for mountain division, the error (dual gap) due to the binary constraint (0-1 constraint) in the mountain division plan is eliminated. The purpose is to ensure that it can be created based on the optimal solution.

The mountain division plan creating device of the present invention sets a problem of creating a mountain division plan for a plurality of target materials as a set division problem, and creates a mountain division plan by solving the set division problem using a column generation method. Regarding the heaping of the target material for the feasible mountain, using a binary variable that determines whether or not to adopt the feasible mountain piled up so as to satisfy a predetermined constraint as a solution. By finding the decision variable in which the value of the objective function including the column cost, which is the evaluation value, becomes the minimum or the maximum, the optimum combination of the feasible peaks including the plurality of target materials without duplication and omission is obtained. A column generation means for deriving the optimum solution of a column generator problem that generates a candidate mountain that is a candidate for a feasible mountain that constitutes the optimum solution of the original problem with the problem as the original problem, and a column generation means derived by the column generation means. If the set of candidate mountains does not satisfy the predetermined convergence requirements, the search for the feasible mountains in the vicinity where a part of the target material has a different configuration is searched for each candidate mountain included in the set. Based on the set of the feasible mountains including the search means for adding the feasible mountains in the vicinity as the candidate mountains, the candidate mountains derived by the column generation means, and the candidate mountains added by the search means. The first original problem deriving means for deriving the optimum value of the original problem by solving the original problem, and the realization corresponding to the optimum value of the original problem derived by the first original problem deriving means. It is characterized by having an output means for outputting information indicating a combination of possible peaks as information indicating an optimum solution of the original problem.

In the method for creating a mountain division plan of the present invention, a problem of creating a mountain division plan for a plurality of target materials is set as a set division problem, and the mountain division plan is created by solving the set division problem using a column generation method. Regarding the pile-up of the target material for the feasible mountain, using a binary variable that determines whether or not to adopt the feasible mountain piled up so as to satisfy a predetermined constraint as a solution. By finding the decision variable in which the value of the objective function including the column cost, which is the evaluation value, becomes the minimum or the maximum, the optimum combination of the feasible peaks including the plurality of target materials without duplication and omission is obtained. Using the problem as the original problem, the column generation step of deriving the optimum solution of the column generator problem in which the computer generates the candidate mountain which is a candidate of the feasible mountain that constitutes the optimum solution of the original problem, and the column generation step If the derived set of candidate ridges does not meet the predetermined convergence requirements, the computer will perform the near feasible ridges in the vicinity of each candidate ridge included in the set, with some of the target materials having different configurations. A search step of searching for and adding a feasible mountain in the vicinity of the search as the candidate mountain, a candidate mountain derived by the computer in the column generation step, and a candidate mountain added by the search step. The first original problem derivation step for deriving the optimum value of the original problem by solving the original problem based on the set of the feasible peaks including the computer, and the computer are derived by the first original problem derivation step. It is characterized by having an output step for outputting information indicating a combination of feasible peaks corresponding to the optimum value of the original problem as information indicating an optimum solution of the original problem.

The program of the present invention is characterized in that a computer functions as each means of the mountain division planning apparatus.

According to the present invention, even when there are many target materials for mountain division, the mountain division plan can be reliably created based on the optimum solution that eliminates the error (dual gap) associated with the binary constraint (0-1 constraint). can.

It is a figure which shows an example of the functional structure of the pile division plan making apparatus of a steel material. It is a figure which shows an example of the result of having performed the processing in the pre-processing part. It is a figure explaining the concept of 1 increase neighborhood mountain and 1 decrease neighborhood mountain. It is a figure which shows an example of the result of performing the processing in this processing part. It is a flowchart explaining an example of the method of making a pile division plan of a steel material. It is a flowchart following FIG. 5-1. It is a flowchart explaining the detail of the neighborhood search process (step S511 of FIG. 5-2). It is a flowchart following FIG. 6-1. It is a figure which conceptually shows an example of how this processing part increases. It is a figure which shows an example of the result of having performed the process of finding up to the 2nd neighborhood column in this processing part. It is a figure which shows an example of the creation result of the mountain division plan. It is a figure which shows an example of the calculation time in the method described in this Embodiment and the method described in <modification example 2>. It is a figure which shows an example of the layout of a yard.

Hereinafter, an embodiment of the present invention will be described with reference to the drawings.
(Original problem P (C))
First, the original problem P (C), which is a problem to be solved in this embodiment, will be described. In this embodiment, the original problem P (C) is a set partition problem. The partition of a set problem assumes that any subset S _j of the whole set N has its column cost c _j , and as shown in the following equation (1), the elements i of the whole set N are not duplicated and It is a problem of dividing into subsets m ₁ , m ₂ , ..., m _k without omission. At this time, the sum of the column costs c ₁ , c ₂ , ..., C _k for the subsets m ₁ , m ₂ , ..., M _k is set to the minimum. The following equation (1) represents that the element i of the whole set N is divided into subsets m ₁ , m ₂ , ..., M _k without duplication and omission.

A set of subsets of a whole set N = {1,2, ..., n} with n elements (set family) C = {m _1, ..., m _j , ..., m _k } Let c _j be the cost of the element m _j of (m _j ⊆ N). In the matrix A with i rows and j columns, the rows correspond to the element i (∈ N) and the columns correspond to the subset m _j (∈ C), and the element i is made of steel, and the subset m _j is a feasible mountain. do. Then, the mountain-building problem can be formulated as a 0-1 integer programming problem as follows.

<Coefficient of determination>
The coefficient of determination x [j] of the original problem P (C) is a 0-1 variable that is "1" when the feasible mountain m _j is adopted, and "0 (zero)" when it is not adopted.
<Constraint expression>
The constraint equation of the original problem P (C) is that for each of the steel materials i ∈ N, one subset m from the family of sets (set of subsets m _j ) M _j (i) ⊆ C including the steel material i. It is a constraint expression indicating that only _j must be selected, and is expressed by the following equation (2).
The steel material i may be a single steel material or a group of steel materials (transport lot) that can be transported by one transport device (crane 1A, 1B, 2A, 2B). Since a method for determining a transport lot is described in, for example, Patent Document 3, detailed description thereof will be omitted here.

Here, the element a _ij (element of i row j column) of the matrix A is defined as a _ij = 1 when the feasible peak m _j includes the steel material i, and a _ij = 0 when it does not include the steel material i. In this case, in a certain column j of the matrix A, the steel material i corresponding to the row having the value of "1" is the steel material constituting the feasible mountain corresponding to the column j, and in the column j, "0". The steel material i corresponding to the row having the value of "(zero)" does not constitute the feasible mountain corresponding to the column j. When the element a _ij of the matrix A is defined in this way, the equation (2) can be expressed by the matrix A as the following equation (2-1). Here, the right side of the equation (2-1) is a vector in which all the elements are "1". In each formula, those shown in bold represent vectors.

<Objective function>
The objective function of the original problem P (C) is a function whose purpose is to select the feasible mountain m _j so that the sum of the column costs c _j is minimized, and is expressed by the following equation (3). ..

The column cost c _j is an evaluation value for determining whether or not to select the feasible mountain m _j as the optimum solution of the original problem P (C), and evaluates the pile of steel material i for the feasible mountain m _j . It is determined based on one or more evaluation indicators. When the equation (3) is expressed in vector, it becomes the following equation (3-1).

In the present embodiment, the column cost c _j is obtained by multiplying the number c _1j of the feasible peaks (payout peaks) and the temporary placement number c 2 _j by the weight coefficients k ₁ and k ₂ , respectively. Details will be described later). Then, the objective function of the original problem P is expressed by the following equation (4). The relationship between the column cost c _j of the feasible mountain m _j (m _j ∈ C) and the mountain number c _1j and the temporary placement number c _2j is as shown in the following equation (4-1).

Here, since the number of the determinants x [j] having the value of "1" is the total number of mountains, the value of the number of mountains c _1j is "1" in any feasible mountain m _j . Therefore, in equation (4), the term for evaluating the number c _1j (the first term on the right side) is expressed separately from the term for evaluating the temporary number c _2j (the second term on the right side), which is another cost. ing. k ₁ and k ₂ are weighting coefficients, and are for balancing each evaluation index (mountain number c _1j , temporary placement number c _2j ). The relative weights of each evaluation index (mountain number c _1j , temporary placement number c _2j ) can be determined by the weighting coefficients k ₁ and k ₂ . For example, when the mountain number c _1j is used as an evaluation index (evaluation index to be evaluated with priority) more important than the temporary placement number c _2j , the value of the weighting coefficient k ₁ for the mountain number c _1j should be increased. At least one of reducing the value of the weighting coefficient k ₂ with respect to the temporary placement number c _2j is adopted. As described above, in this embodiment, the case where the objective function of the original problem P (C) is represented by a weighted linear sum of the term for evaluating the mountain number c _1j and the term for evaluating the temporary placement number c _2j is taken as an example. I will list it.

Here, the number of temporary placements will be described. As explained in the background technology section, the steel materials that arrived in the yard first are temporarily placed in the temporary storage area and then relatively piled up in the lower tier until the steel materials that are relatively piled up in the lower tier at the payout mountain arrive at the yard. After the steel materials arrive at the yard and are piled up, it is desirable to pile up the steel materials on the steel materials so that the work of stacking the steel materials in the temporary storage area is as small as possible. Since the number of transports increases by the number of such temporarily placed steel materials, the reduction in the number of temporarily placed steel materials is reflected in the reduction in the number of direct transports. In order to count the number of temporary placements, it is possible to stack any pair of steel materials (i ₁ , i ₂ ) ⊆ N ² on the same payout pile, and when stacking on the same payout pile, the order of arrival and stacking. A pair of steel materials whose order needs to be exchanged is defined as a reversing pair, and this set R (reversing pair set) is defined as the following equation (4-2). Here, (i ₁ , i ₂ ) means that the steel material i ₁ is a first-in first-out steel material (a steel material that arrives at the yard first and is delivered to the next process first) than the steel material i ₂ .

In this way, the reversal pair is a pair of steel materials that have a reversal relationship in which the steel material i ₁ with the earliest arrival order to the yard is piled up above the steel material i ₂ with the slower arrival order in the same payout mountain. Is defined as the inversion logarithm. If there is one reversal pair, in this example, the steel material i ₁ with the earliest arrival order becomes the steel material that requires the above-mentioned temporary placement. The reversal logarithm is a guideline for the number of temporary placements, because one pile is generated for temporary placement. In order to extract the reversal pair set R, information for determining the order of arrival of any steel material i at the yard and the stacking order at the payout pile (that is, the payout order) is required. The number of temporary placements is the steel material in consideration of not counting the same steel material twice for (i ₁ , i ₂ ) ∈ R among the steel material pairs (i ₁ , i ₂ ) included in the feasible mountain m _j . It is the count of i ₁ . For example, among the pairs of steel materials included in the feasible mountain mj, the set that is the element of R is ( _{i 1} , i ₂ ), (i ₁ , i ₄ ), (i ₃ , i ₄ ), (i ₃ ). , I ₅ ), (i ₂ , i ₅ ), the reversal logarithm is 5, but the steel materials to be temporarily placed are 3 of the reversal pairs, steel materials i ₁ , i ₃ , and i ₂ . At this time, the temporary placement number 3 is generally used for c _2j for this feasible mountain m _j , but the inversion logarithm 5 may also be used (see also the modification 3 described later). In this embodiment, c _2j uses a temporary placement number.

As described above, in the present embodiment, the problem of finding the decision variable x [j] that minimizes the value of the objective function J of the equation (4) within the range that satisfies the constraint equation of the equation (2) is solved as the original problem P (C). ). In the technique described in Patent Document 1, all feasible peaks m _j are generated from the entire set N of steel materials i that is the target of the mountain division plan, and these are set as the set C of feasible peaks m _j , and the original problem P ( Solve C). On the other hand, in the present embodiment, as will be described later, a column generation method is used to generate a feasible mountain m _j as much as necessary from the total set N of the steel materials i that is the target of the mountain division plan, and realize these. Solve the original problem P (C) as a set C of possible mountains m _j . Therefore, in this embodiment, (usually) the set C of the feasible mountains m _j does not include all the feasible mountains m _j , and the feasible mountains m _{j required to obtain the optimum feasible mountains m j .} Only candidates are generated by the column generation method.

In this embodiment, the case where the column cost c _j is the number of peaks c _1j and the number of temporary placements c _2j will be described as an example. However, the column cost c _j is not limited to the number of piles, the number of temporary placements, or the reversal logarithm as long as it is an evaluation index for evaluating the pile (realizable pile m _j ) of the steel material i. For example, the heat dissipation amount of the steel material i at the time of receiving the yard and at the time of paying out to the next process may be further included in the column cost c _j .

(Steel material pile division plan creation device 100)
Next, an example of a pile division plan making device for steel materials will be described. FIG. 1 is a diagram showing an example of a functional configuration of a steel material pile division plan creating device 100. The hardware of the steel material pile division plan creating device 100 is realized by using, for example, an information processing device having a CPU, ROM, RAM, HDD, various interfaces, and dedicated hardware.

As shown in FIG. 1, the steel material mountain division plan creating device 100 includes a steel material information acquisition unit 110, a pretreatment unit 120, a main processing unit 130, and an output unit 140.
((Steel material information acquisition unit 110))
The steel material information acquisition unit 110 acquires information on each of the steel materials i ∈ N for which the mountain division plan is created. In the following description, this information will be referred to as steel material information as necessary. The steel material information includes, for example, the ID (identification information) of the steel material, the size (width, length) of the steel material, the order of arrival of the steel material in the yard, and the order of delivery of the steel material to the next process. Is done. The arrival order and the payout order are relative orders in the steel materials included in the steel material information.

The steel material information acquisition unit 110 acquires steel material information from, for example, a steel material management device. However, this is not always necessary, and the steel material information acquisition unit 110 may acquire the steel material information input by the user's operation on the user interface of the steel material pile division plan creating device 100. The steel material information acquisition unit 110 is realized by using, for example, a CPU, ROM, RAM, and a communication interface (or user interface).

((Pretreatment unit 120))
In the preprocessing unit 120, the dual problem D (C) when the linear relaxation problem of the set partitioning problem (original problem P (C)) formulated as the 0-1 integer programming problem which is the original problem P is the main problem. Is solved using the column generation method. Therefore, first, the outline of the column generation method will be described.
<< Derivation of the optimal solution for the dual problem >>
In the column generation method, the linear relaxation problem of the original problem P (C) is solved based on the initial value of the set C of the feasible mountain m _j which is a candidate for the optimum solution of the original problem P (C) (partition of a set problem). The optimum solution of the dual problem D (C) is derived when the main problem is used (in the following description, the optimum solution of the dual problem D (C) is referred to as a dual solution as necessary).
<< Derivation of the optimal solution for the column generator problem >>
Then, the optimum solution of the column generator problem S is derived using the dual solution, and a feasible mountain m _j that is a candidate for the optimum solution of the original problem P (C) is generated.
<< Judgment of convergence requirements >>
Then, it is determined whether or not the generated feasible mountain m _j satisfies the convergence requirement. The convergence requirement here is the sum of the column cost c _j for the generated feasible mountain m _j and the values of the dual variables described later for the steel material included in the feasible mountain m _j (hereinafter, if necessary, the dual cost). If the dual cost exceeds the column cost c _j or the generated feasible mountain m _j is already included in the set C of the feasible mountain m _j , it is determined to be convergent.

<< Add column >>
As a result of this determination, if the feasible mountain m _j does not satisfy the convergence requirement, the generated feasible mountain m _j is added to the set C of the feasible mountain m _j , and the optimum solution of the above << dual problem is derived. Return to >>. When the convergence requirement is satisfied, the iterative processing is terminated and the preprocessing is terminated.
There are several different techniques collectively referred to as column generation methods, and the above method is one of them, but the column generation method itself is known as described in Non-Patent Document 1. Technology.

Hereinafter, an example of the function of the preprocessing unit 120 will be described.
<Initial column set setting unit 121>
The initial column set setting unit 121 is from the entire set N = {1,2, ..., i, ..., n} of the steel material i for which the mountain division plan is created, that is, from the steel material i included in the steel material information. , Set the initial value of the set C of the feasible mountain m _j . At this time, the initial column set setting unit 121 includes the steel material i included in the steel material information without duplication and omission, and further, a loading prohibition constraint (see the equation (17)) and a mountain height constraint ((18)) described later. The initial value of the set C of the feasible mountain m _j is set so as to satisfy (see the equation). As an example, in the present embodiment, in the initial column set setting unit 121, as shown in the following equation (5), each feasible mountain m _j has only one arbitrary steel material i that is different from each other as an element. As described above, the initial value of the set C of the feasible mountain m _j is set.

For example, the user inputs the information of the initial value of the set C of the feasible mountain m _j by operating the user interface of the steel material mountain division plan creation device 100, and the initial column set setting unit 121 performs the steel material mountain division plan. By storing the information in the storage medium in the creating device 100, the initial value of the set C of the feasible peaks m _j can be set. However, this is not always necessary, and for example, the initial column set setting unit 121 may derive the initial value of the set C of the feasible mountain m _j by a predetermined logic. The initial column set setting unit 121 is realized by using, for example, a CPU, a ROM, a RAM, and a user interface.

<Dual solution derivation unit 122>
The dual solution derivation unit 122 derives a dual solution which is the optimum solution of the dual problem D (C) when the linear relaxation problem of the above-mentioned original problem P (C) (partition of a set problem) is used as the main problem. The original problem P (C) itself is a 0-1 integer programming problem, but the dual problem D (C) is a linear relaxation problem (linear programming problem). The dual problem D (C) when the linear relaxation problem of the original problem P (C), which is a 0-1 integer programming problem, is the main problem, can be formulated as follows from the relationship between the main problem and the dual problem. ..

Since the original problem P (C) is a minimization problem, the dual problem D can be obtained by considering the problem of finding the optimum lower limit value of the objective function J shown in the equation (3-1). Therefore, consider a variable p ^T that satisfies the following equation (6) (p ^T is a vector).

When x (≧ 0) is multiplied from the right on both sides of the equation (6), the following equation (7) holds (x is a vector as shown in the equation (3-1)).

That is, the left side (= p ^T Ax) of Eq. (7) is the lower limit of the objective function J of the original problem P (C). In order to give a better lower limit value of the objective function J of the original problem P (C), the left side (= ^pTAx ) of the equation (7) is set under the condition of the equation (6) (= ^pTA≤c ). Consider the problem of maximizing. Here, the following equation (8) holds from the constraint equation (2-1) of the original problem P (C).

Therefore, the dual problem D (C) is formulated as follows. Since the dual problem itself, whose main problem is the linear relaxation problem of the partition of a set problem, can be realized by a known technique as described in Non-Patent Document 1, detailed description thereof will be omitted here.

[Coefficient of determination]
In this embodiment, the dual variable p [i] is used as the determinant of the dual problem D (C).
The dual variable p [i] is a continuous variable (−∞ <p [i] <∞) determined for each steel material i. The number of dual variables p [i] is n (the number of steel materials i included in the steel material information).

[Constraint expression]
The constraint equation of the dual problem D (C) is expressed by the above-mentioned equation (6). Here, the matrix A corresponds to the set C of the feasible peaks m _j generated during the calculation of the dual solution derivation unit 122. In the first calculation of the dual solution derivation unit 122, the matrix A corresponds to the initial value of the set C of the feasible peak m _j set by the initial column set setting unit 121.
When the equation (6) is expressed for each element, the constraint equation of the dual problem D (C) is expressed by the following equation (9). The left side (Σp [i] · m _j [i] (= P _j )) of the equation (9) is the same as the above-mentioned “dual cost”. As shown in the equation (9), the dual cost P _j is the value of the dual variable p [i] with respect to the steel material i and the value in the column j of the matrix A, and the value in the row i corresponding to the steel material i ( It is represented by the sum of the products of "0 (zero)" or "1") for the steel material i included in the steel material information.

In equation (9), m _j [i] is the j column itself of the matrix A, and if the feasible mountain m _j corresponding to the j column is the steel material i, it is "1", otherwise it is "0 (zero)". ) ”, Which is a 0-1 variable. Therefore, the number of the constraint equations in Eq. (9) is the number of feasible peaks m _j (columns) generated during the calculation of the dual solution derivation unit 122 (that is, the elements of the set C of the feasible peaks m _j ). Number).

[Objective function]
Under the conditions of Eq. (6), the following Eq. (10) holds from Eqs. (7) and (8), so Σp [i] of Eq. (8) is the lower limit of cx ((3-3-). 1) As shown in the equation, c and x are vectors). If Σp [i] is obtained as large as possible, a better lower limit value of the objective function J of the original problem P (C) can be obtained. Therefore, the objective function J of the dual problem D (C) becomes a maximization problem, and is as shown in the following equation (11).

As described above, in the present embodiment, the problem of finding the dual variable p [i] that maximizes the value of the objective function J of the equation (11) within the range satisfying the constraint equation of the equation (9) is solved by the dual problem D (C). ). Therefore, the dual solution derivation unit 122 performs an optimization calculation by a linear programming method using a known solver such as CPLEX (registered trademark), for example, to the extent that the constraint equation of Eq. (9) is satisfied (11). ) The dual variable p [i] that maximizes the value of the objective function J of the equation is derived as the optimum solution of the dual problem D.
The dual solution derivation unit 122 is realized by using, for example, a CPU, a ROM, a RAM, and an HDD.

<Column generator 123>
By solving the column generator problem S, the column generator 123 derives a candidate for the optimum solution of the original problem P, that is, a candidate for the feasible mountain m _j to be added to the set C of the feasible mountain m _j . Since the column j of the matrix A corresponds to the feasible mountain m _j as described above, the column generation unit 123 derives the elements of the column j added to the matrix A.

In the present embodiment, the column generator problem S has a dual cost P _j (= Σp [i] · m _j [= from the column cost c _j of the feasible mountain m _j to the feasible mountain m _j . The problem is to find the feasible peak m _j that minimizes the value obtained by subtracting i]) (see equation (12) below).

[Coefficient of determination]
In the present embodiment, the pile constituent steel material presence / absence variable m _j [i], the steel material vertical relation variable y [i ₁ ] [i ₂ ], and the temporary placement presence / absence variable t [i] are used as the decision variables of the column generator problem S. ..
The variable for presence / absence of mountain constituent steel material m _j [i] is the same variable as m _j [i] shown in Eq. (9). The mountain composition steel material presence / absence variable m _j [i] is determined for each steel material i, and is "1" when the feasible pile m _j includes the steel material i, and "0 (zero)" when it is not. -1 variable.
In the steel material vertical relation variables y [i ₁ ] and [i ₂ ], the steel material i ₁ is placed relatively above and the steel material i ₂ is placed relatively below in the same feasible pile m _j (payout pile). It is a 0-1 variable that becomes "1" when it is used, and "0 (zero)" when it is not.
The temporary placement variable t [i] is a 0-1 variable that becomes "1" when the steel material i is temporarily placed, and becomes "0 (zero)" when the steel material i is not placed.

[Constraint expression]
In the present embodiment, the steel material vertical relation variable definition constraint formula, the temporary placement variable definition constraint formula, the loading prohibition constraint formula, and the mountain height constraint formula are used as the constraint formulas of the column generator problem S.
The steel material vertical relation variable definition constraint formula is a constraint formula for defining the steel material vertical relation variable y [i ₁ ] [i ₂ ], and is represented by the following equations (13) to (15).

The temporary placement variable definition constraint formula is a constraint formula for defining the temporary placement presence / absence variable t [i] using the steel material vertical relation variables y [i ₁ ] [i ₂ ], and is the following formula (16). expressed.

Here, R is an inversion pair set defined by Eq. (4-2). As described above, the steel material vertical relation variables y [i ₁ ] [i ₂ ] place the steel material i ₁ relatively above and the steel material i ₂ relative to each other in the same feasible pile m _j (payout pile). It is a 0-1 variable that becomes "1" when it is placed below, and becomes "0 (zero)" when it is not. For example, when steel materials i _A , i _B , and i _C are arranged on the same pile and (i _A , i _B ), (i _A , i _C ) ∈ R, y [i _A ] [i _B ] = 1 , Y [i _A ] [i _C ] = 1, so from equation (16), t [i _A ] = 1.

The inversion logarithm is a guideline for the number of temporary placements, but they do not correspond strictly. For example, the payout order of steel materials i _A , i _B , and i _C placed on the same pile is "1", "2", and "3" (i _A → i _B → i _C ), and they arrive at the yard. It is assumed that the order is "1", "3", and "2" (i _A → i _C → i _B ). In this case, there are two reversal pairs (i _A , i _B ) and (i _A , i _C ) (the reversal logarithm is "2"). On the other hand, in this case, since only the steel material _iA needs to be temporarily placed, the number of temporary placements is "1". In this way, the reverse logarithm may exceed the temporary placement number, and the reverse logarithm may not be able to strictly evaluate the temporary placement number. Therefore, in the present embodiment, the temporary placement variable t [i] is used in order to strictly evaluate the temporary placement number.

The loading prohibition constraint formula is an example of a stacking constraint, and is a constraint formula that defines a steel material that cannot be placed on the steel material i in the same feasible pile m _j (payout pile). Assuming that the set of steel materials that cannot be placed on the steel material i in the same feasible mountain m _j (payout mountain) is U (i)-and the element is i _U , the loading prohibition constraint equation is as follows. It is expressed by the equation (17). It should be noted that U (i)-cannot be placed on the steel material i in the equation (17), which is obtained by subtracting-on U (i) (the same feasible mountain m _j (payout mountain)). A set of steel materials). In the following description, a set of steel materials that cannot be placed on the steel material i in the same feasible pile m _j (payout pile) is referred to as a no-loading set as necessary.

The overload prohibited set U (i)-can be determined according to the yard management method and the like, and can be determined, for example, as follows. In the pile up in the yard, in order to smoothly pay out the steel material i to the next process, it is necessary to pile up the steel material i in the same feasible pile m _j (payout pile) in the earlier payout order. In addition, in order to stabilize the stacking shape of the feasible mountain m _j (payout mountain), it is necessary to avoid stacking in an extremely inverted pyramid shape. That is, the value obtained by subtracting the width / length of the steel material i relatively piled up from the width / length of the steel material i placed relatively above in the same feasible mountain m _j (payout mountain) is obtained. , It is necessary not to exceed the specified value. These requirements uniquely determine whether or not another steel material can be placed on the steel material i in the same feasible pile m _j (payout pile). The column generation unit 123 puts a set of steel materials that do not meet these requirements for each steel material i included in the steel material information based on the size and the payout order of the steel materials included in the steel material information. Derived as.

The mountain height constraint formula is an example of a pile constraint, and is a constraint formula that defines the maximum value of the height of one feasible mountain m _j (payout mountain), and is expressed by the following formula (18).

In the equation (18), nmb [i] is the number of steel materials i. As described above, in the present embodiment, the steel material i is a group of steel materials (multiple steel materials) that can be transported by one transport device (crane 1A, 1B, 2A, 2B) even if it is one steel material. There may be. When one transport device (crane 1A, 1B, 2A, 2B) cannot transport two or more steel materials and the steel material i corresponds to each steel material, nmb [i] in the formula (18) is , Becomes "1". Further, let h _max be the maximum number of piles (the maximum number of steel materials that can be piled up in one feasible pile m _j (payout pile)). However, the mountain height constraint equation does not necessarily have to be the equation (18). For example, when the thickness of each steel material i is different, the following may be performed. First, the thickness of the steel material i is included in the steel material information, and the mountain constituent steel material presence / absence variable m _j [i] for the steel material i is multiplied by the thickness of the steel material i, but all the steel materials i included in the steel material information A mountain height constraint equation may be used to indicate that the sum is less than or equal to the maximum value of the height of one feasible mountain m _j (payout mountain).

[Objective function]
From the relationship between the main problem and the dual problem (weak duality theorem), the value of the objective function of the main problem is originally greater than or equal to the value of the objective function of the dual problem when the main problem is the minimization problem. In this embodiment, the objective function of the main problem is Eq. (3), and the objective function of the dual problem is Eq. (11). Therefore, originally, the column cost c _j of the feasible mountain m _j is equal to or greater than the dual cost P _j for the feasible mountain m _j (c _j ≧ P _j ). Further, when the column cost c _j of the feasible mountain m _j and the dual cost P _j for the feasible mountain m _j are equal (c _j = P _j ), the solutions of the main problem and the dual problem are the optimum solutions, respectively. ..

Therefore, if the column cost c _j of the feasible mountain m _j is less than the dual cost P _j for the feasible mountain m _j (c _j <P _j ), the dual solution of the dual problem D (C) is dual. It is not the optimal solution for problem D (C). That is, in this case, the feasible mountain m _j is not sufficiently added to the set C (matrix A) of the feasible mountain m _j . Therefore, when the column cost c _j of the feasible mountain m _j becomes the dual cost P _j or less (c _j ≤ P _j ) with respect to the feasible mountain m _j , the feasible mountain m _j (mountain constituent steel material presence / absence variable m _j ). [I]) is a candidate for the optimum solution of the original problem P (C) and needs to be added to the set C (matrix A) of the feasible mountain m _j .

From the above, in the column generator problem S of the present embodiment, the column cost c _j of the feasible mountain m _j is feasible so that the dual cost P _j or less (c _j ≤ P _j ) for the feasible mountain m _j . The main purpose is to find the mountain m _j (mountain constituent steel material presence / absence variable m _j [i]). Therefore, in the present embodiment, the incurred cost (= c _j −P _j : the value obtained by subtracting the dual cost P _j for the feasible mountain m _j from the column cost c _j of the feasible mountain m _j ) becomes the minimum. Let the column generator problem S be a problem in which the feasible mountain m _j (mountain constituent steel material presence / absence variable m _j [i]) is obtained as a candidate for the optimum solution of the original problem P (C). The feasible mountain m _j (mountain) is determined by determining whether or not the minimum value of the incurred cost (= c _j −P _j ) is “0 (zero)” or less (that is, c _j ≦ P _j ). This is because it can be determined whether or not the constituent steel material presence / absence variable m _j [i]) should be added to the set C (matrix A) of the feasible peak m _j .

The column cost c _j of the feasible mountain m _j determined by the mountain constituent steel material presence / absence variable m _j [i], which is the coefficient of determination of the column generator problem S, is (4-1) when the temporary placement / absence variable t [i] is used. ) Is expressed by the following equation (19).

Here, the second term on the right side of Eq. (19) corresponds to the number of temporary placements in the feasible mountain m _j .

Further, as described above, the dual cost P _j is represented by the left side of the equation (9), so that it is as shown in the following equation (20).

As described above, in the present embodiment, the column generator problem S is a feasible mountain m _j when the incurred cost (= c _j − P _j ) is minimized (mountain constituent steel material presence / absence variable m _j [i]). It is a problem to ask for. Therefore, the objective function J _S of the column generator problem S can be obtained by subtracting the equation (20) from the equation (19), but the first term on the right side of the equation (19) is a constant, so this is excluded. When expressed as, it becomes the following equation (21).

As described above, the decision variable that minimizes the value of the objective function _{J S} of Eq. (21) within the range that satisfies the constraint equations of Eqs. , The steel material vertical relation variable y [i ₁ ] [i ₂ ], and the temporary placement presence / absence variable t [i]) may be derived as the optimum solution of the column generator problem S.
By the way, the column generator problem S is a 0-1 integer programming problem and can be solved repeatedly. Therefore, the calculation time of the column generator problem S largely depends on the total calculation time. Therefore, in order to speed up the column generator problem S, the following method is adopted in this embodiment.

As described above, in the column generator problem S, the column cost c _j of the feasible mountain m _j is less than or equal to the dual cost P _j for the feasible mountain _{m j} (c _j ≤ P _j ). The main purpose is to find the mountain composition steel material presence / absence variable m _j [i]). Therefore, if this main purpose is achieved, the value (= c _j − P _j ) obtained by subtracting the dual cost P _j for the feasible mountain m _j from the column cost c _j of the feasible mountain m _j is not necessarily achieved. It is considered unnecessary to find the minimum value.
Therefore, in the present embodiment, the column cost c _j of the feasible mountain m _j is equal to or less than the dual cost P _j for the feasible mountain m _j (c _j ≤ P) in the constraint equations of the equations (13) to (18). Add a further constraint expression that is _j ). That is, the constraint equation of the following equation (22) is added.

When adding the constraint equation of the equation (22), it is only necessary to obtain an executable solution, so the calculation is terminated as soon as the executable solution is obtained.
Therefore, in the present embodiment, the column generation unit 123 uses a known solver such as CPLEX (registered trademark) to perform optimization calculation by the 0-1 integer programming method, whereby equations (13) to (18) are used. , Determining variable that minimizes the value of the objective function _{J S} in Eq. (21) within the range that satisfies the constraint equation in _Eq . ] [I ₂ ], and the temporary placement variable t [i]) is derived. Then, the column generation unit 123 is derived from the derived decision variables (mountain-constituting steel material presence / absence variable m _j [i], steel material vertical relation variable y [i ₁ ] [i ₂ ], and temporary placement presence / absence variable t [i]). From equations (19) and (20), the column cost c _j of the feasible mountain m _j and the dual cost P _j for the feasible mountain m _j are derived. As will be described later, even if the calculation of the column generator problem S is discontinued with the dual gap remaining, the reduced cost (= c _j − P _j ), which is the optimum condition of the generated column, is obtained by Eq. (22). ) Is 0 or less is satisfied.
The column generation unit 123 is realized by using, for example, a CPU, a ROM, a RAM, and an HDD.

<Column determination unit 124>
As described above, when the column cost c _j of the feasible mountain m _j is less than or equal to the dual cost P _j for the feasible mountain m _j (c _j ≤ P _j ), the set C of the feasible mountain m _j . The feasible mountain m _j is not sufficiently added to (matrix A). Therefore, the column determination unit 124 determines whether or not the incurred cost (= c _j −P _j ) is “0 (zero)” or less. If there is a constraint in equation (22), if a feasible solution is obtained, the incurred cost (= c _j -P _j ) will be "0 (zero)" or less, so it is feasible. Whether or not a solution is obtained matches the above-mentioned determination condition.

As a result of this determination, when the incurred cost (= c _j −P _j ) is “0 (zero)” or less, the column determination unit 124 has a feasible peak m based on the pile constituent steel material presence / absence variable m _j [i]. It is determined whether or not _j is included in the set C (matrix A) of the feasible mountain m _j . As a result of this determination, if the feasible crest m _j based on the crest constituent steel material presence / absence variable m _j [i] is not included in the set C of the feasible crests m _j , it is derived by the column generation unit 123 ( It is necessary to add the feasible crest m _j based on the latest) crest constituent steel material presence / absence variable m _j [i] to the set C (matrix A) of the feasible crest m _j . On the other hand, when the incurred cost (= c _j -P _j ) exceeds "0 (zero)", the feasible mountain m _j based on the pile constituent steel material presence / absence variable m _j [i] is the feasible mountain m _j . If it is included in the set C, even if the feasible mountain m _j is added to the set C (matrix A) of the feasible mountain m _j any more, the feasible mountain m _j is the original problem P (C). It can be considered that it is not a candidate for the optimum solution of.
The column determination unit 124 is realized by using, for example, a CPU, a ROM, a RAM, and an HDD.

<Column addition part 125>
In the column addition unit 125, the value (= c _j − P _j ) obtained by subtracting the dual cost P _j for the feasible mountain m _j from the column cost c _j of the feasible mountain m _j by the column determination unit 124 is “0”. If it is determined to be "(zero)" or less, the feasible mountain m _j based on the (latest) mountain constituent steel material presence / absence variable m _j [i] derived by the column generator 123 is obtained from the feasible mountain m _j . Add to set C (matrix A). For example, the column addition section 125 is placed in the next column after the last column of the current matrix A, and is a feasible peak m based on the (latest) pile constituent steel material presence / absence variable m _j [i] derived by the column generation unit 123. Add the information of _j .
The column addition unit 125 is realized by using, for example, a CPU, a ROM, a RAM, and an HDD.

<Repeat calculation after adding feasible mountain m _j >
When the feasible mountain m _j is added by the column addition unit 125 as described above, the number of columns of the matrix A in the equation (6) increases. Therefore, the dual solution derivation unit 122 uses a new matrix A to maximize the value of the objective function J of the equation (11) within the range satisfying the constraint equation of the equation (6) or the equation (9). Derivation of p [i].

Further, the column generation unit 123 uses the dual variable p [i] derived in this way to the extent that the constraint equations of Eqs. (13) to (18) and (22) are satisfied (21). Determinants that minimize the value of the objective function J _S of the equation (mountain-constituting steel material presence / absence variable m _j [i], steel material vertical relation variable y [i ₁ ] [i ₂ ], and temporary placement / presence / absence variable t [i]) Is derived. Then, the column generation unit 123 is derived from the derived decision variables (mountain-constituting steel material presence / absence variable m _j [i], steel material vertical relation variable y [i ₁ ] [i ₂ ], and temporary placement presence / absence variable t [i]). From equations (19) and (20), the column cost c _j of the feasible mountain m _j and the dual cost P _j for the feasible mountain m _j are derived.

Then, the column determination unit 124 uses the column cost c _j of the feasible mountain m _j derived in this way and the dual cost P _j for the feasible mountain m _j , and the incurred cost (= c). It is determined whether or not _j −P _j ) is “0 (zero)” or less. As a result of this determination, if the incurred cost (= c _j -P _j ) is "0 (zero)" or less, the (latest) mountain constituent steel material presence / absence variable m _j [the latest) derived by the column generator 123 [ It is determined whether or not the feasible mountain m _j based on i] is included in the set C (matrix A) of the feasible mountain m _j , and if it is not included, the column addition unit 125 is the column generation unit. The feasible crest m _j based on the (latest) crest constituent steel material presence / absence variable m _j [i] derived by 123 is added to the set C (column of the matrix A) of the feasible crest m _j .

The above processing is performed until the column determination unit 124 determines that the incurred cost (= c _j −P _j ) exceeds “0 (zero)”, or the feasible mountain m _j is the feasible mountain at that time. This is repeated until it is determined that the set C (matrix A) of m _j is already included. In the following description, the set C of the feasible mountain m _j obtained at the time when the column determination unit 124 determines that it is not necessary to add the feasible mountain m _j to the column of the matrix A can be realized as needed. It is called a set C _cg of mountains m _j . Further, the optimum solution p [i] of the dual problem D (C _cg ) derived by the dual solution derivation unit 122 immediately before it is determined that the feasible mountain m _j is not required to be added to the column of the matrix A by the column determination unit 124. Is referred to as a dual optimal solution p [i], if necessary. Further, the value of the objective function J in the equation (11) when the optimum solution p [i] of the dual problem D (C _cg ) is obtained is referred to as a dual optimum value V _D (C _cg ), if necessary. ..

((Main processing unit 130))
When the above preprocessing unit 120 is applied to an actual problem, the present inventors apply the optimum solution of the column generator problem S before the incurred cost (= c _j − P _j ) exceeds “0 (zero)”. It is easy to happen that m _{j_opt} [i] (i ∈ N) (optimal solution of the mountain constitutive steel material presence / absence variable m _j [i]) is already included in the set C _cg of the feasible mountain m _j , and this realization. Solving the original problem P (C _cg ) for the set C _cg of possible peaks m _j minimizes the value of the objective function J in equation (4) within the range that satisfies the constraint equation in equation (2) x [ j] (optimal solution)), it was found that the error of the optimum value of the objective function J becomes large. FIG. 2 is a diagram showing in a table format an example of the result of processing in the pretreatment unit 120 using 10 types of steel material information in which the number n of steel materials is 50 (n = 50).

In FIG. 2, "Data" is an identification number of 10 kinds of steel material information. The “repetition number” indicates the number of repetitions of the above-mentioned <repetition calculation after adding the feasible mountain m _j > (the number of repetitions of the dual solution derivation unit 122, the column generation unit 123, and the column determination unit 124). The VP (C _cg ) is the original problem _P for the set C _cg of the feasible mountain m _j obtained at the time when the column determination unit 124 determines that the feasible mountain m _j is not required to be added to the column of the matrix A. The optimum value of (C _cg ) (the value of the objective function J of the equation (4) that is the minimum within the range that satisfies the constraint equation of the equation (2)) (in the following description, this optimum value is used as necessary. It is called the optimum value of the original problem. Also, the determinant x [j] when the optimum value of the original problem is obtained (“1” when the feasible peak m _j is adopted, and “0 (zero)” when it is not adopted. The value of _{0-1 variable} ) that _becomes Is not necessary to be added to the _column of the _{matrix A.} Is the minimum value of the objective function of Eq. (11)). VP (C _{all) is the optimum value of the original problem P (C all ) for} the set C _all of all feasible peaks m _j (that is, The relative error is the relative error of the original problem optimum value _{VP (C cg )} with respect to the true optimum value _VP (C _all ) (= {( _VP (C _cg ) _-VP ). (C _all )) ÷ _VP (C _all )} × 100) is shown.

As shown in FIG. 2, it can be seen that the relative error exceeds 40% at the maximum value and exceeds 20% at the average value.
The column generation method is originally a solution to a linear programming problem, but the preprocessing unit 120 applies the column generation method to the original problem P (C) which is a 0-1 integer programming problem. From this, it is considered that a relative error as shown in FIG. 2 occurs. The reason why the relative error occurs due to such a cause is that the optimum value _{VP (C cg )} of the original problem is equal to or less than the true optimum value _VP (C _all ) in FIG. It can be inferred that the dual optimal solution V _D (C _cg ) of C _cg ) is in agreement with the optimal value _VP (C _all ) in which the 0-1 condition is relaxed as a linear programming problem.

Therefore, the present inventors considered to reduce such a relative error. The relative error occurs in the set C _cg of the feasible peaks m _j obtained by the preprocessing unit 120, the columns required to construct the optimum solution of the 0-1 integer programming problem (realizable peaks m _j ). It is thought that this is due to the lack of. That is, in order to make the covering condition (Σx [j] = 1) shown above the equation (2) compatible with the 0-1 condition (x [j] ∈ {0,1}) shown below the equation (2). Unlike the dual problem D (C) without the 0-1 condition, the matrix A requires a considerable number of columns in which the incurred cost (= c _j -P _j ) is near "0 (zero)". Conceivable. It should be noted that not only the column in which the incurred cost (= c _j -P _j ) is "0 (zero)" but also the column in which the incurred cost (= c _j -P _j ) is near "0 (zero)" is required, as shown in the figure. The dual optimum value V _D (C _cg ) is the true optimum value V _P (C _all ), such as 2 Data "1", "3", "6", "7", "8", "9". This is because there are cases where the value is less than (V _D (C _cg ) < _VP (C _all )). In other words, in the case where such a dual gap remains, it means that the column whose incurred cost (= c _j -P _j ) exceeds "0 (zero)" is also included in the true optimal solution (note that). , It is guaranteed by the duality theorem that the incurred cost (= c _j -P _j ) never falls below "0 (zero)").

Therefore, the present inventors have investigated a method for compensating for the missing row (feasibility mountain m _j ). Here, the optimum solution of the original problem P (C _all ) for the set C _all of all feasible mountains m _j (determined variable x [j]: "1" when adopting the feasible mountain m _j , otherwise. A 0-1 variable that becomes "0 (zero)") is referred to as an optimal solution composition column. Further, a column (feasibility peak m _j ) that can be an optimal solution candidate sequence is referred to as an optimal solution configuration candidate sequence. It is a necessary condition that the optimal solution configuration candidate column is a column in which the incurred cost (= c _j − P _j ) is in the vicinity of “0 (zero)”. On the other hand, if the optimum value (original problem optimum value) VP (C _s ) of the original problem _P (C _s ) for the column C _s extracted by some method satisfies the following equation (23), the column C It can be said that _s is a sufficient sequence for finding the optimum solution of the original problem P (C _all ) for the set C _all of all feasible mountains m _j . This is because, in the 0-1 integer programming problem, if the coefficient of the objective function is an integer, it is not possible to take a solution with a decimal number, and according to the dual theorem, V _D (C _cg ) ≤ V _P (C _all ), so it is true. This is because the optimum value V _P (C _all ) of is satisfied with V _D (C _cg ) ≤ V _P (C _all ) <V _D (C _cg ) +1.

In the present embodiment, the processing unit 130 is considered to be sufficient for finding the optimum solution of the original problem P (C _all ) for the set C _all of all feasible mountains m _j based on such an idea. The column is extracted by the neighborhood search of the set C _cg of the feasible mountain m _j obtained at the time when the column determination unit 124 determines that the feasible mountain m _j is not required to be added to the column of the matrix A. Hereinafter, an example of the function of the processing unit 130 of the present embodiment will be described in detail. In the following description, the set C _cg of the feasible mountain m _j obtained at the time when the column determination unit 124 determines that the feasible mountain m _j is not required to be added to the column of the matrix A is previously added as necessary. It is referred to as a set C _cg of feasible peaks m _j obtained by the processing unit 120.

In FIG. 1, the processing unit 130 includes a dual optimum value acquisition unit 131, a preprocessing original problem derivation unit 132, a processing execution determination unit 133, a neighborhood search unit 134, and a processing original problem derivation unit 135.

<Dual optimal value acquisition unit 131>
The dual optimum value acquisition unit 131 acquires the dual optimum value V _D (C _cg ). As described above, the dual optimum value V _D (C _cg ) is the optimum value of the dual problem D (C _cg ) for the set C _cg of the feasible peaks m _j obtained by the preprocessing unit 120 ((9). It is the minimum value of the objective function of Eq. (11) in the range that satisfies the constraint equation).
The dual optimum value acquisition unit 131 is realized by using, for example, a CPU, a ROM, a RAM, and an HDD.

<Preprocessing original problem derivation unit 132>
The preprocessing original problem derivation unit 132 derives the original problem optimum value _{VP (C cg )} and the original problem optimum solution x [j]. As described above, the original problem optimum value V _P (C _cg ) is obtained when the original problem P (C _cg ) for the set C _cg of the feasible peaks m _j obtained by the pretreatment unit 120 is solved ((2). ) Objective function J (when the decision variable x [j] (optimal solution of the original problem) that minimizes the value of the objective function J in equation (4) is obtained within the range that satisfies the constraint equation in equation (4). ) Is the value.
The preprocessing original problem derivation unit 132 is realized by using, for example, a CPU, a ROM, a RAM, and an HDD.

<Main processing implementation determination unit 133>
The processing execution determination unit 133 has a dual optimum value V _D (C _cg ) acquired by the dual optimum value acquisition unit 131 from the original problem optimum value _VP (C _cg ) derived by the preprocessing original problem derivation unit 132. It is determined whether or not the value obtained by subtracting is less than "1" (whether or not _{VP (C cg )} -V _D (C _cg ) <1 holds). As a result of this determination, if the value obtained by subtracting the dual optimum value V _D (C _cg ) from the original problem optimum value _VP (C cg) is _less than "1", the feasible mountain m _j obtained by the preprocessing unit 120. From the set C _cg of, it is judged that a sufficient sequence is obtained for finding the optimum solution of the original problem P (C _all ) for the set C _all of all feasible mountains m _j . On the other hand, if the value obtained by subtracting the dual optimum value V _D (C _cg ) from the original problem optimum value _VP (C _cg ) does not fall below "1", the set of feasible peaks m _j obtained by the preprocessing unit 120. In C _cg , it is determined by the preprocessing unit 120 that a sufficient sequence is not obtained for finding the optimum solution of the original problem P (C _all ) for the set C _all of all feasible peaks m _j .
The processing execution determination unit 133 is realized by using, for example, a CPU, a ROM, a RAM, and an HDD.

<Neighborhood search unit 134>
In the neighborhood search unit 134, the processing execution determination unit 133 uses the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120 to solve the original problem P (C) for the set C _all of all the feasible mountain m _j . It is activated when it is determined that a sufficient column is not obtained for the solution of the optimum solution of _all ). The neighborhood search unit 134 is a column not included in the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120, based on the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120. (Feasible mountain m _j ) is searched and added to the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120.

In the present embodiment, the neighborhood search unit 134 extracts the feasible mountain m _j in the vicinity of the set C c _g of the feasible mountain m _j obtained by the pretreatment unit 120. Specifically, the neighborhood search unit 134 constitutes each column of the "0 (zero)" element (matrix A) of the feasible mountain m _j for each of the feasible mountain m _j obtained by the preprocessing unit 120. Search for a feasible mountain m _{j_np} where any one of the elements) is set to "1". In the following description, the feasible mountain searched in this way is referred to as a 1-increased neighborhood mountain m _{j_np} , if necessary. As shown in FIG. 3, the 1-increased neighborhood m _{j_np} is located at the top, bottom, or between two adjacent steel materials of the feasible crest m _j obtained by the pretreatment section 120. , It is a feasible mountain with one additional steel material. Further, the neighborhood search unit 134 sets any one of the elements of "1" of the feasible mountain m _j to "0 (zero)" for each of the feasible mountain m _j obtained by the preprocessing unit 120. Search for the feasible mountain m _{j_nm} . In the following description, the feasible mountain searched in this way is referred to as a 1-reduction neighborhood mountain m _{j_nm} , if necessary. As shown in FIG. 3, the 1-decreased neighborhood m _{j_nm} is a feasible mountain obtained by removing any one of the steel materials constituting the feasible mountain m _j obtained by the pretreatment unit 120. The rectangle shown in FIG. 3 represents one steel material i, and all the vertically arranged rectangles (steel materials) collectively represent one feasible mountain m _j .

When the total set N of steel materials is N = {1,2,3,4,5} and S _j = {1,3,5} is obtained as the subset S _j of the total set N. Assuming that the loading prohibition constraint (see equation (17)) and the mountain height constraint (see equation (18)) are not satisfied, the feasible peak m _j (column) obtained by the preprocessing unit 120 is not satisfied. ) Becomes m _j = [1,0,1,0,1] ^T (T represents transposition). In this case, the 1-increasing neighborhood mountain m _{j_np} becomes two feasible mountains of m _{j_np} = [1,1,1,0,1] ^T and [1,0,1,1,1] ^T. On the other hand, the 1-decrease neighborhood mountain m _{j_nm} is m _{j_nm} = [0,0,1,0,1] ^T , [1,0,0,0,1] ^T , [1,0,1,0,0]. There are three feasible mountains of ^T.

The neighborhood search unit 134 includes the search for the 1-increasing neighborhood mountain m _{j_np} and the 1-decreasing neighborhood mountain m _{j_nm} in the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120. Do each of _j individually.

Here, in the neighborhood search unit 134, the mountain m j'in which any one of the elements of "0 (zero)" of the feasible mountain m _j is changed to "1 _" is the feasible mountain (mounting prohibition constraint (overload prohibition constraint). A mountain that satisfies (see equation (17)) and the mountain height constraint (see equation (18)), and is a _feasible mountain obtained by the pretreatment unit 120. If the mountain m j is not m _{j_np} and the incurred cost (= c _j − P _j ) for the changed mountain m _j is equal to or less than the threshold TH, the mountain m _j is added to the 1-increased neighborhood mountain set C _{nb_p} . ..

Similarly, in the neighborhood search unit 134, the mountain m j'in which any one of the elements of "1" of the feasible mountain m _j is changed to "0 (zero) _" is the feasible mountain (mounting prohibition constraint (overload prohibition constraint). A mountain that satisfies (see equation (17)) and the mountain height constraint (see equation (18)), and is a _feasible mountain obtained by the pretreatment unit 120. If it is not m _{j_nb} and the incurred cost (= c _j -P _j ) for the changed mountain m _j'is less than or equal to the threshold TH, the mountain m _j is added to the 1-decreased neighborhood mountain set C _{nb_m} . do.

The condition that the contracted cost (= c _j' -P _{j' )} for the changed mountain m j'is equal to or less than the threshold TH is a necessary condition (contracted cost (= c)) described above when the contracted cost is too large. Since _j -P _j ) does not satisfy the column near "0 (zero)"), it is provided to exclude such a column. The threshold value TH can be determined, for example, by the following equation (24).

Here, ceil (x) is a ceiling function (a function that associates the smallest integer greater than or equal to x with a real number x).
The neighborhood search unit 134 has "0 (zero)" of the feasible mountain m _j for each of the feasible mountain m _j included in the set C _cg of the feasible mountain m _j obtained by the pretreatment unit 120 as described above. ) ”, And the mountain m _j'that can be added is determined by determining whether or not the mountain m _j'that has changed any one of the elements to" 1 "can be added to the 1-increased neighborhood mountain set C _{nb_p} . Addition to the 1 increase neighborhood mountain set C _{nb_p} and the change of any one of the "1 (zero)" elements of the feasible mountain m _j to "0 (zero)", the mountain m _j'decreases by 1. It is determined whether or not it can be added to the neighboring mountain set C _{nb_m} , and the mountain m _j'that can be added is added to the 1-decreased neighboring mountain set C _{nb_m} . Then, the neighborhood search unit 134 performs the above processing for all the feasible mountain m _j included in the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120, and when the above processing is performed, the neighborhood mountain set is increased by 1. C _{nb_p} and 1 decreasing neighborhood mountain set C _{nb_m} includes 1 increasing neighborhood mountain m _{j_np} and 1 decreasing neighborhood mountain m _{j_nm} are added to the set C _cg of feasible mountain m _j obtained by the pretreatment unit 120. In the following description, when the above processing is performed, the 1-increasing neighborhood mountain set C _{nb_p} and the 1-decreasing neighborhood mountain set C _{nb_m} include the 1-increasing neighborhood mountain set C _{nb_n and the 1-decreasing neighborhood mountain set m j_nm .} The set C of the feasible mountain m _j obtained by adding to the set C _cg of the feasible mountain m _j obtained in is added to the set C of the _feasible mountain m _j obtained by the main processing unit 130 as needed. It is called.
The neighborhood search unit 134 is realized by using, for example, a CPU, a ROM, a RAM, and an HDD.

<Main processing original problem derivation unit 135>
The processing original problem derivation unit 135 derives the original problem optimum value _VP ( _{CL S1} ) and the original problem optimum solution x [j]. As described above, the original problem optimum value VP (C _LS1 ) is obtained by solving the original problem _P (C _LS1 ) for the set C _LS1 of the feasible peaks m _j obtained by the processing unit 130 ((2). ) Objective function J (when the decision variable x [j] (optimal solution of the original problem) that minimizes the value of the objective function J in equation (4) is obtained within the range that satisfies the constraint equation in equation (4). ).

FIG. 4 is a diagram showing an example of the result of processing in the processing unit 130 using the same steel material information as the result shown in FIG. 2 in a table format. In FIG. 4, “Data” is an identification number of 10 kinds of steel material information, and corresponds to “Data” shown in FIG. | C _cg | is the number of feasible peaks m _j (columns) included in the set C _cg of feasible peaks m _j obtained by the pretreatment unit 120. | C _LS1 | is the number of feasible peaks m _j (columns) included in the set C _LS1 of feasible peaks m _j obtained by the processing unit 130. _VP (C _LS1 ) is the optimum value of the original problem derived by the processing original problem deriving unit 135 with respect to C _LS1 . | C _all | is the number of feasible mountains m _j (columns) included in the set C _all of all feasible mountains m _j . VP (C _{all) is the optimum value (that is, the true optimum value) of the original problem P (C all ) for} the set C _all of all feasible peaks m _j , and _VP (C) shown in FIG. corresponds to _all ). The relative error is the relative error of the original problem optimum value _VP (C _LS1 ) with respect to the true optimum value _VP (C _all ) (= {( _VP (C _LS1 ) _-VP (C _all )) ÷ _VP ). (C _all )} × 100) is shown.

As can be seen by comparing the relative error shown in FIG. 4 with the relative error shown in FIG. 2, by adding a column by the local search method in the processing unit 130 (neighborhood search unit 134) as in the present embodiment. Relative error, which is a problem of column generation method, can be significantly reduced. In the examples shown in FIGS. 2 and 4, the average value of the relative error can be reduced from 22.6% to 0.64%.
The processing original problem derivation unit 135 is realized by using, for example, a CPU, a ROM, a RAM, and an HDD.

((Output unit 140))
In the output unit 140, the original problem P (C _all ) for the set C _all of all the feasible peaks m _j by the present processing execution determination unit 133 by the set C _cg of the feasible peaks m _j obtained by the preprocessing unit 120. ), When it is determined that a sufficient column is obtained for the solution of the optimum solution, the value of the original problem optimum solution x [j] derived by the preprocessing original problem derivation unit 132 becomes "1". The possible mountain m _j is specified, and the information of the specified feasible mountain m _j is output as the information of the mountain division plan.
On the other hand, in the output unit 140, the processing execution determination unit 133 uses the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120 to solve the original problem P (for the set C _all of all the feasible mountains m _j ). When it is determined that a sufficient column is not obtained for the solution of the optimum solution of C _all ), the value of the optimum solution x [j] of the original problem derived by the processing original problem derivation unit 135 is set to "1". The feasible mountain m _j is specified, and the information of the specified feasible mountain m _j is output as the information of the mountain division plan.

For example, the output unit 140 can use information including the ID of the feasible mountain and the ID of the steel material belonging to the feasible mountain of the ID as the information of the mountain division plan. Here, the ID of the steel material is an ID included in the steel material information. Further, the output unit 140 derives the stacking order of the steel materials belonging to the feasible pile in the feasible pile based on the size of the steel material included in the steel material information and the loading prohibition constraint formula, and the information of the stacking order is obtained. May be included in the information of the mountain division plan and output.

As a form of output of the information of the mountain division plan, for example, at least one of transmission to an external device and storage of an internal or external storage medium of the steel material mountain division plan creation device 100 can be adopted. Further, the output unit 140 is based on the information of the mountain division plan, the arrival order of the steel materials included in the steel material information, the yard storage areas 1101 to 1104, and the information of the transport equipment (crane 1A, 1B, 2A, 2B). It is possible to specify which steel material is to be transported to which place by which transport device at the timing, and to issue an operation command to the transport device based on the specified content. In this case, it is not necessary to output the information of the mountain division plan.
The output unit 140 is realized by using, for example, a CPU, ROM, RAM, and a communication interface (or an interface with a storage medium).

(Operation flow chart)
Next, an example of the method for creating a pile division plan for steel materials according to the present embodiment will be described with reference to the flowcharts of FIGS. 5-1 and 5-2.
First, in step S501, the steel material information acquisition unit 110 acquires steel material information.
Next, in step S502, the initial column set setting unit 121 sets the initial value of the set C of the feasible peak m _j .

Next, in step S503, the dual solution derivation unit 122 of the objective function J of the equation (11) within the range satisfying the constraint equation of the equation (9) based on the current value of the set C of the feasible peak m _j . The dual variable p [i] that maximizes the value is derived as the optimum solution (dual solution p _sol [i]) of the dual problem D (C). When step S503 is first performed, the current value of the set C of the feasible peaks m _j is the initial value of the set C of the feasible peaks m _j set in step S502.

Next, in step S504, the column generator 123 uses the (latest) dual solution p _sol [i] derived in step S503 to constrain the equations (13) to (18) and (22). Determinants that minimize the value of the objective function _{J S} in Eq. ₍ 21) within the range that satisfies _Eq . Derivation of the temporary placement variable t [i]). Then, the column generation unit 123 is derived from the derived decision variables (mountain-constituting steel material presence / absence variable m _j [i], steel material vertical relation variable y [i ₁ ] [i ₂ ], and temporary placement presence / absence variable t [i]). From equations (19) and (20), the column cost c _j of the feasible mountain m _j and the dual cost P _j for the feasible mountain m _j are derived.

Next, in step S505, the column determination unit 124 determines whether or not the incurred cost (= c _j −P _j ) is “0 (zero)” or less. As a result of this determination, if the incurred cost (= c _j −P _j ) is “0 (zero)” or less (YES in step S505), the process proceeds to step S506.

Proceeding to step S506, the column determination unit 124 changes the feasible mountain m _j based on the (latest) mountain constituent steel material presence / absence variable m _j [i] derived in step S504 into the set C of the feasible mountain m _j . Determine if it is included. As a result of this determination, when the feasible crest m _j based on the (latest) crest constituent steel material presence / absence variable m _j [i] derived in step S504 is included in the set C of the feasible crests m _j (step). If YES in S506), the process proceeds to step S508 of FIG. 5-2, which will be described later. On the other hand, when the feasible crest m _j based on the (latest) crest constituent steel material presence / absence variable m _j [i] derived in step S504 is not included in the set C of the feasible crests m _j (NO in step S506). In the case of), the process proceeds to step S507.

Proceeding to step S507, the column addition unit 125 changes the feasible mountain m _j based on the (latest) mountain constituent steel material presence / absence variable m _j [i] derived in step S504 into the set C of the feasible mountain m _j . Add and update the current value of the set C of the feasible mountain m _j . Then, returning to step S503, in step S505, whether it is determined that the incurred cost (= c _j −P _j ) exceeds “0 (zero)” (whether it is determined as NO in step S505), or In step S506, it is determined that the feasible crest m _j based on the (latest) crest constituent steel material presence / absence variable m _j [i] derived in step S504 is included in the set C of the feasible crests m _j . Until (until it is determined to be YES in step S506), the processes of steps S503 to S507 are repeated.

As described above, in step S505, is it determined that the incurred cost (= c _j −P _j ) is not “0 (zero)” or less (whether it is determined as NO in step S505), or is it determined in step S506? In, it is determined that the feasible crest m _j based on the (latest) crest constituent steel material presence / absence variable m _j [i] derived in step S504 is included in the set C of the feasible crests m _j (. If YES is determined in step S506), the process proceeds to step S508 of FIG. 5-2. The set C of the feasible peaks m _j obtained at this time becomes the set C _cg of the feasible peaks m _j obtained by the preprocessing unit 120.

Proceeding to step S508, the dual optimum value acquisition unit 131 acquires the dual optimum value V _D (C _cg ). The dual optimum value V _D (C _cg ) obtains the optimum solution of the dual problem D derived in step S503 immediately before it is determined that the mountain m _j that can be realized in step S505 or S506 does not need to be added to the column of the matrix A. It is the value of the objective function J of the equation (11) at the time.

Next, in step S509, the preprocessing original problem deriving unit 132 solves the original problem P (C _cg ) for the set C _cg of the feasible peaks m _j obtained by the preprocessing unit 120, thereby solving the original problem optimum value. _{VP (C cg )} and the optimum solution x [j] of the original problem are derived.

Next, in step S510, the process execution determination unit 133 subtracts the dual optimum value V _D (C _cg ) from the original problem optimum value _VP (C _cg ) derived in step S509 in step S508. It is determined whether or not it is less than "1". As a result of this determination, if the value obtained by subtracting the dual optimum value V _D (C _cg ) from the original problem optimum value _VP (C cg) is _less than "1" (YES in step S510), the preprocessing unit. The set C _cg of the feasible mountain m _j obtained in 120 provides a sufficient sequence for finding the optimum solution of the original problem P (C _all ) for the set C _all of all the feasible mountain m _j . Therefore, the process proceeds to step S513, which will be described later, omitting steps S511 and S512.

On the other hand, if the value obtained by subtracting the dual optimum value V _D (C _cg ) from the original problem optimum value _VP (C _cg ) does not fall below "1" (NO in step S510), the process proceeds to step S511. .. In step S511, the neighborhood search unit 134 performs the neighborhood search process. The set C of the feasible mountain m _j obtained by this neighborhood search process becomes the set C _LS1 of the feasible mountain m _j obtained by the processing unit 130. Details of an example of the neighborhood search process will be described later with reference to the flowcharts of FIGS. 6-1 and 6-2.

Next, in step S512, the processing original problem deriving unit 135 solves the original problem P (C _LS1 ) for the set C _LS1 of the feasible peaks m _j obtained by the processing unit 130, thereby solving the original problem optimum value. Derivation of _VP (C _LS1 ) and the optimum solution x [j] of the original problem.
Next, in step S513, the output unit 140 identifies a feasible mountain m _{j in which the value of the original problem optimum solution x [j] is “1”, and the information of the specified feasible mountain m j is} divided into mountains. Output as information. If YES is determined in step S510 and the process proceeds to step S513, the output unit 140 identifies a feasible mountain m _j in which the value of the original problem optimum solution x [j] derived in step S509 is “1”. , The information of the specified feasible mountain m _j is output as the information of the mountain division plan. On the other hand, when NO is determined in step S510 and the process proceeds to step S513, the output unit 140 determines a feasible mountain m _j in which the value of the original problem optimum solution x [j] derived in step S512 is “1”. The information of the specified and specified feasible mountain m _j is output as the information of the mountain division plan. Then, the processing according to the flowcharts of FIGS. 5-1 and 5-2 is completed.

Next, the details of the neighborhood search process in step S511 of FIG. 5-2 will be described with reference to the flowcharts of FIGS. 6-1 and 6-2.
First, in step S601, the neighborhood search unit 134 is the first feasible mountain m _j (column of matrix A) included in the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120. Specify m _j (first column of matrix A (j = 1)). Further, the neighborhood search unit 134 sets φ (empty set) as the 1-increased neighborhood mountain set C _{nb_p} .

Next, in step S602, the neighborhood search unit 134 uses the feasible mountain m _j currently specified among the feasible mountains m _j obtained by the preprocessing unit 120 as the initial value of the 1 increase neighborhood mountain m _{j_np} . To set.
Next, in step S603, the neighborhood search unit 134 designates the first element m _{j_np} [1] (steel material, i = 1) of the initial value of the 1-increased neighborhood mountain m _{j_np} set in step S602. For example, when the total set N of steel materials is N = {1, 2, 3, 4, 5}, S _j = {1, 3, 5} is obtained as the subset S _j of the total set N. In this case, the feasible peak m _j (column) obtained by the preprocessing unit 120 is m _j = [1,0,1,0,1] ^T (T represents transposition). In step S602, the feasible mountain m _j (column) obtained by the preprocessing unit 120 is set as the initial value of the 1 increase neighborhood mountain m _{j_np} , and in step S604, m _{j_np} = [1,0,1, 0,1] "1" is specified as the first element of ^T (element of i = 1). In this case, the values of the elements of i = 1, 2, 3, 4, 5 are 1, 0, 1, 0, 1, respectively.

Next, in step S604, the neighborhood search unit 134 determines whether or not the value of the element m _{j_np} [i] of the initial value of the currently designated 1-increasing neighborhood mountain m _{j_np} is “0 (zero)”. do. As a result of this determination, if the value of the element m _{j_np} [i] of the initial value of the currently specified 1-increased neighborhood mountain m _{j_np} is not "0 (zero)" (NO in step S604), the element concerned Since there is already a steel material, the process skips steps S605 to S609 and proceeds to step S610 described later.

On the other hand, when the value of the element m _{j_np} [i] of the initial value of the currently specified 1-increasing neighborhood mountain m _{j_np} is "0 (zero)" (YES in step S604), the process is performed in step S605. move on. In step S605, the neighborhood search unit 134 changes the value of the element m _{j_np} [i] of the initial value of the currently designated 1-increased neighborhood mountain m _{j_np} to “1”.

Next, in step S606, in the neighborhood search unit 134, the 1-increased neighborhood mountain m _{j_np} changed in step S605 is the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120 or the 1-increased neighborhood mountain set. It is determined whether or not it is included in C _{nb_p} . As a result of this determination, when the 1-increased neighborhood mountain m _{j_np} changed in step S605 is included in the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120 or the 1-increased neighborhood mountain set C _{nb_p} . (When YES in step S606), it is not necessary to add the 1-increased neighborhood mountain m _{j_np} changed in step S605 to the 1-increased neighborhood mountain set C _{nb_p} . Therefore, the process skips steps S607 to S609 and proceeds to step S610 described later.

On the other hand, when the 1-increased neighborhood mountain m _{j_np} changed in step S605 is included in the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120 or the 1-increased neighborhood mountain set C _{nb_p} (step S606). If NO), the process proceeds to step S607. In step S607, the neighborhood search unit 134 sets the feasible mountain (mounting prohibition constraint (see equation (17)) and mountain height constraint ((18) equation) for the one-increased neighborhood mountain m _{j_np} changed in step S605. Refer to) to determine whether or not the mountain) satisfies. As a result of this determination, if the 1-increased neighborhood mountain m _{j_np} after the change in step S605 is not a feasible mountain (NO in step S607), the 1-increased neighborhood mountain m _{j_np} after the change in step S605 is optimally realized. It is not a candidate for the feasible mountain m _j required to obtain the possible mountain m _j . Therefore, the process skips steps S608 to S609 and proceeds to step S610 described later.

On the other hand, if the 1-increased neighborhood mountain m _{j_np} changed in step S605 is a feasible mountain (YES in step S607), the process proceeds to step S608. In step S608, the neighborhood search unit 134 determines whether or not the incurred cost (= c _j − P _j ) for the 1-increased neighborhood mountain m _{j_np} after the change in step S605 is equal to or less than the threshold value TH. As a result of this determination, if the reduced cost (= c _j −P _j ) for the 1-increased neighborhood mountain m _{j_np} after the change in step S605 is not equal to or less than the threshold TH (NO in step S608), the reduced cost is too large. Therefore, it does not satisfy the above-mentioned necessary condition (the incurred cost (= c _j -P _j ) is a column near "0 (zero)"). Therefore, the process skips step S609 and proceeds to step S610 described later.

On the other hand, when the incurred cost (= c j'-P _{j' )} for the 1-increased neighborhood mountain m _{j_np} after the change in step S605 is equal to or less than the threshold value TH (YES in step S608), the process is performed in step S609. move on. In step S609, the neighborhood search unit 134 adds the 1-increased neighborhood mountain m _{j_np} changed in step S605 to the 1-increased neighborhood mountain set C _{nb_p} . Then, the process proceeds to step S610.

In step S610, the neighborhood search unit 134 determines whether or not up to the last element m _{j_np} [i] (steel material) of the initial value of the 1-increased neighborhood mountain m _{j_np} set in step S602 is specified. In the specific example shown in the description of step S603, the neighborhood search unit 134 determines whether or not i = 5 is specified. As a result of this determination, if the last element m _{j_np} [i] (steel material) of the initial value of the 1-increased neighborhood mountain m _{j_np} set in step S602 is not specified (NO in step S610), the process is step. Proceed to S611. In step S611, the neighborhood search unit 134 designates the element i + 1 next to the currently designated element i among the elements i of the initial values of the 1-increased neighborhood mountain m _{j_np} set in step S602. Then, the processing after step S604 is performed with the element i + 1 as the element m _{j_np} [i] of the initial value of the 1-increasing neighborhood mountain m _{j_np} currently designated.

On the other hand, when the last element m _{j_np} [i] (steel material) of the initial value of the 1-increased neighborhood mountain m _{j_np} set in step S602 is specified (YES in step S610), it is obtained by the pretreatment unit 120. Judgment as to whether or not all the 1-increased neighborhood mountains m _{j_np} obtained from the currently specified feasible mountains m _j can be added to the 1-increased neighborhood set C _{nb_p} among the feasible mountains m _j . Then, the addition of the 1-increased neighborhood mountain m _{j_np} that can be added to the 1-increased neighborhood mountain set C _{nb_p} is completed. Therefore, the process proceeds to step S612.

In step S612, the neighborhood search unit 134 determines whether or not all of the feasible peaks m _j obtained by the preprocessing unit 120 have been designated. As a result of this determination, if all of the feasible peaks m _j obtained by the preprocessing unit 120 are not specified (NO in step S612), the process proceeds to step S613. In step S613, the neighborhood search unit 134 currently specifies the realization of the feasible mountain m _j (column of the matrix A) included in the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120. Specify the next feasible mountain m _{j + 1} (the j + 1 column of the matrix A) after the possible mountain m j. Then, the neighborhood search unit 134 performs the processing after step S602 with the feasible mountain m _{j + 1} in the j + 1th column as the currently designated feasible mountain m _j .

On the other hand, when all the feasible mountains m _j obtained by the pretreatment unit 120 are specified (YES in step S612), all the feasible mountains m _j obtained by the pretreatment unit 120 are all specified. Judgment as to whether or not 1 increase neighborhood mountain m _{j_np} can be added to 1 increase neighborhood mountain set C _{nb_p} , and addition of 1 increase neighborhood mountain m _{j_np} that can be added to 1 increase neighborhood mountain set C _{nb_p} . Is finished. Therefore, the process proceeds to step S614 in FIG. 6-2.

In step S614, the neighborhood search unit 134 is the first feasible mountain m _j of the feasible mountain m _j (column of matrix A) included in the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120. (The first column (j = 1) of the matrix A) is specified. Further, the neighborhood search unit 134 sets φ (empty set) as the 1-decreased neighborhood mountain set C _{nb_m} .

Next, in step S615, the neighborhood search unit 134 uses the feasible mountain m _j currently specified among the feasible mountains m _j obtained by the pretreatment unit 120 as the initial value of the 1-decreased neighborhood mountain m _{j_nm} . To set.
Next, in step S616, the neighborhood search unit 134 designates the first element m _{j_nm} [1] (steel material, i = 1) of the initial value of the 1-decreased neighborhood peak m _{j_nm} set in step S615. For example, when the total set N of steel materials is N = {1, 2, 3, 4, 5}, S _j = {1, 3, 5} is obtained as the subset S _j of the total set N. In this case, the feasible peak m _j (column) obtained by the preprocessing unit 120 is m _j = [1,0,1,0,1] ^T (T represents transposition). In step S615, the feasible mountain m _j (column) obtained by the pretreatment unit 120 is set as the initial value of the 1-decreased neighborhood mountain m _{j_nm} , and in step S617, m _{j_nm} = [1,0,1, 0,1] "1" is specified as the first element of ^T (element of i = 1). In this case, the values of the elements of i = 1, 2, 3, 4, 5 are 1, 0, 1, 0, 1, respectively.

Next, in step S617, the neighborhood search unit 134 determines whether or not the value of the element m _{j_nm} [i] of the initial value of the currently designated 1-decreased neighborhood mountain m _{j_nm} is “1”. As a result of this determination, if the value of the element m _{j_nm} [i], which is the initial value of the currently specified 1-decrease neighborhood mountain m _{j_nm} , is not "1" (NO in step S617), the element already contains steel material. Since there is no such process, the process skips steps S618 to S622 and proceeds to step S623 described later.

On the other hand, when the value of the element m _{j_nm} [i] of the initial value of the currently designated 1-decreasing neighborhood mountain m _{j_nm} is “1” (YES in step S617), the process proceeds to step S618. In step S618, the neighborhood search unit 134 changes the value of the element m _{j_nm} [i] of the initial value of the currently designated 1-decreased neighborhood mountain m _{j_nm} to “0 (zero)”.

Next, in step S619, in the neighborhood search unit 134, the 1-reduced neighborhood mountain m _{j_nm} changed in step S618 is the set C _cg or the 1-reduced neighborhood mountain set of the feasible mountain m _j obtained by the pretreatment unit 120. It is determined whether or not it is included in C _{nb_m} . As a result of this determination, when the 1-reduced neighborhood mountain m _{j_nm} changed in step S618 is included in the set C _cg of the feasible mountain m _j obtained by the pretreatment unit 120 or the 1-reduced neighborhood mountain set C _{nb_m} . (When YES in step S619), it is not necessary to add the 1-decreased neighborhood mountain m _{j_nm} after the change in step S618 to the 1-decreased neighborhood mountain set C _{nb_m} . Therefore, the process skips steps S620 to S622 and proceeds to step S623 described later.

On the other hand, when the 1-reduced neighborhood mountain m _{j_nm} changed in step S618 is included in the set C _cg of the feasible mountain m _j obtained by the pretreatment unit 120 or the 1-reduced neighborhood mountain set C _{nb_m} (step S619). If NO), the process proceeds to step S620. In step S620, the neighborhood search unit 134 sets the feasible mountain (mounting prohibition constraint (see equation (17)) and mountain height constraint ((18) equation) for the 1-decreased neighborhood mountain m _{j_nm} changed in step S618. Refer to) to determine whether or not the mountain) satisfies. As a result of this determination, if the 1-decreased near-mountain m _{j_nm} after the change in step S618 is not a feasible mountain (NO in step S620), the 1-decreased near-mountain m _{j_nm} after the change in step S618 is optimally realized. It is not a candidate for the feasible mountain m _j required to obtain the possible mountain m _j . Therefore, the process skips steps S621 to S622 and proceeds to step S623 described later.

On the other hand, when the 1-decreased neighborhood mountain m _{j_nm} changed in step S618 is a feasible mountain (YES in step S620), the process proceeds to step S621. In step S621, the neighborhood search unit 134 determines whether or not the incurred cost (= c _j − P _j ) for the 1-decreased neighborhood mountain m _{j_nm} after the change in step S618 is equal to or less than the threshold value TH. As a result of this determination, if the reduced cost (= c _j −P _j ) for the 1-decreased neighborhood m _{j_nm} after the change in step S618 is not less than or equal to the threshold TH (NO in step S621), the reduced cost is too large. Therefore, it does not satisfy the above-mentioned necessary condition (the incurred cost (= c _j -P _j ) is a column near "0 (zero)"). Therefore, the process skips step S622 and proceeds to step S623 described later.

On the other hand, when the incurred cost (= c _j −P _j ) for the 1-decreased neighborhood mountain m _{j_nm} after the change in step S618 is equal to or less than the threshold value TH (YES in step S621), the process proceeds to step S622. In step S622, the neighborhood search unit 134 adds the 1-decreased neighborhood mountain m _{j_nm} changed in step S618 to the 1-decreased neighborhood mountain set C _{nb_m} . Then, the process proceeds to step S623.

In step S623, the neighborhood search unit 134 determines whether or not the last element m _{j_nm} [i] (steel material) of the initial value of the 1-decreased neighborhood peak m _{j_nm} set in step S615 is specified. In the specific example shown in the description of step S616, the neighborhood search unit 134 determines whether or not i = 5 is specified. As a result of this determination, if the last element m _{j_nm} [i] (steel material) of the initial value of the 1-decreased neighborhood m _{j_nm} set in step S615 is not specified (NO in step S623), the process is step. Proceed to S624. In step S624, the neighborhood search unit 134 designates the next element i + 1 of the currently designated element i among the elements i of the initial value of the 1-decreased neighborhood mountain m _{j_nm} set in step S615. Then, the processing after step S617 is performed with the element i + 1 as the element m _{j_nm} [i] of the initial value of the 1-decreasing neighborhood mountain m _{j_nm} currently designated.

On the other hand, when the last element m _{j_nm} [i] (steel material) of the initial value of the 1-decreased neighborhood m _{j_nm} set in step S615 is specified (YES in step S623), it is obtained by the pretreatment unit 120. Judgment as to whether or not all the 1-decreased neighborhood mountains m _{j_nm} obtained from the currently specified feasible mountains m _j can be added to the 1-decreased neighborhood mountain set C _{nb_m} among the feasible mountains m _j . Then, the addition of the 1-reduced neighborhood mountain m _{j_nm} that can be added to the 1-reduced neighborhood mountain set C _{nb_m} is completed. Therefore, the process proceeds to step S625.

In step S625, the neighborhood search unit 134 determines whether or not all of the feasible peaks m _j obtained by the preprocessing unit 120 have been designated. As a result of this determination, if all of the feasible peaks m _j obtained by the preprocessing unit 120 are not specified (NO in step S625), the process proceeds to step S626. In step S626, the neighborhood search unit 134 is the realization currently specified among the feasible mountain m _j (column of the matrix A) included in the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120. Specify the next feasible mountain m _{j + 1} (the j + 1 column of the matrix A) after the possible mountain m j. Then, the neighborhood search unit 134 performs the processing after step S615 with the feasible mountain m _{j + 1} in the j + 1th column as the currently designated feasible mountain m _j .

On the other hand, when all the feasible mountains m _j obtained by the pretreatment unit 120 are specified (YES in step S625), all the feasible mountains m _j obtained by the pretreatment unit 120 are all specified. Judgment as to whether or not 1 reduced neighborhood mountain m _{j_nm} can be added to 1 reduced neighborhood mountain set C _{nb_m} , and addition of 1 reduced neighborhood mountain m _{j_nm} that can be added to 1 reduced neighborhood mountain set C _{nb_m} . Is finished. Therefore, the process of FIG. 6-2 is completed, and the process proceeds to step S512 of FIG. 5-2.

(summary)
As described above, in the present embodiment, the pretreatment unit 120 has a set C (matrix A) of feasible peaks m _j when the incurred cost (c _j − P _i ) is “0 (zero)” or less. Add a feasible mountain m _j to. The addition of the feasible mountain m _j is repeated until the incurred cost (c _j − P _i ) exceeds “0 (zero)”.

The main processing unit 130 is a column not included in the set C _cg of the feasible mountain m _j obtained by the pretreatment unit 120 based on the set C _cg of the feasible mountain m _j obtained by the pretreatment unit 120. (Feasible mountain m _j ) is searched and added to the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120. By solving the original problem _P (C _LS1 ) for the set C _LS1 of the feasible mountain m _j in this way, the processing unit 130 has the original problem optimum value VP (C _LS1 ) and the original problem optimum solution x [j. ] Is derived.

Therefore, it becomes possible to apply the column generation method to the mountain division problem, and it is possible to list the feasible mountain candidates as much as possible as possible as possible feasible mountain candidates (that is, all feasible mountains). No need to enumerate). Therefore, with the technology described in Patent Document 1, even if it is a large-scale problem that cannot even enumerate the peaks of realization, there is no dual gap (discretization error) and a strictly appropriate mountain division plan is binary-constrained (0). It can be reliably created based on the optimum solution that eliminates the error (dual gap) associated with (-1 constraint).

Also, as explained in the section of the problem to be solved by the invention, the column generation method is guaranteed to obtain the optimum solution of the linear programming problem by using it, but it is similar to the set division problem. For the 0-1 integer programming problem, a feasible solution can be obtained (in the case of a minimization problem, the upper limit of the solution can be obtained), but it is not always guaranteed that the optimum solution can be obtained. This point remains an issue even in the technique described in Patent Document 2. On the other hand, in the present embodiment, the optimum solution of the original problem P (original problem optimum solution x [j]) can be derived by the processing unit 130.

Further, the column generation method is a method that requires a calculation time because it is a repetitive calculation. Therefore, in order to use the mountain division plan for real-time control, a method of shortening the calculation time as much as possible may be required. However, Patent Document 2 does not touch on this issue because it is premised on an offline use such as seeking a correspondence between sentences contained in two different documents. On the other hand, in the present embodiment, when solving the column generator problem S, the column cost c _j of the feasible mountain m _j is equal to or less than the dual cost P _j for the feasible mountain m _j as shown in equation (22). Add the constraint that (c _j ≤ P _j ). Therefore, the calculation time of the column generator problem S, which requires a long calculation time, can be shortened.

Further, in the present embodiment, the processing unit 130 is a preprocessing unit when the value obtained by subtracting the dual optimum value V _D (C _cg ) from the original problem optimum value _VP (C cg) is _less than "1". The set C _cg of the feasible mountain m _j obtained in 120 provides a sufficient sequence for finding the optimum solution of the original problem P (C _all ) for the set C _all of all the feasible mountain m _j . As a result, the process of adding a column (realizable mountain m _j ) to the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120 is not performed. Therefore, the processing load in the processing unit 130 can be reduced.

Further, in the present embodiment, the main processing unit 130 sets any one of the "0 (zero)" elements of the feasible mountain m _j for each of the feasible mountain m _j obtained by the pretreatment unit 120. Which of the elements of "1" of the feasible mountain m _j for each of the feasible mountain m _{j_np} (1 increase neighborhood mountain m _{j_np} ) and the feasible mountain m _j obtained by the pretreatment unit 120? Search for a feasible mountain m _{j_nm} (mountain near 1 reduction m _{j_nm} ) where one of them is "0 (zero)". Therefore, it is possible to limit the search range of the column to be added to the set C _cg of the feasible mountain m _j obtained by the preprocessing unit 120 without significantly reducing the accuracy of the mountain division plan. Therefore, the processing load in the processing unit 130 can be reduced.

(Modification example)
<Modification 1>
In the present embodiment, the neighborhood search unit 134 searches for 1 increase neighborhood mountain m _{j_np} and 1 decrease neighborhood mountain m _{j_nm} , and 1 increase neighborhood mountain m _{j_np} and 1 decrease neighborhood mountain m _{j_nm} are searched by the pretreatment unit 120. The case where the set C _LS1 of the feasible mountain m _j obtained by the processing unit 130 is added to the set C _cg of the obtained feasible mountain m _j has been described as an example. The local search method in the neighborhood search unit 134 can be applied many times to the generated sequence (realizable mountain m _j ).

FIG. 7 shows an example of how the sets C _LS1 , C _LS2 , ..., C _LS n of the feasible peaks m _j obtained by the processing unit 130 increase by repeatedly performing the neighborhood search by the local search method. It is a figure which shows conceptually.
In FIG. 7, the set C _LS2 of the feasible mountain m _j obtained by the main processing unit 130 is the set C _{nb_p} and 1 of the near-increased mountain set C _LS1 with respect to the set C LS1 of the feasible mountain m _j obtained by the main processing unit 130. It is obtained by searching the reduced neighborhood mountain set C _{nb_m} and adding it to the set C _LS1 of the feasible mountain m _j obtained by the processing unit 130. Specifically, the set C _LS2 of the feasible mountain m _j obtained by the main processing unit 130 is the preprocessing unit 120 in the description of the <neighborhood search unit 134> and the flowcharts of FIGS. 6-1 and 6-2. The obtained set C _cg of the feasible mountain m _j is added to the set C _LS1 of the feasible mountain m _j obtained by the main processing unit 130, and the set C _LS1 of the feasible mountain m _j obtained by the main processing unit 130. Is replaced with the set C _LS2 of the feasible mountain m _j obtained by the main processing unit 130, respectively. Similarly, the set C _LSn of the feasible mountain m _j obtained by the processing unit 130 is the set C _{nb_p} and the neighboring mountain set C nb_p with respect to the set C _LSn-1 of the feasible mountain m _j obtained by the processing unit 130. It is obtained by searching for the set C _{nb_m} of 1 reduced neighborhood mountains and adding it to the set C _LSn-1 of the feasible mountain m _j obtained by the processing unit 130.

Seen from the set C _cg of the feasible mountain m _j obtained by the pretreatment unit 120, the set of 1 increase neighborhood mountain m j added to the set C _cg of the feasible mountain m _j obtained by the pretreatment unit 120 C _{The nb_p} and the 1-decreasing neighborhood mountain set C _{nb_m} are the 1-increasing neighborhood mountain set C _{nb_p} and the 1-decreasing neighborhood that are added to the set C _LS1 of the feasible mountain m _j obtained by the first neighborhood column, this processing unit 130. The mountain set C _{nb_m} is the second neighborhood row. In this case, n of the n-th neighborhood column (n of the set C _LS1 , C _LS2 , ..., C _LSn of the feasible mountain m _j obtained by the processing unit 130) is, for example, the feasible mountain m _j . Size (number of elements) can be adopted.

For example, as in the specific example shown in the section of <Neighborhood search unit 134>, the feasible mountain m _j (column) obtained by the preprocessing unit 120 is m _j = [1,0,1,0,1. ] ^T. In this case, the first neighborhood column becomes 1 increase neighborhood mountain m _{j_np} and 1 decrease neighborhood mountain m _{j_nm} in the specific example shown in the section of <neighborhood search unit 134> (m _{j_np} = [1,1,1,0). , 1] ^T , [1,0,1,1,1] ^T , m _{j_nm} = [0,0,1,0,1] ^T , [1,0,0,0,1] ^T , [1, 0,1,0,0] ^T ). The second neighborhood column (1 increase neighborhood mountain set C _{nb_p} and 1 decrease neighborhood mountain m _{j_nm} with respect to the 1st neighborhood column) is m _{j_np} = [1,1,1,1,1] ^T , m _{j_nm} = [ 0,0,0,0,1] ^T , [0,0,1,0,0] ^T , [1,0,0,0,0] ^T. In this case, the set C _LS2 of the feasible mountain m _j obtained by the main processing unit 130 includes the feasible mountain m _j (row) obtained by the preprocessing unit 120, the first neighborhood row, and the second neighborhood. Contains columns and.

FIG. 8 is a diagram showing in a table format an example of the result of performing the above-mentioned processing up to the second neighborhood row in the processing unit 130 using the same steel material information as the results shown in FIGS. 2 and 4. .. In FIG. 8, “Data” is an identification number of 10 types of steel material information, and corresponds to “Data” shown in FIGS. 2 and 4. | C _LS1 | is the number of feasible peaks m _j (columns) included in the set C _LS1 of feasible peaks m _j obtained by this processing unit 130, and corresponds to | C _LS1 | shown in FIG. do. | C _LS1 | is the number of feasible peaks m _j (column) obtained by searching up to the first neighborhood column described above. The _{VP (C LS1 )} is the original problem optimum value _VP (C _LS1 ) derived by the processing original problem deriving unit 135, and corresponds to the _{VP (C LS1 )} shown in FIG.

| C _LS2 | is the number of feasible peaks m _j (columns) included in the set C _LS2 of feasible peaks m _j obtained by the processing unit 130. | C _LS2 | is the number of feasible peaks m _j (column) obtained by searching up to the second neighborhood column described above. _{VP (C LS2 )} is the original problem optimum value _{VP (C LS2 )} derived by the processing original problem deriving unit 135. | C _all | is the number of feasible mountains m _j (columns) included in the set C _all of all feasible mountains m _j , and corresponds to | C _all | shown in FIG. VP (C _{all) is the optimum value (that is, the true optimum value) of the original problem P (C all ) for} the set C _all of all feasible peaks m _j , and is V shown in FIGS. 2 and 4. Corresponds to _P (C _all ). The relative error is the relative error of the original problem optimum value _{VP (C LS2 )} with respect to the true optimum value _VP (C _all ) (= {( _VP (C _LS1 ) _-VP (C _all ))) ÷ _VP (C _all )} × 100 or {(VP (C _LS2 ) _-VP (C _all )) _{÷ VP} (C _all )} × 100) is shown. In addition, "/" indicates that the search is not performed up to the second neighborhood column described above.

As shown in FIG. 4, for the steel material information of Data1, 5, and 7, a relative error remained in the above-mentioned search up to the first neighborhood row. On the other hand, as shown in FIG. 8, when the above-mentioned second neighborhood row is searched, it can be seen that the relative error with respect to the steel material information of Data1, 5, and 7 becomes "0 (zero)". In addition, the original problem optimum value VP (C _LS2 ) of _Data1 , 5, and 7 matches the true optimum value _VP (C _all ), and the original problem optimum value _VP (C _LS1 ) is used for all steel material information. _{Alternatively, it can be seen that VP (C LS2 )} matches the true optimum value _VP (C _all ).

In addition to the above, at least one of the top, bottom, and at least one of the two adjacent steel materials included in the set _CLSn of the feasible peak _{m j} that has already been obtained. If it is a feasible mountain m _j with at least one steel material added, and it is a feasible mountain m _j that can be a candidate for a feasible mountain m _j that constitutes the optimum solution of the original problem P (C). , The number and position of steel materials to be added are not particularly limited. Further, it is a feasible mountain m _j obtained by removing at least one of the feasible mountain m _j included in the set C _LSn of the feasible mountain m _j that has already been obtained, and the optimum solution of the original problem P (C) is obtained. The number and position of the steel materials to be removed are not particularly limited as long as the feasible mountain m _j can be a candidate for the feasible mountain m _j to be constructed.

<Modification 2>
In the column generation method, since there is an iterative process (steps S503 to S507), performing this iterative process at high speed leads to shortening the overall processing time. The main calculations in this iterative process are a calculation for solving the dual problem D (C) (step S503) and a calculation for solving the column generator problem S (step S504). Since the column generator problem S is a 0-1 integer programming problem, it generally requires more calculation time than the dual programming problem D (C), which is a linear programming problem.

Therefore, in the present embodiment, as a preferable example when solving the column generator problem S, a case where the calculation time of the column generator problem S is shortened by adding the constraint equation of the equation (22) has been described. However, the method for shortening the calculation time of the column generator problem S is not limited to such a method. For example, the dual gap, which is a condition for discontinuing the calculation of the column generator problem S, may be adjusted each time the column generator problem S (step S504) is executed.

In the column generator problem S, the problem of minimizing the incurred cost (= c _j − P _j ) is solved by using the dual solution p _sol [i] obtained by solving the dual problem D (C). The accuracy of the dual solution p _sol [i] increases as the above-mentioned iterative processing (steps S503 to S507) progresses and the number of feasible mountains m _j added to the set C of the feasible mountains m _j (column) increases. Along with this, the reduced cost (= c _j − P _j ) of the feasible mountain m _j (column), which is the optimum solution of the column generator problem S, also converges to “0 (zero)”. That is, in the initial stage where the number of repetitions of the above-mentioned iterative processing (steps S503 to S507) is small, the accuracy of the dual solution p _sol [i] is low, so it is inefficient to obtain the optimum accuracy of the column generator problem S. Is.

On the other hand, as the number of repetitions of the above-mentioned iterative processing (steps S503 to S507) increases, the feasible mountain m _j obtained from the optimum solution (mountain-constituting steel material presence / absence variable m _j [i]) calculated by the column generation unit 123 becomes larger. Since the possibility of becoming a component of the true optimum solution of the original problem P increases, it is required to improve the accuracy of the dual solution p _sol [i]. Therefore, the condition for discontinuing the calculation of the column generator problem S according to the incurred cost (= c _j − P _j ) obtained by the column generator 123 based on the optimum solution of the column generator problem S in the previous calculation. The dual gap ({(upper bound value-lower bound value) ÷ upper bound value}) may be set.

In this case, in the calculation of the column generator problem S, even if the dual gap is not necessarily "0 (zero)", the condition for discontinuing the calculation of the column generator problem S is as shown in the following equation (25). It is preferable to set the value G _S of the dual gap to be, and stop the calculation of the column generator problem S when the dual gap becomes G _S ( _GS or less) from the viewpoint of reducing the processing time.

In the equation (25), | rc _prv / k ₁ | is a value derived in the calculation of the previous step S504, and is a determinant variable (mountain-constituting steel material presence / absence variable m _j [) which is a solution result of the column generator problem S. The value obtained by dividing the incurred cost rc _prv (= c _j − P _j ) obtained from i], the steel material vertical relation variable y [i ₁ ] [i ₂ ], and the temporary placement variable t [i]) by k ₁ . It is an absolute value. In addition, k ₁ is a weighting coefficient k ₁ for the evaluation of the number of peaks in the objective function of the original problem P (C) used in the equation (4) or the equation (19), and is another evaluation, the temporary placement number. It is determined by the relative weight of.
For example, the column generator 123 sets the value G _S [%] of the dual gap, which is a condition for terminating the calculation of the column generator problem S, according to the equation (25). Then, when the absolute value | rc _prv / k ₁ | of the incurred cost exceeds the predetermined threshold TH _S , the column generator 123 determines the dual gap for discontinuing the calculation of the column generator problem S. When "1 (= 100%)" is used as the value G _S and the absolute value | rc _prv / k ₁ | of the incurred cost is equal to or less than the predetermined threshold TH _S , the column generator problem S As the value G _S of the dual gap for discontinuing the calculation, α · | rc _prv / k ₁ | is used.

In this method, it is important to set the threshold value TH _S , for example, TH _S = 0.05. That is, when the incurred cost becomes small to a few percent of the weighting coefficient k ₁ , the value G _S of the dual gap, which is a condition for terminating the calculation of the column generator problem S, is switched to α · | rc _prv / k ₁ |. Is appropriate. Increasing the threshold TH _S speeds up the switching and increases the calculation time, but improves the accuracy of the solution. On the other hand, if the threshold TH _S is made too small, the opposite phenomenon occurs. Further, α may be basically 1 but is used for fine adjustment in the range of about 0.5 <α <1.5.

Here, the upper bound value and the lower bound value that define the dual gap are the upper bound value and the lower bound value obtained when the column generator problem S is solved by the column generator 123 (step S504 in FIG. 5-1). The upper bound value is the value of the objective function J _S when the best solution (optimal solution) of the executable solutions of the column generator problem S is given to the objective function J _S of the equation (21). The lower bound value is the purpose when the worst solution (maximum value) of the solutions of the linear relaxation problem used when solving the column generator problem S by the branch-and-bound method is given to the objective function of the linear relaxation problem. The value of the function.

The column generator 123 derives a dual gap when solving the column generator problem S in step S504 of FIG. 5-1. Further, the column generation unit 123 derives and stores the value G _S of the dual gap, which is a condition for discontinuing the calculation of the column generator problem S, by performing the calculation of the equation (25). The column generator 123 determines the column generator problem when the dual gap derived at the time of the previous calculation of the column generator problem S becomes the value G _S of the dual gap derived by performing the calculation of the equation (25). The calculation of S is discontinued, and the solution obtained at that time (mountain composition steel material presence / absence variable m _j [i], steel material vertical relation variable y [i ₁ ] [i ₂ ], and temporary placement presence / absence variable t [i]) Is the optimum solution.
In addition, the constraint equation of Eq. (22) is added so that the calculation of the column generator problem S is not completed when the incurred cost (= c _j -P _j ) exceeds "0 (zero)". The process described in the second modification may be performed.

<Modification 3>
As described above, it is preferable to use the temporary placement variable t [i] because the number of temporary placements can be strictly evaluated. However, the temporary placement number may be evaluated by the steel material vertical relation variables y [i ₁ ] [i ₂ ] without using the temporary placement presence / absence variable t [i]. In this case, for example, the equation (16) (temporary variable definition constraint equation) becomes unnecessary. Further, "k ₂ · Σ _i ∈ _N t [i]" of the right-hand side second term of the equation (19), the right-hand side first term of the equation (21), and the left-hand side second term of the equation (22) is "k ₂ ".・ Σ _{[i1, i2]} ∈ _R y [i ₁ ] [i ₂ ] ”.

<Modification example 4>
In this embodiment, the case where the original problem P (C) is a minimization problem has been described as an example. However, the original problem P may be a maximization problem. Changing the original problem P (C) from the minimization problem to the maximization problem can be easily inferred from the explanation of the present embodiment, but the outline will be described below.

First, the objective function of the original problem P (C) is a function that aims to select the feasible mountain m _j so that the sum of the column costs c _j is maximized. (3') is used. Further, as the constraint equation and the objective function of the dual problem D (C), the following equations (9') and (11') are used instead of the equations (9) and (11), respectively. That is, in the dual problem D (C), the dual variable p [i] that minimizes the value of the objective function J in the equation (11') within the range satisfying the constraint equation in the equation (9') is set in the dual problem D. Derived as the optimal solution. Further, as the objective function of the column generator problem S, the following equation (21') is used instead of the equation (21). That is, in the column generator problem S, the determination variable (which maximizes the value of the objective function J _S of the equation (21') within the range satisfying the constraint equations of the equations (13) to (18) and (22). Derivation of the pile constituent steel material presence / absence variable m _j [i], the steel material vertical relation variable y [i ₁ ] [i ₂ ], and the temporary placement presence / absence variable t [i]). Then, in step S505, the column determination unit 124 determines whether or not the incurred cost (= P _j −c _j ) is “0” or “0 (zero)” or less. The column cost c _j of the feasible mountain m _j is also formulated according to the maximization problem.

<Modification 5>
In this embodiment, a case where a steel material is to be transported has been described as an example. However, the target material does not necessarily have to be a steel material. For example, the present embodiment can be applied to a metal manufacturing process for manufacturing a metal material such as aluminum, titanium, or copper instead of a steel material. In this case, the "steel material" can be replaced with a "metal material" such as an "aluminum material" in the above description.
Further, as a storage space between processes, a storage space between two manufacturing processes may be targeted, a semi-finished product may be targeted as a metal material, and a storage space between manufacturing processes and a shipping process may be targeted as a storage space between processes. , As a metal material, the final product may be targeted. At this time, when a plurality of metal materials are housed in a container for transportation and arrangement, the container containing the metal materials may be treated as one steel material. Further, the storage space between processes is not limited to the storage space in the metal manufacturing process, and may be targeted for general distribution and transportation between processes. In the field of logistics, it can be applied not only to the contents but also to the transportation and arrangement of containers.

(Example)
Next, an embodiment will be described. In this embodiment, when the technique described in Patent Document 1 is used, a problem that the feasible mountains cannot be listed and a problem that the feasible mountains can be listed but the subsequent set partitioning problem cannot be solved. The method of this embodiment was applied and the effect was investigated. Here, the fact that the feasible mountains cannot be enumerated means that the capacity of the main memory reaches the upper limit in the calculation process for enumerating the feasible mountains, and the calculation cannot be continued. Further, the fact that the set partitioning problem cannot be solved means that the capacity of the main memory reaches the upper limit in the calculation process of the optimum solution, and the calculation cannot be continued.

In this example, the calculation was performed in the following calculation environment.
Processor: Intel (registered trademark) Xeon (registered trademark) CPU E5-2687W@3.1GHz (2 processors)
Mounted memory (RAM): 128GB
OS: Windows7 (registered trademark) Professional 64-bit operation system Optimal calculation software: ILOG CPLEX (registered trademark) Cplex11.0 Concert25

FIG. 9 shows an example of the creation result of the mountain division plan. Here, the method described in this embodiment for 16 different types of steel material information in which the number n of elements n of the total set N is 50 (n = 50) (that is, a method of searching the neighborhood up to the first neighborhood row). And the method described in Patent Document 1 were compared. If the optimum solution was not obtained even after the calculation time reached 300 seconds, the calculation was terminated at that point. When the calculation is discontinued in this way, the solution is evaluated by the gap between the solution obtained at the time of discontinuing the calculation and the optimum solution (= {(upper bound value-lower bound value) ÷ upper bound value} × 100). I decided to do it.

In FIG. 9, "Data" is an identification number of 16 kinds of steel material information. The comparative example shows that it is the result by the method described in Patent Document 1, and the invention example shows that it is the result by the method described in this embodiment. The time indicates the calculation time, and the gap indicates the gap between the solution obtained at the time when the calculation is terminated and the optimum solution described above. "Av." Indicates an average value. Further, "AT" indicates that a feasible solution could not be obtained within the time limit of 300 seconds, and "LM" indicates that the calculation could not be performed due to insufficient memory.

In FIG. 9, Data 2, 6 to 10, 16 are difficult problems that cannot be solved even by the method described in Patent Document 1, but in the method of the present embodiment, a feasible solution is required, and in most cases, a feasible solution is required. It can be seen that the optimum solution is obtained.
As described above, in the method of this embodiment, when applying the partitioning problem to the partitioning problem, column generation is performed for a large-scale problem in which the feasible mountain m _j (column) cannot be listed due to lack of memory or the like. It turns out that the law applies. Further, as described above, when the column generation method is applied to a 0-1 integer programming problem such as a mountain division problem, an error due to the 0-1 condition is unavoidable (relative error shown in FIG. 2). See). On the other hand, in the method of the present embodiment, it is possible to deal with the problem of the scale of the actual operation by efficiently searching for the optimum solution candidate column in the vicinity of the column group obtained by the column generation process. , It is possible to formulate an optimal mountain division plan even for large-scale problems.

FIG. 10 is a diagram showing an example of the calculation time in the method described in the present embodiment and the method described in <Modification 2> in a table format. Here, calculations were performed until the optimum solution was obtained for each method.
In FIG. 10, “Data” is an identification number of steel material information and corresponds to “Data” shown in FIG. The first aspect of the invention shows the calculation time (seconds) in the method of the present embodiment. That is, in Invention Example 1, the equation (25) is not used. Invention Example 2 shows the calculation time (seconds) in the method described in <Modification Example 2>. In Invention Example 2, the calculation of the column generator problem S is terminated when the dual gap becomes G _S shown in Eq. (25).
As shown in FIG. 10, it can be seen that the calculation time can be reduced to about half by applying the method described in <Modification 2>.

<Other variants>
The present embodiment and each modification described above can be realized by executing a program by a computer. Further, a computer-readable recording medium on which the program is recorded and a computer program product such as the program can also be applied as the present embodiment and each modification. As the recording medium, for example, a flexible disk, a hard disk, an optical disk, a magneto-optical disk, a CD-ROM, a magnetic tape, a non-volatile memory card, a ROM, or the like can be used.
Further, the present embodiment and each modification described above are merely examples of embodiment in carrying out the present invention, and the technical scope of the present invention is limitedly interpreted by these. It shouldn't be. That is, the present invention can be implemented in various forms without departing from the technical idea or its main features.

(Relationship with claims)
An example of the correspondence between the claims and the embodiments will be described below. The description of the claims is not limited to the description of the embodiment, as described in the modified examples and the like.
<Claims 1 and 2>
The predetermined constraint is realized by, for example, the equations (17) and (18).
The decision variable (binary variable) is realized by, for example, the decision variable x [j].
The column cost, which is an evaluation value for the pile of the target material for the feasible mountain, is realized by, for example, the column cost c _j (the number of piles c _1j , the number of temporary placements c _2j ).
The objective function of the original problem is realized by, for example, Eq. (4).
The column generation means is realized by, for example, the column generation unit 123. The candidate mountain is realized by, for example, a feasible mountain m _j based on the mountain constituent steel material presence / absence variable m _j [i] derived by the column generation unit 123.
The search means is realized by, for example, the neighborhood search unit 134.
For each candidate mountain included in the set, the feasible mountain in the vicinity where a part of the target material has a different configuration is added to, for example, 1 increase neighborhood mountain set C _{nb_p} and 1 decrease neighborhood mountain set C _{nb_m1} . It is realized by the increasing neighborhood mountain m _{j_np} and the decreasing neighborhood mountain m _{j_nb} (see also <Modification example 1> etc.).
The first original problem deriving means is realized by, for example, the processing original problem deriving unit 135.
The output means is realized by, for example, the output unit 140.
<Claim 3>
The increasing neighborhood mountain is realized by, for example, the 1 increasing neighborhood mountain m _{j_np} added to the 1 increasing neighborhood mountain set C _{nb_p} , and the decreasing neighborhood mountain is realized by, for example, the 1 decreasing neighborhood mountain added to the 1 decreasing neighborhood mountain set C _{nb_m} . It is realized by m _{j_nb} .
<Claim 4>
Claim 4 is based on <Modification 1>.
The first Masu neighborhood mountain to the nth Masu neighborhood mountain are realized by, for example, the 1 Masu neighborhood mountain set C _{nb_p} included in the set C _LS1 to C _LSn of the feasible mountain m _j obtained by the processing unit 130. To.
The first reduced neighborhood mountain to the nth reduced neighborhood mountain is realized by, for example, the one reduced neighborhood mountain set C _{nb_m} included in the set C _LS1 to C _LSn of the feasible mountain m _j obtained by the processing unit 130. To.
<Claim 5>
The constraint equation is realized by, for example, the constraint equation of equation (2).
The objective function is realized by, for example, Eq. (3).
The column cost for the feasible mountain is realized by, for example, the column cost c _j , the number of feasible mountains is realized by, for example, the number of mountains c _1j , and the temporary placement number is realized by, for example, the temporary placement number c _{2 j} . Will be done.
<Claim 6>
The dual solution derivation means is realized by, for example, the dual solution derivation unit 122.
The dual solution is realized by, for example, the dual solution p _sol [i].
The column determination means is realized by, for example, the column determination unit 124.
The column addition means is realized by, for example, the column addition unit 125.
<Claim 7>
The second original problem deriving means is realized by, for example, the preprocessing original problem deriving unit 132.
The process execution determination means is realized by, for example, the present process execution determination unit 133.
The optimum value of the original problem derived by the second original problem deriving means is realized by, for example, the original problem optimum value _{VP (C cg )} .
When the column determination means determines that the candidate mountain derived by the column generation means is a mountain satisfying the convergence requirement, the dual solution derived by the dual solution derivation means is obtained. The dual optimum value, which is the value of the objective function of the dual problem at the time, is realized by, for example, the dual optimum value V _D (C _cg ).
<Claim 8>
To compare the column cost for the feasible mountain having a configuration different from that of the candidate mountain included in the set of feasible mountains and the dual cost for the feasible mountain, for example, the processing execution determination unit 133 may use the original. Problem This is achieved by subtracting the dual optimal value V _D (C _cg ) from the optimal value V _P (C _cg ) (see also step S510).
The dual cost for the feasible mountain is realized by, for example, the dual cost _Pj (see also the left side of Eq. (9)).
The pile constituent target material presence / absence variable is realized by, for example, the pile constituent steel material presence / absence variable m _j [i].
<Claim 9>
The constraint equation is realized by, for example, the equation (9).
The objective function is realized by, for example, Eq. (11).
The dual cost for the feasible mountain is realized by, for example, the dual cost _Pj (see also the left side of Eq. (9)).
The mountain constituent target material presence / absence variable corresponding to the feasible mountain is realized by, for example, the pile constituent steel material presence / absence variable m _j [i].
The dual variable is realized by, for example, p [i].
<Claim 10>
The constraint equation is realized by, for example, equations (13) to (18) (see also <modification example 3> and the like).
The objective function is realized by, for example, Eq. (21).
The target material vertical relation variable is realized by, for example, the steel material vertical relation variable y [i ₁ ] [i ₂ ].
The pile constituent target material presence / absence variable is realized by, for example, the pile constituent steel material presence / absence variable m _j [i].
<Claim 11>
The constraint equation is realized by, for example, equation (22) (see also <modification example 3> and the like).
<Claim 12>
Claim 12 is based on <Modification 2>.
The limit value is realized by, for example, G _S.
The absolute value of the value obtained by subtracting the dual cost for the feasible mountain from the cost of the feasible mountain which is the candidate mountain based on the mountain constituent target material presence / absence variable which is the previous solution of the column generator problem is, for example, , | Rc _prv |.
The predetermined value is realized by, for example, "1".
<Claim 13>
The temporary placement presence / absence variable is realized by, for example, the temporary placement presence / absence variable t [i].
The column cost of the feasible mountain, which is the candidate mountain, can be expressed by using the temporary placement / non-presence variable, for example, by the equation (19).
It is realized, for example, by the equation (16) that the constraint equation expressing the predetermined constraint is further expressed by using the temporary placement / presence / absence variable.
<Claim 14>
The set of feasible mountains given as the initial solution is realized by, for example, the initial value of the set C of the feasible mountains m _j set by the initial column set setting unit 121.

100: Steel material mountain division plan creation device, 110: Steel material information acquisition unit, 120: Pretreatment unit, 121: Initial column set setting unit, 122: Dual solution derivation unit, 123: Column generation unit, 124: Column determination unit, 125 : Column addition unit, 130: Main processing unit, 131: Dual optimum value acquisition unit, 132: Preprocessing original problem derivation unit, 133: Main processing execution determination unit, 134: Neighborhood search unit, 135: Main processing original problem derivation unit , 140: Output section

Claims (16)

It is a mountain division plan creation device that creates a mountain division plan by solving the group division problem by using a column generation method, with the problem of creating a mountain division plan for a plurality of target materials as a set division problem.
A column cost, which is an evaluation value for the pile of the target material for the feasible mountain, using a binary variable that determines whether or not to adopt the feasible mountain piled up so as to satisfy a predetermined constraint as a decision variable. The original problem is to find the optimum combination of the feasible peaks including the plurality of target materials without duplication and omission by finding the determination variable in which the value of the objective function including the above is the minimum or the maximum.
A column generator that generates a candidate mountain that is a candidate for a feasible mountain that constitutes the optimum solution of the original problem, and a column generation means that derives the optimum solution of the problem.
When the set of the candidate mountains derived by the column generation means does not satisfy a predetermined convergence requirement, the realization of the vicinity in which a part of the target material has a different configuration for each candidate mountain included in the set. A search means for searching for possible mountains and adding the feasible mountains in the vicinity of the search as the candidate mountains.
The optimum value of the original problem is derived by solving the original problem based on the set of the feasible mountains including the candidate mountain derived by the column generation means and the candidate mountain added by the search means. The first means of deriving the original problem and
An output means for outputting information indicating a combination of feasible peaks corresponding to the optimum value of the original problem derived by the first original problem deriving means as information indicating an optimum solution of the original problem.
A mountain division planning device characterized by having. The search means searches for at least one of at least one increasing neighborhood mountain and at least one decreasing neighborhood mountain for each of the candidate mountains included in the set of feasible mountains.
The Masu neighborhood mountain is a target material in at least one of at least one of the top and bottom stages of the candidate mountain included in the set of feasible mountains and between two adjacent target materials. The feasible mountain to which at least one is added, and the feasible mountain that can be a candidate for the feasible mountain constituting the optimum solution of the original problem.
The reduced neighborhood mountain is the feasible mountain from which at least one of the target materials constituting the candidate mountain included in the set of feasible mountains is removed, and is a feasible mountain that constitutes the optimum solution of the original problem. The mountain division plan creating device according to claim 1, wherein the mountain is a feasible mountain that can be a candidate for. The Masu neighborhood mountain is the one in which one target material is added to any one of the uppermost stage, the lowest stage, or between two adjacent target materials included in the set of feasible mountains. It is a feasible mountain that can be a candidate for a feasible mountain that constitutes the optimum solution of the original problem.
The reduced neighborhood mountain is the feasible mountain from which one of the target materials constituting the candidate mountain included in the set of feasible mountains is removed, and is a feasible mountain that constitutes the optimum solution of the original problem. The mountain division planning apparatus according to claim 2, wherein the mountain is a feasible mountain that can be a candidate. The search means searches for the first increasing neighborhood mountain to the nth increasing neighborhood mountain as the increasing neighborhood mountain, and searches for the first decreasing neighborhood mountain to the n decreasing neighborhood mountain as the decreasing neighborhood mountain. death,
n is an integer of 2 or more,
The first Masu neighborhood mountain is the uppermost mountain of the candidate mountain included in the set of feasible mountains at the time when the candidate mountain derived by the column generation means becomes a mountain satisfying the convergence requirement. It is the feasible mountain to which one target material is added to either one of the bottom or two adjacent target materials, and it is a candidate for the feasible mountain that constitutes the optimum solution of the original problem. The above-mentioned feasible mountain to get,
The nth Masu neighborhood mountain is the top, bottom, or two adjacent target materials of the candidate mountain included in the set of feasible mountains at the time when the n-1 Masu neighborhood mountain is added. The feasible mountain to which one target material is added to any one of the spaces, and the feasible mountain that can be a candidate for the feasible mountain constituting the optimum solution of the original problem.
The first reduced neighborhood mountain is an object constituting the candidate mountain included in the set of feasible mountains at the time when the candidate mountain derived by the column generation means becomes a mountain satisfying the convergence requirement. It is the feasible mountain from which one of the materials is removed, and it is the feasible mountain that can be a candidate for the feasible mountain that constitutes the optimum solution of the original problem.
The nth reduced neighborhood mountain is the feasible mountain obtained by removing one of the target materials constituting the candidate mountain included in the set of the feasible mountains at the time when the n-1 reduced neighborhood mountain is added. The mountain division plan creating device according to claim 3, wherein the feasible mountain can be a candidate for a feasible mountain constituting the optimum solution of the original problem. The original problem is a constraint expression that expresses a constraint that one feasible mountain including the target material is always selected from the set of feasible mountains for each of the plurality of target materials. Using the constraint formula expressed using the determinant and the objective function of the original problem, the determinant whose value of the objective function is minimized within the range satisfying the constraint equation is determined. -1 It is an integer programming problem,
The binary variable is "1" for each of the plurality of feasible mountains when the feasible mountain is adopted as the solution, and "0 (zero)" when the feasible mountain is not adopted as the solution. Is a 0-1 variable
The objective function of the original problem is an objective function for obtaining the sum of the column costs for the feasible peaks included in the set of feasible peaks, and uses the determination variable and the column cost of the feasible peaks. It is an objective function that is represented.
The column cost for the feasible mountain includes the number of the feasible mountain and the number of temporary placements.
The temporary storage number is the number of the target materials to be temporarily placed in the temporary storage place before being placed in the payout mountain.
The mountain according to any one of claims 1 to 4, wherein the payout mountain is a mountain made of the target material and is a mountain that has become the final mountain shape to be paid out in the next step. Mountain division planning device. A dual solution deriving means for deriving a dual solution, which is the optimum solution of the dual problem when the linear relaxation problem of the original problem is used as the main problem.
A column determination means for performing column determination, which is a determination as to whether or not the candidate mountain derived by the column generation means is a mountain that satisfies the convergence requirement.
When it is determined by the column determining means that the candidate mountain derived by the column generating means does not satisfy the convergence requirement, the candidate mountain generated by the column generating means is used as the feasible mountain. Further has a means for adding columns to be added to the set,
The derivation of the dual solution by the dual solution deriving means and the column generation until the candidate mountain derived by the column generating means is determined by the column determining means to be a mountain satisfying the convergence requirement. Convergence calculation is executed by repeating the derivation of the optimum solution of the column generator problem by the means, the column determination, and the addition of the candidate mountain by the column addition means.
In the search means, the candidate mountain derived by the column generation means is derived after the column determination means determines that the candidate mountain derived by the column generation means is a mountain satisfying the convergence requirement. For each candidate mountain included in the set of, the feasible mountain in the vicinity where a part of the target material has a different configuration is searched, and the feasible mountain in the vicinity of the searched is added as the candidate mountain.
Any of claims 1 to 5, wherein the column generator problem is a problem of finding the candidate mountain to be added to the set of feasible mountains by using the dual solution and the predetermined constraint. Or the mountain division planning device described in item 1. By solving the original problem based on the set of feasible mountains at the time when it is determined by the column determination means that the candidate mountain derived by the column generation means is a mountain satisfying the convergence requirement. , A second original problem deriving means for deriving the optimum value of the original problem,
It is determined by the column determining means that the optimum value of the original problem derived by the second original problem deriving means and the candidate mountain derived by the column generating means are mountains satisfying the convergence requirement. Based on the result of comparison with the dual optimum value, which is the value of the objective function of the dual problem when the dual solution derived by the dual solution deriving means is obtained, the search means is used. A process execution determination means for determining whether or not to execute a process,
When the search means determines that the process by the search means is to be executed by the process execution determination means, the search means performs the search and the addition.
When the column determination means determines that the output means does not execute the process by the search means, the process execution determination means of the original problem derived by the second original problem derivation means. The mountain division plan creating device according to claim 6, wherein information indicating the combination of feasible mountains corresponding to the optimum value is output as information indicating the optimum solution of the original problem. The search means is based on the result of comparing the column cost for the feasible mountain having a configuration different from that of the candidate mountain included in the set of feasible mountains and the dual cost for the feasible mountain. It is determined whether or not the mountain is a feasible mountain that can be a candidate for a feasible mountain that constitutes the optimum solution of the original problem.
The dual cost for the feasible mountain is the sum of the value of the dual variable for the target material and the product of the target material and the mountain constituent target material presence / absence variable corresponding to the feasible mountain for the plurality of target materials. Represented
The dual variable is a decision variable in the dual problem.
The mountain constituent target material presence / absence variable is a 0-1 variable determined for each target material, and is "1" when the target material is included in the feasible mountain, and "0 (zero)" when the target material is not included. ) ”, The mountain division planning apparatus according to claim 6 or 7. The dual problem is a constraint expression that expresses a constraint that the cost of each of the feasible mountains included in the set of feasible mountains is equal to or higher than the dual cost for the feasible mountain, and is a sequence of the feasible mountains. To the extent that the constraint equation is satisfied using the constraint equation expressed using the cost, the variable with or without the material to be constructed of the mountain corresponding to the feasible mountain, and the dual variable, and the objective function of the dual problem. It is a linear programming problem that determines the value of the dual variable that maximizes the value of the objective function as the dual solution.
The objective function of the dual problem is an objective function for obtaining the sum of the dual variables for the plurality of target materials, and is an objective function expressed by using the dual variables.
The dual variable is a variable defined for each target material, and is a variable.
The dual cost for the feasible mountain is the sum of the product of the value of the dual variable for the target material and the mountain constituent target material presence / absence variable corresponding to the feasible mountain for the plurality of target materials. Represented by
The mountain constituent target material presence / absence variable is a 0-1 variable determined for each target material, and is "1" when the target material is included in the feasible mountain, and "0 (zero)" when the target material is not included. ) ”, The mountain division planning apparatus according to claim 8, wherein the variable is 0-1. The column generator problem is a constraint expression that expresses the predetermined constraint, and is a constraint expression that is expressed by using the mountain constituent target material presence / absence variable and the target material vertical relation variable, and the feasible that is the candidate mountain. It is an objective function to obtain the value obtained by subtracting the dual cost for the feasible mountain from the column cost of the mountain, and is expressed by using the dual variable, the mountain constituent target material presence / absence variable, and the target material vertical relation variable. In the 0-1 integer planning problem to determine the mountain-constituting target material presence / absence variable and the target material vertical relation variable that minimizes the value of the objective function within the range that satisfies the constraint equation. can be,
The target material vertical relationship variable is a 0-1 variable determined by a combination of the two target materials, and is a 0-1 variable representing the vertical relationship between the two target materials in the same payout mountain.
The mountain division planning apparatus according to claim 9, wherein the payout mountain is a mountain composed of the target material and is a mountain that has become the final mountain shape to be paid out to the next process. The column generator problem is a problem further having a constraint equation indicating that the cost of the feasible mountain, which is the candidate mountain, is equal to or less than the dual cost for the feasible mountain.
When the executable solution of the column generator problem is obtained, the column generator means terminates the calculation for the column generator problem, and based on the mountain construct material presence / absence variable which is the executable solution, the column generator means. The mountain division planning apparatus according to claim 10, wherein a candidate mountain is generated. The column generator means derives a dual gap based on the upper bound value and the lower bound value in the column generator problem, and if it is determined that the dual gap is equal to or less than the limit value, the calculation for the column generator problem is terminated. , The candidate mountain is generated based on the mountain constituent target material presence / absence variable which is the solution of the column generator problem obtained at that time.
The limit value is a value obtained by subtracting the dual cost for the feasible mountain from the cost of the feasible mountain which is the candidate mountain based on the mountain constituent target material presence / absence variable which is the previous solution of the column generator problem. The mountain division planning apparatus according to claim 10 or 11, wherein a predetermined value or a value corresponding to the absolute value is taken according to the absolute value. The constraint expression expressing the predetermined constraint is further expressed by using the temporary placement / presence / absence variable.
The column cost for the feasible mountain that is the candidate mountain is expressed using the temporary placement / non-presence variable.
The temporary storage presence / absence variable is a 0-1 variable determined for each target material, and becomes "1" when the target material is temporarily placed in the temporary storage place before being placed in the payout mountain. The mountain division planning apparatus according to any one of claims 10 to 12, wherein the variable is a 0-1 variable that becomes "0 (zero)" if the above is not the case. The original problem uses the binary variable as the determinant, the column cost, and the set of feasible peaks given as the initial solution, and the value of the objective function including the determinant and the column cost is the smallest. Alternatively, claim 1 to 13, wherein the problem is to obtain the optimum combination of the feasible peaks including the plurality of target materials without duplication and without omission by obtaining the determination variable that becomes the maximum. The mountain division plan making device according to any one of the items. It is a method of creating a mountain division plan that creates a mountain division plan by solving the group division problem using a column generation method, with the problem of creating a mountain division plan for a plurality of target materials as a set division problem.
A column cost, which is an evaluation value for the pile of the target material for the feasible mountain, using a binary variable that determines whether or not to adopt the feasible mountain piled up so as to satisfy a predetermined constraint as a decision variable. The original problem is to find the optimum combination of the feasible peaks including the plurality of target materials without duplication and omission by finding the determination variable in which the value of the objective function including the above is the minimum or the maximum.
A column generation step in which a computer derives an optimum solution for a column generator problem that generates candidate mountains that are candidates for feasible mountains that constitute the optimum solution for the original problem.
When the set of the candidate mountains derived by the column generation step does not satisfy a predetermined convergence requirement, a computer performs a neighborhood in which a part of the target material is different for each candidate mountain included in the set. A search step of searching for the feasible mountain in the above and adding the feasible mountain in the vicinity of the searched as the candidate mountain.
The computer solves the original problem based on the set of feasible mountains including the candidate mountains derived by the column generation step and the candidate mountains added by the search step, so that the optimum value of the original problem is obtained. The first original problem derivation step to derive
An output step in which the computer outputs information indicating the combination of the feasible peaks corresponding to the optimum value of the original problem derived by the first original problem derivation step as information indicating the optimum solution of the original problem. ,
A method of creating a mountain division plan, which is characterized by having. A program characterized in that a computer functions as each means of the mountain division planning apparatus according to any one of claims 1 to 14.

Images