naginterfaces.library.mip.iqp_​dense

naginterfaces.library.mip.iqp_dense(bl, bu, h, intvar, xs, strtgy, comm, a=None, cvec=None, qphess=None, mdepth=None, istate=None, monit=None, data=None, io_manager=None)

iqp_dense solves general quadratic programming problems with integer constraints on the variables. It is not intended for large sparse problems.

Note: this function uses optional algorithmic parameters, see also: iqp_dense_optfile(), iqp_dense_optstr().

For full information please refer to the NAG Library document for h02cb

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/h/h02cbf.html

Parameters

blfloat, array-like, shape $(n+\text{nclin})$

$bl$ must contain the lower bounds and $bu$ the upper bounds, for all the constraints in the following order. The first $n$ elements of each array must contain the bounds on the variables, and the next $m_L$ elements the bounds for the general linear constraints (if any). To specify a nonexistent lower bound (i.e., $l_j=-\infty$), set $bl\left[j\right]\le -\text{bigbnd}$, and to specify a nonexistent upper bound (i.e., $u_j=+\infty$), set $bu\left[j\right]\ge \text{bigbnd}$; the default value of $\text{bigbnd}$ is ${10}^{20}$, but this may be changed by the ‘Infinite Bound Size’. To specify the $j$th constraint as an equality, set $bl\left[j\right]=bu\left[j\right]=\beta$, say, where $\left|\beta \right|<\text{bigbnd}$.

bufloat, array-like, shape $(n+\text{nclin})$

$bl$ must contain the lower bounds and $bu$ the upper bounds, for all the constraints in the following order. The first $n$ elements of each array must contain the bounds on the variables, and the next $m_L$ elements the bounds for the general linear constraints (if any). To specify a nonexistent lower bound (i.e., $l_j=-\infty$), set $bl\left[j\right]\le -\text{bigbnd}$, and to specify a nonexistent upper bound (i.e., $u_j=+\infty$), set $bu\left[j\right]\ge \text{bigbnd}$; the default value of $\text{bigbnd}$ is ${10}^{20}$, but this may be changed by the ‘Infinite Bound Size’. To specify the $j$th constraint as an equality, set $bl\left[j\right]=bu\left[j\right]=\beta$, say, where $\left|\beta \right|<\text{bigbnd}$.

hfloat, array-like, shape $(:,:)$

May be used to store the quadratic term $H$ of the QP objective function if desired. In some cases, you need not use $h$ to store $H$ explicitly (see the specification of $qphess$). The elements of $h$ are referenced only by $qphess$. The number of rows of $H$ is denoted by $m$, whose default value is $n$. (The ‘Hessian Rows’ may be used to specify a value of $m<n$.)

If the default version of $qphess$ is used and the problem is of type QP1 or QP2 (the default), the first $m$ rows and columns of $h$ must contain the leading $m\times m$ rows and columns of the symmetric Hessian matrix $H$.

Only the diagonal and upper triangular elements of the leading $m$ rows and columns of $h$ are referenced.

The remaining elements need not be assigned.

If the default version of $qphess$ is used and the problem is of type QP3 or QP4, the first $m$ rows of $h$ must contain an $m\times n$ upper trapezoidal factor of the symmetric Hessian matrix $H^{T}H$.

The factor need not be of full rank, i.e., some of the diagonal elements may be zero.

However, as a general rule, the larger the dimension of the leading nonsingular sub-matrix of $h$, the fewer iterations will be required.

Elements outside the upper trapezoidal part of the first $m$ rows of $h$ need not be assigned.

In other situations, it may be desirable to compute $Hx$ or $H^{T}Hx$ without accessing $h$ – for example, if $H$ or $H^{T}H$ is sparse or has special structure.

The arguments $h$ and $\text{ldh}$ may then refer to any convenient array.

If the problem is of type FP or LP, $h$ is not referenced.

intvarint, array-like, shape $\left(\text{lintvr}\right)$

