Skip to content

O
opencv
Switch branch/tag
Find file
BlameHistoryPermalink
  • Alex Leontiev's avatar
    Convenience fixes · 6db2596c
    Alex Leontiev authored 
    Attempting to fix issues pointed out by Vadim Pisarevsky during the pull
request review. In particular, the following things are done:
*) The mechanism of debug info printing is changed and made more
procedure-style than the previous macro-style
*) z in solveLP() is now returned as a column-vector
*) Func parameter of solveLP() is now allowed to be column-vector, in
which case it is understood to be the transpose of what we need
*) Func and Constr now can contain floats, not only doubles (in the
former case the conversion is done via convertTo())
*)different constructor to allocate space for z in solveLP() is used,
making the size of z more explicit (this is just a notation change, not
functional, both constructors are achieving the same goal)
*) (big) mat.hpp and iostream headers are moved to precomp-headers from
optim.hpp
    6db2596c
linear_programming.rst 2.55 KB

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:

\mbox{Maximize } c\cdot x\\
\mbox{Subject to:}\\
Ax\leq b\\
x\geq 0

Where c is fixed 1-by-n row-vector, A is fixed m-by-n matrix, b is fixed m-by-1 column vector and x 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.

//!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
};