Method and system for solving subset sum matching problem using dynamic programming approach

Patent metadata

Field	Value
Publication number	US-12567013-B2
Application number	US-202318208608-A
Country	US
Kind code	B2
Filing date	Jun 12, 2023
Priority date	Jun 12, 2023
Publication date	Mar 3, 2026
Grant date	Mar 3, 2026

Abstract

Methods and systems for performing a combinatorial optimization task are provided. The method includes: receiving a first set of data items and discretizing each of the first set of data items in order to generate a first discretized set of data items; receiving a second set of data items and discretizing each of the second set of data items in order to generate a second discretized set of data items; reorganizing the first and second discretized sets of data items into two respective groups of positive integers; using the two groups of positive integers to generate two respective tables for storing a feasibility of obtaining at least one subset sum from among the elements of the first and second discretized sets of data items; and performing a subset sum matching procedure upon the two tables in order to identify the at least one subset sum.

First claim

What is claimed is:

1 . A method for performing a combinatorial optimization task that relates to finding matching digital subsets among items that are associated with two parties, the method being implemented by at least one processor, the method comprising:
implementing a Subset Sum Matching Problem Solver (SSMPS) program with a first algorithm comprising a sub-optimal combinatorial optimization algorithm and a memory search-based algorithm, and a second algorithm comprising a dynamic programming pseudo-polynomial algorithm, wherein the SSMPS program operates via a virtual server in a cloud-based computing environment; receiving, a digital first set of data items that relate to respective characteristics of a first situation, and executing the SSMPS program that virtually discretizes each of the digital first set of data items to generate a digital first discretized set of data items; receiving a digital second set of data items that relate to respective characteristics of a second situation, and executing the SSMPS program that virtually discretizes each of the digital second set of data items in order to generate a digital second discretized set of data items; executing the SSMPS program that virtually reorganizes the digital first and second discretized sets of data items into two respective groups of positive integers; executing the SSMPS program that virtually generates two respective digital tables based on the two respective groups of positive integers that stores a feasibility of obtaining at least one digital subset sum match from among elements of the digital first and second discretized sets of data items; executing the SSMPS program that virtually performs a digital subset sum matching procedure based upon the two respective digital tables to virtually identify the at least one digital subset sum match; executing the SSMPS program that virtually divides the digital first discretized set of data items into a digital first subset that includes all elements having values greater than zero and a digital second subset that includes all elements having values less than zero, and generating a digital third subset that includes absolute values of all elements of the digital second subset; executing the SSMPS program that virtually divides the digital second discretized set of data items into a digital fourth subset that includes all elements having values greater than zero and a digital fifth subset that includes all elements having values less than zero, and generating a digital sixth subset that includes absolute values of all elements of the digital fifth subset; executing the SSMPS program that virtually performs a first vector concatenation operation between the digital first subset and the digital sixth subset to generate a first one of the two respective groups of positive integers; and executing the SSMPS program that virtually performs a second vector concatenation operation between the digital third subset and the digital fourth subset to generate a second one of the two respective groups of positive integers.

2 . The method of claim 1 , further comprising:
executing the SSMPS program that virtually selects a value for a matching threshold, wherein the executing the SSMPS program that virtually performs the digital subset sum matching procedure comprises a virtual determination on whether a difference between a digital subset sum that corresponds to the digital second discretized set of data items and a digital subset sum that corresponds to the digital first discretized set of data items is less than the virtually selected value for the matching threshold.

3 . The method of claim 1 , wherein the executing the SSMPS program that virtually performs the digital subset sum matching procedure further comprises executing the SSMPS program to virtually validate the virtually identified at least one digital subset sum match.

4 . The method of claim 1 , wherein for each of the two respective digital tables, a number of columns is equal to a largest subset value that is matchable between the two respective groups of positive integers plus one; and
for a first one of the two respective digital tables, a number of rows is equal to a number of elements included in a first one of the two respective groups of positive integers; and for a second one of the two digital respective tables, a number of rows is equal to a number of elements included in a second one of the two respective groups of positive integers.

5 . The method of claim 4 , wherein the executing the SSMPS program that virtually performs the digital subset sum matching procedure comprises a virtual comparison of a last row of the first one of the two respective digital tables with a last row of the second one of the two respective digital tables to virtually identify at least one ordered pair of values that corresponds to a digital matching pair of subset sums from among the digital first and second discretized sets of data items.

6 . The method of claim 5 , wherein the executing the SSMPS program that virtually performs the digital subset sum matching procedure further comprises using the at least one ordered pair to apply a binary tree search to each of the two respective digital tables to virtually determine the digital matching pair of subset sums.

7 . The method of claim 1 , wherein the first situation relates to a first set of digital records that is associated with a first party from among the two parties, and the second situation relates to a second set of digital records that is associated with a second party from among the two parties.

8 . A computing apparatus for performing a combinatorial optimization task that relates to finding matching digital subsets among items that are associated with two parties, the computing apparatus comprising:
a processor; a memory; and a communication interface coupled to each of the processor and the memory, wherein the processor is configured to: implement a Subset Sum Matching Problem Solver (SSMPS) program with a first algorithm comprising a sub-optimal combinatorial optimization algorithm and a memory search-based algorithm, and a second algorithm comprising a dynamic programming pseudo-polynomial algorithm, wherein the SSMPS program operates via a virtual server in a cloud-based computing environment; receive, via the communication interface, a digital first set of data items that relate to respective characteristics of a first situation, and execute the SSMPS program that virtually discretizes each of the digital first set of data items to generate a digital first discretized set of data items; receive, via the communication interface, a digital second set of data items that relate to respective characteristics of a second situation, and execute the SSMPS program that virtually discretizes each of the digital second set of data items to generate a digital second discretized set of data items; execute the SSMPS program that virtually reorganizes the first and second discretized sets of data items into two respective groups of positive integers; execute the SSMPS program that virtually generates two respective digital tables based on the two respective groups of positive integers that stores a feasibility of obtaining at least one digital subset sum match from among elements of the digital first and second discretized sets of data items; execute the SSMPS program that virtually performs a digital subset sum matching procedure upon the two respective digital tables to virtually identify the at least one digital subset sum match; execute the SSMPS program that virtually divides the digital first discretized set of data items into a digital first subset that includes all elements having values greater than zero and a d

Assignees

• Jpmorgan Chase Bank Na

Inventors

• Wu Yufei
• Zehtabi Parisa
• Pozanco Alberto
• Borrajo Daniel
• Magazzeni Daniele
• Veloso Manuela
• Cashmore Michael
• Deng Jie

Classifications

• G06Q10/06316 Primary

  Sequencing of tasks or work · CPC title