# 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_sy.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": "",
"docs_url": null,
"requires_python": ">=3.8",
"maintainer_email": "",
"keywords": "optimization,partition",
"author": "Erel Segal-Halevi",
"author_email": "erelsgl@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/fe/d8/35cfdec67854f45e4260dce17c466ccf53eceea31194b857cdd811aba5f4/prtpy-0.8.2.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\u00c3\u00b8ren Fuglede J\u00c3\u00b8rgensen - the code for [complete_greedy](prtpy/partitioning/complete_greedy.py) and [complete_karmarkar_karp](prtpy/partitioning/complete_karmarkar_karp_sy.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.2",
"split_keywords": [
"optimization",
"partition"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "735ab4dfda83b912fca4aacbc70cd9678aa40a1cf147b6808d940ec32d48c9bf",
"md5": "118830838fc153972dfc88d6b5247a93",
"sha256": "56982bb9aaaf855b29d33ebe313a2515c356a7d452099754c101e2adcc62d29c"
},
"downloads": -1,
"filename": "prtpy-0.8.2-py3-none-any.whl",
"has_sig": false,
"md5_digest": "118830838fc153972dfc88d6b5247a93",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.8",
"size": 54506,
"upload_time": "2023-01-12T10:41:51",
"upload_time_iso_8601": "2023-01-12T10:41:51.606885Z",
"url": "https://files.pythonhosted.org/packages/73/5a/b4dfda83b912fca4aacbc70cd9678aa40a1cf147b6808d940ec32d48c9bf/prtpy-0.8.2-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "fed835cfdec67854f45e4260dce17c466ccf53eceea31194b857cdd811aba5f4",
"md5": "2ea1b43cce684a6c59ac0098870c009d",
"sha256": "2d7b4870440041c75161329fcf605f65879e4591a7bbdec324f9c56cba214e60"
},
"downloads": -1,
"filename": "prtpy-0.8.2.tar.gz",
"has_sig": false,
"md5_digest": "2ea1b43cce684a6c59ac0098870c009d",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.8",
"size": 58054,
"upload_time": "2023-01-12T10:41:52",
"upload_time_iso_8601": "2023-01-12T10:41:52.991474Z",
"url": "https://files.pythonhosted.org/packages/fe/d8/35cfdec67854f45e4260dce17c466ccf53eceea31194b857cdd811aba5f4/prtpy-0.8.2.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-01-12 10:41:52",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "erelsgl",
"github_project": "prtpy",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"requirements": [
{
"name": "numpy",
"specs": [
[
">=",
"1.21.3"
]
]
},
{
"name": "scipy",
"specs": [
[
">=",
"1.6.1"
]
]
},
{
"name": "mip",
"specs": [
[
">=",
"1.13.0"
]
]
}
],
"lcname": "prtpy"
}
JSON
