### Navigation

- index
- next |
- previous |
- OpenCV 3.0.0-dev documentation »
- OpenCV API Reference »
- optim. Generic numerical optimization »

# Linear Programming

## optim::solveLP

Solve given (non-integer) 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:

Where is fixed 1-by-n row-vector, is fixed m-by-n matrix, is fixed m-by-1 column vector and is an arbitrary n-by-1 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 type, while simplex method degenerates to exponential time for some special cases), it is well-studied, easy to implement and is shown to work well for real-life 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.

C++:`` int `optim::``solveLP`(const Mat& Func, const Mat& Constr, Mat& z)

  Parameters: | Func – This row-vector corresponds to in the LP problem formulation (see above). It should contain 32- or 64-bit floating point numbers. As a convenience, column-vector may be also submitted, in the latter case it is understood to correspond to . Constr – m-by-n+1 matrix, whose rightmost column corresponds to in formulation above and the remaining to . It should containt 32- or 64-bit floating point numbers. z – The solution will be returned here as a column-vector - it corresponds to in the formulation above. It will contain 64-bit floating point numbers.
  Returns: | One of the return codes:

    //!the return codes for solveLP() function
    enum
    {
        SOLVELP_UNBOUNDED    = -2, //problem is unbounded (target function can achieve arbitrary high values)
        SOLVELP_UNFEASIBLE    = -1, //problem is unfeasible (there are no points that satisfy all the constraints imposed)
        SOLVELP_SINGLE    = 0, //there is only one maximum for target function
        SOLVELP_MULTI    = 1 //there are multiple maxima for target function - the arbitrary one is returned
    };

## Help and Feedback

You did not find what you were looking for?

- Ask a question on the Q&A forum.
- If you think something is missing or wrong in the documentation, please file a bug report.

### Navigation

- index
- next |
- previous |
- OpenCV 3.0.0-dev documentation »
- OpenCV API Reference »
- optim. Generic numerical optimization »