Seidel's Algorithm: Linear-Complexity Linear Programming for Small-Dimensional Variables

Overview

SDLP

Seidel's Algorithm: Linear-Complexity Linear Programming (LP) for Small-Dimensions

About

  1. This solver is super efficient for small-dimensional LP with any constraint number, mostly encountered in computational geometry. It enjoys linear complexity about the constraint number.

  2. The speed is at least an order of magnitude faster than GLPK in small-dimensional LP (<10) with a large constraints number (>100).

  3. This solver is adapted from the linear-fractional programming (LFP) from Mike Hohmeyer at UC Berkerley based on Raimund Seidel's algorithm. Kernel functions are reorganized. Previously-existed bugs are fixed here. An easy-to-use interface for LP via Eigen is also added.

  4. Only a header file is all you need.

Interface

To solve a linear programming:

    min cTx, 
    s.t. Ax<=b,

where x and c are d-dimensional vectors, b an m-dimensional vector and A an m*n matrix. It is assumed that d is small (<10) while m can be arbitrary value (1<= m <= 1e8).

Only one function is all you need:

double linprog(const Eigen::VectorXd &c, 
               const Eigen::MatrixXd &A,
               const Eigen::VectorXd &b,
               Eigen::VectorXd &x);

Input:

    c: objective coefficient
    A: constraint matrix
    b: constraint bound

Output:

    x: optimal solution if solved
    return: finite value if solved
            -infinity if unbounded
            infinity if infeasible

Reference

  1. Megiddo, N., 1984. Linear programming in linear time when the dimension is fixed. Journal of the ACM (JACM), 31(1), pp.114-127.
  2. Seidel, R., 1991. Small-dimensional linear programming and convex hulls made easy. Discrete & Computational Geometry, 6(3), pp.423-434.
Issues
  • How is the adaptability in high dimension?

    How is the adaptability in high dimension?

    When the dimension is high, such as 10000 optimization variables and 100000 constraints, could the solver keep better or same speed to solve as the general solvers?

    good first issue 
    opened by szt008 3
  • Enquiries on dimension

    Enquiries on dimension

    Hi, first of all, I would like to thank you for creating this repo, and I have only one simple question concerning the content of this library. As you have mentioned in the README file, this solver works super efficient when the preset dimension is <10. Thus, my question is that what would happen if I increase the number of the dimension, say like above 50? Thank you in advance for your time.

    opened by pattylo 1
Owner
ZJU FAST Lab
ZJU FAST Lab
a lean linear math library, aimed at graphics programming. Supports vec3, vec4, mat4x4 and quaternions

linmath.h -- A small library for linear math as required for computer graphics linmath.h provides the most used types required for programming compute

datenwolf 684 Jun 12, 2022
nml is a simple matrix and linear algebra library written in standard C.

nml is a simple matrix and linear algebra library written in standard C.

Andrei Ciobanu 33 Jun 4, 2022
Linear Algebra in C

Linear Algebra in C Quick Start Grab la.h and use it as an stb-style header-only library. For more info on such libraries see: https://github.com/noth

Tsoding 65 Jun 4, 2022
C++ library for solving large sparse linear systems with algebraic multigrid method

AMGCL AMGCL is a header-only C++ library for solving large sparse linear systems with algebraic multigrid (AMG) method. AMG is one of the most effecti

Denis Demidov 528 Jun 22, 2022
A large scale non-linear optimization library

Ceres Solver Ceres Solver is an open source C++ library for modeling and solving large, complicated optimization problems. It is a feature rich, matur

null 2.5k Jun 22, 2022
SIMD (SSE) implementation of the infamous Fast Inverse Square Root algorithm from Quake III Arena.

simd_fastinvsqrt SIMD (SSE) implementation of the infamous Fast Inverse Square Root algorithm from Quake III Arena. Why Why not. How This video explai

Liam 7 Jan 28, 2022
Bolt is an algorithm for compressing vectors of real-valued data and running mathematical operations directly on the compressed representations.

Bolt is an algorithm for compressing vectors of real-valued data and running mathematical operations directly on the compressed representations.

null 2.2k Jun 28, 2022
Optimized implementations of the Number Theoretic Transform (NTT) algorithm for the ring R/(X^N + 1) where N=2^m.

optimized-number-theoretic-transform-implementations This sample code package is an implementation of the Number Theoretic Transform (NTT) algorithm f

International Business Machines 13 Mar 23, 2022
Library for nonconvex constrained optimization using the augmented Lagrangian method and the matrix-free PANOC algorithm.

alpaqa Alpaqa is an efficient implementation of the Augmented Lagrangian method for general nonlinear programming problems, which uses the first-order

OPTEC 10 May 11, 2022
qpSWIFT is a light-weight sparse quadratic programming solver

qpSWIFT Light-weight sparse Quadratic Programming Solver Introduction qpSWIFT is light-weight sparse Quadratic Programming solver targetted for embedd

qpSWIFT 54 Jun 26, 2022
Refinements of the WFA alignment algorithm with better complexity

wfalm Refinements of the WFA alignment algorithm with better complexity Introduction This repository contains implementations of the WFA algorithm as

