\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.4 - Linear and Quadratic Programming Solver
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Quadratic_program_from_mps< NT > Class Template Reference

#include <CGAL/QP_models.h>

Definition

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

\( \newcommand{\qprel}{\gtreqless} \newcommand{\qpx}{\mathbf{x}} \newcommand{\qpl}{\mathbf{l}} \newcommand{\qpu}{\mathbf{u}} \newcommand{\qpc}{\mathbf{c}} \newcommand{\qpb}{\mathbf{b}} \newcommand{\qpy}{\mathbf{y}} \newcommand{\qpw}{\mathbf{w}} \newcommand{\qplambda}{\mathbf{\lambda}} \)

\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. More...
 
int variable_index_by_name (const std::string &name) const
 returns the index of the variable with name name. More...
 
const std::string & constraint_name_by_index (int i) const
 returns the name of the \( i\)-th constraint. More...
 
int constraint_index_by_name (const std::string &name) const
 returns the index of the constraint with name name. More...
 
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. More...
 
void set_b (int i, const NT &val)
 sets the entry \( b_i\) of qp to val. More...
 
void set_r (int i, CGAL::Comparison_result rel)
 sets the entry \( \qprel_i\) of qp to rel. More...
 
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\). More...
 
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\). More...
 
void set_c (int j, const NT &val)
 sets the entry \( c_j\) of qp to val. More...
 
void set_c0 (const NT &val)
 sets the entry \( c_0\) of qp to val. More...
 
void set_d (int i, int j, const NT &val)
 sets the entries \( 2D_{ij}\) and \( 2D_{ji}\) of qp to val. More...
 

Member Function Documentation

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\).

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.
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 accomodate this entry.

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 accomodate this entry.

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 accomodate this entry.

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.

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 accomodate these entries.

Precondition
j <= i
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 accomodate this entry.

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 accomodate this entry.

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 accomodate this entry.

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\).

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.