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.
You might also like...
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

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

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

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

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

This is the code that powers FiniteCurve.com, a TSP art style generator without the NP-hard complexity.
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

MPEG-H 3D Audio Low Complexity Profile Decoder
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

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

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

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

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

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.

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

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

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:

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

Linear predictive coding (LPC) is an algorithm used to approximate audio signals like human speech
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

Multi-dimensional dynamically distorted staggered multi-bandpass LV2 plugin
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

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

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.

Comments
  • 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 729 Jan 9, 2023
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 45 Dec 9, 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 74 Nov 26, 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 578 Dec 11, 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.9k Jan 3, 2023
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 Oct 4, 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.3k Dec 30, 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 12 Nov 14, 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 21 Dec 9, 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 72 Dec 17, 2022