SDLP
Seidel's LP Algorithm: Linear-Complexity Linear Programming (LP) for Small-Dimensions
About
-
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.
-
The speed is at least an order of magnitude faster than GLPK in small-dimensional LP (<10) with a large constraints number (>100).
-
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.
-
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
- Megiddo, N., 1984. Linear programming in linear time when the dimension is fixed. Journal of the ACM (JACM), 31(1), pp.114-127.
- Seidel, R., 1991. Small-dimensional linear programming and convex hulls made easy. Discrete & Computational Geometry, 6(3), pp.423-434.