JP6992404B2 - Optimizer, method, and program - Google Patents

Description

The present invention relates to optimization devices, methods, and programs, and in particular, to optimization devices, methods, and programs for solving submodular maximization problems.

The submodular maximization problem is a problem that frequently appears in the context of "choosing a non-redundant subset from a set." For example, consider a situation where you want to collect information such as temperature by arranging multiple sensors indoors. It is assumed that the candidate locations where the sensor can be placed (for example, near the power outlet) are predetermined. This problem is a problem of selecting some places (subsets) from a set of candidate places and deciding where to place the sensor. In this problem, if the sensors are densely arranged, it seems that almost the same information can be obtained from some sensors, so it can be said to be redundant. The submodular function is a function that expresses such redundancy, and by selecting the location where the sensor is placed so as to maximize the score represented by the submodular function, it covers the observation target range evenly. A non-redundant sensor arrangement can be realized.

For such submodular function maximization, the greedy method as in Non-Patent Document 1 is used.

A solution with an approximation guarantee can be obtained (where e is the number of Napiers). Further, if it is allowed to spend a longer calculation time than the greedy method, a solution having an approximate guarantee for any α ∈ [0,1] can be obtained by a method as in Non-Patent Document 2.

M. Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett., 32 (1): 41-43, 2004. W. Chen, Y. Chen, K. Weinberger. Filtered search for submodular maximization with controllable approximation bounds. 18th International Conference on Articial Intelligence and Statistics, 2015.

As described in Non-Patent Document 1 above, the 1-1 / e approximate solution of submodular maximization can be efficiently calculated by the greedy algorithm. However, in many practical problems, the 1-1 / e approximation guarantee is insufficient in terms of accuracy. For example, in the case of the sensor placement problem described above, in a situation where important information is collected using a very expensive sensor, it is desirable to place the sensor according to a solution guaranteed to be as close to the optimum solution as possible. The method of Non-Patent Document 2 can calculate an α approximate solution for any α, but some of the techniques used when searching for a solution are not suitable for the submodular maximization problem, and as a result, a huge calculation time is required. Often.

The present invention has been made to solve the above problems, and provides an optimization device, a method, and a program capable of obtaining an approximate solution of a submodular maximization problem with desired accuracy at high speed. With the goal.

In order to achieve the above object, the optimizer according to the present invention has a parameter α representing approximation accuracy and the submodular maximization problem in a submodular maximization problem for searching a non-redundant subset from a set of elements. An input unit that accepts as inputs a set U including each of the elements of, an inferior modular function that defines a score for a subset of the set U, a cost c _U for each of the elements, and an upper limit B of the cost. Of the set F of the subset S that satisfies the cost constraint based on the upper limit B of the cost, the subset S _max having the maximum score is repeatedly searched by using the greedy method, and the already searched subset S _max is repeated. When the ratio of the score of the newly searched subset S _max to the upper limit of the score determined by using the score of the above and the parameter α representing the approximation accuracy is equal to or greater than the parameter α representing the approximation accuracy. It is configured to include a search unit that outputs the subset S _max as an approximate solution to the inferior modular maximization problem.

In the optimization method according to the present invention, in the submodular maximization problem of searching for a non-redundant subset from a set of elements, the input unit has a parameter α representing approximation accuracy and each of the elements of the submodular maximization problem. A step that accepts as inputs a set U including, an inferior modular function that defines a score for a subset of the set U, a cost c _U for each of the elements, and an upper limit B of the cost, and the search unit receives the cost. Of the set F of the subset S that satisfies the cost constraint based on the upper limit B of, the subset S _max having the maximum score is repeatedly searched by using the greedy method, and the already searched subset S _max . The said when the ratio of the score of the newly searched subset S _max to the upper limit of the score determined by using the score and the parameter α representing the approximation accuracy is equal to or greater than the parameter α representing the approximation accuracy. It is characterized in that the subset S _max is executed including a step of outputting as an approximate solution of the inferior modular maximization problem.

Further, the program of the present invention is a program for making a computer function as each part constituting the above-mentioned optimization device.

