 Visual Servoing Platform  version 3.4.0
vpLinProg Class Reference

#include <vpLinProg.h>

## Public Types

typedef std::pair< unsigned int, double > BoundedIndex

## Static Public Member Functions

Solvers
static bool simplex (const vpColVector &c, vpMatrix A, vpColVector b, vpColVector &x, const double &tol=1e-6)

static bool solveLP (const vpColVector &c, vpMatrix A, vpColVector b, const vpMatrix &C, const vpColVector &d, vpColVector &x, std::vector< BoundedIndex > l={}, std::vector< BoundedIndex > u={}, const double &tol=1e-6)

Dimension reduction for equality constraints
static bool colReduction (vpMatrix &A, vpColVector &b, bool full_rank=false, const double &tol=1e-6)

static bool rowReduction (vpMatrix &A, vpColVector &b, const double &tol=1e-6)

Vector and equality checking
static bool allZero (const vpColVector &x, const double &tol=1e-6)

static bool allClose (const vpMatrix &A, const vpColVector &x, const vpColVector &b, const double &tol=1e-6)

static bool allLesser (const vpMatrix &C, const vpColVector &x, const vpColVector &d, const double &thr=1e-6)

static bool allLesser (const vpColVector &x, const double &thr=1e-6)

static bool allGreater (const vpColVector &x, const double &thr=1e-6)

## Detailed Description

This class provides two solvers for Linear Programs.

One is a classical simplex, the other can deal with various inequality or bound constraints.

Utility functions to reduce or check linear equalities or inequalities are also available.

Warning
The solvers are only available if c++11 or higher is activated during build. Configure ViSP using cmake -DUSE_CXX_STANDARD=11.

Definition at line 66 of file vpLinProg.h.

## Member Typedef Documentation

 typedef std::pair vpLinProg::BoundedIndex

Used to pass a list of bounded variables to solveLP(), as a list of (index, bound).

The type is compatible with C++11's braced initialization. Construction can be done in the call to solveLP or before, as shown in this example: Here the lower bound is built explicitely while the upper one is built during the call to solveLP():

Warning
This function is only available if c++11 or higher is activated during compilation. Configure ViSP using cmake -DUSE_CXX_STANDARD=11.
#include <visp3/core/vpLinProg.h>
int main()
{
vpColVector c(3), x;
vpMatrix C(2, 3);
c = -2; c = -3; c = -4;
C = 3; C = 2; C = 1; d = 10;
C = 2; C = 5; C = 3; d = 15;
// build lower bounds explicitely as a std::vector of std::pair<int, double>
std::vector<vpLinProg::BoundedIndex> lower_bound;
for(unsigned int i = 0; i < 3; ++i)
{
bound.first = i; // index
bound.second = 0; // lower bound for this index
lower_bound.push_back(bound);
}
if(vpLinProg::solveLP(c, vpMatrix(0,0), vpColVector(0), C, d, x,
lower_bound,
{{2,6}})) // upper bound is passed with braced initialization
{
std::cout << "x: " << x.t() << std::endl;
std::cout << "cost: " << c.t()*x << std::endl;
}
}
solveLP()

Definition at line 122 of file vpLinProg.h.

## Member Function Documentation

 static bool vpLinProg::allClose ( const vpMatrix & A, const vpColVector & x, const vpColVector & b, const double & tol = 1e-6 )
inlinestatic

Check if is near .

Parameters
 A : matrix (dimension m x n) x : vector (dimension n) b : vector (dimension m) tol : tolerance
Returns
True if Definition at line 175 of file vpLinProg.h.

References vpMatrix::getRow(), and vpArray2D< Type >::getRows().

Referenced by colReduction(), rowReduction(), simplex(), and solveLP().

 static bool vpLinProg::allGreater ( const vpColVector & x, const double & thr = 1e-6 )
inlinestatic

Check if all elements of are greater or equal to threshold.

Parameters
 x : vector (dimension n) thr : threshold
Returns
True if Definition at line 230 of file vpLinProg.h.

References vpArray2D< Type >::getRows().

 static bool vpLinProg::allLesser ( const vpMatrix & C, const vpColVector & x, const vpColVector & d, const double & thr = 1e-6 )
inlinestatic

Check if all elements of are lesser or equal to threshold.

Parameters
 C : matrix (dimension m x n) x : vector (dimension n) d : vector (dimension m) thr : threshold
Returns
True if Definition at line 194 of file vpLinProg.h.

References vpMatrix::getRow(), and vpArray2D< Type >::getRows().

 static bool vpLinProg::allLesser ( const vpColVector & x, const double & thr = 1e-6 )
inlinestatic

Check if all elements of are lesser or equal to threshold.

Parameters
 x : vector (dimension n) thr : threshold
Returns
True if Definition at line 212 of file vpLinProg.h.

References vpArray2D< Type >::getRows().

 static bool vpLinProg::allZero ( const vpColVector & x, const double & tol = 1e-6 )
inlinestatic

Check if all elements of are near zero.

