Number partitioning in Python
Project description
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
pip install prtpy
If you want 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:
bins
- a Bins structure. It is already initialized with the right number of empty bins (bins.num
). It contains a function for adding items to bins.items
- a list of item-names.valueof
- a function that accepts an item-name and returns its value.- 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:
bins
- a Bins structure. It is initialized with no bins at all. It contains a function for adding new empty bins.binsize
- the capacity of a bin (maximum sum in bin-packing; minimum sum in bin-covering).items
- a list of item-names.valueof
- a function that accepts an item and returns its value.- Any other parameters that are required by your algorithm.
For an example, see the implementation of existing algorithms, e.g. first_fit.
Related libraries
- numberpartitioning by Søren Fuglede Jørgensen - the code for complete_greedy is adapted from there.
- binpacking by Ben Maier.
Limitations
The package is tested only on Python 3.8 and 3.9. Earlier versions, as well as 3.10, are not supported.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.