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 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 9 years ago.
trac_6763.patch (4.4 KB) - added by ncohen 9 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 9 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 9 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 9 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 9 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 9 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 9 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 9 years ago by robertwb

Sort the result before printing.

comment:8 Changed 9 years ago by ncohen

Done

Changed 9 years ago by ncohen

comment:9 Changed 9 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 9 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 9 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.

comment:12 Changed 9 years ago by ncohen

  • Status changed from needs_work to needs_review

Fixed.

Changed 9 years ago by ncohen

comment:13 Changed 9 years ago by jsyri

  • Status changed from needs_review to positive_review

Everything seems to be in order. Positive review.

comment:14 Changed 9 years ago by ncohen

Thank youuuuuuuuu :-)

Nathann

comment:15 Changed 9 years ago by mhansen

  • Authors set to Nathann Cohen
  • 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
Note: See TracTickets for help on using tickets.