Opened 9 years ago
Closed 9 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 9 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 9 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 9 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 9 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 9 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 9 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 9 years ago by
Sort the result before printing.
comment:8 Changed 9 years ago by
Done
Changed 9 years ago by
comment:9 Changed 9 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 9 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 9 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 9 years ago by
comment:13 Changed 9 years ago by
- Status changed from needs_review to positive_review
Everything seems to be in order. Positive review.
comment:14 Changed 9 years ago by
Thank youuuuuuuuu :-)
Nathann
comment:15 Changed 9 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