CGAL 6.1 - Linear and Quadratic Programming Solver

Loading...
Searching...
No Matches
List of all members
CGAL::Quadratic_program_from_mps< NT > Class Template Reference
Reference Manual » Classes

`#include <CGAL/QP_models.h>`

## Definition

template<typename NT>
class CGAL::Quadratic_program_from_mps< NT >

An object of class `Quadratic_program_from_mps` describes a convex quadratic program of the general form.

\begin{eqnarray*} \mbox{(QP)}& \mbox{minimize} & \qpx^{T}D\qpx+\qpc^{T}\qpx+c_0 \\ &\mbox{subject to} & A\qpx\qprel \qpb, \\ & & \qpl \leq \qpx \leq \qpu \end{eqnarray*}

in \( n\) real variables \( \qpx=(x_0,\ldots,x_{n-1})\).

Here,

- \( A\) is an \( m\times n\) matrix (the constraint matrix),
- \( \qpb\) is an \( m\)-dimensional vector (the right-hand side),

- \( \qprel\) is an \( m\)-dimensional vector of relations from \( \{\leq, =, \geq\}\),

- \( \qpl\) is an \( n\)-dimensional vector of lower bounds for \( \qpx\), where \( l_j\in\mathbb{R}\cup\{-\infty\}\) for all \( j\)

- \( \qpu\) is an \( n\)-dimensional vector of upper bounds for \( \qpx\), where \( u_j\in\mathbb{R}\cup\{\infty\}\) for all \( j\)

- \( D\) is a symmetric positive-semidefinite \( n\times n\) matrix (the quadratic objective function),

- \( \qpc\) is an \( n\)-dimensional vector (the linear objective function), and

- \( c_0\) is a constant.

If \( D=0\), the program is a linear program; if the variable bounds are \( x\geq 0\), we have a nonnegative program.

The program data are read from an input stream in `MPSFormat`. This is a commonly used format for encoding linear and quadratic programs that is understood by many solvers. All values are expected to be readable into type `NT`. The constructed program can be further manipulated by using the set-methods below.

Is model of
  `QuadraticProgram`
  `LinearProgram`
  `NonnegativeQuadraticProgram`
  `NonnegativeLinearProgram`

Example

QP_solver/first_qp_from_mps.cpp

QP_solver/first_lp_from_mps.cpp

QP_solver/first_nonnegative_qp_from_mps.cpp

QP_solver/first_nonnegative_lp_from_mps.cpp

See also
  `Quadratic_program<NT>`
  `Quadratic_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it>`
  `Linear_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, C_it>`
  `Nonnegative_quadratic_program_from_iterators<A_it, B_it, R_it, D_it, C_it>`
  `Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it>`

Examples
  QP_solver/cycling.cpp, QP_solver/first_lp_from_mps.cpp, QP_solver/first_nonnegative_lp_from_mps.cpp, QP_solver/first_nonnegative_qp_from_mps.cpp, and QP_solver/first_qp_from_mps.cpp.

## Types
typedef unspecified_type | NT
| The number type of the program entries.

## Creation
| Quadratic_program_from_mps (std::istream &in)
| reads `qp` from the input stream `in`.

## Operations
bool | is_valid () const
| returns `true` if and only if an MPS-encoded quadratic program could be extracted from the input stream.
const std::string & | get_error () const
| if !`qp``.is_valid()`, this method returns an error message explaining why the input does not conform to the `MPSFormat`.
const std::string & | variable_name_by_index (int j) const
| returns the name of the \( j\)-th variable.
int | variable_index_by_name (const std::string &name) const
| returns the index of the variable with name `name`.
const std::string & | constraint_name_by_index (int i) const
| returns the name of the \( i\)-th constraint.
int | constraint_index_by_name (const std::string &name) const
| returns the index of the constraint with name `name`.
bool | is_linear () const
| returns `true` if and only if `qp` is a linear program.
bool | is_nonnegative () const
| returns `true` if and only if `qp` is a nonnegative program.
void | set_a (int j, int i, const NT &val)
| sets the entry \( A_{ij}\) in column \( j\) and row \( i\) of the constraint matrix \( A\) of `qp` to `val`.
void | set_b (int i, const NT &val)
| sets the entry \( b_i\) of `qp` to `val`.
void | set_r (int i, CGAL::Comparison_result rel)
| sets the entry \( \qprel_i\) of `qp` to `rel`.
void | set_l (int j, bool is_finite, const NT &val=NT(0))
| if `is_finite`, this sets the entry \( l_j\) of `qp` to `val`, otherwise it sets \( l_j\) to \( -\infty\).
void | set_u (int j, bool is_finite, const NT &val=NT(0))
| if `is_finite`, this sets the entry \( u_j\) of `qp` to `val`, otherwise it sets \( u_j\) to \( \infty\).
void | set_c (int j, const NT &val)
| sets the entry \( c_j\) of `qp` to `val`.
void | set_c0 (const NT &val)
| sets the entry \( c_0\) of `qp` to `val`.
void | set_d (int i, int j, const NT &val)
| sets the entries \( 2D_{ij}\) and \( 2D_{ji}\) of `qp` to `val`.

