OpenCV
4.0.0dev
Open Source Computer Vision

Classes  
class  cv::ConjGradSolver 
This class is used to perform the nonlinear nonconstrained minimization of a function with known gradient,. More...  
class  cv::DownhillSolver 
This class is used to perform the nonlinear nonconstrained minimization of a function,. More...  
class  cv::MinProblemSolver 
Basic interface for all solvers. More...  
Enumerations  
enum  cv::SolveLPResult { cv::SOLVELP_UNBOUNDED = 2, cv::SOLVELP_UNFEASIBLE = 1, cv::SOLVELP_SINGLE = 0, cv::SOLVELP_MULTI = 1 } 
return codes for cv::solveLP() function More...  
Functions  
int  cv::solveLP (InputArray Func, InputArray Constr, OutputArray z) 
Solve given (noninteger) linear programming problem using the Simplex Algorithm (Simplex Method). More...  
The algorithms in this section minimize or maximize function value within specified constraints or without any constraints.
enum cv::SolveLPResult 
return codes for cv::solveLP() function
int cv::solveLP  (  InputArray  Func, 
InputArray  Constr,  
OutputArray  z  
) 
Python:  

retval, z  =  cv.solveLP(  Func, Constr[, z]  ) 
Solve given (noninteger) linear programming problem using the Simplex Algorithm (Simplex Method).
What we mean here by "linear programming problem" (or LP problem, for short) can be formulated as:
\[\mbox{Maximize } c\cdot x\\ \mbox{Subject to:}\\ Ax\leq b\\ x\geq 0\]
Where \(c\) is fixed 1
byn
rowvector, \(A\) is fixed m
byn
matrix, \(b\) is fixed m
by1
column vector and \(x\) is an arbitrary n
by1
column vector, which satisfies the constraints.
Simplex algorithm is one of many algorithms that are designed to handle this sort of problems efficiently. Although it is not optimal in theoretical sense (there exist algorithms that can solve any problem written as above in polynomial time, while simplex method degenerates to exponential time for some special cases), it is wellstudied, easy to implement and is shown to work well for reallife purposes.
The particular implementation is taken almost verbatim from Introduction to Algorithms, third edition by T. H. Cormen, C. E. Leiserson, R. L. Rivest and Clifford Stein. In particular, the Bland's rule http://en.wikipedia.org/wiki/Bland%27s_rule is used to prevent cycling.
Func  This rowvector corresponds to \(c\) in the LP problem formulation (see above). It should contain 32 or 64bit floating point numbers. As a convenience, columnvector may be also submitted, in the latter case it is understood to correspond to \(c^T\). 
Constr  m byn+1 matrix, whose rightmost column corresponds to \(b\) in formulation above and the remaining to \(A\). It should contain 32 or 64bit floating point numbers. 
z  The solution will be returned here as a columnvector  it corresponds to \(c\) in the formulation above. It will contain 64bit floating point numbers. 