Skip to content

PetterS/monolith

master
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Monolith

Monolith is a monorepo with several optimization projects. Some of the code was originally written for research or as hobby projects in other repositories (e.g. spii and easy-IP).

One of the highlights is a state-of-the-art scheduler using column generation, which significantly outperforms all other optimizers at schedulingbenchmarks.org. Try it in the browser (wasm) here!

Why a monorepo?

  • C++ does not have an ABI. Every compiler, or worse, every flag configuration of every compiler generates potentially incompatible code. I want to use many compilers (MCVC, GCC, Clang) and many settings (debug, release, asan, fuzzers etc.). I also use Emscripten to compile programs to WASM (example here).
  • Refactoring code becomes much easier if all code with all dependencies is available in one IDE at the same time.

Contact

Petter Strandmark, petter.strandmark@gmail.com

Modules

Column generation

Implements the algorithm described in First-order Linear Programming in a Column Generation-Based Heuristic Approach to the Nurse Rostering Problem (2020) doi link.

The minimum::linear::colgen module contains code for solving scheduling problems. It significantly outperforms all other optimizers at schedulingbenchmarks.org.

Some of the reasons it is fast:

  • It uses a first-order LP solver based on papers by Chambolle and Pock.
  • The Ryan-Foster rule is used to iteratively work towards an integer solution. There is no time to branch and bound for big problems.
  • The pricing problem uses highly optimized dynamic programming in a DAG (in minimum::algorithms).

See the README in the module itself for more info.

Minimum/AI

The minimum::ai module contains code originally from my Monte-Carlo tree search repository. It is very fast – some years ago it evaluated almost 2 million complete games per second when playing 4 in a row.

Minimum/Linear

The minimum::linear module contains code originally from my easy-IP repository. It is a modelling interface (DSL) for integer programming and supports converting IPs to SAT. It also uses two free solvers: Cbc and Glpk.

minimum::linear also contains an implementation of a first-order LP solver based on papers by Chambolle and Pock. Using a first-order LP solver is very important when solving really big scheduling problems.

Minimum/Nonlinear

The minimum::nonlinear module contains code originally from my spii repository. When a function is defined, it will be automatically differentiated with an autodiff library. This makes the resulting code very fast and numerically stable. The library contains minimization routines like L-BFGS and Newton’s method.

For example, a function of one vector variable is simply defined as:

auto lambda = [](auto* x) {
    auto d0 = x[1] - x[0] * x[0];
    auto d1 = 1 - x[0];
    return 100 * d0 * d0 + d1 * d1;
};

Having auto here instead of e.g. double is crucial. Efficient code for first and second-order derivatives is generated with

auto term = make_differentiable<2>(lambda);

Minimum/Constrained

Using both minimum::linear and minimum::nonlinear, this module implements constrained optimization via successive linear programming.

Minimum/Curvature

The module minimum::curvature contains code originally written at curve_extraction. It computes shortest paths in regular graphs taking curvature into account.

Building

Everything needed to build the library is included. With CMake and a modern C++ compiler, you can do

$ cmake /path/to/source
$ make

Licence

The license can be found in the LICENSE file. Contact me if you need another license.

The software in the third-party folder is not written exclusively by me and their respective license files apply.

About

A C++ monorepo for discrete and continuous optimization. Batteries included!

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published