Opened 11 years ago
Closed 11 years ago
#6763 closed enhancement (fixed)
[with patch, needs review] Bin Packing (uses Linear Programming)
Reported by: | ncohen | Owned by: | jkantor |
---|---|---|---|
Priority: | major | Milestone: | sage-4.4.4 |
Component: | numerical | Keywords: | |
Cc: | Merged in: | sage-4.4.4.alpha0 | |
Authors: | Nathann Cohen | Reviewers: | Joni Syri |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch implements a solver for the Bin Packing problem using Linear Programming.. To test this you will have to first install GLPK and one patch, all available on ticket #6869 ;-)
I hope you will like the documentation, I tried to make it clean ;-)
Attachments (2)
Change History (17)
comment:1 Changed 11 years ago by
- Summary changed from [with patch, needs review] Bin Packing (uses Linear Programming) to [with patch, needs work] Bin Packing (uses Linear Programming)
comment:2 Changed 11 years ago by
- Description modified (diff)
- Summary changed from [with patch, needs work] Bin Packing (uses Linear Programming) to [with patch, needs review] Bin Packing (uses Linear Programming)
New version, ready for review !!!!
Nathann
comment:3 Changed 11 years ago by
- Report Upstream set to N/A
- Status changed from needs_review to needs_work
What is the output format? You should include several more examples. Also, unless success returns True, it's better to raise an error on failure than return False.
comment:4 Changed 11 years ago by
- Status changed from needs_work to needs_review
updated... This patch was 5 months old and was not working anymore ;-)
Nathann
comment:5 Changed 11 years ago by
Thanks, that clarifies things more. I would raise a ValueError? rather than a generic exception. Also, you still need more examples. (You never actually even show the output.)
comment:6 Changed 11 years ago by
Well, maybe you can help me for the output : I deliberately avoided to show it as a valid solution [A,B] could be returned [B, A], for example... It depends on the solvers you use, but also on the platform (hashing functions depend on it, I learnt that recently from William and it was breaking som eof my docstring). How do you think we could avoid it ? :-)
Nathann
comment:7 Changed 11 years ago by
Sort the result before printing.
comment:8 Changed 11 years ago by
Done
Changed 11 years ago by
comment:9 Changed 11 years ago by
- Status changed from needs_review to needs_work
I think check should be added to make sure all weights are <= max. At the moment
binpacking([1,2,3],2)
causes infinite loop. Otherwise code seems fine.
comment:10 Changed 11 years ago by
- Status changed from needs_work to needs_review
Patch updated !! With a few other modifications, as this patch is one of the first LP patches Trac received, and is even older than the 8 months this ticket indicates... I'm not sorry to see it finally reviewed ! :-)
By the way, if you like Linear Programming and have some time to spend on trac tickets... I desperately need some help with LP patches in the Graph Theory section ;-)
Thank you very much !
Nathann
comment:11 Changed 11 years ago by
- Status changed from needs_review to needs_work
One last thing, I'm sorry I didn't catch it first time around. Documentation for the parameter 'k' claims function will return false if solution doesn't exist. Instead exception is raised if no solution exists.
Changed 11 years ago by
comment:13 Changed 11 years ago by
- Status changed from needs_review to positive_review
Everything seems to be in order. Positive review.
comment:14 Changed 11 years ago by
Thank youuuuuuuuu :-)
Nathann
comment:15 Changed 11 years ago by
- Merged in set to sage-4.4.4.alpha0
- Resolution set to fixed
- Reviewers set to Joni Syri
- Status changed from positive_review to closed
As the functions dealing with LP have not been reviewed, I prefer to rewrite the MIP class for Sage to make it easier to use. I will post a new version of the MIP patch as soon as possible, along with all the patches for functions using it.
Sorry for the trouble, I'll try to make it quick !
Nathann