A model of NonnegativeLinearProgram describes a linear program of the 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} &\qpc^{T}\qpx+c_0 \\ &\mbox{subject to} & A\qpx\qprel \qpb, \\ & & \qpx \geq 0 \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\}$,
• $\qpc$ is an $n$-dimensional vector (the linear objective function), and
• $c_0$ is a constant.

The description is given by appropriate random-access iterators over the program data, see below. The program therefore comes in dense representation which includes zero entries.

Has Models:

CGAL::Quadratic_program<NT>

CGAL::Quadratic_program_from_mps<NT>

CGAL::Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, FL_it, L_it, FU_it, U_it, D_it, C_it>

CGAL::Quadratic_program_from_mps<NT>

CGAL::Nonnegative_linear_program_from_iterators<A_it, B_it, R_it, C_it>

Requires:

The value types of all iterator types (nested iterator types, respectively, for A_iterator) must be convertible to some common IntegralDomain ET.

Has Models:

CGAL::Quadratic_program<NT>

See Also

QuadraticProgram

LinearProgram

NonnegativeQuadraticProgram