Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Add bertsekas algo for assignment problem #600

Open
wants to merge 14 commits into
base: main
Choose a base branch
from
Open

Add bertsekas algo for assignment problem #600

wants to merge 14 commits into from

Conversation

smu160
Copy link

@smu160 smu160 commented Sep 13, 2024 •
edited
Loading

Hi,

Apologies for the delay. I added a basic implementation with random cost matrices that compare to the hungarian algorithm. I'll add benchmarks, but I think I'll create a non-criterion based benchmark in order to account for possibly sub-optimal solutions. That is, we want to not only compare the speedup, but how close the total score is to what the hungarian algorithm provides.

I didn't have the time just yet to fix the lack of parallelism. However, the structure for concurrency is already there. That is why you'll see the use of mspc::channel. I also need to use the Matrix struct that is used by the current hungarian algorithm implementation. Luckily, that should only improve performance given the 1D representation. I'll keep working on this. Please feel free to let me know what you think.

Thank you!!

Fix #586

@codspeed-hq CodSpeed HQ
Copy link

codspeed-hq bot commented Sep 13, 2024 •
edited
Loading

CodSpeed Performance Report

Merging #600 will not alter performance

Comparing smu160:bertsekas (d2479d9) with main (e8e81df)

Summary

✅ 36 untouched benchmarks

🆕 14 new benchmarks

Benchmarks breakdown

Benchmark main smu160:bertsekas Change
🆕 Bertekas Auction[1000] N/A 20.2 ms N/A
🆕 Bertekas Auction[100] N/A 393.5 µs N/A
🆕 Bertekas Auction[10] N/A 19.2 µs N/A
🆕 Bertekas Auction[200] N/A 1.2 ms N/A
🆕 Bertekas Auction[20] N/A 33.9 µs N/A
🆕 Bertekas Auction[500] N/A 5.8 ms N/A
🆕 Bertekas Auction[50] N/A 124.9 µs N/A
🆕 Hungarian Algorithm[1000] N/A 5.8 s N/A
🆕 Hungarian Algorithm[100] N/A 1.2 ms N/A
🆕 Hungarian Algorithm[10] N/A 16.3 µs N/A
🆕 Hungarian Algorithm[200] N/A 7.5 ms N/A
🆕 Hungarian Algorithm[20] N/A 50.9 µs N/A
🆕 Hungarian Algorithm[500] N/A 450.2 ms N/A
🆕 Hungarian Algorithm[50] N/A 237.6 µs N/A

@smu160

This comment was marked as outdated.

Sign in to view
@smu160 smu160 marked this pull request as ready for review September 20, 2024 00:20
@smu160
Copy link
Author

smu160 commented Sep 20, 2024 •
edited
Loading

@samueltardieu

I added a benchmark, using criterion, to compare the kuhn_munkres implementation with the bertsekas implementation.

Since the Bertsekas auction can give sub-optimal results (this is dependent on $\epsilon$ and the scaling factor), I included plots I rendered via matplotlib to compare the run-time as well as the overall score of the assignments. The underlying "benchmark" for these plots can be found in examples/assignment.rs.

cargo criterion --bench kuhn_munkres_vs_bertsekas --output-format bencher
    Finished `bench` profile [optimized] target(s) in 0.02s
test Assignment Problem/Bertekas Auction/10 ... bench:        3346 ns/iter (+/- 902)
test Assignment Problem/Hungarian Algorithm/10 ... bench:         777 ns/iter (+/- 126)
test Assignment Problem/Bertekas Auction/20 ... bench:        7051 ns/iter (+/- 1342)
test Assignment Problem/Hungarian Algorithm/20 ... bench:        2634 ns/iter (+/- 362)
test Assignment Problem/Bertekas Auction/50 ... bench:       20769 ns/iter (+/- 2251)
test Assignment Problem/Hungarian Algorithm/50 ... bench:       17671 ns/iter (+/- 2471)
test Assignment Problem/Bertekas Auction/100 ... bench:       54119 ns/iter (+/- 4672)
test Assignment Problem/Hungarian Algorithm/100 ... bench:      174590 ns/iter (+/- 38993)
test Assignment Problem/Bertekas Auction/200 ... bench:      169806 ns/iter (+/- 15348)

Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 5.4s, enable flat sampling, or reduce sample count to 60.
test Assignment Problem/Hungarian Algorithm/200 ... bench:      989247 ns/iter (+/- 128546)
test Assignment Problem/Bertekas Auction/500 ... bench:      888877 ns/iter (+/- 52426)
test Assignment Problem/Hungarian Algorithm/500 ... bench:    45738048 ns/iter (+/- 2187718)
test Assignment Problem/Bertekas Auction/1000 ... bench:     2360069 ns/iter (+/- 317069)

Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 47.1s, or reduce sample count to 10.
test Assignment Problem/Hungarian Algorithm/1000 ... bench:   492148479 ns/iter (+/- 10239431)

execution_time_comparison
score_comparison

This PR is definitely still a work in progress, but I thought I'd share these preliminary results with you so you can have a clearer picture.

Note that the code is setup for parallelism already via the use of channels. Thus, these benchmark results contain a lot of unnecessary overhead for the bertseka's algorithm implementation, without the advantage of using multiple threads.

In addition this is a very basic implementation of this algorithm. We can actually converge on the solution much quicker if we have a forward/reverse auction. Luckily, this current implementation can be easily extended to facilitate this.

Lastly, please note this current implementation does not support asymmetric assignment problems. Thus, we always have to have $N == M$, where $N$ is the # of agents, and $M$ is the # of tasks. The addition of the reverse auction (see the above paper) would facilitate assignment problems where $N < M$.

Thank you!!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Consider using a faster solver for maximum weight matching
1 participant
@smu160