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

Different Results For SSP and muSSP #16

Open
Kumarj95 opened this issue Oct 21, 2024 · 12 comments
Open

Different Results For SSP and muSSP #16

Kumarj95 opened this issue Oct 21, 2024 · 12 comments

Comments

@Kumarj95
Copy link

Hello Everyone,

Firstly I would like to thank the authors for this repository.

I have been trying to use the SSP solver included within this repository for my project. The reason I am using SSP over the titular muSSP is because the results from that algorithm seem to be closer to the old method I was using (https://developers.google.com/optimization/flow/mincostflow). It was a little confusing to me why the algorithms would produce different results (drastically different results at that).

I was wondering if anyone could help me out with this and provide some reading to better understand why this would be the case if it is not a bug in the code.
@yu-lab-vt
Copy link
Owner

yu-lab-vt commented Oct 22, 2024 via email

@Kumarj95
Copy link
Author

Hello,

Sure, I have attached a sample graph.txt file.

Here, if I use the muSSP solver I get the following output as my last line

The number of paths: 159, total cost is -193821.0000000, final path cost is: -1.0000000.

Meanwhile if I use the SSP solver I get the following output as my last line

The number of paths: 276, total cost is -206895.0000000, final path cost is: -1.0000000.

I have made some changes to the SSP solver, but they were related to being able to print out the solution in a text file, maybe I changed something important in the solver that causes this discrepancy.

Please let me know if you are able to recreate this!

graph.txt

@Kumarj95
Copy link
Author

Hello,

After looking into it further, I was able to recreate the issue with a much smaller test file that might be beneficial for debugging (~2500 lines).

In this case, the muSSP solver outputs the following:

The number of paths: 6, total cost is -367.4988948, final path cost is: -48.3267876.

While the SSP solver outputs the following:

The number of paths: 7, total cost is -358.1871302, final path cost is: -2.8918555.

Sorry for the large initial file.

graph3.txt

@Kumarj95
Copy link
Author

Hello,

I just wanted to follow up to see if there were any updates on this! Thanks!

@yu-lab-vt
Copy link
Owner

yu-lab-vt commented Nov 24, 2024 via email

@yu-lab-vt
Copy link
Owner

yu-lab-vt commented Nov 25, 2024 via email

@ccwang92
Copy link
Contributor

Hello,

I just wanted to follow up to see if there were any updates on this! Thanks!

Hey Kumarj95,

Sorry that I missed your uploaded example. I am currently out of town for Thanksgiving with my family and I will take a look right after I coming back. Thanks!

Congchao

@Kumarj95
Copy link
Author

Kumarj95 commented Dec 3, 2024

Sorry that I missed your uploaded example. I am currently out of town for Thanksgiving with my family and I will take a look right after I coming back. Thanks!

No worries. Let me know if the second example I provided is still too tedious for debugging and I can try to produce something more manageable. Thanks again!

@Kumarj95
Copy link
Author

Hello,

I just wanted to follow up to see if there was an update on this.

@yu-lab-vt
Copy link
Owner

yu-lab-vt commented Dec 25, 2024 via email

@ccwang92
Copy link
Contributor

ccwang92 commented Jan 2, 2025

Hey @Kumarj95 , sorry for the late reply. I have some urgent family issue recently. I double checked your graph. It indeed has different results using SSP vs. muSSP. I have not figured out how this could happen. Do you have a smaller graph to reproduce the results? This graph contains 500k+ arcs, I tried to print out intermediate results but it is very hard to debug with such big graph. Thanks!

@Kumarj95
Copy link
Author

Kumarj95 commented Jan 2, 2025

Hello @ccwang92 ,
I have attached another graph here, with far fewer arcs
graph3.txt

I am sorry to hear about your family issue and appreciate you taking the time to look into this.

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

No branches or pull requests
3 participants
@ccwang92 @Kumarj95 @yu-lab-vt