According to the optimizer, method, and program of the present invention, the input is the parameter α representing the accepted approximation accuracy, the set U, the submodular function, the cost c _U for each of the elements, and the upper limit B of the cost. Of the set F of the subset S that satisfies the cost constraint based on the upper limit B of the cost, the subset S _max having the maximum score is repeatedly searched by using the greedy method, and the already searched subset S _max . When the ratio of the score of the newly searched subset S _max to the upper limit of the score determined by using the score of and the parameter α representing the approximation accuracy is equal to or greater than the parameter α representing the approximation accuracy, the subset S By outputting _max as an approximate solution of the submodular maximization problem, it is possible to obtain an approximate solution of the submodular maximization problem at a high speed with a desired accuracy.

It is a figure which shows an example of the state space tree constructed by embodiment of this invention. It is a figure which shows an example of BFSTC shown in Algorithm1 used in embodiment of this invention. It is a figure which shows an example of Algorithm2 called in Algorithm1. It is a figure which shows an example of Algorithm3 called in Algorithm2. It is a block diagram which shows the structure of the optimization apparatus which concerns on embodiment of this invention. It is a block diagram which shows the structure of a search part. It is a flowchart which shows the optimization processing routine in the optimization apparatus which concerns on embodiment of this invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

<Overview of Embodiments of the Present Invention>

First, an outline of the embodiment of the present invention will be described.

The present invention proposes a submodular maximizing device that is significantly faster than the existing method by improving the technique of [Non-Patent Document 2]. Non-Patent Document 2 uses a method based on the best-first search (hereinafter referred to as BFS) widely known in the field of submodular maximization problem. As will be described later, BFS is an algorithm that advances the search while setting the priority by the function value called a heuristic function. The present invention proposes a more efficient BFS (BFSTC described later) by adding the following three improvements to the BFS for this submodular maximization. First, the space to be searched is expressed by a structure called a state space tree, and the required memory is reduced. Second, we will introduce a technique to detect that an approximation has been achieved in the middle of a search, and eliminate redundant searches. Third, a heuristic function suitable for submodular maximization is designed and the search is performed more efficiently.

<Principle of the Embodiment of the present invention>

Next, the principle in the embodiment of the present invention will be described.

For any positive integer k, let [k] = {1,2, ..., k}, and now U = [n], and consider submodular maximization on the set U of n elements. Function defined on U

は、任意のＸ,Ｙ⊆Ｕに対してｇ(Ｘ)＋ｇ(Ｙ)≧ｇ(Ｘ∪Ｙ)＋ｇ(Ｘ∩Ｙ)を満たすとき、劣モジュラ関数であると言われる（２^ＵはＵの冪集合）。また、任意のＸ⊆Ｙ⊆Ｕに対してｇ(Ｘ)≦ｇ(Ｙ)が成り立つとき、gは単調であるという。

Is said to be a submodular function when g (X) + g (Y) ≧ g (X∪Y) + g (X∩Y) is satisfied for any X, Y⊆U (2 ^U is U). Power set). Further, when g (X) ≤ g (Y) holds for any X⊆Y⊆U, g is said to be monotonous.

In the following, we consider a monotonic submodular function such that g (φ) = 0. Assuming that a non-negative cost c _v is assigned to each item v ∈ _U , we define c _X = {c _v : v ∈ X} and c (X) = Σ v ∈ X c _v . In the embodiment of the present invention, one of the most common problems in submodular maximization, the following knapsack-constrained monotonous submodular maximization will be considered.

・・・（１）

... (1)

However, B> 0 is a predetermined upper limit of cost. Hereinafter, this problem is abbreviated as SKP for Submodular Knapsack Problem, and its optimum solution is written as X ^* . Further, a set of executable subsets satisfying the cost constraint of this problem is written as F = {X⊆U: c (X) ≦ B}. In the following, for any X, Y⊆U,

Is defined as.

Hereinafter, a device that outputs an α approximate solution X (that is, a solution X such that g (X) ≧ αg (X ^* )) for any α ∈ [0,1] will be described. The outline of the apparatus assumed below is basically based on the BFS procedure described in Non-Patent Document 2. The parts corresponding to the improvements of the present invention will be specified each time they appear.

