JP6725920B2 - Set division problem solving apparatus, method, and program - Google Patents
Set division problem solving apparatus, method, and program Download PDFInfo
- Publication number
- JP6725920B2 JP6725920B2 JP2017139319A JP2017139319A JP6725920B2 JP 6725920 B2 JP6725920 B2 JP 6725920B2 JP 2017139319 A JP2017139319 A JP 2017139319A JP 2017139319 A JP2017139319 A JP 2017139319A JP 6725920 B2 JP6725920 B2 JP 6725920B2
- Authority
- JP
- Japan
- Prior art keywords
- solution
- depth
- subset
- subsets
- solutions
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Landscapes
- Complex Calculations (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
本発明は、集合分割問題求解装置、方法、及びプログラムに係り、特に、集合分割問題を解くための集合分割問題求解装置、方法、及びプログラムに関する。 The present invention relates to a set division problem solving apparatus, method, and program, and more particularly to a set division problem solving apparatus, method, and program for solving a set division problem.
組合せ最適化問題の一種である、集合分割問題は、Ｍ個の要素からなる全体集合Ｕ = ｛1,...,Ｍ｝、Ｎ個のＵの部分集合
から構成される集合Ｓ＝｛ｓ１,ｓ２，．．．，ｓＮ｝および各siに対する非負のコストc(si)が与えられたときに、
を満たし、かつすべての
であるような
に対して
を満たすような
のうち、コストの総和
を最小とするものを見つける問題である。集合分割問題は、
The set partitioning problem, which is a kind of combinatorial optimization problem, is a total set U={1,...,M} consisting of M elements, and a subset of N U elements.
Set S={s 1 , s 2 ,. ． ． , S N } and a non-negative cost c(s i ) for each s i ,
Meet all and
As is
Against
To meet
Of, the total cost
The problem is to find the one that minimizes. The set partitioning problem is
としても表現できる。ここでxj はsjが解に含まれたときに1、そうでないと0となる二値変数である。cjはc(sj)の値を表す。aijは，全体集合のi番目の要素がsjに含まれているときに1、そうでないときに0をとる。なお，以下ではx1,...,xNをあわせてＮ次元の二値ベクトルＸとして表現する。また、Ｘへのある値｛0,1｝Nの割当をxとして表現する。 Can be expressed as Where x j is a binary variable that is 1 when s j is included in the solution and 0 otherwise. c j represents the value of c(s j ). a ij takes 1 when the ith element of the whole set is contained in s j , and 0 otherwise. In the following, x 1 ,..., X N are combined and expressed as an N-dimensional binary vector X. Also, the assignment of a certain value {0,1} N to X is expressed as x.
集合分割問題はNP困難であることが知られている。 It is known that the set partitioning problem is NP-hard.
大規模な集合分割問題の最適解を求めることは一般に非常に困難である。そこで、最適解でなくとも効率的によい解を見つけることが可能な局所探索法に基づく近似解法が用いられている（非特許文献１）。 It is generally very difficult to find an optimal solution for a large-scale set partitioning problem. Therefore, an approximate solution method based on a local search method that can efficiently find a good solution even if it is not the optimum solution is used (Non-Patent Document 1).
局所探索法は高速に探索を実行できるものの、制約条件を満たす解（実行可能解）を効率的に見つけることができないという課題があった。 Although the local search method can execute a search at high speed, it has a problem that a solution (feasible solution) satisfying the constraint cannot be efficiently found.
本発明は、上記の事情に鑑みてなされたもので、集合分割問題の近似解を効率的に求めることができる集合分割問題求解装置、方法、及びプログラムを提供することを目的とする。 The present invention has been made in view of the above circumstances, and an object of the present invention is to provide a set division problem solving apparatus, method, and program that can efficiently obtain an approximate solution of a set division problem.
上記目的を達成するために、本発明に係る集合分割問題求解装置は、要素の全体集合を、コストの総和が最小となる複数の部分集合に分割する集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返す局所探索実行部と、前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、何れの部分集合にも含まれない要素の集合と、２以上の部分集合に含まれる要素を含む前記部分集合との和集合を全体集合とする厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、２以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求める深さ優先探索実行部と、を含んで構成されている。 In order to achieve the above object, a device for solving a set partitioning problem according to the present invention uses a local search method to find a solution candidate for a set partitioning problem in which a total set of elements is divided into a plurality of subsets having a minimum sum of costs. A local search execution unit that repeats updating and updating the updated solution candidates to calculate the degree of violation of the constraint condition of the set division problem; and when the calculated degree of violation is less than or equal to a threshold, the solution candidates Based on, a strict coverage problem is created that sets the union of a set of elements that is not included in any subset and the subset that includes elements included in two or more subsets as the entire set, and All solutions of the covering problem are obtained by a depth-first search, and among all the solutions of the exact covering problem, a solution that minimizes the sum of the costs and two or more subsets included in the solution candidate are obtained. And a depth-first search execution unit that obtains an approximate solution of the set division problem based on the subset other than the subset including the included element.
本発明に係る集合分割問題求解方法は、局所探索実行部が、要素の全体集合を、コストの総和が最小となる複数の部分集合に分割する集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返し、前記深さ優先探索実行部が、前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、何れの部分集合にも含まれない要素の集合と、２以上の部分集合に含まれる要素を含む前記部分集合との和集合を全体集合とする厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、２以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求める。 In the method of solving a set partitioning problem according to the present invention, a local search executing unit updates a solution candidate for a set partitioning problem in which a total set of elements is divided into a plurality of subsets having a minimum sum of costs by a local search method. , For the updated solution candidate, repeating the calculation of the violation degree of the constraint condition of the set division problem, the depth-first search execution unit, when the calculated violation degree is below a threshold, Create a strict coverage problem based on the solution candidates, which is the union of a set of elements that are not included in any subset and the subset that includes elements included in two or more subsets, All the solutions of the strict coverage problem are obtained by depth-first search, and among all the solutions of the strict coverage problem, the solution that minimizes the sum of the costs and two or more parts included in the solution candidate An approximate solution of the set division problem is obtained based on the subset other than the subset including the elements included in the set.
本発明に係るプログラムは、コンピュータを、上記発明に係る集合分割問題求解装置の各部として機能させるためのプログラムである。 A program according to the present invention is a program for causing a computer to function as each unit of the set division problem solving apparatus according to the present invention.
以上説明したように、本発明に係る集合分割問題求解装置、方法、及びプログラムによれば、集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、前記集合分割問題の制約条件の違反度を計算することを繰り返し、前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、２以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求めることにより、集合分割問題の近似解を効率的に求めることができる。 As described above, according to the set partitioning problem solving apparatus, method, and program according to the present invention, the solution candidates for the set partitioning problem are updated by the local search method, and the updated solution candidates are Repeating the calculation of the degree of violation of the constraint condition, when the calculated degree of violation is less than or equal to a threshold value, based on the solution candidates, create a strict covering problem, and solve all the solutions of the strict covering problem. , A solution that minimizes the sum of the costs among all the solutions of the strict coverage problem obtained by a depth-first search, and the part that includes an element included in two or more subsets included in the solution candidate An approximate solution of the set division problem can be efficiently obtained by obtaining an approximate solution of the set division problem based on the subset other than the set.
以下、図面を参照して、本発明を実施するための形態の一例について詳細に説明する。 Hereinafter, an example of a mode for carrying out the present invention will be described in detail with reference to the drawings.
[本発明の実施形態の概要]
本実施形態においては、集合分割問題の解の制約に対する違反度を導入し、局所探索法を実行しつつ、解の制約に対する違反度がしきい値以下になった場合に、深さ優先探索に基づく解法に切り替えることによって探索を高速化する。局所探索法によって解の大部分を求めてから、深さ優先探索法に切り替えることによって、集合分割問題の解を高速に発見する。
[Outline of Embodiment of the Present Invention]
In the present embodiment, when the degree of violation of the solution constraint of the set partitioning problem is introduced and the degree of violation of the solution constraint is equal to or less than a threshold value while executing the local search method, the depth-first search is performed. Speed up the search by switching to the solution method based on. After finding most of the solutions by the local search method, the solution of the set partitioning problem is found at high speed by switching to the depth-first search method.
ここで、集合分割問題の解の制約に対する違反度について説明する。ある解xが与えられたときに、yiを Here, the degree of violation of the solution constraint of the set division problem will be described. Given a solution x, let y i
と定義する。xがすべての制約条件を満たすときには、すべてのiについてyi=0を満たす。このとき、違反度Ｖ（ｘ）を以下の式で表わす。 It is defined as. When x satisfies all the constraints, y i =0 is satisfied for all i. At this time, the violation degree V(x) is represented by the following formula.
上記の式に示すように、違反度Ｖ（ｘ）は、各要素ｘiについて、解候補ｘに当該要素ｘiが何れの部分集合にも含まれないこと、及び当該要素ｘiが２以上の部分集合に含まれることを表している。 As shown in the above equation, the violating degree V(x) is such that, for each element x i , the solution candidate x does not include the element x i in any subset, and the element x i is 2 or more. Is included in the subset.
＜本実施形態に係る集合分割問題求解装置の構成＞
図１は、本発明の実施形態に係る集合分割問題求解装置１０の機能的な構成の一例を示すブロック図である。
<Configuration of Set Division Problem Solving Device According to this Embodiment>
FIG. 1 is a block diagram showing an example of a functional configuration of a set division problem solving device 10 according to the embodiment of the present invention.
図１に示すように、集合分割問題求解装置１０は、問題入力部１２と、局所探索実行部１４と、深さ優先探索実行部１６と、計算結果出力部１８と、を備えている。 As shown in FIG. 1, the set division problem solving device 10 includes a problem input unit 12, a local search execution unit 14, a depth-first search execution unit 16, and a calculation result output unit 18.
本実施形態に係る集合分割問題求解装置１０は、ＣＰＵ（Central Processing Unit）、ＲＡＭ(Random Access memory)、ＲＯＭ(Read Only Memory)、及びＨＤＤ(Hard Disk Drive)等を備えたコンピュータとして構成される。ＲＯＭには、本実施形態に係る集合分割問題求解処理を実行するためのプログラムが記憶されている。なお、プログラムは、ＨＤＤに記憶されていてもよい。 The set partitioning problem solving apparatus 10 according to the present embodiment is configured as a computer including a CPU (Central Processing Unit), a RAM (Random Access Memory), a ROM (Read Only Memory), an HDD (Hard Disk Drive), and the like. .. A program for executing the set division problem solving process according to the present embodiment is stored in the ROM. The program may be stored in the HDD.
上記のプログラムは、例えば、集合分割問題求解装置１０に予めインストールされていてもよい。プログラムは、不揮発性の記憶媒体に記憶して、又は、ネットワークを介して配布して、集合分割問題求解装置１０に適宜インストールすることで実現してもよい。なお、不揮発性の記憶媒体の例としては、ＣＤ-ＲＯＭ(Compact Disc Read Only Memory)、光磁気ディスク、ＤＶＤ-ＲＯＭ(Digital Versatile Disc Read Only Memory)、フラッシュメモリ、メモリカード等が挙げられる。 The above program may be installed in advance in the set division problem solving device 10, for example. The program may be realized by being stored in a non-volatile storage medium or distributed via a network and appropriately installed in the set partitioning problem solving apparatus 10. Examples of the non-volatile storage medium include a CD-ROM (Compact Disc Read Only Memory), a magneto-optical disc, a DVD-ROM (Digital Versatile Disc Read Only Memory), a flash memory, and a memory card.
ＣＰＵは、ＲＯＭに記憶されているプログラムを読み込んで実行することにより、集合分割問題求解装置１０の各部として機能する。 The CPU functions as each unit of the set division problem solving apparatus 10 by reading and executing the program stored in the ROM.
問題入力部１２は、集合分割問題を外部より受け取る。具体的には、aij(i∈｛1,...,M｝、ｊ∈｛1,...,Ｎ｝)及びｃj（ｊ＝1,...,Ｎ）を入力として受け取る。 The problem input unit 12 receives a set division problem from the outside. Specifically, it receives a ij (i ∈ {1,...,M}, j ∈ {1,...,N}) and c j (j=1,...,N) as input. ..
局所探索実行部１４は、問題入力部１２より入力された集合分割問題に対して局所探索法を実行する。 The local search execution unit 14 executes the local search method for the set division problem input from the problem input unit 12.
具体的には、局所探索実行部１４は、要素の全体集合Ｕを、コストの総和が最小となる複数の部分集合に分割する集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、集合分割問題の制約条件の違反度を計算することを繰り返す。 Specifically, the local search execution unit 14 updates the solution candidate for the set division problem that divides the entire set U of elements into a plurality of subsets having the minimum total cost by the local search method, and is updated. For the solution candidates, the calculation of the degree of violation of the constraint condition of the set partitioning problem is repeated.
局所探索法は、あるx1,. ..,xNへの値の割当を初期解として、そこから割当を部分的に変更することで、よりよい実行可能解を得るための方法である。 The local search method is a method for obtaining a better feasible solution by setting a value assignment to a certain x 1 ,.. .,x N as an initial solution and then partially changing the assignment.
また、局所探索実行部１４は、探索の進み具合に相当する、集合分割問題の制約条件の違反度が閾値以下となった場合に、深さ優先探索実行部１６を用いて部分問題に対する深さ優先探索を実行する。 Further, the local search executing unit 14 uses the depth-first search executing unit 16 to determine the depth of the partial problem when the degree of violation of the constraint condition of the set partitioning problem, which corresponds to the progress of the search, is equal to or less than a threshold value. Perform a priority search.
深さ優先探索実行部１６は、局所探索実行部１４より解候補を受け取り、集合分割問題の部分問題を作成し、集合分割問題の部分問題に対する深さ優先探索を実行して、部分問題に対する最適解を得て、最適解から求まる集合分割問題の近似解を局所探索実行部１４に返却する処理を実行する。 The depth-first search executing unit 16 receives the solution candidates from the local search executing unit 14, creates a subproblem of the set partitioning problem, executes a depth-first search for the subproblem of the set partitioning problem, and optimizes the subproblem. A process of obtaining a solution and returning an approximate solution of the set division problem obtained from the optimum solution to the local search execution unit 14 is executed.
具体的には、深さ優先探索実行部１６は、計算された違反度が閾値以下となったときに、解候補に基づいて、何れの部分集合にも含まれない要素の集合と、２以上の部分集合に含まれる要素を含む部分集合との和集合を全体集合とする厳密被覆問題を、集合分割問題の部分問題として作成し、厳密被覆問題の全ての解を、深さ優先探索により求め、厳密被覆問題の全ての解のうち、コストの和を最小とする解と、解候補に含まれる、２以上の部分集合に含まれる要素を含む部分集合ではない部分集合とに基づいて、集合分割問題の近似解を求める。 Specifically, the depth-first search executing unit 16 sets, based on the solution candidates, a set of elements that are not included in any subset when the calculated violation degree is equal to or less than a threshold value, and 2 or more. We create a strict coverage problem that is the union with the subset that contains the elements included in the subset of, as a subproblem of the set partitioning problem, and find all the solutions of the strict coverage problem by depth-first search. , A set of all solutions of the strict coverage problem that minimizes the sum of costs and a subset that is included in the solution candidate and is not a subset that includes elements included in two or more subsets Find an approximate solution to the split problem.
ここで、深さ優先探索実行部１６は、厳密被覆問題の全ての解を、深さ優先探索により求め、厳密被覆問題の全ての解のうち、コストの和を最小とする解を求める際には、厳密被覆問題の全ての解を保持するゼロサプレス型二分決定グラフ(Zero-suppressed Binary Decision Diagram)を、深さ優先探索により構築し、ゼロサプレス型二分決定グラフが保持する厳密被覆問題の全ての解のうち、コストの和を最小とする解を求める。 Here, when the depth-first search execution unit 16 finds all solutions of the strict coverage problem by the depth-first search and finds a solution that minimizes the sum of costs among all the solutions of the strict coverage problem. Constructs a zero-suppressed binary decision diagram that holds all solutions of the exact covering problem by a depth-first search, and solves all solutions of the exact covering problem held by the zero-suppressed binary decision graph. Among them, the solution that minimizes the sum of costs is obtained.
予め定められた終了条件を満たすまで、局所探索実行部１４による処理と、深さ優先探索実行部１６による処理とを繰り返す。 The process by the local search executing unit 14 and the process by the depth-first search executing unit 16 are repeated until a predetermined end condition is satisfied.
計算結果出力部１８では、局所探索実行部１４で最終的に得られた集合分割問題に対する近似解を外部に出力する。 The calculation result output unit 18 outputs the approximate solution to the set division problem finally obtained by the local search execution unit 14 to the outside.
＜本実施形態に係る集合分割問題求解装置の作用＞
次に集合分割問題求解装置１０による処理の流れを図２の処理フローを用いて説明する。
<Operation of Set Division Problem Solving Device According to this Embodiment>
Next, the flow of processing by the set division problem solving device 10 will be described using the processing flow of FIG.
まず、ステップＳ０１で問題入力部１２にて外部から集合分割問題を受け取る。 First, in step S01, the problem input unit 12 receives a set division problem from the outside.
次に、ステップＳ０２で、上記非特許文献１に代表される、集合分割問題に対する局所探索法を実行する。局所探索アルゴリズムではある割当xから、その一部の要素の値を変更して別の割当x′を得て、Σcixiの値が改善されたならば解候補を更新することを繰り返して問題を解く。ステップＳ０２で局所探索を実行し、解候補が更新されたならば、次にステップＳ０３へ進み、更新後の解候補における違反度V(x)の値を計算し、あらかじめ定めたしきい値以下であったならば、ステップＳ０４に遷移する。しきい値より大きい場合には、上記ステップＳ０２に遷移し、局所探索を繰り返す。 Next, in step S02, a local search method for the set partitioning problem represented by Non-Patent Document 1 is executed. In the local search algorithm, the values of some elements are changed from one allocation x to obtain another allocation x′, and if the value of Σc i x i is improved, the solution candidate is repeatedly updated. Solve the problem. When the local search is executed in step S02 and the solution candidate is updated, the process proceeds to step S03, the value of the violation degree V(x) in the updated solution candidate is calculated, and is equal to or less than a predetermined threshold value. If so, the process proceeds to step S04. If it is larger than the threshold value, the process proceeds to step S02 and the local search is repeated.
ステップＳ０４で深さ優先探索を実行する。詳細については後述する。ステップＳ０５で、現在の探索が、予め定められた終了条件を満たしているならば現在の解候補を集合分割問題の近似解として出力して処理を終了する。終了条件としては、例えば、上記非特許文献１であるように、ある解候補とその一つ前に得られた解候補とのコストを比較して、コストの低下の度合いがあるしきい値を下回ったときに探索を終了するなどの方法が考えられる。 In step S04, the depth-first search is executed. Details will be described later. In step S05, if the current search satisfies a predetermined termination condition, the current solution candidate is output as an approximate solution of the set division problem, and the process ends. As the termination condition, for example, as in Non-Patent Document 1, the cost of a certain solution candidate is compared with the cost of the solution candidate obtained immediately before, and a threshold value having a degree of cost reduction is set. A method such as ending the search when the value falls below is conceivable.
次にステップＳ０４の深さ優先探索処理について、図３の処理フローを用いて説明する。 Next, the depth-first search process of step S04 will be described with reference to the process flow of FIG.
深さ優先探索処理は，厳密被覆問題とよばれる離散アルゴリズムの問題に対するすべての解の集合を保持する、ゼロサプレス型二分決定グラフ(ＺＤＤ)を構築する処理を実行し、その後に構築されたＺＤＤを用いて、集合分割問題の部分問題に対する解を求める。その後に求まった部分問題の解を用いて元の集合分割問題の解を求めて処理を終了する。厳密被覆問題とは、集合分割問題における目的関数を削除した問題である。すなわち、全体集合ＵとＵの部分集合の集合Ｓとが与えられた場合に、式（２）、（３）を満たすようなx1,...,ｘNをすべて求める問題である。まずステップＳ１０１で、集合分割問題の部分問題であるような厳密被覆問題を作成する。 The depth-first search process executes a process of constructing a zero-suppressed binary decision graph (ZDD) that holds a set of all solutions to a problem of a discrete algorithm called an exact covering problem, and then constructs the constructed ZDD. Then, the solution to the subproblem of the set partitioning problem is obtained. The solution of the original set division problem is obtained using the solution of the subproblem obtained after that, and the process is terminated. The exact coverage problem is a problem in which the objective function in the set partitioning problem is deleted. That is, when a total set U and a set S of subsets of U are given, it is a problem to find all x 1 ,..., X N that satisfy the expressions (2) and (3). First, in step S101, an exact covering problem that is a partial problem of the set partitioning problem is created.
ステップＳ１０１の具体的な手順は以下の（手順１）〜（手順２Ａ）、又は（手順１）〜（手順２Ｂ）である。 The specific procedure of step S101 is the following (procedure 1) to (procedure 2A) or (procedure 1) to (procedure 2B).
（手順１）現在の解候補xに対して、Ｕの要素の集合Ｉ- = ｛i∈｛1,...,Ｍ｝|yi<0｝とＩ+=｛i∈｛1,...,Ｍ｝|yi>0｝を取り出す。また、インデックスの集合
および
を用意する。
(Procedure 1) For the current solution candidate x, a set of elements of U I − = {iε{1,...,M}|y i <0} and I + ={iε{1,. ..,M}|y i >0} is taken out. Also, a set of indexes
and
To prepare.
（手順２Ａ）全体集合をＵ′=Ｉ−∪ＩＪ、Ｕの部分集合の集合を
とするような厳密被覆問題を作成する。
(Procedure 2A) Let U′=I − ∪I J , the set of subsets of U
Create a strict coverage problem such that.
なお、上記の（手順２Ａ）で生成されるＵ′,Ｓ′は、以下の（手順２Ｂ）で作成されるものに置き換えてもよい。 The U'and S'generated in the above (procedure 2A) may be replaced with those generated in the following (procedure 2B).
（手順２Ｂ）全体集合をＵ′=Ｉ−∪ＩJ、Ｕの部分集合の集合を
とするような厳密被覆問題を作成する。
(Procedure 2B) Let U′=I − ∪I J be the whole set, and the set of U subsets
Create a strict coverage problem such that.
以上の具体的な手順で作成された厳密被覆問題に対し、ステップＳ１０２で、非特許文献２の手法を適用することで、厳密被覆問題のすべての解の集合を保持するＺＤＤを構築する。 In step S102, the method of Non-Patent Document 2 is applied to the strict covering problem created by the above specific procedure to construct a ZDD that holds a set of all solutions of the strict covering problem.
例えば、二値行列として表現されている厳密被覆問題のインスタンスの入力を受け付ける。ここで、二値行列は、｜Ｓ′｜行、｜Ｕ′｜列からなり、各列番号が全体集合Ｕ′に含まれる各要素に対応し、各行ベクトルが、部分集合の集合Ｓ′に含まれる各要素に対応している。そして、二値行列に基づいて、選択される列番号を１とする行番号の各々に対し、行番号を解に含めたときに得られる厳密被覆問題の部分問題を求め、求められた厳密被覆問題の部分問題を再帰的に解いて、部分問題の解を表すＺＤＤの根ノードを得ることにより、厳密被覆問題の全ての解の集合を保持するＺＤＤを構築する。 For example, the input of an instance of the exact covering problem expressed as a binary matrix is accepted. Here, the binary matrix is composed of |S'| rows and |U'| columns, each column number corresponds to each element included in the overall set U', and each row vector corresponds to the subset S'. Corresponds to each included element. Then, based on the binary matrix, for each row number having the selected column number as 1, a subproblem of the exact coverage problem obtained when the row number is included in the solution is obtained, and the obtained exact coverage is obtained. Construct a ZDD that holds the set of all solutions of the exact coverage problem by recursively solving the subproblems of the problem and obtaining the root node of the ZDD that represents the solution of the subproblem.
[非特許文献２] Masaaki Nishino, Norihito Yasuda, Shinichi Minato, and Masaaki Nagata, “Dancing with Decision Diagrams: a Combined Approach to Exact Cover", In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-17), 2017 [Non-Patent Document 2] Masaaki Nishino, Norihito Yasuda, Shinichi Minato, and Masaaki Nagata, “Dancing with Decision Diagrams: a Combined Approach to Exact Cover”, In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI-17), 2017
なお、上記非特許文献２の手法以外の手法を用いて、厳密被覆問題のすべての解の集合を保持するＺＤＤを構築するようにしてもよい。 A ZDD that holds a set of all solutions of the strict coverage problem may be constructed by using a method other than the method described in Non-Patent Document 2.
次に、ステップＳ１０３で、厳密被覆問題のすべての解の集合を保持するＺＤＤに対して、非特許文献３に記載されているAlgorithm Bを実行することにより、厳密被覆問題の解のうち、コストの和を最小にする最適解を求める。 Next, in step S103, by executing Algorithm B described in Non-Patent Document 3 on the ZDD that holds a set of all solutions of the strict coverage problem, the cost of the solutions of the strict coverage problem is reduced. Find the optimal solution that minimizes the sum of.
[非特許文献３] Donald E. Knuth, “The Art of Computer Programming Volume 4A: Combinatorial Algorithms, Part 1", Addison-Wesley, 2011 [Non-Patent Document 3] Donald E. Knuth, "The Art of Computer Programming Volume 4A: Combinatorial Algorithms, Part 1", Addison-Wesley, 2011.
そして、見つかった最適解（Ｕの部分集合）をＴとすると、Ｕの部分集合
は元の集合分割問題に対する実行可能解となっている。そこで、
を集合分割問題の近似解として出力して、深さ優先探索処理を終了する。
Then, if the found optimum solution (a subset of U) is T, then a subset of U
Is a feasible solution to the original set partitioning problem. Therefore,
Is output as an approximate solution of the set division problem, and the depth-first search process is terminated.
以上説明したように、本発明の実施形態に係る集合分割問題求解装置によれば、集合分割問題に対する解候補を局所探索法により更新し、更新された解候補について、集合分割問題の制約条件の違反度を計算することを繰り返し、計算された違反度が閾値以下となったときに、解候補に基づいて、厳密被覆問題を作成し、厳密被覆問題の全ての解を、深さ優先探索により求め、厳密被覆問題の全ての解のうち、コストの和を最小とする解と、解候補に含まれる、２以上の部分集合に含まれる要素を含む部分集合以外の部分集合とに基づいて、集合分割問題の近似解を求めることにより、集合分割問題の近似解を効率的に求めることができる。 As described above, according to the set partitioning problem solving apparatus according to the embodiment of the present invention, the solution candidate for the set partitioning problem is updated by the local search method, and the updated solution candidate is subject to the constraint condition of the set partitioning problem. Repeating the calculation of the degree of violation, when the calculated degree of violation is less than or equal to the threshold value, create a strict coverage problem based on the solution candidates, and find all the solutions of the strict coverage problem by the depth-first search. Based on a solution that minimizes the sum of costs among all solutions of the strict coverage problem and a subset other than a subset that includes elements included in two or more subsets included in the solution candidate, By obtaining an approximate solution of the set division problem, an approximate solution of the set division problem can be efficiently obtained.
以上、実施形態として集合分割問題求解装置及び方法を例示して説明した。実施形態は、コンピュータを、集合分割問題求解装置における各部として機能させるためのプログラムの形態としてもよい。実施形態は、このプログラムを記憶したコンピュータが読み取り可能な記憶媒体の形態としてもよい。 The set division problem solving apparatus and method have been illustrated and described as the embodiments. The embodiment may be in the form of a program for causing a computer to function as each unit in the set division problem solving device. The embodiment may be in the form of a computer-readable storage medium storing this program.
その他、上記実施形態で説明した集合分割問題求解装置の構成は、一例であり、主旨を逸脱しない範囲内において状況に応じて変更してもよい。 In addition, the configuration of the set division problem solving device described in the above embodiment is an example, and may be changed according to the situation without departing from the spirit of the invention.
また、上記実施形態で説明したプログラムの処理の流れも、一例であり、主旨を逸脱しない範囲内において不要なステップを削除したり、新たなステップを追加したり、処理順序を入れ替えたりしてもよい。 The flow of processing of the program described in the above embodiment is also an example, and unnecessary steps may be deleted, new steps may be added, or the processing order may be changed without departing from the spirit of the invention. Good.
また、上記実施形態では、プログラムを実行することにより、実施形態に係る処理がコンピュータを利用してソフトウェア構成により実現される場合について説明したが、これに限らない。実施形態は、例えば、ハードウェア構成や、ハードウェア構成とソフトウェア構成との組み合わせによって実現してもよい。 Further, in the above-described embodiment, the case where the process according to the embodiment is realized by the software configuration using the computer by executing the program has been described, but the present invention is not limited to this. The embodiment may be realized by, for example, a hardware configuration or a combination of a hardware configuration and a software configuration.
１０ 集合分割問題求解装置
１２ 問題入力部
１４ 局所探索実行部
１６ 深さ優先探索実行部
１８ 計算結果出力部
10 Set Division Problem Solving Device 12 Problem Input Unit 14 Local Search Execution Unit 16 Depth Priority Search Execution Unit 18 Calculation Result Output Unit
Claims (8)
前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、何れの部分集合にも含まれない要素の集合と、２以上の部分集合に含まれる要素を含む前記部分集合との和集合を全体集合とする厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、２以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求める深さ優先探索実行部と、
を含む集合分割問題求解装置。 A local search method is used to update the solution candidates for the set partitioning problem that partitions the entire set of elements into a plurality of subsets with the minimum total cost, and the updated solution candidates violate the constraint conditions of the set partitioning problem. A local search execution unit that repeats calculating the degree,
A set of elements that are not included in any subset, and a subset that includes elements included in two or more subsets, based on the solution candidates, when the calculated violation degree is less than or equal to a threshold value. Create a strict coverage problem with the union of and as the whole set, find all solutions of the strict coverage problem by depth-first search, and minimize the sum of the costs among all the solutions of the strict coverage problem. And a depth-first search execution for obtaining an approximate solution of the set division problem based on the solution and the subset other than the subset including elements included in the two or more subsets included in the solution candidate Department,
A set partitioning problem solving apparatus including.
深さ優先探索実行部が、前記計算された違反度が閾値以下となったときに、前記解候補に基づいて、何れの部分集合にも含まれない要素の集合と、２以上の部分集合に含まれる要素を含む前記部分集合との和集合を全体集合とする厳密被覆問題を作成し、前記厳密被覆問題の全ての解を、深さ優先探索により求め、前記厳密被覆問題の全ての解のうち、前記コストの和を最小とする解と、前記解候補に含まれる、２以上の部分集合に含まれる要素を含む前記部分集合以外の前記部分集合とに基づいて、前記集合分割問題の近似解を求める
集合分割問題求解方法。 A local search execution unit updates a solution candidate for a set partitioning problem in which the total set of elements is divided into a plurality of subsets having a minimum sum of costs by a local search method, and the updated solution candidate is subjected to the set partitioning. Repeatedly calculating the degree of violation of the problem constraint,
When the calculated degree of violation is equal to or less than a threshold, the depth-first search execution unit determines, based on the solution candidate, a set of elements that are not included in any subset and two or more subsets. Create a strict covering problem with the union with the subset including the included elements as a whole set, and obtain all solutions of the strict covering problem by depth-first search, and obtain all solutions of the strict covering problem. An approximation of the set division problem based on the solution that minimizes the sum of the costs and the subsets other than the subset that includes elements included in the two or more subsets that are included in the solution candidate Solving method of set division problem.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2017139319A JP6725920B2 (en) | 2017-07-18 | 2017-07-18 | Set division problem solving apparatus, method, and program |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2017139319A JP6725920B2 (en) | 2017-07-18 | 2017-07-18 | Set division problem solving apparatus, method, and program |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2019021052A JP2019021052A (en) | 2019-02-07 |
| JP6725920B2 true JP6725920B2 (en) | 2020-07-22 |
Family
ID=65353103
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2017139319A Active JP6725920B2 (en) | 2017-07-18 | 2017-07-18 | Set division problem solving apparatus, method, and program |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP6725920B2 (en) |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0863457A (en) * | 1994-08-24 | 1996-03-08 | Fujitsu Ltd | Combination problem constraint satisfaction processor |
| SG133421A1 (en) * | 2005-12-13 | 2007-07-30 | Singapore Tech Dynamics Pte | Method and apparatus for an algorithm development environment for solving a class of real-life combinatorial optimization problems |
| JP4570095B2 (en) * | 2006-05-31 | 2010-10-27 | 財団法人電力中央研究所 | Loop controller installation method and loop controller installation position determination program |
-
2017
- 2017-07-18 JP JP2017139319A patent/JP6725920B2/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| JP2019021052A (en) | 2019-02-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Haag et al. | From easy to hopeless—predicting the difficulty of phylogenetic analyses | |
| JP7003753B2 (en) | Search point determination program, search point determination method and search point determination device | |
| US11068655B2 (en) | Text recognition based on training of models at a plurality of training nodes | |
| US12204830B2 (en) | Simulation optimization method and apparatus based on time prediction | |
| US20240046099A1 (en) | Method and system for jointly pruning and hardware acceleration of pre-trained deep learning models | |
| KR102215978B1 (en) | Distributed asynchronous parallelized ensemble model training and inference system on the blockchain network and method thereof | |
| Corus et al. | Fast artificial immune systems | |
| Doerr et al. | Simple on-the-fly parameter selection mechanisms for two classical discrete black-box optimization benchmark problems | |
| CN110032682A (en) | A kind of information recommendation list generation method, device and equipment | |
| Liu et al. | Identifying the cardinality-constrained critical nodes with a hybrid evolutionary algorithm | |
| Corus et al. | On easiest functions for mutation operators in bio-inspired optimisation | |
| US20230361902A1 (en) | Method and apparatus for optimizing otn resources, computer device and storage medium | |
| US8422802B2 (en) | Robust large-scale visual codebook construction | |
| WO2017072717A1 (en) | Learning of the structure of bayesian networks from a complete data set | |
| US20090106022A1 (en) | System and method for learning a network of categories using prediction | |
| JP5555238B2 (en) | Information processing apparatus and program for Bayesian network structure learning | |
| TWI844931B (en) | Boosting classification and regression tree performance with dimension reduction | |
| WO2016067548A1 (en) | Region linear model optimization system, method, and program | |
| KR102559605B1 (en) | Method and apparatus for function optimization | |
| JP6725920B2 (en) | Set division problem solving apparatus, method, and program | |
| US11676050B2 (en) | Systems and methods for neighbor frequency aggregation of parametric probability distributions with decision trees using leaf nodes | |
| JP2016095568A (en) | Model construction apparatus and program | |
| JP7424373B2 (en) | Analytical equipment, analytical methods and analytical programs | |
| Goldengorin et al. | Data correcting approaches in combinatorial optimization | |
| JP6203313B2 (en) | Feature selection device, feature selection method, and program |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A821 Effective date: 20170719 |
|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20190802 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20200417 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20200609 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20200622 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 6725920 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| S533 | Written request for registration of change of name |
Free format text: JAPANESE INTERMEDIATE CODE: R313533 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |