Seidel's Algorithm: Linear-Complexity Linear Programming (LP) for Small-Dimensions
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 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.
Only a header file is all you need.
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);
c: objective coefficient A: constraint matrix b: constraint bound
x: optimal solution if solved return: finite value if solved -infinity if unbounded infinity if infeasible
- 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.