Opened 15 months ago
Closed 13 months ago
#24975 closed enhancement (fixed)
Improve method binpacking
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  numerical  Keywords:  
Cc:  jmantysalo, mkoeppe  Merged in:  
Authors:  David Coudert  Reviewers:  Jori Mäntysalo 
Report Upstream:  N/A  Work issues:  
Branch:  1d82cf2 (Commits)  Commit:  1d82cf2f4ec0ee890255264a21eb3614f3aacdad 
Dependencies:  Stopgaps: 
Description
This is part of #20416. Here, we
 polish method binpacking
 add arguments
solver
andverbose
 enable to give a dictionary of items as input, in which case each bin contains the list of items in it. When the input is a list of weights, each bin contains the list of the weight of the items in it.
Change History (18)
comment:1 Changed 15 months ago by
 Branch set to u/dcoudert/24975_binpacking
 Cc jmantysalo mkoeppe added
 Commit set to 22f25bcf54ebe657ad9bb42971128c06e7be9962
 Status changed from new to needs_review
comment:2 Changed 15 months ago by
 Commit changed from 22f25bcf54ebe657ad9bb42971128c06e7be9962 to 6c55579421a8daa3d954fa54e8204d7e7ad50748
Branch pushed to git repo; I updated commit sha1. New commits:
6c55579  trac #24975: fix identation in documentation

comment:3 Changed 13 months ago by
 Commit changed from 6c55579421a8daa3d954fa54e8204d7e7ad50748 to 53b6a60c06197cf2037a635afb0ef00d998e5b10
Branch pushed to git repo; I updated commit sha1. New commits:
53b6a60  trac #24975: Merged with 8.3.beta0

comment:4 Changed 13 months ago by
 Milestone changed from sage8.2 to sage8.3
comment:5 Changed 13 months ago by
Seems to be OK, but I have no additional solver to test against.
comment:6 Changed 13 months ago by
 Commit changed from 53b6a60c06197cf2037a635afb0ef00d998e5b10 to 80ebbb522ef82dce2caea440e891dfa1488465d0
Branch pushed to git repo; I updated commit sha1. New commits:
80ebbb5  trac #24975: correct parameters in internal calls

comment:7 followup: ↓ 8 Changed 13 months ago by
I forgot to add the parameters in internal calls.
For the solvers, you have at least GLPK
and PPL
. I also tried with Cplex
.
sage: from sage.numerical.optimize import binpacking sage: values = [1/5, 1/3, 2/3, 3/4, 5/7] sage: binpacking(values, solver='GLPK') [[1/5, 3/4], [5/7], [1/3, 2/3]] sage: binpacking(values, solver='PPL') [[5/7], [1/5, 3/4], [1/3, 2/3]] sage: binpacking(values, solver='Cplex') [[2/3, 1/3], [1/5, 5/7], [3/4]]
comment:8 in reply to: ↑ 7 Changed 13 months ago by
 Reviewers set to Jori Mäntysalo
Replying to dcoudert:
For the solvers, you have at least
GLPK
andPPL
. I also tried withCplex
.
OK then. Tested, seems to be OK.
Feel free to mark this as positive review. Or if you want to make bikeshedding:
"Solves the bin packing problem." > "Solve the bin packing problem.", see https://doc.sagemath.org/html/en/developer/coding_basics.html#thedocstringofafunctioncontent
After "Two version of this problem are solved by this algorithm" there is unnecessary indentation for the twoelement list.
comment:9 Changed 13 months ago by
 Commit changed from 80ebbb522ef82dce2caea440e891dfa1488465d0 to 1aaf8f0e1674e6e45d078fc81e8e75ba2a128796
Branch pushed to git repo; I updated commit sha1. New commits:
1aaf8f0  trac #24975: polishing

comment:10 Changed 13 months ago by
you are right.
comment:11 Changed 13 months ago by
 Status changed from needs_review to positive_review
comment:12 Changed 13 months ago by
I don't know if it is the last commit or what but I am failing at building the doc on this file
Error building the documentation. Traceback (most recent call last): File "sage_setup/docbuild/__main__.py", line 2, in <module> main() File "/dev/shm/portage/scimathematics/sage9999/work/sage9999/srcpython2_7/sage_setup/docbuild/__init__.py", line 1713, in main builder() File "/dev/shm/portage/scimathematics/sage9999/work/sage9999/srcpython2_7/sage_setup/docbuild/__init__.py", line 340, in _wrapper getattr(get_builder(document), 'inventory')(*args, **kwds) File "/dev/shm/portage/scimathematics/sage9999/work/sage9999/srcpython2_7/sage_setup/docbuild/__init__.py", line 535, in _wrapper build_many(build_ref_doc, L) File "/dev/shm/portage/scimathematics/sage9999/work/sage9999/srcpython2_7/sage_setup/docbuild/__init__.py", line 276, in build_many ret = x.get(99999) File "/usr/lib64/python2.7/multiprocessing/pool.py", line 572, in get raise self._value OSError: [numerical] /dev/shm/portage/scimathematics/sage9999/work/sage9999/srcpython2_7/build/lib/sage/numerical/optimize.py:docstring of sage.numerical.optimize.binpacking:15: WARNING: Unexpected indentation.
Not sure if Volker will see the same thing.
comment:13 Changed 13 months ago by
Reverting the indent of the last commit fixes it for me.
comment:14 Changed 13 months ago by
 Status changed from positive_review to needs_work
True, it needs a linefeed after the line "Two version of this problem are solved by this algorithm".
comment:15 Changed 13 months ago by
 Commit changed from 1aaf8f0e1674e6e45d078fc81e8e75ba2a128796 to 1d82cf2f4ec0ee890255264a21eb3614f3aacdad
comment:16 Changed 13 months ago by
 Status changed from needs_work to needs_review
Should be fixed now.
comment:17 Changed 13 months ago by
 Status changed from needs_review to positive_review
comment:18 Changed 13 months ago by
 Branch changed from u/dcoudert/24975_binpacking to 1d82cf2f4ec0ee890255264a21eb3614f3aacdad
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #24975: improve method binpacking