A numpy based implementation of revised simplex with numerical stability checks. The implementation was found 16% faster than scipy's revised-simplex method running a series of random configurations.
This repositry offers an implementation for an algorithm that solves Linear Programming configurations. A Linear Programming Maximization Problem is defined as:
Where the A matrix and b & c vectors are given and we need to find a valid x vector that maximizes the score function.
The Revised Simplex method is a variant of the classic simplex algorithm for solving Linear Programming configurations. This method allows for a greater computational efficiency. For more details you can watch the slides here.
The implementation is based on numpy. It includes a number of numerical stability checks utilizing eta matrices and lu factorization to keep it efficient.
The implementation allows the use of both Bland & Dantzig rules. The module provides two main external API functions:
- get_optimal_solution - searches for an optimal solution. This function returns a SimplexResult object:
class ResultCode(Enum): INFEASIBLE = 1 FINITE_OPTIMAL = 2 UNBOUNDED_OPTIMAL = 3 CYCLE_DETECTED = 4 @dataclass class SimplexResult(object): res_code: ResultCode assignment: Union[None, np.ndarray] optimal_score: Union[None, float]
- has_feasible_solution - checks if there is a feasible solution for the configuration. Returns True\False.
Here is an example of how to use the module:
import numpy as np from Simplex import Simplex, PickingRule solver = Simplex() A = np.array([[-1, 1], [-2, -2], [-1, 4]]) b = np.array([-1, -6, 2]) c = np.array([1, 3]) rule = PickingRule.DANTZIG_RULE # Or PickingRule.BLAND_RULE # optimal using the default rule - bland's solver.get_optimal_solution(A, b, c) # optimal using a specified rule - dantzig's solver.get_optimal_solution(A, b, c) # check for existance of feasible solution solver.has_feasible_solution(A, b, c)
The performance of this repository was compared to scipy's revised-simplex method by running 10,000 random generated configurations. The results show an improvement of 16% compared to scipy's performance when running the full revised simplex (searching for optimal solution). The more humble method (has_feasible_solution) was 41% faster than scipy's full revised simplex.