Next, the state space tree used in this embodiment will be described. As a preparation, the state space tree G = (F, E) is defined. G is a tree structure rooted at φ ∈ F, F is a set of vertices, and E is a set of directed branches. The two vertices X, Y ∈ F are connected by a directed branch (X, Y) ∈ E when X = Y-maxY. However, maxY represents the element having the highest number among the elements included in Y [n]. An example of G is shown in FIG. FIG. 1 shows a state-space tree G having subsets X of U such that c (X) ≦ 2 with U = [3], c1 = c2 = c3 = 1, B = 2. There is. For example, since {1} = {1,3} -max {1,3} holds between {1} and {1,3}, the directed branch ({1}, {1,, 3}) exists. In Non-Patent Document 2, a structure called a state-space graph is used instead of a state-space tree, and whether or not each S ∈ F has already been searched is managed by a data structure called a closed list. It often requires a huge amount of memory. In the embodiment of the present invention, the use of the closed list is avoided by using the state space tree as described above, and the memory used at the time of searching is reduced.

Next, the details of the BFS with Termination Condition (hereinafter referred to as BFSTC) proposed in the embodiment of the present invention will be described. In the embodiment of the present invention, the BFSTC shown in Algorithm 1 of FIG. 2 is used to search on the state-space tree defined above to find an α-approximate solution.

BFSTC uses a data structure called MaxHeap, which is widely known in this field. MaxHeap is S ∈ F and the value calculated for S

It is a data structure that stores the set <S, f (S)> of. A new set <S, f (S)> can be added to MaxHeap by MaxHeap.push <S, f (S)>. Further, MaxHeap.pop () can extract S of the set <S, f (S)> having the maximum value of f among the sets stored in MaxHeap. Further, T is the vertex of the set having the maximum value of f among the sets stored in MaxHeap. Here, f (S) is a value calculated by the formula f (S) = g (S) + αh (S), and h (S) is a value of a function called a heuristic function. The formula for calculating the value of the heuristic function will be described later. GreedySK (V, ~ g (・), c _V , C) of Algorithm1 is a given submodular function for any V⊆U, C ≧ 0.

It is a greedy method that approximately solves the problem max _{X ⊆ V: c (X) ≦ C} to g (X), and the details thereof are described in Algorithm 2 shown in FIG. 3 and Algorithm 3 shown in FIG. It's a street. However, any set function

And X, Y⊆V are defined as ~ g (X | Y) = ~ g (X + Y)-~ g (Y). Also, for any given _S ∈ F, BS = B-c ( _S ), VS = {v ∈ U: c _V ≤ BS}, g _S (・) = g (・ | _S ) And.

Here, Algorithm 2 and Algorithm 3 will be described. Algorithm2 is called in Step 12 of Algorithm1 and takes (V, ~ g (・), c _V , C) as an input to find the maximum ~ g (Y) of Y ∈ (v _max , Y). , ^ Get the solution of S. ^ S is the optimum S discovered by the greedy algorithm. Also, in Step 1 of Algorithm2, GredyAdd of Algorithm3 is called to obtain X, and (V, ~ g (・), c _V , C) is input, and X that is the maximum among satisfying the cost constraint of C or less is set. Ask.

One of the improvements of BFS in the embodiment of the present invention is the Termination Condition described in Step 12-16 of Algorithm 1. Specifically, if the stop condition of Step 14 of Algorithm 1 is satisfied, it is guaranteed that S _max ∈ F is a desired α approximate solution. Therefore, by outputting S _max and ending the search, the execution time can be increased. It can be shortened. S _max is the most suitable S for searching. In BFSTC, the search efficiency is improved by using the following heuristic functions proposed by this method. Given the current solution S ∈ F, we show how to calculate the value of h (S) required in Step 17 of Algorithm 1.

Here is the function of Algorithm3

