LinProg¶

class LinProg¶

Bases: pybind11_object

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.

Methods

__init__
allClose	Check if \(\mathbf{A}\mathbf{x}\) is near \(\mathbf{b}\) .
allGreater	Check if all elements of \(\mathbf{x}\) are greater or equal to threshold.
allLesser	Overloaded function.
allZero	Check if all elements of \(x\) are near zero.
colReduction	Reduces the search space induced by an equality constraint.
rowReduction	Reduces the number of equality constraints.
simplex	Solves a Linear Program under simplex canonical form
solveLP	Solves a Linear Program under various constraints

Inherited Methods

Operators

__doc__
__init__
__module__

Attributes

__annotations__

__init__(*args, **kwargs)¶

static allClose(A: visp._visp.core.Matrix, x: visp._visp.core.ColVector, b: visp._visp.core.ColVector, tol: float = 1e-6) → bool¶

Check if \(\mathbf{A}\mathbf{x}\) is near \(\mathbf{b}\) .

Parameters:

A: visp._visp.core.Matrix¶

matrix (dimension m x n)

x: visp._visp.core.ColVector¶

vector (dimension n)

b: visp._visp.core.ColVector¶

vector (dimension m)

tol: float = 1e-6¶

tolerance

Returns:

True if \(\forall i, |\mathbf{A}_i\mathbf{x} - \mathbf{b}_i| < \text{~tol}\)

static allGreater(x: visp._visp.core.ColVector, thr: float = 1e-6) → bool¶

Check if all elements of \(\mathbf{x}\) are greater or equal to threshold.

Parameters:

x: visp._visp.core.ColVector¶

vector (dimension n)

thr: float = 1e-6¶

threshold

Returns:

True if \(\forall i, \mathbf{x}_i \geq \text{~thr}\)

static allLesser(*args, **kwargs)¶

Overloaded function.

1. allLesser(C: visp._visp.core.Matrix, x: visp._visp.core.ColVector, d: visp._visp.core.ColVector, thr: float = 1e-6) -> bool

Parameters:

C

matrix (dimension m x n)

x

vector (dimension n)

d

vector (dimension m)

thr

threshold

Returns:

True if \(\forall i, \mathbf{C}_i\mathbf{x} - \mathbf{d}_i \leq \text{~thr}\)

2. allLesser(x: visp._visp.core.ColVector, thr: float = 1e-6) -> bool

Check if all elements of \(\mathbf{x}\) are lesser or equal to threshold.

Parameters:

x

vector (dimension n)

thr

threshold

Returns:

True if \(\forall i, \mathbf{x}_i \leq \text{~thr}\)

static allZero(x: visp._visp.core.ColVector, tol: float = 1e-6) → bool¶

Check if all elements of \(x\) are near zero.

Parameters:

x: visp._visp.core.ColVector¶

vector to be checked

tol: float = 1e-6¶

tolerance

Returns:

True if \(\forall i, |\mathbf{x}_i| < \text{~tol}\)

static colReduction(A: visp._visp.core.Matrix, b: visp._visp.core.ColVector, full_rank: bool = false, tol: float = 1e-6) → bool¶

Reduces the search space induced by an equality constraint.

Changes A and b so that the constraint \(\mathbf{A}\mathbf{x} = \mathbf{b}\) can be written \(\exists\mathbf{z}, \mathbf{x} = \mathbf{b} + \mathbf{A}\mathbf{z}\)

This method is destructive for A and b.

Here is an example with \(\mathbf{A} = \left[\begin{array}{cccc}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\1 & 1& 0 & 0\end{array}\right]\) and \(\mathbf{b} = \left[\begin{array}{c}1\\2\\3\end{array}\right]\) that become \(\mathbf{A} = \left[\begin{array}{cc}0 & 0\\0 & 0\\1& 0\\0& 1\end{array}\right]\) and \(\mathbf{b} = \left[\begin{array}{c}1\\2\\0\\0\end{array}\right]\) .

We indeed have \(\forall \mathbf{z}\in\mathbb{R}^2, \left[\begin{array}{cccc}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\1 & 1& 0 & 0\end{array}\right] \left(\left[\begin{array}{c}1\\2\\0\\0\end{array}\right] + \left[\begin{array}{cc}0 & 0\\0 & 0\\1& 0\\0& 1\end{array}\right]\mathbf{z}\right) = \left[\begin{array}{c}1\\2\\3\end{array}\right]\)

#include <visp3/core/vpLinProg.h>

