search

SleipnirGroup / Sleipnir

A linearity-exploiting sparse nonlinear constrained optimization problem solver that uses the interior-point method.
BSD 3-Clause "New" or "Revised" License
36 stars 10 forks source link
optimization solver

readme

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.

The following thirdparty software was used in the benchmarks:

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

See benchmark details for more.

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

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:

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 .
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.