Bin Packing (uses Linear Programming)

[nathanncohen]

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 ;-)

Component: numerical

Author: Nathann Cohen

Reviewer: Joni Syri

Merged: sage-4.4.4.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/6763

[nathanncohen]

comment:1

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

[nathanncohen]

comment:2

New version, ready for review !!!!

Nathann

[robertwb]

comment:3

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.

[nathanncohen]

comment:4

updated... This patch was 5 months old and was not working anymore ;-)

Nathann

[robertwb]

comment:5

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.)

[nathanncohen]

comment:6

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

[robertwb]

comment:7

Sort the result before printing.

[nathanncohen]

comment:8

Done

[sagetrac-jsyri]

comment:9

Attachment: binpacking.patch.gz

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.

[nathanncohen]

comment:10

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

[sagetrac-jsyri]

comment:11

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.

[nathanncohen]

comment:12

Fixed.

[sagetrac-jsyri]

comment:13

Attachment: trac_6763.patch.gz

Everything seems to be in order. Positive review.

[nathanncohen]

comment:14

Thank youuuuuuuuu :-)

Nathann

[mwhansen]

Merged: sage-4.4.4.alpha0

[mwhansen]

Reviewer: Joni Syri

[mwhansen]

Author: Nathann Cohen