CGAL 5.5 - CGAL and Solvers
LinearProgramTraits Concept Reference

Definition

A concept that describes the set of methods used to define and solve a linear programming (lp) problem of the general form:

\begin{eqnarray*} & \mbox{minimize} & \mathbf{q}^{T}\mathbf{x} + r \\ & \mbox{subject to} & \mathbf{l} \leq A\mathbf{x} \leq \mathbf{u} \end{eqnarray*}

in \( n \) real variables \( \mathbf{x} = (x_0, \ldots, x_{n-1}) \) and \( m \) constraints.

Here,

  • \( \mathbf{q} \) is an \( n \)-dimensional vector (the linear objective function),
  • \( r \) is a constant,
  • \( A \) is an \( m\times n\) matrix (the constraint matrix),
  • \( \mathbf{l} \) is an \( m \)-dimensional vector of lower constraint bounds, where \( l_i \in \mathbb{R} \cup \{-\infty\} \) for all \( i \),
  • \( \mathbf{u} \) is an \( m \)-dimensional vector of upper constraint bounds, where \( u_i \in \mathbb{R} \cup \{+\infty\} \) for all \( i \).

Memory

void resize (const std::size_t n, const std::size_t m)
 Allocates memory for n variables and m constraints in lp.
 

Initialization

void set_q (const std::size_t i, const FT value)
 Sets the entry qi of lp to value.
 
void set_r (const FT value)
 Sets the entry r of lp to value.
 
void set_A (const std::size_t i, const std::size_t j, const FT value)
 Sets the entry Aij in the row i and column j of the constraint matrix A of lp to value.
 
void set_l (const std::size_t i, const FT value)
 Sets the entry li of lp to value.
 
void set_u (const std::size_t i, const FT value)
 Sets the entry ui of lp to value.
 

Solution

template<typename OutIterator >
bool solve (OutIterator solution)
 solves the linear program. More...
 

Member Function Documentation

◆ solve()

template<typename OutIterator >
bool LinearProgramTraits::solve ( OutIterator  solution)

solves the linear program.

Number of values in solution equals to the number n of values in the vector x.

Template Parameters
OutIteratora model of OutputIterator that accepts values of type FieldNumberType
Parameters
solutionan output iterator with the solution
Returns
a status of the computation success == true