$intvar\left[i\right]$ must contain the index of the solution vector $x$ which is required to be integer. For example, if $x_1$ and $x_3$ are constrained to take integer values then $intvar\left[0\right]$ might be set to $1$ and $intvar\left[1\right]$ to $3$. The order in which the indices are specified is important, since this determines the order in which the sub-problems are generated. As a rule-of-thumb, the important variables should always be specified first. Thus, in the above example, if $x_3$ relates to a more important quantity than $x_1$, then it might be advantageous to set $intvar\left[0\right]=3$ and $intvar\left[1\right]=1$. If $k$ is the smallest integer such that $intvar\left[k\right]$ is less than or equal to zero then iqp_dense assumes that $k-1$ variables are constrained to be integer; components $intvar[k+1]$, $\dots$, $intvar[\text{lintvr}-1]$ are not referenced.

xsfloat, array-like, shape $\left(n\right)$

An initial estimate of the solution.

strtgyint

Determines a branching strategy to be used throughout the computation, as follows:

$strtgy$	Meaning
$0$	Always left branch first, i.e., impose an upper bound constraint on the variable first.
$1$	Always right branch first, i.e., impose a lower bound constraint on the variable first.
$2$	Branch towards the nearest integer, i.e., if $x_k=2.4$ then impose an upper bound constraint $x_k\le 2$, whereas if $x_k=2.6$ then impose the lower bound constraint $x_k\ge 3.0$.
$3$	A random choice is made between a left-hand and a right-hand branch.

commdict, communication object, modified in place

Communication structure.

This argument must have been initialized by a prior call to opt.nlp1_init with $\text{rname}=\text{'opt.qp\_dense\_solve'}$.

aNone or float, array-like, shape $(\text{nclin},:)$, optional

Note: the required extent for this argument in dimension 2 is determined as follows: if $\text{nclin}>0$: $n$; if $\text{nclin}=0$: $1$; otherwise: $0$.

The $\text{i}$th row of $a$ must contain the coefficients of the $\text{i}$th general linear constraint, for $\text{i}=1,2,\dots ,m_L$.

cvecNone or float, array-like, shape $\left(n\right)$, optional

The coefficients of the explicit linear term of the objective function when the problem is of type LP, QP2 (the default) and QP4.

If the problem is of type FP, QP1, or QP3, $cvec$ is not referenced.

