This is Subset Sum and is famously NP-complete so, no, an LP doesn't work. However, the problem is only weakly NP-hard and there is a pseudo-polynomial time algorithm running in time O(M • n) where M is the sum and n is the number of accounts.
The problem is, perhaps, most of all, that it takes the same amount of space.
Ps, it's not a permutations problem, but a subsets problem. While permutations is n! subsets are "only" 2^n.
I agree that you can solve it using MILP, but I would say that commercial solvers will solve many instances of the problem pretty fast. But we know that you need even Ω(n²) time for 3SUM, so given large enough n, some instances will take a long time, regardless of solver.
This is not what math programming does. Theoretically if you derive tight enough cuts for the problem and the solution lies on a vertex of the relaxed simplex you you can get the optimal solution in polynomial time.
I used to walk people through the "2sum" and "3sum" variants of this for an interview question. I was not looking for anything complicated, such that it was easy enough to talk through solutions that we could play with. Had a few people that would take us down some rather complicated approaches. (Even gave offers to some that got through some complicated solutions that wouldn't work.)
I never tried doing an "optimal" solution. Thinking about the problem, I'm curious if a BDD approach wouldn't work? Will try and write one up to see. Fun times.
In the real world this would be more complicated, because there could be more mixing and withdrawals. Banks also have a lot of visibility into account transactions, at least in the case of accounts which they would know the balances for.
This is Subset Sum and is famously NP-complete so, no, an LP doesn't work. However, the problem is only weakly NP-hard and there is a pseudo-polynomial time algorithm running in time O(M • n) where M is the sum and n is the number of accounts.
The problem is, perhaps, most of all, that it takes the same amount of space.
Ps, it's not a permutations problem, but a subsets problem. While permutations is n! subsets are "only" 2^n.
This is a MIP. CBC is an open source solver with a very basic implementation of branch & bound, cuts and search heuristics.
Any modern commercial solver (Gurobi, Xpress, IBM-CPLEX, COPT) can solve problems of this size pretty fast.
I agree that you can solve it using MILP, but I would say that commercial solvers will solve many instances of the problem pretty fast. But we know that you need even Ω(n²) time for 3SUM, so given large enough n, some instances will take a long time, regardless of solver.
This is assuming exhaustive search.
This is not what math programming does. Theoretically if you derive tight enough cuts for the problem and the solution lies on a vertex of the relaxed simplex you you can get the optimal solution in polynomial time.
I used to walk people through the "2sum" and "3sum" variants of this for an interview question. I was not looking for anything complicated, such that it was easy enough to talk through solutions that we could play with. Had a few people that would take us down some rather complicated approaches. (Even gave offers to some that got through some complicated solutions that wouldn't work.)
I never tried doing an "optimal" solution. Thinking about the problem, I'm curious if a BDD approach wouldn't work? Will try and write one up to see. Fun times.
In the real world this would be more complicated, because there could be more mixing and withdrawals. Banks also have a lot of visibility into account transactions, at least in the case of accounts which they would know the balances for.