Visual Servoing Platform  version 3.6.1 under development (2024-03-04)
vpLinProg Class Reference

#include <visp3/core/vpLinProg.h>

## Public Types

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

## Static Public Member Functions

Solvers <br>
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 <br>
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 <br>
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 61 of file vpLinProg.h.

## ◆ BoundedIndex

 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 explicitly while the upper one is built during the call to solveLP():

#include <visp3/core/vpLinProg.h>
int main()
{
vpColVector c(3), x;
vpMatrix C(2, 3);
c[0] = -2; c[1] = -3; c[2] = -4;
C[0][0] = 3; C[0][1] = 2; C[0][2] = 1; d[0] = 10;
C[1][0] = 2; C[1][1] = 5; C[1][2] = 3; d[1] = 15;
// build lower bounds explicitly 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;
}
}
Implementation of column vector and the associated operations.
Definition: vpColVector.h:163
vpRowVector t() const
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)
Definition: vpLinProg.cpp:342
std::pair< unsigned int, double > BoundedIndex
Definition: vpLinProg.h:114
Implementation of a matrix and operations on matrices.
Definition: vpMatrix.h:146
vpColVector t() const
solveLP()

Definition at line 114 of file vpLinProg.h.

## ◆ allClose()

 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 163 of file vpLinProg.h.

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

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

## ◆ allGreater()

 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 215 of file vpLinProg.h.

References vpArray2D< Type >::getRows().

## ◆ allLesser() [1/2]

 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 198 of file vpLinProg.h.

References vpArray2D< Type >::getRows().

## ◆ allLesser() [2/2]

 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 181 of file vpLinProg.h.

References vpMatrix::getRow().

## ◆ allZero()

 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 144 of file vpLinProg.h.

References vpArray2D< Type >::getRows().

## ◆ colReduction()

 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[0][0] = A[1][1] = 1;
A[2][0] = A[2][1] = 1;
b[0] = 1; b[1] = 2; b[2] = 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[0] = (10.*rand())/RAND_MAX;
z[1] = (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";
}
static bool colReduction(vpMatrix &A, vpColVector &b, bool full_rank=false, const double &tol=1e-6)
Definition: vpLinProg.cpp:97

Definition at line 97 of file vpLinProg.cpp.

## ◆ rowReduction()

 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[0][0] = A[1][1] = 1;
A[2][0] = A[2][1] = 1;
// b[2] = 1; // uncomment to make it unfeasible
std::cout << A << std::endl; // A is now 2x4
else
std::cout << "Ax = b not feasible\n";
}
static bool rowReduction(vpMatrix &A, vpColVector &b, const double &tol=1e-6)
Definition: vpLinProg.cpp:248

Definition at line 248 of file vpLinProg.cpp.

Referenced by simplex().

## ◆ 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[0] = -2; c[1] = -3; c[2] = -4;
A[0][0] = 3; A[0][1] = 2; A[0][2] = 1; b[0] = 10;
A[1][0] = 2; A[1][1] = 5; A[1][2] = 3; b[1] = 15;
A[0][3] = A[1][4] = 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;
}
}
static bool simplex(const vpColVector &c, vpMatrix A, vpColVector b, vpColVector &x, const double &tol=1e-6)
Definition: vpLinProg.cpp:543
vpRowVector extract(unsigned int c, unsigned int rowsize) const
Definition: vpRowVector.h:179
solveLP

Definition at line 543 of file vpLinProg.cpp.

## ◆ solveLP()

 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[0] = -2; c[1] = -3; c[2] = -4;
C[0][0] = 3; C[0][1] = 2; C[0][2] = 1; d[0] = 10;
C[1][0] = 2; C[1][1] = 5; C[1][2] = 3; d[1] = 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;
}
}