Skip to main content

pareto_dp

Simple multi-objective optimization using dynamic programming to approximate the Pareto frontier.

Written in Rust, published as a Python PyPI package with PyO3 and maturin.

Problem specification

This library solves a multi-objective multiple-choice combinatorial optimization problem with additive separable objectives, designed for scenarios with precomputed data for independent decision points.

Here's an introductory blogpost that provides more motivation for the problem.

Core user-facing properties

  • Independent groups: The problem consists of n independent groups (e.g., decision stages, components) with no interdependencies.
  • Additive objective aggregation: The total objective vector for a configuration is the sum of per-group contributions. For a configuration x (one scenario chosen per group), the v-dimensional objective is: $$ F(x) = \sum_{i=1}^n a_{i,x_i} \in \mathbb{R}^v $$ where a_{i,j} is the precomputed objective vector for group i, scenario j.
  • Precomputed lookup table: All per-group, per-scenario objective values are precomputed (table-lookup/black-box). The library takes this 3D lookup table as direct input.

Formal structure

  • n independent groups
  • Each group i has m_i scenarios
  • Multiple-choice constraint: A configuration selects exactly one scenario per group
  • v objectives, precomputed as a_{i,j} ∈ ℝᵛ
  • Goal: Compute the Pareto-optimal frontier in the v-dimensional objective space

Scale challenge

The configuration space size is |X| = ∏_{i=1}^n m_i, which grows exponentially with n. Exhaustive search is infeasible for large n, so the library uses dynamic programming with epsilon-dominance pruning to efficiently approximate the Pareto front.

Installation

pip install pareto-dp

Usage

from pareto_dp import find_pareto_front

# Define your multi-objective optimization problem
# Each stand has multiple scenarios, each scenario has objective values
data = [
    [[3.0, 2.1], [2.0, 1.0]],  # Stand 0: 2 scenarios, 2 objectives
    [[1.0, 1.0], [2.0, 0.5]],  # Stand 1: 2 scenarios, 2 objectives
]

# Find Pareto-optimal solutions with epsilon precision
solutions = find_pareto_front(data, epsilon=0.01)

for sol in solutions:
    print(f"Design: {sol.design_vector}, Objectives: {sol.target_vector}")

API

find_pareto_front(data, epsilon)

Finds all Pareto-optimal solutions for a multi-objective optimization problem.

Parameters:

  • data (List[List[List[float]]]): A 3D list where:
    • First dimension: decision points
    • Second dimension: options for each decision point
    • Third dimension: objective variable values (e.g., [cost, time, quality])
  • epsilon (float): Precision parameter for epsilon-dominance pruning

(Note: the context in which this problem originated is forestry land-use, so decision points are called stands in the code, and options are called scenarios).

Returns:

  • List of ParetoFrontSolution objects, each with:
    • design_vector (List[int]): Which scenario to pick for each stand
    • target_vector (List[float]): The summed objective values for that design

Raises:

  • ValueError: If data is empty, has only one stand, or has inconsistent dimensions

Algorithm

The algorithm uses dynamic programming to efficiently find the Pareto front:

  1. Data Validation: Validates input structure and dimensions
  2. Shift to Positive Space: Shifts all objective values to positive space for numerical stability
  3. DP Tree Construction: Builds partial Pareto fronts iteratively for each stand
  4. Epsilon-Dominance Pruning: Uses logarithmic binning to prune dominated solutions
  5. Solution Reconstruction: Traces back through parent pointers to reconstruct full solutions

Requirements

  • Python >= 3.9
  • Compatible with CPython and PyPy

License

MIT License - see LICENSE file for details.

Repository

https://github.com/Txart/pareto_dp

Metadata

Release files for pareto_dp 0.1.8

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for pareto_dp 0.1.8
File Size Uploaded Provenance Actions
pareto_dp-0.1.8.tar.gz 17.7 kB Without provenance Details for pareto_dp-0.1.8.tar.gz

Built distributions (wheels)