The solution output by is described as X _{1: k} . However, for any i ∈ [k], X _{1: i} is a set consisting of the elements added in Step 5 by GreedyAdd of Algorithm3 up to the i-th, and the number of elements included in the solution finally output by GreedyAdd is k. (If i <1, X _{1: i} = φ). Further, X _i is the i-th element of X _{1: k} , where β _{1: k} is defined as follows.

However, for i ∈ [k]

And. The u _mod (X _{1: i} ) will be described later. Using the above, the value of the heuristic function is calculated by the following equation (2).

・・・（２）

... (2)

Since the value of f (S) is calculated using this h (S), the stop condition of Step 14 of Algorithm 1 can be described, and the calculation suitable for solving the submodular maximization problem can be performed. In the following, the procedure for calculating u _mod (Y) for a given _S ∈ F and Y ⊆ VS will be described. First, the elements of VS are sorted in descending order of the value of r _v = g _S (v | Y) / _cv ( _v ∈ _VS ).

The ordered set thus obtained is described as V _{1: m} . However, m is the number of elements of _VS , V _{1: i} is a set consisting of the first i elements of V 1: _m , and V _i is the i-th element of V _{1: m} (i <. If it is 1, V _{1: i} = φ). Further, let l = max _{ i ∈ [m]: c (V _{1: i} ) ≤ BS}. At this time, u _mod (Y) is calculated as follows.

By the above procedure, the value of h (S) can be calculated for any S ∈ F obtained during the execution of BFSTC.

<Structure of the optimization device according to the embodiment of the present invention>

Next, the configuration of the optimization device according to the embodiment of the present invention will be described. As shown in FIG. 5, the optimization device 100 according to the embodiment of the present invention includes a CPU, a RAM, and a ROM that stores a program for executing an optimization processing routine described later and various data. It can be configured with a computer. The optimization device 100 functionally includes an input unit 10, a calculation unit 20, and an output unit 50 as shown in FIG.

The input unit 10 has a parameter α representing approximation accuracy, a set U including each of the elements of the submodular maximization problem, a submodular function g (.) That defines a score for a subset of the set U, and each of the elements. The cost c _U and the upper limit B of the cost are accepted as inputs.

The calculation unit 20 includes a main control unit 30 and a calculation unit 38.

The main control unit 30 includes a construction unit 32, a state space tree 34, and a search unit 36.

The construction unit 32 satisfies the cost constraint based on the inclusion relation of the subset based on the set U including each of the elements of the submodular maximization problem, the cost c _U for each of the elements, and the upper limit B of the cost. G = (F, E) in which the vertices F representing the set are connected by the directed branch E is constructed as the state space tree 34. In addition, according to the sequential search of the search unit 36, G = (F, E) in which the vertex F representing the subset satisfying the cost constraint based on the inclusion relation of the subset is connected by the directed branch E is the state space tree 34. It may be constructed sequentially as. For example, the state space tree 34 for the part required in the calculation of Algorithm 1 in FIG. 2 may be constructed.

The search unit 36 inputs the parameter α representing the approximation accuracy received by the input unit 10, the set U, the inferior modular function g (·), the cost c _U for each of the elements, and the upper limit B of the cost as inputs. Of the set F of the subset S that satisfies the cost constraint based on the upper limit B of, the subset S _max having the maximum score is repeatedly searched by using the greedy method, and the score of the already searched subset S _max . When the ratio of the score of the newly searched subset S _max to the upper limit g _upper of the score determined by using the parameter α representing the approximation accuracy is equal to or greater than the parameter α representing the approximation accuracy, the subset S Output _max as an approximate solution to the inferior modular maximization problem.

As shown in FIG. 6, the search unit 36 includes a sequential execution unit 40 and a stop condition determination unit 42.

The sequential execution unit 40 repeatedly searches for the subset S _max having the maximum score among the set F of the subset S satisfying the cost constraint by using the greedy method. The processing of the sequential execution unit 40 is executed by Algorithm 1 in FIG.

The sequential execution unit 40 uses the score of the subset S _max , the value h (S) of the heuristic function for the subset S _max , and the parameter α representing the approximation accuracy for the newly searched subset S _max . The value f (S) is calculated (Step 17 in Algorithm 1 of FIG. 2 above). The value h (S) of the heuristic function is calculated according to the above equation (2) by calling the calculation unit 38.

