CGAL 6.1.1 - CGAL and Solvers

Loading...
Searching...
No Matches
List of all members
LinearProgramTraits Concept Reference
Reference Manual » Concepts

## 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.

## 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

  OutIterator | a model of `OutputIterator` that accepts values of type `FieldNumberType`

Parameters

  solution | an output iterator with the solution

Returns
  a status of the computation `success == true`