SDLP

Seidel's LP 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 Berkeley 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 mxd matrix. It is assumed that d is small (<10) while m can be arbitrary value (1<= m <= 1e+8).

Only one function is all you need:

template <int d>
double linprog(const Eigen::Matrix<double, d, 1> &c,
               const Eigen::Matrix<double, -1, d> &A,
               const Eigen::Matrix<double, -1, 1> &b,
               Eigen::Matrix<double, d, 1> &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.