Table of built distributions (wheels) for pareto_dp 0.1.8
File Actions
pareto_dp-0.1.8-cp39-abi3-win_arm64.whl CPython 3.9 abi3 Windows ARM64 Details for pareto_dp-0.1.8-cp39-abi3-win_arm64.whl
pareto_dp-0.1.8-cp39-abi3-win_amd64.whl CPython 3.9 abi3 Windows x86-64 Details for pareto_dp-0.1.8-cp39-abi3-win_amd64.whl
pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_x86_64.whl CPython 3.9 abi3 Linux musl 1.2+ x86-64 Details for pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_x86_64.whl
pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_i686.whl CPython 3.9 abi3 Linux musl 1.2+ x86-32 Details for pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_i686.whl
pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_armv7l.whl CPython 3.9 abi3 Linux musl 1.2+ ARMv7l Details for pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_armv7l.whl
pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_aarch64.whl CPython 3.9 abi3 Linux musl 1.2+ ARM64 Details for pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_aarch64.whl
pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl CPython 3.9 abi3 Linux glibc 2.17+ x86-64 Details for pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl CPython 3.9 abi3 Linux glibc 2.17+ IBM System/390x Details for pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl
pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl CPython 3.9 abi3 Linux glibc 2.17+ PowerPC 64-le Details for pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl
pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl CPython 3.9 abi3 Linux glibc 2.17+ ARMv7l Details for pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl
pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl CPython 3.9 abi3 Linux glibc 2.17+ ARM64 Details for pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
pareto_dp-0.1.8-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl CPython 3.9 abi3 Linux glibc 2.5+ x86-32 Details for pareto_dp-0.1.8-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl
pareto_dp-0.1.8-cp39-abi3-macosx_11_0_arm64.whl CPython 3.9 abi3 macOS 11.0+ ARM64 Details for pareto_dp-0.1.8-cp39-abi3-macosx_11_0_arm64.whl
pareto_dp-0.1.8-cp39-abi3-macosx_10_12_x86_64.whl CPython 3.9 abi3 macOS 10.12+ x86-64 Details for pareto_dp-0.1.8-cp39-abi3-macosx_10_12_x86_64.whl

Total release size: 5.1 MB

Release files / pareto_dp-0.1.8.tar.gz

Download URL pareto_dp-0.1.8.tar.gz
Size 17.7 kB
Tags Source
SHA-256 checksum
How to use checksums
29d5a365427244a87d016121bcd8d4c5b6b66fee81894db5d5b819514c8078e7
BLAKE2b-256 checksum
How to use checksums
7e6c29680a03198675d9a690fc4e89968cd201b08d15aa361e88515ec07f05a4
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-win_arm64.whl

Download URL pareto_dp-0.1.8-cp39-abi3-win_arm64.whl
Size 163.6 kB
Tags CPython 3.9 Windows ARM64 abi3
SHA-256 checksum
How to use checksums
031eb904ef5ae52b5fba22d30258dc0851a6ad40bfe318371db044a5e24868aa
BLAKE2b-256 checksum
How to use checksums
b1db336eea6d129e6273a9c5a619fcfc4b42930854c0da4a40199b1d21005647
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-win_amd64.whl

Download URL pareto_dp-0.1.8-cp39-abi3-win_amd64.whl
Size 168.9 kB
Tags CPython 3.9 Windows x86-64 abi3
SHA-256 checksum
How to use checksums
ded961da6f303e0d997b84292032f2c39cb6e121e5ea23d039f7f5b6e9ae27a5
BLAKE2b-256 checksum
How to use checksums
a09f0f1fc24724cd715078219aa482a0feef71213106cc2ac96867597a12d3b3
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_x86_64.whl

Download URL pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_x86_64.whl
Size 519.7 kB
Tags CPython 3.9 Linux musl 1.2+ x86-64 abi3
SHA-256 checksum
How to use checksums
2aacd408fbdce53fe83115b6fc3635fd20b7c424e241218d668920ebfbb2fd93
BLAKE2b-256 checksum
How to use checksums
36514176fe0e5625c44e263c020aa2e08ac35f69329eab6a27b33903d7b7eb7b
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_i686.whl

Download URL pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_i686.whl
Size 547.5 kB
Tags CPython 3.9 Linux musl 1.2+ x86-32 abi3
SHA-256 checksum
How to use checksums
61af1b7d8060a0154e54301119db97d732d50325532af0ad03ef359fb03592c1
BLAKE2b-256 checksum
How to use checksums
eab701963bc5feec478710c728a206c0912c2ecf806cc8f95333412449ba25cd
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_armv7l.whl

Download URL pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_armv7l.whl
Size 586.2 kB
Tags CPython 3.9 Linux musl 1.2+ ARMv7l abi3
SHA-256 checksum
How to use checksums
1f613f5a1767797dcc9291c6163fb98659e129f92b4d81d7339c5b0947193450
BLAKE2b-256 checksum
How to use checksums
8973a66ff9a3009ac4d5e6ffc3a56036a8e396a49c70a32586554527d5ebd020
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_aarch64.whl