Parameters
 x : vector to be checked tol : tolerance
Returns
True if Definition at line 155 of file vpLinProg.h.

References vpArray2D< Type >::getRows().

 bool vpLinProg::colReduction ( vpMatrix & A, vpColVector & b, bool full_rank = false, const double & tol = 1e-6 )
static

Reduces the search space induced by an equality constraint.

Changes A and b so that the constraint can be written This method is destructive for A and b.

Parameters
 A : in = equality matrix (dimension m x n), out = projector to kernel (dimension n x (n-rank(A))) b : in = equality vector (dimension m), out = particular solution (dimension n) full_rank : if we think A is full rank, leads to a faster result but a slower one if A is actually not full rank. tol : tolerance to test the ranks
Returns
True if has a solution.

Here is an example with and that become and .

We indeed have #include <visp3/core/vpLinProg.h>
int main()
{
vpMatrix A(3,4);
A = A = 1;
A = A = 1;
b = 1; b = 2; b = 3;
vpMatrix Z = A;
vpColVector x1 = b;
{
// Z is now 4 x 2
// try with random z-vector
for(int i = 0; i < 10; ++i)
{
z = (10.*rand())/RAND_MAX;
z = (10.*rand())/RAND_MAX;
std::cout << "A.(x1 + Z.z): " << (A*(x1 + Z*z)).t() << std::endl;
}
}
else
std::cout << "Ax = b not feasible\n";
}

Definition at line 97 of file vpLinProg.cpp.

 bool vpLinProg::rowReduction ( vpMatrix & A, vpColVector & b, const double & tol = 1e-6 )
static

Reduces the number of equality constraints.

Changes A and b so that the constraint is written with minimal rows.

This method is destructive for A and b.

Parameters
 A : equality matrix (dimension in = (m x n), out = (rank(A) x n) b : equality vector (dimension in = (m), out = (rank(A))) tol : tolerance to test the ranks
Returns
True if has a solution.

Here is an example with and (feasible) or (not feasible).

#include <visp3/core/vpLinProg.h>
int main()
{
vpMatrix A(3,4);
A = A = 1;
A = A = 1;
// b = 1; // uncomment to make it unfeasible
std::cout << A << std::endl; // A is now 2x4
else
std::cout << "Ax = b not feasible\n";
}

Definition at line 246 of file vpLinProg.cpp.

Referenced by simplex().

 bool vpLinProg::simplex ( const vpColVector & c, vpMatrix A, vpColVector b, vpColVector & x, const double & tol = 1e-6 )
static

Solves a Linear Program under simplex canonical form Parameters
 c : cost vector (dimension n) A : equality matrix (dimension m x n) b : equality vector (dimension m) x : in: feasible point if any, out: solution (dimension n) tol : tolerance to test the ranks
Returns
True if the solution was found.
Warning
This function is only available if c++11 or higher is activated during build. Configure ViSP using cmake -DUSE_CXX_STANDARD=11.

Here is an example: That can be re-written as: #include <visp3/core/vpLinProg.h>
int main()
{
vpColVector c(5), x;
vpMatrix A(2, 5);
c = -2; c = -3; c = -4;
A = 3; A = 2; A = 1; b = 10;
A = 2; A = 5; A = 3; b = 15;
A = A = 1;
if(vpLinProg::simplex(c, A, b, x))
{
std::cout << "x: " << x.t().extract(0,3) << std::endl;
std::cout << "cost: " << c.t()*x << std::endl;
}
}
solveLP

Definition at line 532 of file vpLinProg.cpp.

 bool vpLinProg::solveLP ( const vpColVector & c, vpMatrix A, vpColVector b, const vpMatrix & C, const vpColVector & d, vpColVector & x, std::vector< BoundedIndex > l = {}, std::vector< BoundedIndex > u = {}, const double & tol = 1e-6 )
static

Solves a Linear Program under various constraints Parameters
 c : cost vector (dimension n) A : equality matrix (dimension m x n) b : equality vector (dimension m) C : inequality matrix (dimension p x n) d : inequality vector (dimension p) x : in: feasible point if any, out: solution (dimension n) l : lower bounds (if any) u : upper bounds (if any) tol : tolerance to test the ranks
Returns
True if the solution was found.

Lower and upper bounds may be passed as a list of (index, bound) with C++11's braced initialization.

Warning
This function is only available if c++11 or higher is activated during compilation. Configure ViSP using cmake -DUSE_CXX_STANDARD=11.

Here is an example: #include <visp3/core/vpLinProg.h>
int main()
{
vpColVector c(3), x;
vpMatrix C(2, 3);
c = -2; c = -3; c = -4;
C = 3; C = 2; C = 1; d = 10;
C = 2; C = 5; C = 3; d = 15;
if(vpLinProg::solveLP(c, vpMatrix(0,0), vpColVector(0), C, d, x,
{{0,0},{1,0},{2,0}},
{{2,6}}))
{
std::cout << "x: " << x.t() << std::endl;
std::cout << "cost: " << c.t()*x << std::endl;
}
}