CGAL 5.1.2 - Linear and Quadratic Programming Solver
|
#include <CGAL/QP_models.h>
An object of class Quadratic_program
describes a convex quadratic program of the 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,
\( \qprel\) is an \( m\)-dimensional vector of relations from \( \{\leq, =, \geq\}\),
\( \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),
\( 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.
This class allows you to build your program entry by entry, using the set-methods below.
If you only need to wrap existing (random-access) iterators over your own data, then you may use any of the four models 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>
, and Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it>
.
If you want to read a quadratic program in MPSFormat
from a stream, please use the model Quadratic_program_from_mps<NT>
.
Example
QP_solver/first_nonnegative_qp.cpp
QP_solver/first_nonnegative_lp.cpp
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>
Quadratic_program_from_mps<NT>
Types | |
typedef unspecified_type | NT |
The number type of the program entries. | |
Creation | |
Quadratic_program (CGAL::Comparison_result default_r=CGAL::EQUAL, bool default_fl=true, const NT &default_l=0, bool default_fu=false, const NT &default_u=0) | |
constructs a quadratic program with no variables and no constraints, ready for data to be added. More... | |
Operations | |
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... | |
CGAL::Quadratic_program< NT >::Quadratic_program | ( | CGAL::Comparison_result | default_r = CGAL::EQUAL , |
bool | default_fl = true , |
||
const NT & | default_l = 0 , |
||
bool | default_fu = false , |
||
const NT & | default_u = 0 |
||
) |
constructs a quadratic program with no variables and no constraints, ready for data to be added.
Unless relations are explicitly set, they will be of type default_r
. Unless bounds are explicitly set, they will be as specified by default_fl
(finite lower bound?), default_l
(lower bound value if lower bound is finite), default_fu
(finite upper bound?), and default_l
(upper bound value if upper bound is finite). If all parameters take their default values, we thus get equality constraints and bounds \( x\geq0\) by default. Numerical entries that are not explicitly set will default to \( 0\).
default_fl == default_fu == true
, then default_l <= default_u
. void CGAL::Quadratic_program< 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.
void CGAL::Quadratic_program< 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.
void CGAL::Quadratic_program< 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.
void CGAL::Quadratic_program< NT >::set_c0 | ( | const NT & | val | ) |
sets the entry \( c_0\) of qp
to val
.
An existing entry is overwritten.
void CGAL::Quadratic_program< 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.
j <= i
void CGAL::Quadratic_program< 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.
void CGAL::Quadratic_program< 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.
void CGAL::Quadratic_program< 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.