#24975 closed enhancement (fixed)

Improve method binpacking

Reported by: dcoudert Owned by:
Priority: major Milestone: sage-8.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 and verbose
  • 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 dcoudert

  • Branch set to u/dcoudert/24975_binpacking
  • Cc jmantysalo mkoeppe added
  • Commit set to 22f25bcf54ebe657ad9bb42971128c06e7be9962
  • Status changed from new to needs_review

New commits:

22f25bctrac #24975: improve method binpacking

comment:2 Changed 15 months ago by git

  • Commit changed from 22f25bcf54ebe657ad9bb42971128c06e7be9962 to 6c55579421a8daa3d954fa54e8204d7e7ad50748

Branch pushed to git repo; I updated commit sha1. New commits:

6c55579trac #24975: fix identation in documentation

comment:3 Changed 13 months ago by git

  • Commit changed from 6c55579421a8daa3d954fa54e8204d7e7ad50748 to 53b6a60c06197cf2037a635afb0ef00d998e5b10

Branch pushed to git repo; I updated commit sha1. New commits:

53b6a60trac #24975: Merged with 8.3.beta0

comment:4 Changed 13 months ago by dcoudert

  • Milestone changed from sage-8.2 to sage-8.3

comment:5 Changed 13 months ago by jmantysalo

Seems to be OK, but I have no additional solver to test against.

comment:6 Changed 13 months ago by git

  • Commit changed from 53b6a60c06197cf2037a635afb0ef00d998e5b10 to 80ebbb522ef82dce2caea440e891dfa1488465d0

Branch pushed to git repo; I updated commit sha1. New commits:

80ebbb5trac #24975: correct parameters in internal calls

comment:7 follow-up: Changed 13 months ago by dcoudert

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 jmantysalo

  • Reviewers set to Jori Mäntysalo

Replying to dcoudert:

For the solvers, you have at least GLPK and PPL. I also tried with Cplex.

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#the-docstring-of-a-function-content

After "Two version of this problem are solved by this algorithm" there is unnecessary indentation for the two-element list.

comment:9 Changed 13 months ago by git

  • Commit changed from 80ebbb522ef82dce2caea440e891dfa1488465d0 to 1aaf8f0e1674e6e45d078fc81e8e75ba2a128796

Branch pushed to git repo; I updated commit sha1. New commits:

1aaf8f0trac #24975: polishing

comment:10 Changed 13 months ago by dcoudert

you are right.

comment:11 Changed 13 months ago by jmantysalo

  • Status changed from needs_review to positive_review

comment:12 Changed 13 months ago by fbissey

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/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/sage_setup/docbuild/__init__.py", line 1713, in main
    builder()
  File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/sage_setup/docbuild/__init__.py", line 340, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_7/sage_setup/docbuild/__init__.py", line 535, in _wrapper
    build_many(build_ref_doc, L)
  File "/dev/shm/portage/sci-mathematics/sage-9999/work/sage-9999/src-python2_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/sci-mathematics/sage-9999/work/sage-9999/src-python2_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 fbissey

Reverting the indent of the last commit fixes it for me.

comment:14 Changed 13 months ago by jmantysalo

  • 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 git

  • Commit changed from 1aaf8f0e1674e6e45d078fc81e8e75ba2a128796 to 1d82cf2f4ec0ee890255264a21eb3614f3aacdad

Branch pushed to git repo; I updated commit sha1. New commits:

0c36ea1trac #24975: Merged with 8.3.beta1
1d82cf2trac #24975: identation

comment:16 Changed 13 months ago by dcoudert

  • Status changed from needs_work to needs_review

Should be fixed now.

comment:17 Changed 13 months ago by jmantysalo

  • Status changed from needs_review to positive_review

comment:18 Changed 13 months ago by vbraun

  • Branch changed from u/dcoudert/24975_binpacking to 1d82cf2f4ec0ee890255264a21eb3614f3aacdad
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.