3 ms·

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 alg

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.

whatever1 2y ago
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.
- JohnKemeny 2y ago
  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.
  - whatever1 2y ago
    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.
    - almostgotcaught 2y ago
      > 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 hate when people cloak very obvious things in jargon to make those things seem more insightful and disguise how obvious they are. What you're basically saying is if you're lucky and you win the lottery then you'll be rich. Ie yes we all know that if you luck out then interior point will give you the optimum in polynomial time. But the whole reason why MIP is np-hard is exactly because deriving those cuts in general isn't possible (at least currently). > This is not what math programming does So what gurobi/cplex/etc actually do is first try a bazillion symmetry transformations/warm start heuristics/etc but then ultimately it does boil down to search.
      - whatever1 2y ago
        No and No. This way of thinking describes the plateau that MIP solvers hit in the 90's. Then in 2000's they starting implementing actual math (valid cuts in the root node mainly, but also during the search), which what gave us the exponential speed ups we enjoy today. So you would be right 30 years ago. You are wrong in 2024.
        almostgotcaught 2y ago
        > No and No. > which what gave us the exponential speed ups we enjoy today You're just patently wrong because 1. P=?NP is still open 2. You can consult the implementation of any solver There's really nothing more to be said about it because both of these bullets are formal proofs that you are wrong.
        whatever1 2y ago
        Simplex algorithm should never work given its exponential worst case performance. Yet it solves the vast majority of LP problems, including ones with billions of variables. It is the default algorithm for every solver despite the fact that we have a polynomial interior point method in our disposal. Go figure. Worst case performance or NP completeness is not a predictor of how fast we can solve an optimization problem.
        JohnKemeny 2y ago
        > should never work given its exponential worst case performance This is again not true. We know why it works well. See the paper "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time" by Spielmann and Teng.
        whatever1 2y ago
        We started understanding of why it works so well like 30 years after its first implementation (in the 1950's)? The paper you mention is written in the 2000s while the Simplex dominated the field from at least the 70's. Meanwhile the GP would have discarded the simplex algorithm due to its worst case performance.
TacticalCoder 2y ago
Can't subset sum like in TFA be solved by dynamic programming using a modified 0-1 knapsack? (modified to keep track of selected items)
- JohnKemeny 2y ago
  Yup, in time (and space) O(M • n), so with M = 1 million and let's say n = 1 million, it takes space 1 trillion. Given a byte per number, it takes a TB of memory, but is otherwise doable. Ps, you don't want to risk a running time of form O(Mn²).
JadeNB 2y ago
> weakly NP-hard What does this mean?
- JohnKemeny 2y ago
  Weak NP-completeness is problems that are numeric in nature and that become polynomial time solvable if the encoding of the numbers are given in unary. https://en.wikipedia.org/wiki/Weak_NP-completeness https://en.wikipedia.org/wiki/Weak_NP-completeness
  - JadeNB 2y ago
    Ah, thanks. Then, since "NP-hard" and "NP-complete" are different, I would expect "weakly NP-hard" and "weakly NP-complete" to be different; but, at least according to Wikipedia, they are synonymous.
w1 2y ago
This is also a problem for accountants, trying to do “account reconciliation” to determine which transactions contribute to a given balance. I made a simple tool that does this client-side for an accountant friend a while ago: https://reconciliation.spcdx.com/ https://reconciliation.spcdx.com/ (Warning: runtimes do quickly scale, due to the time complexity described above)

whatever1 2y ago

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.

JohnKemeny 2y ago
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.
- whatever1 2y ago
  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.
  - almostgotcaught 2y ago
    > 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 hate when people cloak very obvious things in jargon to make those things seem more insightful and disguise how obvious they are. What you're basically saying is if you're lucky and you win the lottery then you'll be rich. Ie yes we all know that if you luck out then interior point will give you the optimum in polynomial time. But the whole reason why MIP is np-hard is exactly because deriving those cuts in general isn't possible (at least currently). > This is not what math programming does So what gurobi/cplex/etc actually do is first try a bazillion symmetry transformations/warm start heuristics/etc but then ultimately it does boil down to search.
    - whatever1 2y ago
      No and No. This way of thinking describes the plateau that MIP solvers hit in the 90's. Then in 2000's they starting implementing actual math (valid cuts in the root node mainly, but also during the search), which what gave us the exponential speed ups we enjoy today. So you would be right 30 years ago. You are wrong in 2024.
      - almostgotcaught 2y ago
        > No and No. > which what gave us the exponential speed ups we enjoy today You're just patently wrong because 1. P=?NP is still open 2. You can consult the implementation of any solver There's really nothing more to be said about it because both of these bullets are formal proofs that you are wrong.
        whatever1 2y ago
        Simplex algorithm should never work given its exponential worst case performance. Yet it solves the vast majority of LP problems, including ones with billions of variables. It is the default algorithm for every solver despite the fact that we have a polynomial interior point method in our disposal. Go figure. Worst case performance or NP completeness is not a predictor of how fast we can solve an optimization problem.
        JohnKemeny 2y ago
        > should never work given its exponential worst case performance This is again not true. We know why it works well. See the paper "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time" by Spielmann and Teng.
        whatever1 2y ago
        We started understanding of why it works so well like 30 years after its first implementation (in the 1950's)? The paper you mention is written in the 2000s while the Simplex dominated the field from at least the 70's. Meanwhile the GP would have discarded the simplex algorithm due to its worst case performance.

TacticalCoder 2y ago

Can't subset sum like in TFA be solved by dynamic programming using a modified 0-1 knapsack? (modified to keep track of selected items)

JohnKemeny 2y ago
Yup, in time (and space) O(M • n), so with M = 1 million and let's say n = 1 million, it takes space 1 trillion. Given a byte per number, it takes a TB of memory, but is otherwise doable. Ps, you don't want to risk a running time of form O(Mn²).

JadeNB 2y ago

> weakly NP-hard What does this mean?

JohnKemeny 2y ago
Weak NP-completeness is problems that are numeric in nature and that become polynomial time solvable if the encoding of the numbers are given in unary. https://en.wikipedia.org/wiki/Weak_NP-completeness https://en.wikipedia.org/wiki/Weak_NP-completeness
- JadeNB 2y ago
  Ah, thanks. Then, since "NP-hard" and "NP-complete" are different, I would expect "weakly NP-hard" and "weakly NP-complete" to be different; but, at least according to Wikipedia, they are synonymous.

w1 2y ago

This is also a problem for accountants, trying to do “account reconciliation” to determine which transactions contribute to a given balance. I made a simple tool that does this client-side for an accountant friend a while ago: https://reconciliation.spcdx.com/ https://reconciliation.spcdx.com/ (Warning: runtimes do quickly scale, due to the time complexity described above)