Context Navigation

← Previous Ticket
Next Ticket →

#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 ncohen)

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)

binpacking.patch (4.0 KB) - added by ncohen 11 years ago.
trac_6763.patch (4.4 KB) - added by ncohen 11 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 11 years ago by ncohen

Summary changed from [with patch, needs review] Bin Packing (uses Linear Programming) to [with patch, needs work] Bin Packing (uses Linear Programming)

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

comment:2 Changed 11 years ago by ncohen

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 robertwb

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 ncohen

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 robertwb

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 ncohen

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 robertwb

Sort the result before printing.

comment:8 Changed 11 years ago by ncohen

Done

Changed 11 years ago by ncohen

Attachment binpacking.patch added

comment:9 Changed 11 years ago by jsyri

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 ncohen

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 jsyri

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.