Title:
DEVICE FOR ACCELERATING BRANCH-AND-BOUND METHOD, METHOD, AND PROGRAM
Document Type and Number:
WIPO Patent Application WO/2024/029022
Kind Code:
A1
Abstract:
This device for accelerating a branch-and-bound method comprises a branching unit, an interval determination unit, a presumed threshold determination unit, and a comparison unit. The branching unit performs a branching operation that divides an input problem into a plurality of problems. The interval determination unit determines a first threshold that defines a first interval where a solution set for each divided problem may exist on the basis of feasible solutions of each divided problem, and determines a second threshold that defines the first interval by solving a relaxation problem of each divided problem. The presumed threshold determination unit uses the first threshold, the second threshold, a probability distribution representing a probability that an optimal solution for each divided problem exists in a second interval narrower than the first interval and with one threshold defining the second interval as the first threshold, and a set probability value to determine a third threshold as the other threshold defining the second interval. The comparison unit executes pruning of the solution sets by comparing the first threshold with the third threshold for each solution set.
Inventors:
OGAWA MANAMI (JP)
KANAI SHUNSUKE (JP)
SATO MASATAKA (JP)
AKASHI KAZUAKI (JP)
YAMAZOE MAYU (JP)
KANAI SHUNSUKE (JP)
SATO MASATAKA (JP)
AKASHI KAZUAKI (JP)
YAMAZOE MAYU (JP)
Application Number:
PCT/JP2022/029908
Publication Date:
February 08, 2024
Filing Date:
August 04, 2022
Export Citation:
Assignee:
NIPPON TELEGRAPH & TELEPHONE (JP)
International Classes:
G06N99/00; G06F17/10
Domestic Patent References:
| WO2012176925A1 | 2012-12-27 |
Other References:
YAMAGUCHI, TAKURO ET AL.: "(Efficient enumeration of genetic interactions using the lower bound of p-value by Fisher's exact probability test", IPSJ SIG TECHNICAL REPORT, vol. 2015-MPS-103, no. 56, 16 June 2015 (2015-06-16), JP , pages 1 - 2, XP009552783, ISSN: 2188-8833
Attorney, Agent or Firm:
SUZUYE & SUZUYE (JP)
Download PDF: