[HN Gopher] Suits, money laundering, and linear programming
       ___________________________________________________________________
        
       Suits, money laundering, and linear programming
        
       Author : apwheele
       Score  : 28 points
       Date   : 2024-10-28 20:19 UTC (3 days ago)
        
 (HTM) web link (andrewpwheeler.com)
 (TXT) w3m dump (andrewpwheeler.com)
        
       | JohnKemeny wrote:
       | 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 wrote:
         | 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 wrote:
           | 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 O(n2)
           | time for 3SUM, so given large enough n, some instances will
           | take a long time, regardless of solver.
        
             | whatever1 wrote:
             | 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.
        
       ___________________________________________________________________
       (page generated 2024-10-31 23:00 UTC)