Download URL pareto_dp-0.1.8-cp39-abi3-musllinux_1_2_aarch64.whl
Size 486.7 kB
Tags CPython 3.9 Linux musl 1.2+ ARM64 abi3
SHA-256 checksum
How to use checksums
a5b574072cb1e3a889b6c567241eda75b08b095e67c7a348e088077069d2ea61
BLAKE2b-256 checksum
How to use checksums
92feac80c42387351bc352f6ce378fd4cf21860aa860a3da33ee8ebc999f2cce
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl

Download URL pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Size 317.9 kB
Tags CPython 3.9 Linux glibc 2.17+ x86-64 abi3
SHA-256 checksum
How to use checksums
29fc9a0774511b556c03c9cdd528c956213b224a73040be95cb9a03b589d8bd3
BLAKE2b-256 checksum
How to use checksums
cb546f2a1cc647f3a790e1949754a5a7a1522a2ef98a0d1d2f91cdf36310fb73
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl

Download URL pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl
Size 341.1 kB
Tags CPython 3.9 Linux glibc 2.17+ IBM System/390x abi3
SHA-256 checksum
How to use checksums
7b296b80d79f90f8c6172606433cd365735b65295555564267e40a4a6d238dd5
BLAKE2b-256 checksum
How to use checksums
50082a50d8c45bb9461f3c322f9657e25185c9b6d628db39751f3ebb1e1602de
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl

Download URL pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl
Size 428.2 kB
Tags CPython 3.9 Linux glibc 2.17+ PowerPC 64-le abi3
SHA-256 checksum
How to use checksums
e8d0243b1e5c138c8f46e266459fe602fd98221cfcfae10a2e66c8bc33658f2f
BLAKE2b-256 checksum
How to use checksums
b65fd12d367ee0150b9aee16294718549b2e3cedb1e79acf0ddc1ec9f7e3703e
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl

Download URL pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl
Size 311.4 kB
Tags CPython 3.9 Linux glibc 2.17+ ARMv7l abi3
SHA-256 checksum
How to use checksums
50e9a52c2d025da89bb1bbf3c29a3b14ac299aa971e74746ea981a13bd5b127e
BLAKE2b-256 checksum
How to use checksums
10645b19b1371b43121a11c27653aac036605ac9c02023d7f7fe193593f9dd3a
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl

Download URL pareto_dp-0.1.8-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Size 309.8 kB
Tags CPython 3.9 Linux glibc 2.17+ ARM64 abi3
SHA-256 checksum
How to use checksums
54f39305f485233b5a5027feda57beadbf1de8a4a35f268e5f7b90faf954baa4
BLAKE2b-256 checksum
How to use checksums
4140a94da2ec870332296f3ae3a29f3a306c213e08a58ff9b4a283e61f3b6d89
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl

Download URL pareto_dp-0.1.8-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.whl
Size 330.0 kB
Tags CPython 3.9 Linux glibc 2.5+ x86-32 abi3
SHA-256 checksum
How to use checksums
3aca3deeb5f71b8f80bf0c02fb006bd5f38405ce8722e7176ce61a23240fb658
BLAKE2b-256 checksum
How to use checksums
74a3adb8cb1dbccf93045997c533bf820a5fa14804466fcca1444b3cc805934c
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-macosx_11_0_arm64.whl

Download URL pareto_dp-0.1.8-cp39-abi3-macosx_11_0_arm64.whl
Size 272.8 kB
Tags CPython 3.9 abi3 macOS 11.0+ ARM64
SHA-256 checksum
How to use checksums
eb41d9e34498ad5ba89197e26c8ebdc0077e13a7ea7871b3b5fe257ae7aaecc5
BLAKE2b-256 checksum
How to use checksums
a628e643e8b024ad2dec744aa3c9276b30f6e14b725d48e33297bac31eeb9c4c
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Release files / pareto_dp-0.1.8-cp39-abi3-macosx_10_12_x86_64.whl

Download URL pareto_dp-0.1.8-cp39-abi3-macosx_10_12_x86_64.whl
Size 276.6 kB
Tags CPython 3.9 abi3 macOS 10.12+ x86-64
SHA-256 checksum
How to use checksums
f075f1994d0060bd8e232adc4245eaf88268e54f22171517c7098bcf204b6d93
BLAKE2b-256 checksum
How to use checksums
2203e69c2136460c86806ff4639a214bd3d77121912fd4b8de86fc02838c752d
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via uv/0.13.1 {"installer":{"name":"uv","version":"0.13.1","subcommand":["publish"]},"python":null,"implementation":{"name":null,"version":null},"distro":{"name":"Ubuntu","version":"24.04","id":"noble","libc":null},"system":{"name":null,"release":null},"cpu":null,"openssl_version":null,"setuptools_version":null,"rustc_version":null,"ci":true}

Security for pareto_dp 0.1.8

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.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page