int main()
{
  vpMatrix A(3,4);
  vpColVector b(3);
  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;

  if(vpLinProg::colReduction(Z, x1))
  {
    // Z is now 4 x 2
    // try with random z-vector
    vpColVector z(2);
    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";
}

Parameters:

A: visp._visp.core.Matrix¶

in = equality matrix (dimension m x n), out = projector to kernel (dimension n x (n-rank(A)))

b: visp._visp.core.ColVector¶

in = equality vector (dimension m), out = particular solution (dimension n)

full_rank: bool = false¶

if we think A is full rank, leads to a faster result but a slower one if A is actually not full rank.

tol: float = 1e-6¶

tolerance to test the ranks

Returns:

True if \(\mathbf{A}\mathbf{x} = \mathbf{b}\) has a solution.

static rowReduction(A: visp._visp.core.Matrix, b: visp._visp.core.ColVector, tol: float = 1e-6) → bool¶

Reduces the number of equality constraints.

Changes A and b so that the constraint \(\mathbf{A}\mathbf{x} = \mathbf{b}\) is written with minimal rows.

This method is destructive for A and b.

Here is an example with \(\mathbf{A} = \left[\begin{array}{cccc}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\1 & 1& 0 & 0\end{array}\right]\) and \(\mathbf{b} = \left[\begin{array}{c}0\\0\\0\end{array}\right]\) (feasible) or \(\mathbf{b} = \left[\begin{array}{c}0\\0\\1\end{array}\right]\) (not feasible).

#include <visp3/core/vpLinProg.h>

int main()
{
  vpMatrix A(3,4);
  vpColVector b(3);

  A[0][0] = A[1][1] = 1;
  A[2][0] = A[2][1] = 1;

  // b[2] = 1;    // uncomment to make it unfeasible

  if(vpLinProg::rowReduction(A, b))
    std::cout << A << std::endl; // A is now 2x4
  else
    std::cout << "Ax = b not feasible\n";
}

Parameters:

A: visp._visp.core.Matrix¶

equality matrix (dimension in = (m x n), out = (rank(A) x n)

b: visp._visp.core.ColVector¶

equality vector (dimension in = (m), out = (rank(A)))

tol: float = 1e-6¶

tolerance to test the ranks

Returns:

True if \(\mathbf{A}\mathbf{x} = \mathbf{b}\) has a solution.

static simplex(c: visp._visp.core.ColVector, A: visp._visp.core.Matrix, b: visp._visp.core.ColVector, x: visp._visp.core.ColVector, tol: float = 1e-6) → bool¶

Solves a Linear Program under simplex canonical form

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:

\(\begin{array}{lll} (x,y,z) = & \arg\min & -2x -3y -4z\\& \text{s.t.}& 3x + 2y + z \leq 10\\& \text{s.t.}& 2x + 5y + 3z \leq 15\\& \text{s.t.}& x, y, z \geq 0\end{array}\)

That can be re-written as:

\(\begin{array}{lll} (x,y,z), (s_1, s_2) = & \arg\min & -2x -3y -4z\\& \text{s.t.}& 3x + 2y + z + s_1 = 10\\& \text{s.t.}& 2x + 5y + 3z + s_2 = 15\\& \text{s.t.}& x, y, z, s_1, s_2 \geq 0\end{array}\)

#include <visp3/core/vpLinProg.h>

int main()
{
  vpColVector c(5), x;
  vpMatrix A(2, 5);
  vpColVector b(2);
  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;
  }
}

Note

See solveLP

Parameters:

c: visp._visp.core.ColVector¶

cost vector (dimension n)

A: visp._visp.core.Matrix¶

equality matrix (dimension m x n)

b: visp._visp.core.ColVector¶

equality vector (dimension m)

x: visp._visp.core.ColVector¶

in: feasible point if any, out: solution (dimension n)

tol: float = 1e-6¶

tolerance to test the ranks

Returns:

True if the solution was found.

static solveLP(c: visp._visp.core.ColVector, A: visp._visp.core.Matrix, b: visp._visp.core.ColVector, C: visp._visp.core.Matrix, d: visp._visp.core.ColVector, x: visp._visp.core.ColVector, l: list[tuple[int, float]], u: list[tuple[int, float]], tol: float = 1e-6) → bool¶

Solves a Linear Program under various constraints

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:

\(\begin{array}{lll} (x,y,z) = & \arg\min & -2x -3y -4z\\& \text{s.t.}& 3x + 2y + z \leq 10\\& \text{s.t.}& 2x + 5y + 3z \leq 15\\& \text{s.t.}& x, y, z \geq 0\\& \text{s.t.}& z \leq 6\end{array}\)

#include <visp3/core/vpLinProg.h>

int main()
{
  vpColVector c(3), x;
  vpMatrix C(2, 3);
  vpColVector d(2);
  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;
  }
}

Note

See BoundedIndex

Parameters:

c: visp._visp.core.ColVector¶

cost vector (dimension n)

A: visp._visp.core.Matrix¶

equality matrix (dimension m x n)

b: visp._visp.core.ColVector¶

equality vector (dimension m)

C: visp._visp.core.Matrix¶

inequality matrix (dimension p x n)

d: visp._visp.core.ColVector¶

inequality vector (dimension p)

x: visp._visp.core.ColVector¶

in: feasible point if any, out: solution (dimension n)

l: list[tuple[int, float]]¶

lower bounds (if any)

u: list[tuple[int, float]]¶

upper bounds (if any)

tol: float = 1e-6¶

tolerance to test the ranks

Returns:

True if the solution was found.