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 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:
- Number-partitioning algorithms;
- Bin-packing algorithms;
- Bin-covering algorithms;
- Input formats;
- Optimization objectives;
- Output formats.
Adding new algorithms
To add a new algorithm for number partitioning, write a function that accepts the following parameters:
binner- an item of classBinnerstructure (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 functionbinner.valueof).- Any other parameters that are required by your algorithm.
For an example, see the implementation of existing algorithms, e.g. greedy.
To add a new algorithm for bin packing or bin covering, write a function that accepts the following parameters:
binner- an item of classBinnerstructure (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 functionbinner.valueof).- Any other parameters that are required by your algorithm.
For an example, see the implementation of existing algorithms, e.g. first_fit.
The Binner 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 givenbinsarray 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 newbinsarray with some additional empty bins at the end.bins = binner.remove_bins(bins, numbins)--- creates a newbinsarray with some bins removed at the end.binner.valueof(item)--- returns the value (size) of the given item.
Related libraries
- numberpartitioning by Sֳ¸ren Fuglede Jֳ¸rgensen - the code for complete_greedy and complete_karmarkar_karp was originally adapted from there.
- binpacking by Ben Maier.
Limitations
The package is tested on Python versions 3.8, 3.9 and 3.10. Other versions are not supported.
Metadata
Release files for prtpy 0.8.3
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | Actions |
|---|---|---|---|---|
| prtpy-0.8.3.tar.gz | 61.3 kB | Without provenance | Details for prtpy-0.8.3.tar.gz |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Actions Reset |
|---|---|---|---|---|
| prtpy-0.8.3-py3-none-any.whl | Python 3 | none | any | Details for prtpy-0.8.3-py3-none-any.whl |
Total release size: 125.4 kB
Release files / prtpy-0.8.3.tar.gz
| Download URL | prtpy-0.8.3.tar.gz |
|---|---|
| Size | 61.3 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
a6cec04a8fd7c1add066aef6292a992048527ec8c0e6e0780e46acd5d02ee36a
|
|
BLAKE2b-256 checksum How to use checksums |
3d23907d3b406c8a9b506d11008163c0de10d7c643f91311fc3cd8d71228ab2a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.2 CPython/3.10.11
|
Release files / prtpy-0.8.3-py3-none-any.whl
| Download URL | prtpy-0.8.3-py3-none-any.whl |
|---|---|
| Size | 64.1 kB |
| Tags | Python 3 |
|
SHA-256 checksum How to use checksums |
cb3159172589104a513bac64218ddfe773ecd58f4a25dedcc1f099cf8096700f
|
|
BLAKE2b-256 checksum How to use checksums |
c38961611b2146446a83cfe9103f91c4b6e30026ab7070dd6807dba5b65cce18
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/4.0.2 CPython/3.10.11
|
Security for prtpy 0.8.3
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
No provenance found
None of the files in this release were uploaded with provenance metadata.
A note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.