Jordan Eizenga 23 Jun 11, 2022
Shamir’s Secret Sharing Algorithm: Shamir’s Secret Sharing is an algorithm in cryptography created by Adi Shamir. The main aim of this algorithm is to divide secret that needs to be encrypted into various unique parts.

Shamir-s-Secret-Sharing-Algorithm-Cryptography Shamir’s Secret Sharing Algorithm: Shamir’s Secret Sharing is an algorithm in cryptography created by A

Pavan Ananth Sharma 4 Apr 27, 2022
libmpc++ is a C++ header-only library to solve linear and non-linear MPC

libmpc++ libmpc++ is a C++ library to solve linear and non-linear MPC. The library is written in modern C++17 and it is tested to work on Linux, macOS

Nicola Piccinelli 32 Jun 9, 2022
Complete introduction to size balanced trees (O(1) amortized complexity)

Size Balanced Tree A size balanced tree (SBT) is a self-balancing binary search tree (SBBST) rebalanced by examining the sizes of each node's subtrees

Jishan Shaikh 18 Jun 2, 2022
This is the code that powers FiniteCurve.com, a TSP art style generator without the NP-hard complexity.

FiniteCurve.com -- TSP art on a CPU budget This is the code that powers FiniteCurve.com, a TSP art style generator without the NP-hard complexity. For

Vidar Holen 7 Apr 11, 2022
MPEG-H 3D Audio Low Complexity Profile Decoder

Introduction of the MPEG-H 3D Audio Low Complexity Profile Decoder The advent of object-based audio and scene-based audio has revolutionized the 3D so

Ittiam Systems Pvt. Ltd. 38 Jun 23, 2022
A tool to calculate cyclomatic complexity

Feature: python 3.10.0 is required calculate cyclomatic complexity of a program (python) generate ast from source code with the help of tree-sitter su

null 1 Mar 3, 2022
CMetrics measures size and complexity for C files

C metrics package ================= INSTALL ------- see INSTALL file USAGE ----- cmetrics [-h] [-f] [-p] [-n] target_dir positional arguments:

Metrics Grimoire 63 May 27, 2022
a tool to count accesses to member variables in c++ programs

access_profiler access_profiler is a heavy-weight class field access profiler, implemented as C++ library. to use this profiler, include "access_profi

Arvid Norberg 68 May 31, 2022
jvm-monitor is a lightweight monitoring tool that logs all the local variables whenever exceptions occur.

jvm-monitor jvm-monitor is a Java agent attached to a Java VM (virtual machine), which logs all the local variables when exceptions occur. Rationales

Barosl Lee 13 Nov 21, 2021
défi pour maitrise bien les variables

challengeC Objectif Nous allons écrire des programmes C simples en utilisant les connaissances des types de données, des opérateurs, des fonctions pri

odin 4 Feb 13, 2022
Get_next_line is a project that taught me some new concepts like static variables file_desctiptors how they work

Get_next_line is a project that taught me some new concepts like static variables file_desctiptors how they work, how to create them, read and import data from them.

Ahmed El Mountassir 4 Apr 19, 2022
Just a basic mini library for parsing simple files that only have variables written and with Lua extension.

C++ Parser Lua file config Just a basic mini library for parsing simple files that only have variables written and with Lua extension. Note: At the mo

Marcos Oliveira 3 Dec 26, 2021
c++ program to solve up too 100 equations in 100 variables

linear-equation-solver c++ program to solve up too 100 equations in 100 variables PROGRAMMED BY : FAYSSAL & INASS REVONS COMMUNITY LICENSE & MIT THANK

Fayssal Chokri 2 Mar 14, 2022
libsais is a library for linear time suffix array and burrows wheeler transform construction based on induced sorting algorithm.

libsais libsais is a library for fast (see Benchmarks below) linear time suffix array and Burrows-Wheeler transform construction based on induced sort

Ilya Grebnov 89 Jun 21, 2022
Linear predictive coding (LPC) is an algorithm used to approximate audio signals like human speech

lpc.lv2 LPC analysis + synthesis plugin for LV2 About Linear predictive coding (LPC) is an algorithm used to approximate audio signals like human spee

null 3 May 2, 2022
Multi-dimensional dynamically distorted staggered multi-bandpass LV2 plugin

B.Angr A multi-dimensional dynamicly distorted staggered multi-bandpass LV2 plugin, for extreme soundmangling. Based on Airwindows XRegion. Key featur

null 18 Apr 17, 2022
C++20 N-dimensional Matrix class for hobby project

Ndim-Matrix C++20 N-dimensional Matrix class for hobby project Supporting matrix operations STL compatible iterators reshape (O(1) move operation, no

null 18 Jun 12, 2022
StarRocks is a next-gen sub-second MPP database for full analysis senarios, including multi-dimensional analytics, real-time analytics and ad-hoc query, formerly known as DorisDB.

StarRocks is a next-gen sub-second MPP database for full analysis senarios, including multi-dimensional analytics, real-time analytics and ad-hoc query, formerly known as DorisDB.

StarRocks 2.7k Jun 26, 2022