# SDLP

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

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

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

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.

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

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

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

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

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.

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

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

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

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

23 Jun 11, 2022
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

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

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

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

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

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:

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

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

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

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.

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

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

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

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

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

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

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.

2.7k Jun 26, 2022