Algorithm that is a combination of the continuous knapsack problem and the variable size bin packing problem

Question

Hello, I'm trying to solve a problem (in php, but programming language doesn't matter). I'm having a n number of persons that have paid money, and I have got a m number of persons that are going to pay the same amount as the sum of what the n number of people have paid. I want to calculate the shortest route of money transfers between these persons. It is possible to split the payments and pay to different persons. The ideal is that one person only makes one or two transactions. Can someone maybe point me in the right direction or help me with this?

An example: person A has paid $100

person B has paid $200

person C has paid $50

person D will pay $24

person E will pay $175

person F will pay $151

One possible solution to this is

person E pays $100 to person A,

person E pays $75 to person B,

person F pays $125 to person B,

person F pays $26 to person C

person D pays $24 to person C

Answer 1

In theory this could be framed as an optimization problem:

Basically we're going to establish a set of constraints that enumerate the structure of your problem, seed the initial values, and make sure that we allocate all the money as you've indicated.

Initial condition constraints:

A_paid = 100
B_paid = 200
C_paid = 50
D_out  = 24
E_out  = 175
F_out  = 151

Amount paid out cannot exceed the amount available: (we define D_to_A as a variable holding the amount paid from person D to person A)

D_out >= D_to_A + D_to_B + D_to_C
E_out >= E_to_A + E_to_B + E_to_C
F_out >= F_to_A + F_to_B + F_to_C

Amount paid to each individual must be equal to what they've already paid:

A_paid = D_to_A + E_to_A + F_to_A
B_paid = D_to_B + E_to_B + F_to_B
C_paid = D_to_C + E_to_C + F_to_C

If we were to stop now and solve this as a linear program we'd find any solution spanning the entire variable space, but you're looking to minimize the number of actual payments. We can do this by minimizing over all X_to_Y variables in concert with the constraints above.

min: D_to_A + D_to_B + D_to_C + ...

You can use your favorite optimization technique to solve the problem, there's plenty of available linear program solvers, I like lpsolve.

Though this solves the specific example you described it's easy to see how it can be expanded to larger problems by adding more variables...but the problem grows in complexity substantially as you add people. If I recall correctly the knapsack problem is NP or NP-hard, so this isn't unexpected.