ollieboyne / sslap Goto Github PK

I did some testing with the sparse matrix input for the solver and came across something. Currently I am just using sparse identity matrices for testing purposes and whenever I go above n=130'000 something seems to break. On Linux I typically get a Segmentation fault (core dumped) and on a Windows machine the python kernel seems to just break down.

Python 3.6.8 |Anaconda, Inc.| (default, Dec 30 2018, 01:22:34)
[GCC 7.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from scipy import sparse
>>> from sslap import auction_solve
>>>
>>> Cs = sparse.coo_matrix(sparse.identity(130000))
>>>
>>> sol = auction_solve(coo_mat=Cs, problem='max')
Segmentation fault (core dumped)

First of all, thank you for your great piece of code!
I'm wondering whether it is possible or not to handle rectangular sparse problems, i.e. people < objects.

First of all, thank you for your great piece of code!
I'm wondering whether it is possible or not to handle rectangular sparse problems, i.e. people < objects.

Hi, when I use auction_solve to run 60000 x 60000 matrix, I got "Maximum allowed dimension exceeded" error. I checked your code in sslap/auction_.pyx, but I didn't find any limitation of the maximum dimension. Would you kindly tell me how to solve it? Thank you so much.

I've been trying to use this package to solve a very large (1M x 1M cost matrix, though very sparse) linear assignment problem. doing this causes a segmentation fault even when passing cardinality_check=False.

To get around this, I cut up my problem into many smaller problems of varying sizes (10kx10k to 300x300) because this is suboptimal but feasible for my use-case. My program will start to solve the smaller problems, but will eventually crash, but never at one particular problem.

To isolate the problem, I wrote the following code to remove the other elements of my code:

import numpy as np
from scipy.sparse import random as sparse_random
import sslap

size = 1000
density = 0.01
loop_count = 100

for i in range(loop_count):
    dense_matrix = sparse_random(size, size, density=density, format='coo', data_rvs=np.random.rand).todense()
    result = sslap.auction_solve(dense_matrix, cardinality_check=False, fast=True)
    print(f"Loop {i + 1} completed")

When this is done, memory usage climbs very quickly. Our compute has 200gb ram and a larger swap, and it quickly exceeds this.

Notably this only happens when passing a sparse matrix, and not a dense matrix. I believe it still happens with the dense matrix but it appears to be much much slower.

Hi,

I've run into the following problem: When using the solver on a Windows machine everything is fine. However, trying it on a machine running Linux-Ubuntu I get the following error:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/data/homes/atschan/.conda/envs/python_3_7/lib/python3.7/site-packages/sslap/auction_solve.py", line 49, in auction_solve
    solver = _from_sparse(loc=loc, val=val, size=size, **kw)
  File "sslap/auction_.pyx", line 567, in sslap.auction_._from_sparse
  File "sslap/auction_.pyx", line 596, in sslap.auction_._from_sparse
ValueError: Buffer dtype mismatch, expected 'long' but got 'int'

Hi,

I was trying to use auction solver in one of my solution. While comparing it to scipy linear sum assignment I saw results are not same. Attached is an example with 1 object and 8 people. Scipy is picking the right value (40.4) and auction solver failed to pick it.

Hi, thanks for your work this looks really interesting! I have a question however:

As far as I understand the input at the moment is a numpy array where "-1" defines disallowed assignments. Would it be possible to actually give a sparse matrix (e.g. from scipy sparse) as an input for the algorithm where a cost of 0 would define that no assignment is allowed and the higher the value the more likely is the assignment?

I am asking this because one of my main problems with the traditional LAP solvers is that my cost matrices become too large to fit in memory. Therefore I am looking for something that can handle sparse matrices.

Thank you!