qphessNone or callable hx = qphess(jthcol, h, x, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

In general, you need not provide a version of $qphess$, because supplying None will cause a ‘default’ function to be used.

However, the algorithm of iqp_dense requires only the product of $H$ or $H^{T}H$ and a vector $x$; and in some cases you may obtain increased efficiency by providing a version of $qphess$ that avoids the need to define the elements of the matrices $H$ or $H^{T}H$ explicitly. $qphess$ is not referenced if the problem is of type FP or LP, in which case $qphess$ may be None.

Parameters

jthcolint

Specifies whether or not the vector $x$ is a column of the identity matrix.

$jthcol=j>0$

The vector $x$ is the $j$th column of the identity matrix, and hence $Hx$ or $h^{T}Hx$ is the $j$th column of $h$ or $h^{T}H$, respectively, which may in some cases require very little computation and $qphess$ may be coded to take advantage of this. However special code is not necessary because $x$ is always stored explicitly in the array $x$.

$jthcol=0$

$x$ has no special form.

hfloat, ndarray, shape $(:,:)$

This is the same argument $\text{h}$ as supplied to iqp_dense.

xfloat, ndarray, shape $\left(n\right)$

The vector $x$.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

hxfloat, array-like, shape $\left(n\right)$

The product $Hx$ if the problem is of type QP1 or QP2 (the default), or the product $h^{T}Hx$ if the problem is of type QP3 or QP4.

mdepthNone or int, optional

Note: if this argument is None then a default value will be used, determined as follows: $3\times n/2$.

The maximum depth (i.e., number of extra constraints) that iqp_dense may insert before admitting failure.

istateNone or int, array-like, shape $(n+\text{nclin})$, optional

Need not be set if the (default) option ‘Cold Start’ is used.

If the option ‘Warm Start’ has been chosen, $istate$ specifies the desired status of the constraints at the start of the feasibility phase.

More precisely, the first $n$ elements of $istate$ refer to the upper and lower bounds on the variables, and the next $m_L$ elements refer to the general linear constraints (if any).

Possible values for $istate\left[j\right]$ are as follows:

$istate\left[j\right]$	Meaning
0	The corresponding constraint should not be in the initial working set.
1	The constraint should be in the initial working set at its lower bound.
2	The constraint should be in the initial working set at its upper bound.
3	The constraint should be in the initial working set as an equality. This value must not be specified unless $bl\left[j\right]=bu\left[j\right]$.

The values $-2$, $-1$ and $4$ are also acceptable but will be reset to zero by the function.

If iqp_dense has been called previously with the same values of $\text{n}$ and $\text{nclin}$, $istate$ already contains satisfactory information. (See also the description of the option ‘Warm Start’.) The function also adjusts (if necessary) the values supplied in $xs$ to be consistent with $istate$.

monitNone or callable (bstval, halt, count) = monit(intfnd, nodes, depth, obj, x, bstval, bstsol, bl, bu, halt, count, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

$monit$ may be used to print out intermediate output and to affect the course of the computation.

Specifically, it allows you to specify a realistic value for the cut-off value (see Notes) and to terminate the algorithm.

If you do not require any intermediate output, have no estimate of the cut-off value and require an exhaustive tree search then $monit$ may be None.

Parameters

intfndint

Specifies the number of integer solutions obtained so far.

nodesint

Specifies the number of nodes (sub-problems) solved so far.

depthint

Specifies the depth in the tree of sub-problems the algorithm has now reached.

objfloat

Specifies the value of the objective function of the end of the latest sub-problem.

xfloat, ndarray, shape $\left(n\right)$

Specifies the values of the independent variables at the end of the latest sub-problem.

bstvalfloat

Normally specifies the value of the best integer solution found so far.

bstsolfloat, ndarray, shape $\left(n\right)$

Specifies the solution vector which gives rise to the best integer solution value so far discovered.

blfloat, ndarray, shape $\left(n\right)$

$bl\left[i\right]$ specifies the current lower bounds on the variable $x_i$.

bufloat, ndarray, shape $\left(n\right)$

$bu\left[i\right]$ specifies the current upper bounds on the variable $x_i$.

haltbool

Will have the value $False$.

countint

Unchanged from previous call.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

bstvalfloat

May be set to a cut-off value if you are an experienced user as follows. Before an integer solution has been found $bstval$ will be set by iqp_dense to the largest machine representable number (see machine.real_largest). If you know that the solution being sought is a much smaller number, then $bstval$ may be set to this number as a cut-off value (see Notes). Beware of setting $bstval$ too small, since then no integer solutions will be discovered. Also, on entry to $monit$, $bstval$ should be set using a statement of the form

if intfnd == 0: bstval = cut_off_value

Setting $bstval$ in this way will not prevent the normal operation of the algorithm when subsequent integer solutions are found. It would be a grievous mistake to unconditionally set $bstval$ and if you have any doubts whatsoever about the correct use of this argument then you are strongly recommended to leave it unchanged.

haltbool

If $halt$ is set to $True$, opt.qp_dense_solve will be brought to a halt with $errno$ = -1. This facility may be useful if you are content with any integer solution, or with any integer solution that fits certain criteria. Under these circumstances setting $halt=True$ can save considerable unnecessary computation.

countint

May be used by you to save the last value of $intfnd$. If a subsequent call of $monit$ has a value of $intfnd$ which is greater than $count$, then you know that a new integer solution has been found at this node.

dataarbitrary, optional

User-communication data for callback functions.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

istateint, ndarray, shape $(n+\text{nclin})$

The status of the constraints in the working set at the point returned in $xs$. The significance of each possible value of $istate\left[j\right]$ is as follows:

$istate\left[j\right]$	Meaning
$-2$	The constraint violates its lower bound by more than the feasibility tolerance.
$-1$	The constraint violates its upper bound by more than the feasibility tolerance.
$0$	The constraint is satisfied to within the feasibility tolerance, but is not in the working set.
$1$	This inequality constraint is included in the working set at its lower bound.
$2$	This inequality constraint is included in the working set at its upper bound.
$3$	This constraint is included in the working set as an equality. This value of $istate$ can occur only when $bl\left[j\right]=bu\left[j\right]$.
$4$	This corresponds to optimality being declared with $xs\left[j\right]$ being temporarily fixed at its current value. This value of $istate$ can occur only when $errno$ = 1 on exit.

xsfloat, ndarray, shape $\left(n\right)$

The point at which iqp_dense terminated. If the function exits successfully or $errno$ = 1 or 3, $xs$ contains an estimate of the solution.

objfloat

The value of the objective function at $x$ if $x$ is feasible, or the sum of infeasibilities at $x$ otherwise. If the problem is of type FP and $x$ is feasible, $obj$ is set to zero.

axNone or float, ndarray, shape $(max(1,\text{nclin}))$

The final values of the linear constraints $Ax$.

clamdafloat, ndarray, shape $(n+\text{nclin})$

The values of the Lagrange-multipliers for each constraint with respect to the current working set. The first $n$ elements contain the multipliers for the bound constraints on the variables, and the next $m_L$ elements contain the multipliers for the general linear constraints (if any). If $istate\left[j\right]=0$ (i.e., constraint $j$ is not in the working set), $clamda\left[j\right]$ is zero. If $x$ is optimal, $clamda\left[j\right]$ should be non-negative if $istate\left[j\right]=1$, non-positive if $istate\left[j\right]=2$ and zero if $istate\left[j\right]=4$.

Other Parameters

‘Check Frequency’int

Default $=50$

Every $i$th iteration, a numerical test is made to see if the current solution $x$ satisfies the constraints in the working set. If the largest residual of the constraints in the working set is judged to be too large, the current working set is refactorized and the variables are recomputed to satisfy the constraints more accurately. If $i\le 0$, the default value is used.

‘Cold Start’valueless

Default

This option specifies how the initial working set is chosen. With a ‘Cold Start’, iqp_dense chooses the initial working set based on the values of the variables and constraints at the initial point. Broadly speaking, the initial working set will include equality constraints and bounds or inequality constraints that violate or ‘nearly’ satisfy their bounds (to within ‘Crash Tolerance’).

With a ‘Warm Start’, you must provide a valid definition of every element of the array $istate$ (see Parameters for the definition of this array). iqp_dense will override your specification of $istate$ if necessary, so that a poor choice of the working set will not cause a fatal error. For instance, any elements of $istate$ which are set to $-2$, $-1$ or $4$ will be reset to zero, as will any elements which are set to $3$ when the corresponding elements of $bl$ and $bu$ are not equal. A warm start will be advantageous if a good estimate of the initial working set is available – for example, when iqp_dense is called repeatedly to solve related problems.

‘Warm Start’valueless

This option specifies how the initial working set is chosen. With a ‘Cold Start’, iqp_dense chooses the initial working set based on the values of the variables and constraints at the initial point. Broadly speaking, the initial working set will include equality constraints and bounds or inequality constraints that violate or ‘nearly’ satisfy their bounds (to within ‘Crash Tolerance’).

With a ‘Warm Start’, you must provide a valid definition of every element of the array $istate$ (see Parameters for the definition of this array). iqp_dense will override your specification of $istate$ if necessary, so that a poor choice of the working set will not cause a fatal error. For instance, any elements of $istate$ which are set to $-2$, $-1$ or $4$ will be reset to zero, as will any elements which are set to $3$ when the corresponding elements of $bl$ and $bu$ are not equal. A warm start will be advantageous if a good estimate of the initial working set is available – for example, when iqp_dense is called repeatedly to solve related problems.

‘Crash Tolerance’float

Default $=0.01$

This value is used in conjunction with the option ‘Cold Start’ (the default value) when iqp_dense selects an initial working set. If $0\le r\le 1$, the initial working set will include (if possible) bounds or general inequality constraints that lie within $r$ of their bounds. In particular, a constraint of the form $a_j^{T}x\ge l$ will be included in the initial working set if $|a_j^{T}x-l|\le r(1+\left|l\right|)$. If $r<0$ or $r>1$, the default value is used.

‘Defaults’valueless

This special keyword may be used to reset all options to their default values.

‘Expand Frequency’int

Default $=5$

This option is part of an anti-cycling procedure designed to guarantee progress even on highly degenerate problems.

The strategy is to force a positive step at every iteration, at the expense of violating the constraints by a small amount. Suppose that the value of the option ‘Feasibility Tolerance’ is $\delta$. Over a period of $i$ iterations, the feasibility tolerance actually used by iqp_dense (i.e., the working feasibility tolerance) increases from $0.5\delta$ to $\delta$ (in steps of $0.5\delta /i$).

At certain stages the following ‘resetting procedure’ is used to remove constraint infeasibilities. First, all variables whose upper or lower bounds are in the working set are moved exactly onto their bounds. A count is kept of the number of nontrivial adjustments made. If the count is positive, iterative refinement is used to give variables that satisfy the working set to (essentially) machine precision. Finally, the working feasibility tolerance is reinitialized to $0.5\delta$.

If a problem requires more than $i$ iterations, the resetting procedure is invoked and a new cycle of $i$ iterations is started with $i$ incremented by $10$. (The decision to resume the feasibility phase or optimality phase is based on comparing any constraint infeasibilities with $\delta$.)

The resetting procedure is also invoked when iqp_dense reaches an apparently optimal, infeasible or unbounded solution, unless this situation has already occurred twice. If any nontrivial adjustments are made, iterations are continued.

If $i\le 0$, the default value is used. If $i\ge 9999999$, no anti-cycling procedure is invoked.

‘Feasibility Phase Iteration Limit’int

Default $=max(50,5(n+m_L))$

The scalars $i_1$ and $i_2$ specify the maximum number of iterations allowed in the feasibility and optimality phases. ‘Optimality Phase Iteration Limit’ is equivalent to ‘Iteration Limit’. Setting $i_1=0$ and $\text{‘Print Level'}>0$ means that the workspace needed will be computed and printed, but no iterations will be performed. If $i_1<0$ or $i_2<0$, the default value is used.

‘Optimality Phase Iteration Limit’int

Default $=max(50,5(n+m_L))$

The scalars $i_1$ and $i_2$ specify the maximum number of iterations allowed in the feasibility and optimality phases. ‘Optimality Phase Iteration Limit’ is equivalent to ‘Iteration Limit’. Setting $i_1=0$ and $\text{‘Print Level'}>0$ means that the workspace needed will be computed and printed, but no iterations will be performed. If $i_1<0$ or $i_2<0$, the default value is used.

‘Feasibility Tolerance’float

Default $=\sqrt{ϵ}$

If $r\ge ϵ$, $r$ defines the maximum acceptable absolute violation in each constraint at a ‘feasible’ point. For example, if the variables and the coefficients in the general constraints are of order unity, and the latter are correct to about $6$ decimal digits, it would be appropriate to specify $r$ as ${10}^{-6}$. If $0\le r<ϵ$, the default value is used.

iqp_dense attempts to find a feasible solution before optimizing the objective function. If the sum of infeasibilities cannot be reduced to zero, the ‘Minimum Sum of Infeasibilities’ can be used to find the minimum value of the sum. Let Sinf be the corresponding sum of infeasibilities. If Sinf is quite small, it may be appropriate to raise $r$ by a factor of $10$ or $100$. Otherwise, some error in the data should be suspected.

Note that a ‘feasible solution’ is a solution that satisfies the current constraints to within the tolerance $r$.

‘Hessian Rows’int

Default $=n$

Note that this option does not apply to problems of type FP or LP.

This specifies $m$, the number of rows of the Hessian matrix $H$. The default value of $m$ is $n$, the number of variables of the problem.

If the problem is of type QP, $m$ will usually be $n$, the number of variables. However, a value of $m$ less than $n$ is appropriate for QP3 or QP4 if $h$ is an upper trapezoidal matrix with $m$ rows. Similarly, $m$ may be used to define the dimension of a leading block of nonzeros in the Hessian matrices of QP1 or QP2, in which case the last $n-m$ rows and columns of $h$ are assumed to be zero. In the QP case, $m$ should not be greater than $n$; if it is, the last $m-n$ rows of $h$ are ignored.

If $i<0$ or $i>n$, the default value is used.

‘Infinite Bound Size’float

Default $={10}^{20}$

If $r>0$, $r$ defines the ‘infinite’ bound $\text{bigbnd}$ in the definition of the problem constraints. Any upper bound greater than or equal to $\text{bigbnd}$ will be regarded as $+\infty$ (and similarly any lower bound less than or equal to $-\text{bigbnd}$ will be regarded as $-\infty$). If $r\le 0$, the default value is used.

‘Infinite Step Size’float

Default $=max(\text{bigbnd},{10}^{20})$

If $r>0$, $r$ specifies the magnitude of the change in variables that will be considered a step to an unbounded solution. (Note that an unbounded solution can occur only when the Hessian is not positive definite.) If the change in $x$ during an iteration would exceed the value of $r$, the objective function is considered to be unbounded below in the feasible region. If $r\le 0$, the default value is used.

‘Iteration Limit’int

Default $=max(50,5(n+m_L))$

See option ‘Feasibility Phase Iteration Limit’.

‘Iters’int

Default $=max(50,5(n+m_L))$

See option ‘Feasibility Phase Iteration Limit’.

‘Itns’int

Default $=max(50,5(n+m_L))$

See option ‘Feasibility Phase Iteration Limit’.

‘List’valueless

Option ‘List’ enables printing of each option specification as it is supplied. ‘Nolist’ suppresses this printing.

‘Nolist’valueless

Default

Option ‘List’ enables printing of each option specification as it is supplied. ‘Nolist’ suppresses this printing.

‘Maximum Degrees of Freedom’int

Default $=n$

Note that this option does not apply to problems of type FP or LP.

This places a limit on the storage allocated for the triangular factor $R$ of the reduced Hessian $H_R$. Ideally, $i$ should be set slightly larger than the value of $n_R$ expected at the solution. It need not be larger than $m_n+1$, where $m_n$ is the number of variables that appear nonlinearly in the quadratic objective function. For many problems it can be much smaller than $m_n$.

For quadratic problems, a minimizer may lie on any number of constraints, so that $n_R$ may vary between $1$ and $n$. The default value of $i$ is, therefore, the number of variables $n$. If ‘Hessian Rows’ $m$ is specified, the default value of $i$ is the same number, $m$.

‘Minimum Sum of Infeasibilities’str

Default $=\text{'NO'}$

If no feasible point exists for the constraints, this option is used to control whether or not iqp_dense will calculate a point that minimizes the constraint violations. If $\text{‘Minimum Sum of Infeasibilities'}=\text{'[N]O'}$, iqp_dense will terminate as soon as it is evident that no feasible point exists for the constraints. The final point will generally not be the point at which the sum of infeasibilities is minimized. If $\text{‘Minimum Sum of Infeasibilities'}=\text{'[Y]ES'}$, iqp_dense will continue until the sum of infeasibilities is minimized.

‘Monitoring File’int

Default $=-1$

If $i\ge 0$ and $\text{‘Print Level'}\ge 5$, monitoring information produced by iqp_dense at every iteration is sent to a file with logical unit number $i$. If $i<0$ and/or $\text{‘Print Level'}<5$, no monitoring information is produced.

‘Optimality Tolerance’float

Default $={ϵ}^{0.8}$

If $r\ge ϵ$, $r$ defines the tolerance used to determine if the bounds and general constraints have the right ‘sign’ for the solution to be judged to be optimal.

If $0\le r<ϵ$, the default value is used.

‘Print Level’int

Default $=10$

The value of $i$ controls the amount of printout produced by iqp_dense, as indicated below. A detailed description of the printed output is given in Further Comments (summary output at each iteration and the final solution) and Monitoring Information (monitoring information at each iteration). If $i<0$, the default value is used.

The following printout is sent to the file object associated with the advisory I/O unit (see FileObjManager):

$i$	Output
$0$	No output.
$1$	The final solution only.
$5$	One line of summary output ($<80$ characters; see Further Comments) for each iteration (no printout of the final solution).
$\ge 10$	The final solution and one line of summary output for each iteration.

The following printout is sent to the logical unit number defined by the ‘Monitoring File’:

$i$	Output
$<5$	No output.
$\ge 5$	One long line of output ($>80$ characters; see Monitoring Information) for each iteration (no printout of the final solution).
$\ge 20$	At each iteration, the Lagrange-multipliers, the variables $x$, the constraint values $Ax$ and the constraint status.
$\ge 30$	At each iteration, the diagonal elements of the upper triangular matrix $T$ associated with the $TQ$ factorization (3) (see Definition of the Search Direction) of the working set, and the diagonal elements of the upper triangular matrix $R$.

If $\text{‘Print Level'}\ge 5$ and the unit number defined by ‘Monitoring File’ is the advisory unit number, then the summary output is suppressed.

‘Problem Type’str

Default $=$ QP2

This option specifies the type of objective function to be minimized during the optimality phase. The following are the five optional keywords and the dimensions of the arrays that must be specified in order to define the objective function:

LP	$h$ not referenced, length-$\text{n}$ $cvec$ required;
QP1	rank-$2$ $h$ symmetric, $cvec$ not referenced;
QP2	rank-$2$ $h$ symmetric, length-$\text{n}$ $cvec$ required;
QP3	rank-$2$ $h$ upper trapezoidal, $cvec$ not referenced;
QP4	rank-$2$ $h$ upper trapezoidal, length-$\text{n}$ $cvec$ required.

For problems of type FP, the objective function is omitted and neither $h$ nor $cvec$ are referenced.

The following keywords are also acceptable.

$a$	Option
Quadratic	QP2
Linear	LP
Feasible	FP

In addition, the keyword QP is equivalent to the default option QP2.

If $h=0$, i.e., the objective function is purely linear, the efficiency of iqp_dense may be increased by specifying $a$ as LP.

‘Rank Tolerance’float

Default $=100ϵ$

Note that this option does not apply to problems of type FP or LP.

This argument enables you to control the condition number of the triangular factor $R$ (see Algorithmic Details). If ${\rho }_i$ denotes the function ${\rho }_i=max\{\left|R_{11}\right|,\left|R_{22}\right|,\dots ,\left|R_{ii}\right|\}$, the dimension of $R$ is defined to be smallest index $i$ such that $\left|R_{i+1,i+1}\right|\le \sqrt{r}\left|{\rho }_{i+1}\right|$. If $r\le 0$, the default value is used.

Raises

NagValueError

(errno $1$)

Invalid input argument for basic problem.

(errno $1$)

On entry, $strtgy=⟨value⟩$.

Constraint: $strtgy=0$, $1$, $2$ or $3$.

(errno $1$)

On entry, $mdepth=⟨value⟩$.

Constraint: $mdepth\ge 1$.

(errno $1$)

On entry, $\text{lintvr}=⟨value⟩$.

Constraint: $\text{lintvr}\ge 1$.

(errno $1$)

On entry, $\text{nclin}=⟨value⟩$.

Constraint: $\text{nclin}\ge 0$.

(errno $1$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $2$)

No integer solutions found.

(errno $3$)

Need to increase depth, $mdepth=⟨value⟩$.

(errno $4$)

Basic problem (without integer constraints) unbounded.

(errno $5$)

Basic problem is infeasible.

(errno $6$)

Basic problem requires too many iterations.

(errno $7$)

Basic problem has a reduced Hessian exceeding assigned dimensions.

(errno $9$)

Error in designated problem type.

(errno $12$)

Unexpected error in NAG function – contact NAG.

Warns

NagAlgorithmicWarning

(errno $-1$)

Halted at your request.

Notes

No equivalent traditional C interface for this routine exists in the NAG Library.

iqp_dense uses a ‘Branch and Bound’ algorithm in conjunction with opt.qp_dense_solve to try and determine integer solutions to a general quadratic programming problem. The problem is assumed to be stated in the following general form:

$$\begin{array}{c}{minimize}_{x\in R^n}f\left(x\right)\text{subject to}l\le \left(\begin{array}{c}x\\ Ax\end{array}\right)\le u\text{,}\end{array}$$

where $A$ is an $m_L\times n$ matrix and $f\left(x\right)$ may be specified in a variety of ways depending upon the particular problem to be solved. The available forms for $f\left(x\right)$ are listed in Table [label omitted], in which the prefixes FP, LP and QP stand for ‘feasible point’, ‘linear programming’ and ‘quadratic programming’ respectively and $c$ is an $n$-element vector.

Problem type	$f\left(x\right)$	Matrix $H$
FP	Not applicable	Not applicable
LP	$c^{T}x$	Not applicable
QP1	$\frac{1}{2}{x}^{T}Hx$	symmetric
QP2	$c^{T}x+\frac{1}{2}{x}^{T}Hx$	symmetric
QP3	$\frac{1}{2}{x}^T{H}^{T}Hx$	$m\times n$ upper trapezoidal
QP4	$c^{T}x+\frac{1}{2}{x}^T{H}^{T}Hx$	$m\times n$ upper trapezoidal

Only when the problem is linear or the matrix $H$ is positive definite can the technique be guaranteed to work; but often useful results can be obtained for a wider class of problems.

The default problem type is QP2 and other objective functions are selected by using the option ‘Problem Type’. For problems of type FP, the objective function is omitted and iqp_dense attempts to find a feasible point for the set of constraints.

Branch and bound consists firstly of obtaining a solution without any of the variables $x={(x_1,x_2,\dots ,x_n)}^T$ constrained to be integer. Suppose $x_1$ ought to be integer, but at the optimal value just computed $x_1=2.4$. A constraint $x_1\le 2$ is added to the system and the second problem solved. A constraint $x_1\ge 3$ gives rise to a third sub-problem. In a similar manner a whole series of sub-problems may be generated, corresponding to integer constraints on the variables. The sub-problems are all solved using opt.qp_dense_solve.

In practice the function tries to compute an integer solution as quickly as possible using a depth-first approach, since this helps determine a realistic cut-off value. If we have a cut-off value, say the value of the function at this first integer solution, and any sub-problem, $W$ say, has a solution value greater than this cut-off value, then subsequent sub-problems of $W$ must have solutions greater than the value of the solution at $W$ and, therefore, need not be computed. Thus a knowledge of a good cut-off value can result in fewer sub-problems being solved and thus speed up the operation of the function. (See the description of $monit$ in Parameters for details of how you can supply your own cut-off value.)

References

Gill, P E, Hammarling, S, Murray, W, Saunders, M A and Wright, M H, 1986, Users’ guide for LSSOL (Version 1.0), Report SOL 86-1, Department of Operations Research, Stanford University

Gill, P E and Murray, W, 1978, Numerically stable methods for quadratic programming, Math. Programming (14), 349–372

Gill, P E, Murray, W, Saunders, M A and Wright, M H, 1984, Procedures for optimization problems with a mixture of bounds and general linear constraints, ACM Trans. Math. Software (10), 282–298

Gill, P E, Murray, W, Saunders, M A and Wright, M H, 1989, A practical anti-cycling procedure for linearly constrained optimization, Math. Programming (45), 437–474

Gill, P E, Murray, W, Saunders, M A and Wright, M H, 1991, Inertia-controlling methods for general quadratic programming, SIAM Rev. (33), 1–36

Gill, P E, Murray, W and Wright, M H, 1981, Practical Optimization, Academic Press

Pardalos, P M and Schnitger, G, 1988, Checking local optimality in constrained quadratic programming is NP-hard, Operations Research Letters (7), 33–35