DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Priority
The present application, 17685428, filed 03/03/2022 claims foreign priority to JP2021-101881, filed 06/18/2021.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 03/03/2022, 11/22/2022 and 11/15/2024 are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Specification
The specification is objected to under 37 C.F.R. 1.74, which requires the detailed description to refer to the different parts of the figures by use of reference letters or reference numerals. Implicit in this rule is that the detailed description correctly reference the figures. In this application the figures and detailed description are inconsistent as explained below.
In paragraph [0049] line 10, “FIG. 3” should read “FIG. 2” instead.
Claim Objections
Claims 4 and 6 are objected to under 37 C.F.R. 1.71(a) which requires “full, clear, concise, and exact terms” as to enable any person skilled in the art or science to which the invention or discovery appertains, or with which it is most nearly connected, to make and use the same. The following should be corrected.
A. In claim 4 line 9, “first bit” should read “the first bit” instead because first bit is already introduced in line 3. Claim 6 inherit the same deficiency as claim 4 by reason of dependence.
B. In claim 4 line 10, “a certain condition” should read “the certain condition” instead because certain condition is already introduced in claim 1 lines 9-10 from which the claim depends. Claim 6 inherit the same deficiency as claim 4 by reason of dependence.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-10 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 1 recites “when the selected plurality of bits are not accepted, inverting the plurality of bits to return to a state before the determining in the bit group information” in lines 14-15. It is unclear how inverting the plurality of bits would return the plurality of bits to a state before the determining. In the context of the claim, no other bit inversion is performed when the selected plurality of bits are not accepted, therefore, it is unclear how a single inversion step would cause the plurality of bits to return to its initial state, i.e., state before the determining. For purposes of examination, a double inversion or no inversion (consistent with paragraph [0084]) is performed when the selected plurality of bits are not accepted in order to return the plurality of bits to a state before the determining. Claims 9-10 recite a similar limitation and are rejected for the same reason. Claims 2-8 inherit the same deficiency as claim 1 by reason of dependence.
Claim 2 recites “the inverting” in line 4. It is unclear whether this is supposed to refer to the inverting the plurality of bits when the selected plurality of bits are accepted or to the inverting the plurality of bits when the selected plurality of bits are not accepted or to both. For purposes of examination, this is interpreted to both. Claim 3 recites a similar limitation in line 5 and is rejected for the same reason.
Claim 3 recites “the condition” in lines 3, 6 and 9. There is insufficient antecedent basis for this limitation in the claim. Further, it is unclear whether this supposed to be interpreted to refer to the constraint condition or to the certain condition or to some other condition. For purposes of examination, the first recitation in line is interpreted as a condition.
Further, claim 3 recites “the specified selection status” in line 7. There is insufficient antecedent basis for this limitation in the claim. There is no specifying a selection status step recited in the claim. For purposes of examination, this is interpreted as the selection status.
Claim 4 recites “when the first bit and the second bit are not accepted, inverting the first bit and the second bit to return to a state before the determining in the bit group information” in lines 13-15. It is unclear how inverting the first bit and the second bit would return the first bit and the second bit to a state before the determining. In the context of the claim, no other bit inversion is performed when the first bit and the second bit are not accepted, therefore, it is unclear how a single inversion step would cause the first bit and the second bit to return to their initial state, i.e., state before the determining. For purposes of examination, a double inversion or no inversion (consistent with paragraph [0084]) is performed when the first bit and the second bit are not accepted in order to return the first bit and the second bit to a state before the determining. Claim 6 inherit the same deficiency as claim 4 by reason of dependence.
Claim 7 recites “the first element” in line 3. There is insufficient antecedent basis for this limitation in the claim. It is unclear which element of the plurality of first elements this is supposed to refer. Further, it is unclear whether this is supposed to refer to the plurality of first elements. For purposes of examination, this is interpreted as the plurality of first elements.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-10 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Under Step 1, claims 1-8 recite a non-transitory computer-readable storage medium and, therefore, is an article of manufacture. Claim 9 recites a series of steps and, therefore, is a process. Claim 10 recites a device and, therefore, is a machine.
Claim 10 will be addressed first followed by claims 9 and 1-8.
Under Step 2A prong 1, claim 10 recites
An optimization device comprising:
one or more memories; and
one or more processors coupled to the one or more memories and the one or more processors configured to:
select a plurality of bits based on a constraint condition of an optimization problem for each of a plurality of first elements that are search targets of a solution for the optimization problem, from bit group information indicating whether each of a plurality of second elements included in each of the plurality of first elements are selected to be used for searching for the solution of the optimization problem;
determine whether to accept the selected plurality of bits based on a certain condition;
when the selected plurality of bits are accepted, invert the plurality of bits in the bit group information;
when the selected plurality of bits are not accepted, invert the plurality of bits to return to a state before the determining in the bit group information; and
search for the solution of the optimization problem based on a selection status of each of the plurality of bits in the bit group information.
The above underlined limitations are related to searching for a solution of an optimization problem which amounts to processing mathematical relationships/calculations and falls within the “Mathematical Concepts” and/or “Mental Processes” grouping of abstract ideas. The steps of “select”, “determine”, “invert” and “search” is a process that under its broadest reasonable interpretation, covers performance of the limitation in the mind. That is, other than reciting “one or more processors”, nothing in the claim element precludes the step from practically being performed in the human mind. For example, but for the “one or more processors” language, the claim encompasses manually representing variables of an optimization as a plurality of bits each representing a variable, selecting a subset of the plurality of bits to invert, determining whether to invert the plurality of bits based on a predetermined criteria, inverting the plurality of bits based on satisfying the predetermined criteria, not inverting the plurality of bits based on not satisfying the predetermined criteria, and repeating the above steps to find the solution of the optimization problem using pen and paper. Accordingly, the claim is directed to recite an abstract idea.
Under step 2A prong 2, claim 10 recites the following additional elements: one or more memories and one or more processors coupled to the one or more memories. However, the additional elements of “one or more memories” and “one or more processors” are recited at a high-level of generality (i.e., as generic computer memory; and as a generic computer component for executing a series of mathematical operations) such that they amount to no more than mere instructions using a generic computer component or merely as tools to implement the abstract idea. The additional elements do not, individually or in combination, integrate the exception into a practical application. Accordingly, the claim is not integrated into a practical application.
Under step 2B, claim 10 does not include additional elements that, individually or in combination, are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the additional elements of “one or more memories” and “one or more processors” are recited at a high-level of generality (i.e., as generic computer memory; and as a generic computer component for executing a series of mathematical operations) such that they amount to no more than mere instructions using a generic computer component or merely as tools to implement the abstract idea. The claim does not recite additional elements that alone or in combination amount to an inventive concept. Accordingly, the claim does not amount to significantly more than the abstract idea.
Regarding claim 9, it is directed to a method practiced by the device of claim 10. All steps performed by the method of claim 9 would be practiced by the device of claim 10. Claim 10 analysis applies equally to claim 9.
Regarding claim 1, it is directed to a non-transitory computer-readable storage medium storing an optimization program. All steps included in the optimization program stored in the non-transitory computer-readable storage medium of claim 1 would be practiced by the device of claim 10. Claim 10 analysis applies equally to claim 1.
Under step 2A prong 1, claims 2-8 recite the same abstract idea as claim 1 by reason of dependence. Further, claim 2 recites further details of the abstract idea of the searching “wherein the searching includes: specifying a selection status satisfying a condition of the solution after a series of processes including the selecting, the determining, and the inverting are executed a plurality of times.” Claim 3 recites further details of the abstract idea of the searching “wherein the searching includes: determining whether a selection status satisfies the condition of the solution for each time a series of processes including the selecting, the determining, and the inverting are executed; when the selection status satisfies the condition, and when the selection status does not satisfy the condition, repeating the series of processes.” Claim 4 recites further details of the abstract idea of the selecting and the determining “wherein the selecting includes: selecting a first bit from the bit group information based on at least one selected from a constraint satisfaction rate and a cumulative number of times of inversion; and selecting a second bit for each of the plurality of first elements different from a first element including the first bit, wherein the determining includes: determining whether to accept first bit and the second bit based on a certain condition; when the first bit and the second bit are accepted, inverting the first bit and the second bit in the bit group information; and when the first bit and the second bit are not accepted, inverting the first bit and the second bit to return to a state before the determining in the bit group information.” Claim 5 recites further details of the abstract idea of the selecting and the determining “wherein the selecting includes selecting a first bit from the bit group information based on at least one selected from a constraint satisfaction rate and a cumulative number of times of inversion; and selecting a second bit for each of the plurality of first elements different from a first element including the first bit, wherein the determining includes determining whether to exclude the first bit and the second bit from being used for searching for the solution of the optimization problem based on the certain condition.” Claim 6 recites further details of the abstract idea of the selecting “wherein the selecting the first bit includes selecting the first bit that derives a local solution of the optimization problem by being inverted.” Claim 7 recites further details of the abstract idea of the selecting based on the constraint condition “wherein the first element is a set of bits whose total number of bits that have identical states under the constraint condition is set.” Claim 8 recites further details of the abstract idea regarding the number of the plurality of bits selected “wherein a number of the plurality of bits is equal to or less than twice a total number of bits defined under the constraint condition” and falls within the “Mathematical Concepts” and/or “Mental Processes” grouping of abstract ideas. In particular claims 4-8 do not include additional elements that would require further analysis under step 2A prong 2 and step 2B. Accordingly, the claims are directed to recite an abstract idea.
Under step 2A prong 2, claim 2 recites the following additional elements: outputting each of the plurality of second elements specified based on the specified selection status as a search result. Claim 3 recites the following additional elements: outputting each of the plurality of second elements specified based on the specified selection status as a search result. However, the additional elements of “outputting each of the plurality of second elements specified based on the specified selection status as a search result” in claims 2 and 3 are merely adding insignificant extra-solution activities. The additional elements do not, individually or in combination, integrate the exception into a practical application. Accordingly, the claims are not integrated into a practical application.
Under step 2B, claims 2-3 do not include additional elements that, individually or in combination, are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the additional elements of “outputting each of the plurality of second elements specified based on the specified selection status as a search result” in claims 2 and 3 are merely adding insignificant extra-solution activities. See MPEP 2106.05(d)(II) which states that the courts have recognized computer functions such as “Receiving or transmitting data over a network” and “Storing and retrieving information in memory” as well‐understood, routine, and conventional functions when they are claimed in a merely generic manner (e.g., at a high level of generality) or as insignificant extra-solution activity. The claims do not recite additional elements that alone or in combination amount to an inventive concept. Accordingly, the claims do not amount to significantly more than the abstract idea.
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-3 and 9-10 are rejected under 35 U.S.C. 102(a)(1) and (a)(2) as being anticipated by Naveh (US 20050021486 A1).
Regarding claim 10, Naveh teaches an optimization device comprising:
one or more memories (Naveh claim 35; one or more memories - computer-readable medium, in which program instructions are stored); and
one or more processors coupled to the one or more memories and the one or more processors configured to (Naveh Fig. 1 and claim 18; paragraph [0062] one or more processors – processor 28):
select a plurality of bits based on a constraint condition of an optimization problem for each of a plurality of first elements that are search targets of a solution for the optimization problem, from bit group information indicating whether each of a plurality of second elements included in each of the plurality of first elements are selected to be used for searching for the solution of the optimization problem (Naveh Fig. 3 steps 60-64 and paragraphs [0072-0073 and 0078] “The CSP solver on processor 28 receives definitions of variables 24 and constraints 26, at a problem definition step 60 … The solver initializes variables 24 in order to define a starting state for solving the CSP, at an initialization step 62. For this purpose, the solver may instruct each of the constraints to initialize the variables in the variable subset to which it applies … The CSP solver now explores new states, in order to find a path from the initial state to a state that solves the CSP. For this purpose, the solver first decides which bits of which variables will be flipped in order to generate the new state from the current state, at a bit selection step 64. Typically, the algorithm used in determining which bits to flip may change and be adjusted as the CSP solving process progresses”; plurality of bits – variables/bits to flip; constraint condition – constraints; optimization problem – CSP; plurality of first elements – problem variables; solution – state that solves the CSP; from bit group information – bits representing the variables; plurality of second elements – bits selected to be flipped; paragraph [0020] “stochastic CSP solvers essentially map the CSP into an optimization problem”; paragraph [0062]);
determine whether to accept the selected plurality of bits based on a certain condition (Naveh Fig. 3 step 70 and paragraph [0086] “At a cost comparison step 70, the solver compares this new state cost to the cost of the current state, which was calculated previously”);
when the selected plurality of bits are accepted, invert the plurality of bits in the bit group information (Naveh Fig. 3 steps 66, 74 and 78 and paragraphs [0086-0087 and 0090] “Following the selection of the bits at step 64 (regardless of the strategy selected), the CSP solver flips all the selected bits simultaneously, at a bit flipping step 66, thus defining a new state to be evaluated … if the solver finds at step 70 that the new state has a lower cost than the current state, it discards the current state and keeps the new state for further processing … since the new state was at least determined to have lower cost than the previous current state, the current state is discarded, and the new state becomes the current state, at a state replacement step 78);
when the selected plurality of bits are not accepted, invert the plurality of bits to return to a state before the determining in the bit group information (Naveh Fig. 3 steps 66 and 72 and paragraph [0086] “If the cost of the new state is no lower than the current state cost, the bits that were flipped at step 66 are flipped back, returning to the current state, at a new state rejection step 72”); and
search for the solution of the optimization problem based on a selection status of each of the plurality of bits in the bit group information (Naveh Fig. 3 and paragraph [0090] “The process then continues with the selection of the next hop at step 64, and iterates through the remaining steps until a solution is found (or until processor 28 times out).
Regarding claim 9, it is directed to a method practiced by the device of claim 10. All steps performed by the method of claim 9 would be practiced by the device of claim 10. Claim 10 analysis applies equally to claim 9.
Regarding claim 1, it is directed to a non-transitory computer-readable storage medium storing an optimization program. All steps included in the optimization program stored in the non-transitory computer-readable storage medium of claim 1 would be practiced by the device of claim 10. Claim 10 analysis applies equally to claim 1.
Regarding claim 2, Naveh teaches all the limitations of claim 1 as stated above. Further, Naveh teaches wherein the searching includes: specifying a selection status satisfying a condition of the solution after a series of processes including the selecting, the determining, and the inverting are executed a plurality of times; and outputting each of the plurality of second elements specified based on the specified selection status as a search result (Naveh Fig. 3 step 76 and paragraph [0090] “if processor 28 determines that the new state chosen at step 66 has zero cost, it returns this state as a solution of the CSP, at a solution step 76. Otherwise, since the new state was at least determined to have lower cost than the previous current state, the current state is discarded, and the new state becomes the current state, at a state replacement step 78. The process then continues with the selection of the next hop at step 64, and iterates through the remaining steps until a solution is found (or until processor 28 times out)”; selection status = new state cost = 0 or when processor times out).
Regarding claim 3, Naveh teaches all the limitations of claim 1 as stated above. Further, Naveh teaches wherein the searching includes: determining whether a selection status satisfies the condition of the solution for each time a series of processes including the selecting, the determining, and the inverting are executed; when the selection status satisfies the condition, outputting each of the plurality of second elements specified based on the specified selection status as a search result; and when the selection status does not satisfy the condition, repeating the series of processes (Naveh Fig. 3 step 76 and paragraph [0090] “if processor 28 determines that the new state chosen at step 66 has zero cost, it returns this state as a solution of the CSP, at a solution step 76. Otherwise, since the new state was at least determined to have lower cost than the previous current state, the current state is discarded, and the new state becomes the current state, at a state replacement step 78. The process then continues with the selection of the next hop at step 64, and iterates through the remaining steps until a solution is found (or until processor 28 times out)”; selection status = new state cost = 0 or when processor times out).
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 4-8 are rejected under 35 U.S.C. 103 as being unpatentable over Naveh as applied to claim 1 above, and further in view of Kellerer et al. (NPL – “Knapsack Problems”), hereinafter Kellerer.
Regarding claim 4, Naveh teaches all the limitations of claim 1 as stated above. Further, Naveh teaches wherein the selecting includes:
selecting bits from the bit group information based on at least one selected from a constraint satisfaction rate and a cumulative number of times of inversion (Naveh paragraphs [0080-0081] “ characteristics of "successful" hops (leading to states of reduced cost) are saved and learned … choose the bits to be flipped according to some or all of the learned characteristics”); and
wherein the determining includes: determining whether to accept the bits based on a certain condition (Naveh Fig. 3 step 70 and paragraph [0086] “At a cost comparison step 70, the solver compares this new state cost to the cost of the current state, which was calculated previously”);
when the first bit and the second bit are accepted, inverting the bits in the bit group information (Naveh Fig. 3 steps 66, 74 and 78 and paragraphs [0086-0087 and 0090] “Following the selection of the bits at step 64 (regardless of the strategy selected), the CSP solver flips all the selected bits simultaneously, at a bit flipping step 66, thus defining a new state to be evaluated … if the solver finds at step 70 that the new state has a lower cost than the current state, it discards the current state and keeps the new state for further processing … since the new state was at least determined to have lower cost than the previous current state, the current state is discarded, and the new state becomes the current state, at a state replacement step 78); and
when the bits are not accepted, inverting the bits to return to a state before the determining in the bit group information (Naveh Fig. 3 steps 66 and 72 and paragraph [0086] “If the cost of the new state is no lower than the current state cost, the bits that were flipped at step 66 are flipped back, returning to the current state, at a new state rejection step 72”).
Naveh does not explicitly teach selecting a first bit from the bit group information based on at least one selected from a constraint satisfaction rate and a cumulative number of times of inversion; and selecting a second bit for each of the plurality of first elements different from a first element including the first bit, wherein the determining includes: determining whether to accept first bit and the second bit based on a certain condition; when the first bit and the second bit are accepted, inverting the first bit and the second bit in the bit group information; and when the first bit and the second bit are not accepted, inverting the first bit and the second bit to return to a state before the determining in the bit group information.
However, on the same field of endeavor, Kellerer discloses an optimization wherein a first bit is selected from a first class and a second bit is selected from each of a plurality of classes different from the first class (Kellerer page 317 section 11.1).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention, to modify Naveh using Kellerer and configure the device to be able to solve a multiple-choice knapsack problem (MCKP) by selecting a first bit from the bit group information based on a constraint satisfaction rate; and selecting a second bit for each of the plurality of first elements different from a first element including the first bit, inverting the first bit and the second bit; determining whether to accept first bit and the second bit based on a certain condition; accepting the bit inversion when the first bit and the second bit are accepted; and inverting the first bit and the second bit back when the first bit and the second bit are not accepted in order to solve MCKP by selecting exactly one item from each class such that the profit sum is maximized without exceeding the capacity c in the corresponding weight sum. By inverting two or more bits, the processor would be able to find the solution with enhanced speed (Naveh paragraph [0023]).
Therefore, the combination of Naveh as modified in view of Kellerer teaches selecting a first bit from the bit group information based on at least one selected from a constraint satisfaction rate and a cumulative number of times of inversion; and selecting a second bit for each of the plurality of first elements different from a first element including the first bit, wherein the determining includes: determining whether to accept first bit and the second bit based on a certain condition; when the first bit and the second bit are accepted, inverting the first bit and the second bit in the bit group information; and when the first bit and the second bit are not accepted, inverting the first bit and the second bit to return to a state before the determining in the bit group information.
Regarding claim 5, Naveh teaches all the limitations of claim 1 as stated above. Further, Naveh teaches wherein the selecting includes:
selecting bits from the bit group information based on at least one selected from a constraint satisfaction rate and a cumulative number of times of inversion (Naveh paragraphs [0080-0081] “ characteristics of "successful" hops (leading to states of reduced cost) are saved and learned … choose the bits to be flipped according to some or all of the learned characteristics”); and
wherein the determining includes determining whether to exclude the bits from being used for searching for the solution of the optimization problem based on the certain condition (Naveh Fig. 3 step 70 and paragraph [0086] “At a cost comparison step 70, the solver compares this new state cost to the cost of the current state, which was calculated previously”; Fig. 3 step 72 and paragraph [0086] “If the cost of the new state is no lower than the current state cost, the bits that were flipped at step 66 are flipped back, returning to the current state, at a new state rejection step 72”).
Naveh does not explicitly teach selecting a first bit from the bit group information based on at least one selected from a constraint satisfaction rate and a cumulative number of times of inversion; and selecting a second bit for each of the plurality of first elements different from a first element including the first bit, wherein the determining includes determining whether to exclude the first bit and the second bit from being used for searching for the solution of the optimization problem based on the certain condition.
However, on the same field of endeavor, Kellerer discloses an optimization wherein a first bit is selected from a first class and a second bit is selected from each of a plurality of classes different from the first class (Kellerer page 317 section 11.1).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention, to modify Naveh using Kellerer and configure the device to be able to solve a multiple-choice knapsack problem (MCKP) by selecting a first bit from the bit group information based on a constraint satisfaction rate; selecting a second bit for each of the plurality of first elements different from a first element including the first bit; and determining whether to exclude the first bit and the second bit from being used for searching for the solution of the optimization problem based on the certain condition by comparing the cost of the new state with the current state and excluding the first bit and the second bit from being used for searching for the solution of the optimization problem by flipping the first bit and the second bit back if the cost of the new state is not lower than the previous state in order to solve the MCKP by selecting exactly one item from each class such that the profit sum is maximized without exceeding the capacity c in the corresponding weight sum. By inverting two or more bits, the processor would be able to find the solution with enhanced speed (Naveh paragraph [0023]).
Therefore, the combination of Naveh as modified in view of Kellerer teaches a first bit from the bit group information based on at least one selected from a constraint satisfaction rate and a cumulative number of times of inversion; and selecting a second bit for each of the plurality of first elements different from a first element including the first bit, wherein the determining includes determining whether to exclude the first bit and the second bit from being used for searching for the solution of the optimization problem based on the certain condition.
Regarding claim 6, Naveh as modified in view of Kellerer teaches all the limitations of claim 4 as stated above. Further, Naveh as modified in view of Kellerer teaches wherein the selecting the first bit includes selecting the first bit that derives a local solution of the optimization problem by being inverted (Naveh Fig. 2 and paragraph [0069-0070] “ When the new state has a lower topographic cost than the current state, the new state becomes the current state. In this manner, the solver may reach local minimum 42, which is relatively deep and distant from other, lower minima of function 40 … When one of the variable-range hops leads to a new state of higher topographic cost than the current state, such as a state near local minimum 46, the process remains in its current state. On the other hand, when a hop leads to a new state of lower topographic cost, such as near local minimum 48, the current state is replaced by this new state. In this manner, the solver "escapes" from local minimum 42”).
Regarding claim 7, Naveh teaches all the limitations of claim 1 as stated above.
Naveh does not explicitly teach wherein the first element is a set of bits whose total number of bits that have identical states under the constraint condition is set.
However, on the same field of endeavor, Kellerer discloses an optimization problem wherein a plurality of variables is represented as binary variables and a total number of bits of the plurality of variables that have identical states under a constraint condition is set by having exactly one bit set for each class (Keller page 317 section 11.1 including Equation (11.2); “choose exactly one item from each class”; only one bit is set for each class).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention, to modify Naveh using Kellerer and configure the device to be able to solve a multiple-choice knapsack problem (MCKP) subject to the constraint conditions in Equations (11.1)-(11.3) such that the first element represents a set of bits whose total number of bits that have identical states under the constraint condition is set in order to select exactly one item from each class such that the profit sum is maximized without exceeding the capacity c in the corresponding weight sum as defined by the optimization problem (Kellerer page 317 section 11.1).
Therefore, the combination of Naveh as modified in view of Kellerer teaches wherein the first element is a set of bits whose total number of bits that have identical states under the constraint condition is set.
Regarding claim 8, Naveh teaches all the limitations of claim 1 as stated above.
Naveh does not explicitly teach wherein a number of the plurality of bits is equal to or less than twice a total number of bits defined under the constraint condition.
However, on the same field of endeavor, Kellerer discloses selecting a number of bits that is equal to or less than twice the total number of bits defined under a constraint condition by selecting exactly one item from each class (Kellerer page 317 section 11.1).
Accordingly, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention, to modify Naveh using Kellerer and configure the device to be able to solve a multiple-choice knapsack problem (MCKP) subject to the constraint conditions in Equations (11.1)-(11.3) by selecting an item having a bit value of ‘1’ and another item having a bit value of ‘0’ for each class such that inverting the bits would satisfy the constraint condition of having only item having a bit ‘1’ in each class. Doing so would result in the selected plurality of bits to invert in step 64 of Naveh having a number equal to or less than twice a total number of bits defined under the constraint condition. The reason to do so is to satisfy the constraint condition in Equations (11.1)-(11.3) (Kellerer page 317 section 11.1).
Therefore, the combination of Naveh as modified in view of Kellerer teaches wherein a number of the plurality of bits is equal to or less than twice a total number of bits defined under the constraint condition.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Carlo Waje whose telephone number is (571)272-5767. The examiner can normally be reached 9:00-6:00 M-F.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Andrew Caldwell can be reached at (571) 272-3702. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/Carlo Waje/Examiner, Art Unit 2182 (571)272-5767