# prtpy
[](https://badge.fury.io/py/prtpy)
Python code for multiway number partitioning and bin packing algorithms.
Supports several exact and approximate algorithms, with several input formats, optimization objectives and output formats.
## Installation
Basic installation:
pip install prtpy
To run simulation experiments:
pip install prtpy[simulations]
To speed up the ILP code, you can install the GUROBI solver.
See the [documentation of Python-MIP](https://www.python-mip.com/) for more information.
## Usage
The function `prtpy.partition` can be used to activate all number-partitioning algorithms. For example, to partition the values [1,2,3,4,5] into two bins using the greedy approximation algorithm, do:
import prtpy
prtpy.partition(algorithm=prtpy.partitioning.greedy, numbins=2, items=[1,2,3,4,5])
To use the exact algorithm based on ILP, and maximize the smallest sum:
prtpy.partition(algorithm=prtpy.partitioning.ilp, numbins=2, items=[1,2,3,4,5], objective=prtpy.obj.MaximizeSmallestSum)
Similarly, the function `prtpy.packing` can be used to activate all bin-packing algorithms.
For more features and examples, see:
1. [Number-partitioning algorithms](examples/partitioning_algorithms.md);
1. [Bin-packing algorithms](examples/packing_algorithms.md);
1. [Bin-covering algorithms](examples/covering_algorithms.md);
1. [Input formats](examples/input_formats.md);
1. [Optimization objectives](examples/objectives.md);
1. [Output formats](examples/output_formats.md).
## Adding new algorithms
To add a new algorithm for number partitioning, write a function that accepts the following parameters:
* `binner` - an item of class `Binner` structure (see below).
* `numbins` - an integer - how many bins to put the items into.
* `items` - a list of item-names (the item values are given by the function `binner.valueof`).
* Any other parameters that are required by your algorithm.
For an example, see the implementation of existing algorithms, e.g. [greedy](prtpy/partitioning/greedy.py).
To add a new algorithm for bin packing or bin covering, write a function that accepts the following parameters:
* `binner` - an item of class `Binner` structure (see below).
* `binsize` - the capacity of a bin (maximum sum in bin-packing; minimum sum in bin-covering).
* `items` - a list of item-names (the item values are given by the function `binner.valueof`).
* Any other parameters that are required by your algorithm.
For an example, see the implementation of existing algorithms, e.g. [first_fit](prtpy/packing/first_fit.py).
The [Binner](prtpy/binner.py) class contains methods for handling bins in a generic way --- handling both item-names and item-values with a single interface. The main supported methods are:
* `bins = binner.new_bins(numbins)` --- constructs a new array of empty bins.
* `binner.add_item_to_bin(bins, item, index)` --- updates the given `bins` array by adding the given item to the bin with the given index.
* `binner.sums(bins)` --- extracts, from the bins array, only the array of sums.
* `bins = binner.add_empty_bins(bins, numbins)` --- creates a new `bins` array with some additional empty bins at the end.
* `bins = binner.remove_bins(bins, numbins)` --- creates a new `bins` array with some bins removed at the end.
* `binner.valueof(item)` --- returns the value (size) of the given item.
## Related libraries
* [numberpartitioning](https://github.com/fuglede/numberpartitioning) by Sֳ¸ren Fuglede Jֳ¸rgensen - the code for [complete_greedy](prtpy/partitioning/complete_greedy.py) and [complete_karmarkar_karp](prtpy/partitioning/complete_karmarkar_karp.py) was originally adapted from there.
* [binpacking](https://github.com/benmaier/binpacking) by Ben Maier.
## Limitations
The package is tested on Python versions 3.8, 3.9 and 3.10. Other versions are not supported.
Raw data
{
"_id": null,
"home_page": "https://github.com/erelsgl/prtpy",
"name": "prtpy",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.8",
"maintainer_email": null,
"keywords": "optimization, partition",
"author": "Erel Segal-Halevi",
"author_email": "erelsgl@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/3d/23/907d3b406c8a9b506d11008163c0de10d7c643f91311fc3cd8d71228ab2a/prtpy-0.8.3.tar.gz",
"platform": null,
"description": "# prtpy \r\n\r\n\r\n[](https://badge.fury.io/py/prtpy)\r\n\r\nPython code for multiway number partitioning and bin packing algorithms.\r\n\r\nSupports several exact and approximate algorithms, with several input formats, optimization objectives and output formats.\r\n\r\n## Installation\r\n\r\nBasic installation:\r\n\r\n pip install prtpy\r\n\r\nTo run simulation experiments:\r\n\r\n pip install prtpy[simulations]\r\n\r\nTo speed up the ILP code, you can install the GUROBI solver.\r\nSee the [documentation of Python-MIP](https://www.python-mip.com/) for more information.\r\n\r\n## Usage\r\n\r\nThe function `prtpy.partition` can be used to activate all number-partitioning algorithms. For example, to partition the values [1,2,3,4,5] into two bins using the greedy approximation algorithm, do:\r\n\r\n import prtpy\r\n prtpy.partition(algorithm=prtpy.partitioning.greedy, numbins=2, items=[1,2,3,4,5])\r\n\r\nTo use the exact algorithm based on ILP, and maximize the smallest sum:\r\n\r\n prtpy.partition(algorithm=prtpy.partitioning.ilp, numbins=2, items=[1,2,3,4,5], objective=prtpy.obj.MaximizeSmallestSum)\r\n\r\nSimilarly, the function `prtpy.packing` can be used to activate all bin-packing algorithms.\r\n\r\nFor more features and examples, see:\r\n\r\n1. [Number-partitioning algorithms](examples/partitioning_algorithms.md);\r\n1. [Bin-packing algorithms](examples/packing_algorithms.md);\r\n1. [Bin-covering algorithms](examples/covering_algorithms.md);\r\n1. [Input formats](examples/input_formats.md);\r\n1. [Optimization objectives](examples/objectives.md);\r\n1. [Output formats](examples/output_formats.md).\r\n\r\n## Adding new algorithms\r\n\r\nTo add a new algorithm for number partitioning, write a function that accepts the following parameters:\r\n\r\n* `binner` - an item of class `Binner` structure (see below).\r\n* `numbins` - an integer - how many bins to put the items into.\r\n* `items` - a list of item-names (the item values are given by the function `binner.valueof`).\r\n* Any other parameters that are required by your algorithm.\r\n\r\nFor an example, see the implementation of existing algorithms, e.g. [greedy](prtpy/partitioning/greedy.py).\r\n\r\nTo add a new algorithm for bin packing or bin covering, write a function that accepts the following parameters:\r\n\r\n* `binner` - an item of class `Binner` structure (see below).\r\n* `binsize` - the capacity of a bin (maximum sum in bin-packing; minimum sum in bin-covering).\r\n* `items` - a list of item-names (the item values are given by the function `binner.valueof`).\r\n* Any other parameters that are required by your algorithm.\r\n\r\nFor an example, see the implementation of existing algorithms, e.g. [first_fit](prtpy/packing/first_fit.py).\r\n\r\nThe [Binner](prtpy/binner.py) class contains methods for handling bins in a generic way --- handling both item-names and item-values with a single interface. The main supported methods are:\r\n\r\n* `bins = binner.new_bins(numbins)` --- constructs a new array of empty bins.\r\n* `binner.add_item_to_bin(bins, item, index)` --- updates the given `bins` array by adding the given item to the bin with the given index. \r\n* `binner.sums(bins)` --- extracts, from the bins array, only the array of sums.\r\n* `bins = binner.add_empty_bins(bins, numbins)` --- creates a new `bins` array with some additional empty bins at the end.\r\n* `bins = binner.remove_bins(bins, numbins)` --- creates a new `bins` array with some bins removed at the end.\r\n* `binner.valueof(item)` --- returns the value (size) of the given item.\r\n\r\n\r\n## Related libraries\r\n\r\n* [numberpartitioning](https://github.com/fuglede/numberpartitioning) by S\u05b3\u00b8ren Fuglede J\u05b3\u00b8rgensen - the code for [complete_greedy](prtpy/partitioning/complete_greedy.py) and [complete_karmarkar_karp](prtpy/partitioning/complete_karmarkar_karp.py) was originally adapted from there.\r\n* [binpacking](https://github.com/benmaier/binpacking) by Ben Maier.\r\n\r\n## Limitations\r\n\r\nThe package is tested on Python versions 3.8, 3.9 and 3.10. Other versions are not supported.\r\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Number partitioning in Python",
"version": "0.8.3",
"project_urls": {
"Bug Reports": "https://github.com/erelsgl/prtpy/issues",
"Homepage": "https://github.com/erelsgl/prtpy",
"Source Code": "https://github.com/erelsgl/prtpy"
},
"split_keywords": [
"optimization",
" partition"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "c38961611b2146446a83cfe9103f91c4b6e30026ab7070dd6807dba5b65cce18",
"md5": "c45917ab1bf82ae522a890d62d90ef54",
"sha256": "cb3159172589104a513bac64218ddfe773ecd58f4a25dedcc1f099cf8096700f"
},
"downloads": -1,
"filename": "prtpy-0.8.3-py3-none-any.whl",
"has_sig": false,
"md5_digest": "c45917ab1bf82ae522a890d62d90ef54",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.8",
"size": 64068,
"upload_time": "2024-05-15T10:57:49",
"upload_time_iso_8601": "2024-05-15T10:57:49.657558Z",
"url": "https://files.pythonhosted.org/packages/c3/89/61611b2146446a83cfe9103f91c4b6e30026ab7070dd6807dba5b65cce18/prtpy-0.8.3-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "3d23907d3b406c8a9b506d11008163c0de10d7c643f91311fc3cd8d71228ab2a",
"md5": "d09a9e9bee8f79a3cf62b463cab53277",
"sha256": "a6cec04a8fd7c1add066aef6292a992048527ec8c0e6e0780e46acd5d02ee36a"
},
"downloads": -1,
"filename": "prtpy-0.8.3.tar.gz",
"has_sig": false,
"md5_digest": "d09a9e9bee8f79a3cf62b463cab53277",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.8",
"size": 61319,
"upload_time": "2024-05-15T10:57:51",
"upload_time_iso_8601": "2024-05-15T10:57:51.365402Z",
"url": "https://files.pythonhosted.org/packages/3d/23/907d3b406c8a9b506d11008163c0de10d7c643f91311fc3cd8d71228ab2a/prtpy-0.8.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-05-15 10:57:51",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "erelsgl",
"github_project": "prtpy",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"requirements": [],
"lcname": "prtpy"
}
JSON
