Skip to main content

A linearity-exploiting sparse nonlinear constrained optimization problem solver that uses the interior-point method.

Project description

Sleipnir

C++ Build Python Build PyPI Downloads Website C++ API Python API Discord

Sparsity and Linearity-Exploiting Interior-Point solver - Now Internally Readable

Named after Odin's eight-legged horse from Norse mythology, Sleipnir is a linearity-exploiting sparse nonlinear constrained optimization problem solver that uses the interior-point method.

#include <print>

#include <sleipnir/optimization/OptimizationProblem.hpp>

int main() {
  // Find the x, y pair with the largest product for which x + 3y = 36
  sleipnir::OptimizationProblem problem;

  auto x = problem.DecisionVariable();
  auto y = problem.DecisionVariable();

  problem.Maximize(x * y);
  problem.SubjectTo(x + 3 * y == 36);
  problem.Solve();

  // x = 18.0, y = 6.0
  std::println("x = {}, y = {}", x.Value(), y.Value());
}
#!/usr/bin/env python3

from jormungandr.optimization import OptimizationProblem


def main():
    # Find the x, y pair with the largest product for which x + 3y = 36
    problem = OptimizationProblem()

    x = problem.decision_variable()
    y = problem.decision_variable()

    problem.maximize(x * y)
    problem.subject_to(x + 3 * y == 36)
    problem.solve()

    # x = 18.0, y = 6.0
    print(f"x = {x.value()}, y = {y.value()}")


if __name__ == "__main__":
    main()

Sleipnir's internals are intended to be readable by those who aren't domain experts with links to explanatory material for its algorithms.

Benchmarks

flywheel-scalability-results cart-pole-scalability-results
flywheel-scalability-results-casadi.csv
flywheel-scalability-results-sleipnir.csv
cart-pole-scalability-results-casadi.csv
cart-pole-scalability-results-sleipnir.csv

Generated by tools/generate-scalability-results.sh from benchmarks/scalability source.

  • CPU: AMD Ryzen 7 7840U
  • RAM: 64 GB, 5600 MHz DDR5
  • Compiler version: g++ (GCC) 14.2.1 20240805

The following thirdparty software was used in the benchmarks:

  • CasADi 3.6.7 (autodiff and NLP solver frontend)
  • Ipopt 3.14.16 (NLP solver backend)
  • MUMPS 5.7.0 (linear solver)

Ipopt uses MUMPS by default because it has free licensing. Commercial linear solvers may be much faster.

See benchmark details for more.

Install

Minimum system requirements

Sleipnir requires somewhat newer operating systems and C++ runtimes for std::print().

  • Windows
  • Linux
    • OS: Ubuntu 24.04
    • Runtime: GCC 14 libstdc++ (run sudo apt install g++-14)
  • macOS
    • OS: macOS 14
    • Runtime: Apple Clang 15.0.0 libc++ from Xcode 15.3 (run xcode-select --install)

C++ library

See the build instructions.

Python library

pip install sleipnirgroup-jormungandr

API docs

See the C++ API docs and Python API docs.

Examples

See the examples, C++ optimization unit tests, and Python optimization unit tests.

Build

Dependencies

  • C++23 compiler
    • On Windows 10 or greater, install Visual Studio Community 2022 and select the C++ programming language during installation
    • On Ubuntu 24.04 or greater, install GCC 14 via sudo apt install g++-14
    • On macOS 14 or greater, install the Xcode 15.3 command-line build tools via xcode-select --install
  • CMake 3.21 or greater
    • On Windows, install from the link above
    • On Linux, install via sudo apt install cmake
    • On macOS, install via brew install cmake
  • Python 3.9 or greater
    • On Windows, install from the link above
    • On Linux, install via sudo apt install python
    • On macOS, install via brew install python
  • Eigen
  • nanobind (build only)
  • Catch2 (tests only)

Library dependencies which aren't installed locally will be automatically downloaded and built by CMake.

The benchmark executables require CasADi to be installed locally.

C++ library

On Windows, open a Developer PowerShell. On Linux or macOS, open a Bash shell.

# Clone the repository
git clone git@github.com:SleipnirGroup/Sleipnir
cd Sleipnir