Further, when the sequential execution unit 40 searches for the subset S _max having the maximum score by using the greedy algorithm, the portion where the initial value f (φ) of f or the calculated value f (S) becomes the maximum. From the optimal subset ^ S found by the greedy method that includes the set S _max and satisfies the cost constraint, the subset S _max that maximizes the score is searched for using the greedy method (Algorithm 1 in FIG. 2 above). Step 11-19) in. The search using the greedy algorithm is performed by calling the calculation unit 38 (Algorithm 2 in FIG. 3 and Algorithm 3 in FIG. 4).

The stop condition determination unit 42 determines the ratio of the score of the newly searched subset S _max to the upper limit of the score determined by using the score of the already searched subset S _max and the parameter α representing the approximation accuracy. It is determined whether or not the parameter α represents the approximation accuracy or more, and when the ratio of the scores is equal to or greater than the parameter α representing the approximation accuracy, the newly searched subset S _max is output as an approximation solution ( Step 14-15 in Algorithm 1 of Fig. 2 above.

Further, the stop condition determination unit 42 determines the subset S _max at which the value f (S) is maximum when the value of the heuristic function for the subset S _max at which the value f (S) is maximum is 0. Output as an approximate solution (Step 7-8 in Algorithm 1 in Fig. 2 above).

The calculation unit 38 inputs the set U, the submodular function g (.), The cost c _U for each of the elements, and the upper limit B of the cost, and S _max , which is the initial value of the sequential execution unit 40 of the main control unit 30. , Calculate the initial value h (φ) of the heuristic function. Further, the calculation unit 38 outputs a modular function g _S (・) that outputs an additional score when an element is added to the remaining cost C, the subset V consisting of the remaining cost C or less elements, and the subset S. ), The cost c _V for the subset V is used as an input, and the optimum subset ^ S found by the greedy algorithm that satisfies the cost constraint to be sequentially obtained, and the value h (S) of the heuristic function are obtained. The processing of the calculation unit 38 is called from the sequential execution unit 40 by the Algorithm 2 of FIG. 3 and the Algorithm 3 of FIG. 4, and is executed sequentially.

<Operation of the optimization device according to the embodiment of the present invention>

Next, the operation of the optimization device 100 according to the embodiment of the present invention will be described. In the input unit 10, the parameter α representing the approximation accuracy, the set U including each of the elements of the submodular maximization problem, the submodular function g (・) that defines the score for the subset of the set U, and the cost for each of the elements. Upon receiving c _U and the upper limit B of the cost, the optimization device 100 executes the optimization processing routine shown in FIG. 7.

First, in step S100, the main control unit 30 acquires the parameter α received by the input unit 10, the set U, the submodular function g (·), the cost c _U for each of the elements, and the upper limit B of the cost. do.

In step S102, the main control unit 30 constructs G = (F, E) in which the vertices F representing the subsets satisfying the cost constraint based on the inclusion relation of the subset are connected by the directed branch E as the state space tree 34. do.

Next, in step S104, the calculation unit 38 inputs the submodular function g (.), The cost c _U for each of the elements, and the upper limit B of the cost, and sets the initial value S _max and the initial value of the heuristic function. Calculate h (φ).

In step S106, the main control unit 30 repeatedly searches for the subset S _max having the maximum score by using the greedy method while calling the calculation unit 38 until the stop condition is satisfied, so that the portion is an approximate solution. Find the set. The stop condition is a newly searched subset for the upper limit of the score determined by using the score of the subset S _max already searched and the parameter α representing the approximation accuracy in Step 14 in Algorithm 1 of FIG. Whether or not the ratio of the scores of S _max is equal to or greater than the parameter α indicating the approximation accuracy, or whether or not h (T) = 0 in Step 7. It should be noted that T is returned when it is found that no solution that can be searched further is found (when all the searches are completed), such as when α = 1 is set.

In step S108, the main control unit 30 outputs the solution (T or S _max ) obtained in step S106 and ends the process.