## Member Function Documentation

## ◆ constraint_index_by_name()

template<typename NT >

int CGAL::Quadratic_program_from_mps< NT >::constraint_index_by_name | ( | const std::string & | name | ) | const

returns the index of the constraint with name `name`.

If there is no constraint with this name, the result is \( -1\).

## ◆ constraint_name_by_index()

template<typename NT >

const std::string & CGAL::Quadratic_program_from_mps< NT >::constraint_name_by_index | ( | int | i | ) | const

returns the name of the \( i\)-th constraint.

Precondition
  \( i\) must not refer to a constraint that has been added later, using one of the set methods below.

## ◆ set_a()

template<typename NT >

void CGAL::Quadratic_program_from_mps< NT >::set_a | ( | int | j,
|  | int | i,
|  | const NT & | val
| ) |  |

sets the entry \( A_{ij}\) in column \( j\) and row \( i\) of the constraint matrix \( A\) of `qp` to `val`.

An existing entry is overwritten. `qp` is enlarged if necessary to accommodate this entry.

## ◆ set_b()

template<typename NT >

void CGAL::Quadratic_program_from_mps< NT >::set_b | ( | int | i,
|  | const NT & | val
| ) |  |

sets the entry \( b_i\) of `qp` to `val`.

An existing entry is overwritten. `qp` is enlarged if necessary to accommodate this entry.

## ◆ set_c()

template<typename NT >

void CGAL::Quadratic_program_from_mps< NT >::set_c | ( | int | j,
|  | const NT & | val
| ) |  |

sets the entry \( c_j\) of `qp` to `val`.

An existing entry is overwritten. `qp` is enlarged if necessary to accommodate this entry.

## ◆ set_c0()

template<typename NT >

void CGAL::Quadratic_program_from_mps< NT >::set_c0 | ( | const NT & | val | ) |

sets the entry \( c_0\) of `qp` to `val`.

An existing entry is overwritten.

## ◆ set_d()

template<typename NT >

void CGAL::Quadratic_program_from_mps< NT >::set_d | ( | int | i,
|  | int | j,
|  | const NT & | val
| ) |  |

sets the entries \( 2D_{ij}\) and \( 2D_{ji}\) of `qp` to `val`.

Existing entries are overwritten. `qp` is enlarged if necessary to accommodate these entries.

Precondition
  `j <= i`

## ◆ set_l()

template<typename NT >

void CGAL::Quadratic_program_from_mps< NT >::set_l | ( | int | j,
|  | bool | is_finite,
|  | const NT & | val = `NT(0)`
| ) |  |

if `is_finite`, this sets the entry \( l_j\) of `qp` to `val`, otherwise it sets \( l_j\) to \( -\infty\).

An existing entry is overwritten. `qp` is enlarged if necessary to accommodate this entry.

## ◆ set_r()

template<typename NT >

void CGAL::Quadratic_program_from_mps< NT >::set_r | ( | int | i,
|  | CGAL::Comparison_result | rel
| ) |  |

sets the entry \( \qprel_i\) of `qp` to `rel`.

`CGAL::SMALLER` means that the \( i\)-th constraint is of type "\f$ \leq\f$", `CGAL::EQUAL` means "\f$ =\f$", and `CGAL::LARGER` encodes "\f$ \geq\f$". An existing entry is overwritten. `qp` is enlarged if necessary to accommodate this entry.

## ◆ set_u()

template<typename NT >

void CGAL::Quadratic_program_from_mps< NT >::set_u | ( | int | j,
|  | bool | is_finite,
|  | const NT & | val = `NT(0)`
| ) |  |

if `is_finite`, this sets the entry \( u_j\) of `qp` to `val`, otherwise it sets \( u_j\) to \( \infty\).

An existing entry is overwritten. `qp` is enlarged if necessary to accommodate this entry.

## ◆ variable_index_by_name()

template<typename NT >

int CGAL::Quadratic_program_from_mps< NT >::variable_index_by_name | ( | const std::string & | name | ) | const

returns the index of the variable with name `name`.

If there is no variable with this name, the result is \( -1\).

## ◆ variable_name_by_index()

template<typename NT >

const std::string & CGAL::Quadratic_program_from_mps< NT >::variable_name_by_index | ( | int | j | ) | const

returns the name of the \( j\)-th variable.

Precondition
  \( j\) must not refer to a variable that has been added later, using one of the set methods below.