# Configure; automatically downloads library dependencies
cmake -B build -S .

# Build
cmake --build build

# Test
ctest --test-dir build --output-on-failure

# Install
cmake --install build --prefix pkgdir

The following build types can be specified via -DCMAKE_BUILD_TYPE during CMake configure:

  • Debug
    • Optimizations off
    • Debug symbols on
  • Release
    • Optimizations on
    • Debug symbols off
  • RelWithDebInfo (default)
    • Release build type, but with debug info
  • MinSizeRel
    • Minimum size release build
  • Asan
    • Enables address sanitizer
  • Tsan
    • Enables thread sanitizer
  • Ubsan
    • Enables undefined behavior sanitizer
  • Perf
    • RelWithDebInfo build type, but with frame pointer so perf utility can use it

Python library

On Windows, open a Developer PowerShell. On Linux or macOS, open a Bash shell.

# Clone the repository
git clone git@github.com:SleipnirGroup/Sleipnir
cd Sleipnir

# Setup
pip install --user build

# Build
python -m build --wheel

# Install
pip install --user dist/sleipnirgroup_jormungandr-*.whl

# Test
pytest

Test diagnostics

Passing the --enable-diagnostics flag to the test executable enables solver diagnostic prints.

Some test problems generate CSV files containing their solutions. These can be plotted with tools/plot_test_problem_solutions.py.

Benchmark details

Running the benchmarks

Benchmark projects are in the benchmarks folder. To compile and run them, run the following in the repository root:

# Install CasADi and [matplotlib, numpy, scipy] pip packages first
cmake -B build -S . -DBUILD_BENCHMARKING=ON
cmake --build build
./tools/generate-scalability-results.sh

See the contents of ./tools/generate-scalability-results.sh for how to run specific benchmarks.

How we improved performance

Make more decisions at compile time

During problem setup, equality and inequality constraints are encoded as different types, so the appropriate setup behavior can be selected at compile time via operator overloads.

Reuse autodiff computation results that are still valid (aka caching)

The autodiff library automatically records the linearity of every node in the computational graph. Linear functions have constant first derivatives, and quadratic functions have constant second derivatives. The constant derivatives are computed in the initialization phase and reused for all solver iterations. Only nonlinear parts of the computational graph are recomputed during each solver iteration.

For quadratic problems, we compute the Lagrangian Hessian and constraint Jacobians once with no problem structure hints from the user.

Use a performant linear algebra library with fast sparse solvers

Eigen provides these. It also has no required dependencies, which makes cross compilation much easier.

Use a pool allocator for autodiff expression nodes

This promotes fast allocation/deallocation and good memory locality.

We could mitigate the solver's high last-level-cache miss rate (~42% on the machine above) further by breaking apart the expression nodes into fields that are commonly iterated together. We used to use a tape, which gave computational graph updates linear access patterns, but tapes are monotonic buffers with no way to reclaim storage.

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.

Source Distribution

sleipnirgroup_jormungandr-0.0.1.dev255.tar.gz (120.6 kB view details)

Uploaded Source

Built Distributions

sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-win_amd64.whl (473.0 kB view details)

Uploaded CPython 3.13 Windows x86-64

sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-manylinux_2_35_x86_64.whl (412.5 kB view details)

Uploaded CPython 3.13 manylinux: glibc 2.35+ x86-64

sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-macosx_10_13_universal2.whl (687.3 kB view details)

Uploaded CPython 3.13 macOS 10.13+ universal2 (ARM64, x86-64)

sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-win_amd64.whl (473.0 kB view details)

Uploaded CPython 3.12 Windows x86-64

sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-manylinux_2_35_x86_64.whl (412.5 kB view details)

Uploaded CPython 3.12 manylinux: glibc 2.35+ x86-64

sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-macosx_10_13_universal2.whl (687.4 kB view details)

Uploaded CPython 3.12 macOS 10.13+ universal2 (ARM64, x86-64)

sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-win_amd64.whl (472.5 kB view details)

Uploaded CPython 3.11 Windows x86-64

sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-manylinux_2_35_x86_64.whl (412.7 kB view details)

Uploaded CPython 3.11 manylinux: glibc 2.35+ x86-64

sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-macosx_10_9_universal2.whl (687.9 kB view details)

Uploaded CPython 3.11 macOS 10.9+ universal2 (ARM64, x86-64)

sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-win_amd64.whl (472.3 kB view details)

Uploaded CPython 3.10 Windows x86-64

sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-manylinux_2_35_x86_64.whl (412.3 kB view details)

Uploaded CPython 3.10 manylinux: glibc 2.35+ x86-64

sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-macosx_10_9_universal2.whl (687.1 kB view details)

Uploaded CPython 3.10 macOS 10.9+ universal2 (ARM64, x86-64)

sleipnirgroup_jormungandr-0.0.1.dev255-cp39-cp39-win_amd64.whl (472.8 kB view details)

Uploaded CPython 3.9 Windows x86-64

sleipnirgroup_jormungandr-0.0.1.dev255-cp39-cp39-manylinux_2_35_x86_64.whl (412.5 kB view details)

Uploaded CPython 3.9 manylinux: glibc 2.35+ x86-64

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255.tar.gz.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255.tar.gz
Algorithm Hash digest
SHA256 5ddca604fff96c5abab556462ccde2a8713c27d28fe5319ed47c1c7c11332a84
MD5 3b4b45d84a203182dc691a5d260d42da
BLAKE2b-256 5da95464f35a42fcc9e58dd0d9e193d20ef03305a7e130bf93762a4f581bf60e

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255.tar.gz:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-win_amd64.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-win_amd64.whl
Algorithm Hash digest
SHA256 b939e511cc3e58a50b857a896fefa59c3a6de4f280ab3f3573509ef0d128b8ad
MD5 edd00a76ee90045f8e2023b4796fa117
BLAKE2b-256 07e737bf0194c6ff7208f22328dce766bf32fae2847e707ce3963018db2e3d6a

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-win_amd64.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-manylinux_2_35_x86_64.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-manylinux_2_35_x86_64.whl
Algorithm Hash digest
SHA256 d0337008d6ec0c6d897829f17e2e50daea201449d3f52cfc75305e682bd5e7de
MD5 d9dc65c9db6ba6f65d80d28bb4fc1b34
BLAKE2b-256 624181f038fa9b00d6d5f1eea610f5502798cc0360e36aa70ccc9bc876571710

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-manylinux_2_35_x86_64.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-macosx_10_13_universal2.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-macosx_10_13_universal2.whl
Algorithm Hash digest
SHA256 578141ad136ca4237a29b4d7ef67d64efcb57e2128abc76ebcbbe2ffeda52009
MD5 feeb0ab8450ce73ead2652ca3c95272e
BLAKE2b-256 bb8a3c319d1cadb924be0826c3af7d7140575cb54c2d83aa89a5dac167c8202f

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp313-cp313-macosx_10_13_universal2.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-win_amd64.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-win_amd64.whl
Algorithm Hash digest
SHA256 e1bf3443bffbf11705e224da1008bb662ad7e8d7564c50e0140f04a3bac643fd
MD5 af49fd1d460161ff4dd0cdaceb7c3349
BLAKE2b-256 82ff3537d4a6125651d39c8def009c52e4de7f828e8dae08678d1c5e9855e7c1

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-win_amd64.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-manylinux_2_35_x86_64.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-manylinux_2_35_x86_64.whl
Algorithm Hash digest
SHA256 658f1f95e82f1e6f0fb7d4d6d915d3d5d61932d3b9d75391bf3d0679efbd0671
MD5 8cca9082fded222a5fcbb5c23154b40d
BLAKE2b-256 c6f0f62716922a117d083692c1f1a1d2d17d8cfbf2b00e226cad73280baaf355

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-manylinux_2_35_x86_64.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-macosx_10_13_universal2.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-macosx_10_13_universal2.whl
Algorithm Hash digest
SHA256 c44dacff30f7a1323f0220ebb4039c03d5253c3ba95bb2e2f9db4772b8b992b6
MD5 88acfdde5092326cb7756391aab8aba1
BLAKE2b-256 5cbd159b973c8aafead5373f5a1ea47c89b91e530216df0a5063903c5e78ce2f

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp312-cp312-macosx_10_13_universal2.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-win_amd64.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-win_amd64.whl
Algorithm Hash digest
SHA256 d60e21891a980c1cf1bc09db99757c009eb20488b2e96b3ed093c3ee996a1950
MD5 79f4842262471324a835c07e999a2c51
BLAKE2b-256 655974c5e403152f4906d51b96646bb2799dc1d51836ce0ac85f2f7113c341e6

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-win_amd64.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-manylinux_2_35_x86_64.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-manylinux_2_35_x86_64.whl
Algorithm Hash digest
SHA256 2e79ddd5cd246a1aac3363ad4f102b2f3e21d587c3ecbb84c4815b4bc26833d4
MD5 6b2feba380f79a8dadf9dd9791fc1ca3
BLAKE2b-256 1961887ffe5bc1c3c6e021f71490e3ee3efe3389af5fd41d6a19731c56bb2877

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-manylinux_2_35_x86_64.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-macosx_10_9_universal2.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-macosx_10_9_universal2.whl
Algorithm Hash digest
SHA256 46b4c11194cca06ae62a366d4a63c7f764eb887608323e1d6a9d1ab860cda1a5
MD5 bba287ca2d492cfa38e1c24e4768c979
BLAKE2b-256 73c4629bcd931275a63416c2dd30b661c44a2acb1c26ebfa7c69a3c9653e7e18

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp311-cp311-macosx_10_9_universal2.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-win_amd64.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-win_amd64.whl
Algorithm Hash digest
SHA256 63fa9fe977e94e1876f9ca24d9e7ec22b2951c148a4bbd0cb9d5e4cb9595b082
MD5 de6f9b3d8f3332db3a71a65e71afbd8e
BLAKE2b-256 9b3d63b459e612537de3020acd635aa7d986fee13e023d3ebd6edf2e194b39e7

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-win_amd64.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-manylinux_2_35_x86_64.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-manylinux_2_35_x86_64.whl
Algorithm Hash digest
SHA256 1792dbc29d4e0845826a66385bd71cd24833c9c605e7906707a920b856024ba6
MD5 af45afd6bb6da2e424670920453cb001
BLAKE2b-256 5f0e38abc8962bd96d54f5fa74945b3f1f6c2bb283a56d3ffde470f3cba2c90d

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-manylinux_2_35_x86_64.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-macosx_10_9_universal2.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-macosx_10_9_universal2.whl
Algorithm Hash digest
SHA256 331aa4578b669f23802fe1249ca2c5d84bc0c046e3b93455877f9d1325ca6ba1
MD5 525cc6d1c6bf3c2309027fbef7afa0ca
BLAKE2b-256 191950dae2e3e8b9d5c4b61c592defc2919b115e368bb0aa7ca40f2218a87b15

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp310-cp310-macosx_10_9_universal2.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp39-cp39-win_amd64.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp39-cp39-win_amd64.whl
Algorithm Hash digest
SHA256 887e2dfe30ee164402c0737ec0dd235c37f112bb8e318eef61d58dd3e61b7ddf
MD5 d6bf3d6b578d6ec960b567a7bc581499
BLAKE2b-256 8a107b647e103b1f4df586b434cdc2317e43f7dffe9cea2f8bb5b29a372b112a

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp39-cp39-win_amd64.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

File details

Details for the file sleipnirgroup_jormungandr-0.0.1.dev255-cp39-cp39-manylinux_2_35_x86_64.whl.

File metadata

File hashes

Hashes for sleipnirgroup_jormungandr-0.0.1.dev255-cp39-cp39-manylinux_2_35_x86_64.whl
Algorithm Hash digest
SHA256 6d0266ff87ef99b9bd443c3a068bc5dceedb86c7144ae00d30d680fd509ebf88
MD5 13aeb020b93245bb89125a6236c9f651
BLAKE2b-256 114a33d2d3518b916e61d71413734021111cb5ec797cdf082dc6a81d0d34d6a7

See more details on using hashes here.

Provenance

The following attestation bundles were made for sleipnirgroup_jormungandr-0.0.1.dev255-cp39-cp39-manylinux_2_35_x86_64.whl:

Publisher: build-python.yml on SleipnirGroup/Sleipnir

Attestations:

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page