As described above, according to the optimization device according to the embodiment of the present invention, the parameter α representing the approximation accuracy received by the input unit 10, the set U, the submodular function g (·), and each of the elements Of the set F of the subset S satisfying the cost constraint, the subset S _max having the maximum score is repeatedly searched by using the greedy method, with the cost c _U and the upper limit B of the cost as inputs. The ratio of the score of the newly searched subset S _max to the upper limit of the score determined by using the score of the already searched subset S _max and the parameter α representing the approximation accuracy is equal to or greater than the parameter α representing the approximation accuracy. By outputting the subset S _max when becomes as an approximate solution of the submodular maximization problem, the submodular maximization problem can be solved at high speed.

The present invention is not limited to the above-described embodiment, and various modifications and applications can be made without departing from the gist of the present invention.

10 Input unit 20 Calculation unit 30 Main control unit 32 Construction unit 34 State space tree 36 Search unit 38 Calculation unit 40 Sequential execution unit 42 Stop condition determination unit 50 Output unit 100 Optimization device

Claims (6)

In a submodular maximization problem that searches for non-redundant subsets from a set of elements
A parameter α representing approximation accuracy, a set U containing each of the elements of the submodular maximization problem, a submodular function defining a score for a subset of the set U, a cost c _U for each of the elements, and the above. An input unit that accepts the upper limit B of the cost as an input,
Of the set F of the subset S that satisfies the cost constraint based on the upper limit B of the cost, the subset S _max having the maximum score is repeatedly searched by using the greedy method, and the subset S already searched. When the ratio of the score of the newly searched subset S _max to the upper limit of the score determined by using the score of _max and the parameter α representing the approximation accuracy is equal to or greater than the parameter α representing the approximation accuracy. A search unit that outputs the subset S _max of the above as an approximate solution to the inferior modular maximization problem.
Optimizer including. The search unit uses the score of the subset S _max , the value of the heuristic function for the subset S _max , and the parameter α representing the approximation accuracy for the newly searched subset S _max . Calculate the value f and
When searching for the subset S _max that maximizes the score by using the greedy algorithm, from the subset S that includes the subset S _max that maximizes the value f and satisfies the cost constraint. The optimization device according to claim 1, wherein the subset S _max having the maximum score is searched for by using the greedy method. The optimization device according to claim 2, wherein the value of the heuristic function is calculated by the following equation (1).

... (1)
However, X _{1: k} is a set consisting of elements added up to the i-th search for any i ∈ [k] in the search unit.

X _i is the i-th element of X _{1: k} , gs (・) = g (・ | S) is a submodular function, and ~ g is an arbitrary set function.

V is an arbitrary subset V ∈ U for the set U, VS is an arbitrary subset of the subset _S that satisfies the cost constraint, and l is a predetermined element in the calculation of the search unit. It is a number, and m is the number of elements of the _VS. It further includes a construction unit that constructs a state-space tree in which vertices representing the subset satisfying the cost constraint based on the inclusion relation of the subset are connected by directed branches.
When the search unit repeatedly searches for the subset S _max that maximizes the score by using the greedy method, the search unit searches for the subset S _max that maximizes the score using the state space tree. The optimization device according to any one of claims 1 to 3. In a submodular maximization problem that searches for non-redundant subsets from a set of elements
The input unit has a parameter α representing approximation accuracy, a set U including each of the elements of the submodular maximization problem, a submodular function that defines a score for a subset of the set U, and a cost c for each of the elements. A step of accepting _U and the upper limit B of the cost as inputs, and
The search unit repeatedly searches the set S _max of the subset S having the maximum score among the set F of the subset S satisfying the cost constraint based on the upper limit B of the cost by using the greedy method, and has already been searched. The ratio of the newly searched score of the subset S _max to the upper limit of the score determined by using the score of the subset S _max and the parameter α representing the approximation accuracy is equal to or greater than the parameter α representing the approximation accuracy. The step of outputting the subset S _max when becomes as an approximate solution of the inferior modular maximization problem, and
Optimization methods including. A program for making a computer function as each part of the optimization device according to any one of claims 1 to 4.

Images