NAG Library Routine Document

h02cef  (iqp_sparse)

1

Purpose

2

Specification

3

Description

4

References

5

Arguments

1:     $\mathbf{n}$ – IntegerInput

On entry: $n$, the number of variables (excluding slacks). This is the number of columns in the linear constraint matrix $A$.

Constraint: $\mathbf{n}\ge 1$.

2:     $\mathbf{m}$ – IntegerInput

On entry: $m$, the number of general linear constraints (or slacks). This is the number of rows in $A$, including the free row (if any; see iobj).

Constraint: $\mathbf{m}\ge 1$.

3:     $\mathbf{nnz}$ – IntegerInput

On entry: the number of nonzero elements in $A$.

Constraint: $1\le \mathbf{nnz}\le \mathbf{n}\times \mathbf{m}$.

4:     $\mathbf{iobj}$ – IntegerInput

On entry: if $\mathbf{iobj}>0$, row iobj of $A$ is a free row containing the nonzero elements of the vector $c$ appearing in the linear objective term $c^{\mathrm{T}}x$.

If $\mathbf{iobj}=0$, there is no free row, i.e., the problem is either an FP problem (in which case iobj must be set to zero), or a QP problem with $c=0$.

Constraint: $0\le \mathbf{iobj}\le \mathbf{m}$.

5:     $\mathbf{ncolh}$ – IntegerInput

On entry: $n_H$, the number of leading nonzero columns of the Hessian matrix $H$. For FP and LP problems, ncolh must be set to zero.

Constraint: $0\le \mathbf{ncolh}\le \mathbf{n}$.

6:     $\mathbf{qphx}$ – Subroutine, supplied by the NAG Library or the user.External Procedure

For QP problems, you must supply a version of qphx to compute the matrix product $Hx$. If $H$ has rows and columns consisting entirely of zeros, it is most efficient to order the variables $x={\left(yz\right)}^{\mathrm{T}}$ so that

$$Hx=\left(\begin{array}{cc}{H}_1& 0\\ 0& 0\end{array}\right)\left(\begin{array}{c}y\\ z\end{array}\right)=\left(\begin{array}{c}{H}_{1}y\\ 0\end{array}\right)\text{,}$$

where the nonlinear variables $y$ appear first as shown. For LP problems, qphx will never be called by h02cef.

The specification of qphx is:

Fortran Interface

Subroutine qphx ( nstate, ncolh, x, hx) Integer, Intent (In) :: nstate, ncolh Real (Kind=nag_wp), Intent (In) :: x(ncolh) Real (Kind=nag_wp), Intent (Out) :: hx(ncolh)

C Header Interface

#include nagmk26.h void  qphx ( const Integer *nstate, const Integer *ncolh, const double x[], double hx[])

1:     $\mathbf{nstate}$ – IntegerInput

On entry: if $\mathbf{nstate}=1$, then h02cef is calling qphx for the first time on a sub-problem. This argument setting allows you to save computation time if certain data must be read or calculated only once.

If $\mathbf{nstate}\ge 2$, then h02cef is calling qphx for the last time. This argument setting allows you to perform some additional computation on the final sub-problem solution. In general, the last call to qphx is made with $\mathbf{nstate}=2+\mathbf{ifail}$ (see Section 6).

Otherwise, $\mathbf{nstate}=0$.

2:     $\mathbf{ncolh}$ – IntegerInput

On entry: this is the same argument ncolh as supplied to h02cef.

3:     $\mathbf{x}\left(\mathbf{ncolh}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: the first ncolh elements of the vector $x$.

4:     $\mathbf{hx}\left(\mathbf{ncolh}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: the product $Hx$.

qphx must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which h02cef is called. Arguments denoted as Input must not be changed by this procedure.

Note: qphx should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by h02cef. If your code inadvertently does return any NaNs or infinities, h02cef is likely to produce unexpected results.

7:     $\mathbf{a}\left(\mathbf{nnz}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: the nonzero elements of $A$, ordered by increasing column index. Note that multiple elements with the same row and column indices are not allowed.

On exit: used as internal workspace prior to being restored and hence is unchanged.

8:     $\mathbf{ha}\left(\mathbf{nnz}\right)$ – Integer arrayInput

On entry: $\mathbf{ha}\left(\mathit{i}\right)$ must contain the row index of the nonzero element stored in $\mathbf{a}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,\mathbf{nnz}$. Note that the row indices for a column may be supplied in any order.

Constraint: $1\le \mathbf{ha}\left(\mathit{i}\right)\le \mathbf{m}$, for $\mathit{i}=1,2,\dots ,\mathbf{nnz}$.

9:     $\mathbf{ka}\left(\mathbf{n}+1\right)$ – Integer arrayInput

On entry: $\mathbf{ka}\left(\mathit{j}\right)$ must contain the index in a of the start of the $\mathit{j}$th column, for $\mathit{j}=1,2,\dots ,\mathbf{n}$. To specify the $j$th column as empty, set $\mathbf{ka}\left(j\right)=\mathbf{ka}\left(j+1\right)$. Note that the first and last elements of ka must be such that $\mathbf{ka}\left(1\right)=1$ and $\mathbf{ka}\left(\mathbf{n}+1\right)=\mathbf{nnz}+1$.

Constraints:

• $\mathbf{ka}\left(1\right)=1$;
• $\mathbf{ka}\left(\mathit{j}\right)\ge 1$, for $\mathit{j}=2,3,\dots ,\mathbf{n}$;
• $\mathbf{ka}\left(\mathbf{n}+1\right)=\mathbf{nnz}+1$;
• $0\le \mathbf{ka}\left(\mathit{j}+1\right)-\mathbf{ka}\left(\mathit{j}\right)\le \mathbf{m}$, for $\mathit{j}=1,2,\dots ,\mathbf{n}$.

10:   $\mathbf{bl}\left(\mathbf{n}+\mathbf{m}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: $l$, the lower bounds for all the variables and general constraints, in the following order. The first n elements of bl must contain the bounds on the variables $x$, and the next m elements the bounds for the general linear constraints $Ax$ (or slacks $s$) and the free row (if any). To specify a nonexistent lower bound (i.e., $l_j=-\infty$), set $\mathbf{bl}\left(j\right)\le -\mathit{bigbnd}$, where $\mathit{bigbnd}$ is the value of the optional parameter Infinite Bound Size ($\text{default value}={10}^{20}$). To specify the $j$th constraint as an equality, set $\mathbf{bl}\left(j\right)=\mathbf{bu}\left(j\right)=\beta$, say, where $\left|\beta \right|<\mathit{bigbnd}$. Note that the lower bound corresponding to the free row must be set to $-\infty$ and stored in $\mathbf{bl}\left(\mathbf{n}+\mathbf{iobj}\right)$.

Constraint: if $\mathbf{iobj}>0$, $\mathbf{bl}\left(\mathbf{n}+\mathbf{iobj}\right)\le -\mathit{bigbnd}$

(See also the description for bu.)

11:   $\mathbf{bu}\left(\mathbf{n}+\mathbf{m}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: $u$, the upper bounds for all the variables and general constraints, in the following order. The first n elements of bl must contain the bounds on the variables $x$, and the next m elements the bounds for the general linear constraints $Ax$ (or slacks $s$) and the free row (if any). To specify a nonexistent upper bound (i.e., $u_j=+\infty$), set $\mathbf{bu}\left(j\right)\ge \mathit{bigbnd}$. Note that the upper bound corresponding to the free row must be set to $+\infty$ and stored in $\mathbf{bu}\left(\mathbf{n}+\mathbf{iobj}\right)$.

On exit: used as internal workspace prior to being restored and hence is unchanged.

Constraints:

• if $\mathbf{iobj}>0$, $\mathbf{bu}\left(\mathbf{n}+\mathbf{iobj}\right)\ge \mathit{bigbnd}$;
• $\mathbf{bl}\left(\mathit{j}\right)\le \mathbf{bu}\left(\mathit{j}\right)$, for $\mathit{j}=1,2,\dots ,\mathbf{n}+\mathbf{m}$;
• if $\mathbf{bl}\left(j\right)=\mathbf{bu}\left(j\right)=\beta$, $\left|\beta \right|<\mathit{bigbnd}$.

12:   $\mathbf{start}$ – Character(1)Input

On entry: indicates how a starting basis is to be obtained.

$\mathbf{start}=\text{'C'}$

An internal crash procedure will be used to choose an initial basis matrix $B$.

$\mathbf{start}=\text{'W'}$

A basis is already defined in istate (probably from a previous call).

Constraint: $\mathbf{start}=\text{'C'}$ or $\text{'W'}$.

13:   $\mathbf{names}\left(5\right)$ – Character(8) arrayInput

On entry: a set of names associated with the so-called MPSX form of the problem.

$\mathbf{names}\left(1\right)$

Must contain the name for the problem (or be blank).

$\mathbf{names}\left(2\right)$

Must contain the name for the free row (or be blank).

$\mathbf{names}\left(3\right)$

Must contain the name for the constraint right-hand side (or be blank).

$\mathbf{names}\left(4\right)$

Must contain the name for the ranges (or be blank).

$\mathbf{names}\left(5\right)$

Must contain the name for the bounds (or be blank).

(These names are used in the monitoring file output; see Section 13.)

14:   $\mathbf{nname}$ – IntegerInput

On entry: the number of column (i.e., variable) and row names supplied in the array names.

$\mathbf{nname}=1$

There are no names. Default names will be used in the printed output.

$\mathbf{nname}=\mathbf{n}+\mathbf{m}$

All names must be supplied.

Constraint: $\mathbf{nname}=1$ or $\mathbf{n}+\mathbf{m}$.

15:   $\mathbf{crname}\left(\mathbf{nname}\right)$ – Character(8) arrayInput

On entry: the optional column and row names.

If $\mathbf{nname}=1$, crname is not referenced and the printed output will use default names for the columns and rows.

If $\mathbf{nname}=\mathbf{n}+\mathbf{m}$, the first n elements must contain the names for the columns and the next m elements must contain the names for the rows. Note that the name for the free row (if any) must be stored in $\mathbf{crname}\left(\mathbf{n}+\mathbf{iobj}\right)$.

16:   $\mathbf{ns}$ – IntegerInput/Output

On entry: $n_S$, the number of superbasics. For QP problems, ns need not be specified if $\mathbf{start}=\text{'C'}$, but must retain its value from a previous call when $\mathbf{start}=\text{'W'}$. For FP and LP problems, ns need not be initialized.

On exit: the final number of superbasics. This will be zero for FP and LP problems.

17:   $\mathbf{xs}\left(\mathbf{n}+\mathbf{m}\right)$ – Real (Kind=nag_wp) arrayInput/Output

On entry: the initial values of the variables and slacks $\left(x,s\right)$. (See the description for istate.)

On exit: $\mathbf{xs}\left(\mathit{i}\right)$ contains the final value of $x_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,n$.

18:   $\mathbf{intvar}\left(\mathbf{lintvr}\right)$ – Integer arrayInput

On entry: specifies which components of the solution vector $x$ are constrained to be integer. Specifically, if $k$ elements of $x$ are required to take integer values then $\mathbf{intvar}\left(\mathit{i}\right)=l_{\mathit{i}}$, for $\mathit{i}=1,2,\dots ,k$, where $l_i$ is the integer index such that $x_{l_i}$ is integer. If $k<\mathbf{lintvr}$ then $\mathbf{intvar}\left(k+1\right)$ must be set to $-1$ to signal the end of the integer variable indices.

The order in which the indices of those components of $x$ required to be integer is presented determines the order in which the sub-problems are treated and solved. As such it can be a powerful tool to assist the routine in achieving a solution efficiently. The general advice is to enter the important integer variables in the model early in intvar; secondary or less important variables should be entered near the end of the list. However some experimentation might be required to find the optimal order.

19:   $\mathbf{lintvr}$ – IntegerInput

On entry: $k$, the number of components of $x$ required to be integer. If $k=0$, then lintvr must be set to $1$ and $\mathbf{intvar}\left(1\right)$ set to $-1$.

20:   $\mathbf{mdepth}$ – IntegerInput

On entry: specifies the maximum depth the tree of sub-problems may be developed.

Suggested value: $\mathbf{mdepth}=2\times \mathbf{n}+20$.

Constraint: $\mathbf{mdepth}>0$.

21:   $\mathbf{istate}\left(\mathbf{n}+\mathbf{m}\right)$ – Integer arrayInput/Output

On entry: if $\mathbf{start}=\text{'C'}$, the first n elements of istate and xs must specify the initial states and values, respectively, of the variables $x$. (The slacks $s$ need not be initialized.) An internal crash procedure is then used to select an initial basis matrix $B$. The initial basis matrix will be triangular (neglecting certain small elements in each column). It is chosen from various rows and columns of columns of $\left(A-I\right)$. Possible values for $\mathbf{istate}\left(j\right)$ are as follows:

$\mathbf{istate}\left(j\right)$	State of $\mathbf{xs}\left(j\right)$ during crash procedure
0 or $1$	Eligible for the basis
2	Ignored
3	Eligible for the basis (given preference over $0$ or $1$)
4 or $5$	Ignored

If nothing special is known about the problem, or there is no wish to provide special information, you may set $\mathbf{istate}\left(\mathit{j}\right)=0$ and $\mathbf{xs}\left(\mathit{j}\right)=0.0$, for $\mathit{j}=1,2,\dots ,\mathbf{n}$. All variables will then be eligible for the initial basis. Less trivially, to say that the $j$th variable will probably be equal to one of its bounds, set $\mathbf{istate}\left(j\right)=4$ and $\mathbf{xs}\left(j\right)=\mathbf{bl}\left(j\right)$ or $\mathbf{istate}\left(j\right)=5$ and $\mathbf{xs}\left(j\right)=\mathbf{bu}\left(j\right)$ as appropriate.

Following the crash procedure, variables for which $\mathbf{istate}\left(j\right)=2$ are made superbasic. Other variables not selected for the basis are then made nonbasic at the value $\mathbf{xs}\left(j\right)$ if $\mathbf{bl}\left(j\right)\le \mathbf{xs}\left(j\right)\le \mathbf{bu}\left(j\right)$, or at the value $\mathbf{bl}\left(j\right)$ or $\mathbf{bu}\left(j\right)$ closest to $\mathbf{xs}\left(j\right)$.

If $\mathbf{start}=\text{'W'}$, istate and xs must specify the initial states and values, respectively, of the variables and slacks $\left(x,s\right)$. If h02cef has been called previously with the same values of n and m, istate already contains satisfactory information.

Constraints:

• if $\mathbf{start}=\text{'C'}$, $0\le \mathbf{istate}\left(\mathit{j}\right)\le 5$, for $\mathit{j}=1,2,\dots ,\mathbf{n}$;
• if $\mathbf{start}=\text{'W'}$, $0\le \mathbf{istate}\left(\mathit{j}\right)\le 3$, for $\mathit{j}=1,2,\dots ,\mathbf{n}+\mathbf{m}$.

On exit: the final states of the variables and slacks $\left(x,s\right)$ from the solution of the last sub-problem tackled. The significance of each possible value of $\mathbf{istate}\left(j\right)$ is as follows:

$\mathbf{istate}\left(j\right)$	State of variable $j$	Normal value of $\mathbf{xs}\left(j\right)$
$0$	Nonbasic	$\mathbf{bl}\left(j\right)$
$1$	Nonbasic	$\mathbf{bu}\left(j\right)$
$2$	Superbasic	Between $\mathbf{bl}\left(j\right)$ and $\mathbf{bu}\left(j\right)$
$3$	Basic	Between $\mathbf{bl}\left(j\right)$ and $\mathbf{bu}\left(j\right)$

If $\mathtt{Ninf}=0$ (see Section 9.1), basic and superbasic variables may be outside their bounds by as much as the value of the optional parameter Feasibility Tolerance ($\text{default value}=\max \left({10}^{-6},\sqrt{\epsilon }\right)$, where $\epsilon$ is the machine precision). Note that unless the optional parameter $\mathbf{Scale\; Option}=0$ ($\text{default value}=2$) is specified, the Feasibility Tolerance applies to the variables of the scaled problem. In this case, the variables of the original problem may be as much as $0.1$ outside their bounds, but this is unlikely unless the problem is very badly scaled.

Very occasionally some nonbasic variables may be outside their bounds by as much as the Feasibility Tolerance, and there may be some nonbasic variables for which $\mathbf{xs}\left(j\right)$ lies strictly between its bounds.

If $\mathtt{Ninf}>0$, some basic and superbasic variables may be outside their bounds by an arbitrary amount (bounded by Sinf (see Section 9.1) if $\mathbf{Scale\; Option}=0$).

22:   $\mathbf{miniz}$ – IntegerOutput

On exit: the minimum value of leniz required to start solving the problem. If $\mathbf{ifail}=\mathbf{14}$, h02cef may be called again with leniz suitably larger than miniz. (The bigger the better, since it is not certain how much workspace the basis factors need.)

23:   $\mathbf{minz}$ – IntegerOutput

On exit: the minimum value of lenz required to start solving the problem. If $\mathbf{ifail}=\mathbf{15}$, h02cef may be called again with lenz suitably larger than minz. (The bigger the better, since it is not certain how much workspace the basis factors need.)

24:   $\mathbf{obj}$ – Real (Kind=nag_wp)Output

On exit: the value of the objective function.

If $\mathtt{Ninf}=0$, obj includes the quadratic objective term $\frac{1}{2}{x}^{\mathrm{T}}Hx$ (if any).

If $\mathtt{Ninf}>0$, obj is just the linear objective term $c^{\mathrm{T}}x$ (if any). For FP problems, obj is set to zero.

25:   $\mathbf{clamda}\left(\mathbf{n}+\mathbf{m}\right)$ – Real (Kind=nag_wp) arrayOutput

On exit: a set of Lagrange-multipliers for the bounds on the variables and the general constraints. More precisely, the first n elements contain the multipliers (reduced costs) for the bounds on the variables, and the next m elements contain the multipliers (shadow prices) for the general linear constraints.

26:   $\mathbf{strtgy}$ – IntegerInput

On entry: defines the branching strategy adopted by the routine.

$\mathbf{strtgy}=0$

Each sub-problem first explored imposes a tighter upper bound on the component of $x$.

$\mathbf{strtgy}=1$

Each sub-problem first explored imposes a tighter lower bound on the component of $x$.

$\mathbf{strtgy}=2$

Each branch explored imposes a tighter upper bound on the component of $x$ if its fractional part is less than $0.5$, otherwise it imposes a tighter lower bound.

$\mathbf{strtgy}=3$

Random choice is made between first exploring a tighter lower bound or a tighter upper bound sub-problem.

Constraint: $\mathbf{strtgy}=0$, $1$, $2$ or $3$.

27:   $\mathbf{iz}\left(\mathbf{leniz}\right)$ – Integer arrayWorkspace

28:   $\mathbf{leniz}$ – IntegerInput

On entry: the dimension of the array iz as declared in the (sub)program from which h02cef is called.

Constraint: $\mathbf{leniz}\ge 1$.

29:   $\mathbf{z}\left(\mathbf{lenz}\right)$ – Real (Kind=nag_wp) arrayWorkspace

30:   $\mathbf{lenz}$ – IntegerInput

On entry: the dimension of the array z as declared in the (sub)program from which h02cef is called.

Constraint: $\mathbf{lenz}\ge 1$.

The amounts of workspace provided (i.e., leniz and lenz) and required (i.e., miniz and minz) are (by default) output on the current advisory message unit (as defined by x04abf). Since the minimum values of leniz and lenz required to start solving the problem are returned in miniz and minz, respectively, you may prefer to obtain appropriate values from the output of a preliminary run with leniz and lenz set to $1$. (h02cef will then terminate with $\mathbf{ifail}=\mathbf{14}$.)

31:   $\mathbf{monit}$ – Subroutine, supplied by the NAG Library or the user.External Procedure

To provide feed-back on the progress of the branch and bound process. Additionally monit provides, via its argument halt, the ability to terminate the process. (You might choose to do this when an integer solution is found, rather than search for a better solution.) If you do not require any intermediate output then monit may be the dummy routine h02cey.

The specification of monit is:

Fortran Interface

Subroutine monit ( intfnd, nodes, depth, obj, x, bstval, bstsol, bl, bu, n, halt, count) Integer, Intent (In) :: intfnd, nodes, depth, n Integer, Intent (Inout) :: count Real (Kind=nag_wp), Intent (In) :: obj, x(n), bstsol(n), bl(n), bu(n) Real (Kind=nag_wp), Intent (Inout) :: bstval Logical, Intent (Inout) :: halt

C Header Interface

#include nagmk26.h void  monit ( const Integer *intfnd, const Integer *nodes, const Integer *depth, const double *obj, const double x[], double *bstval, const double bstsol[], const double bl[], const double bu[], const Integer *n, logical *halt, Integer *count)

1:     $\mathbf{intfnd}$ – IntegerInput

On entry: contains the number of integer solutions obtained so far.

2:     $\mathbf{nodes}$ – IntegerInput

On entry: contains the number of nodes (sub-problems) solved so far.

3:     $\mathbf{depth}$ – IntegerInput

On entry: contains the depth reached in the tree of problems.

4:     $\mathbf{obj}$ – Real (Kind=nag_wp)Input

On entry: contains the solution value to the sub-problem at this node.

5:     $\mathbf{x}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: contains the solution vector to the sub-problem at this node.

6:     $\mathbf{bstval}$ – Real (Kind=nag_wp)Input/Output

On entry: contains the value of the objective function corresponding to the best integer solution obtained so far. If no integer solution has been found bstval contains the largest machine representable number (see x02alf).

On exit: may be set to a cut-off value, if you are a sophisticated user, as follows. Before an integer solution has been found bstval will be set by h02cef to the largest machine representable number (see x02alf). 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 Section 3). Beware of setting bstval too small, since then no integer solutions will be discovered. Also make sure that bstval is set using a statement of the form

IF (intfnd.EQ.0) $\mathbf{bstval}=$ cut-off value

on entry to monit. This statement 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.

7:     $\mathbf{bstsol}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: contains the value of the best integer solution obtained so far.

8:     $\mathbf{bl}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: contains the current lower bounds on the variables at this point.

9:     $\mathbf{bu}\left(\mathbf{n}\right)$ – Real (Kind=nag_wp) arrayInput

On entry: contains the current upper bounds on the variables at this point.

10:   $\mathbf{n}$ – IntegerInput

On entry: contains the number of variables in the minimization problem.

11:   $\mathbf{halt}$ – LogicalInput/Output

On entry: will have the value .FALSE..

On exit: if halt is set to .TRUE., e04nkf/e04nka will be brought to a halt with ifail exit $-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 $\mathbf{halt}=\mathrm{.TRUE.}$ can save considerable unnecessary computation.

12:   $\mathbf{count}$ – IntegerUser Data

count may be used 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.

monit must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which h02cef is called. Arguments denoted as Input must not be changed by this procedure.

Note: monit should not return floating-point NaN (Not a Number) or infinity values, since these are not handled by h02cef. If your code inadvertently does return any NaNs or infinities, h02cef is likely to produce unexpected results.

32:   $\mathbf{ifail}$ – IntegerInput/Output

On entry: ifail must be set to $0$, $-1\text{ or }1$. If you are unfamiliar with this argument you should refer to Section 3.4 in How to Use the NAG Library and its Documentation for details.

For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{ or }1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is $0$. When the value $-\mathbf{1}\text{ or }\mathbf{1}$ is used it is essential to test the value of ifail on exit.

On exit: $\mathbf{ifail}=\mathbf{0}$ unless the routine detects an error or a warning has been flagged (see Section 6).

6

Error Indicators and Warnings

$\mathbf{ifail}=-1$

Halted at your request.

$\mathbf{ifail}=0$

Successful exit.

$\mathbf{ifail}=1$

Input argument error immediately detected.

$\mathbf{ifail}=2$

No integer solution found.

$\mathbf{ifail}=3$

mdepth is too small.

$\mathbf{ifail}=4$

The problem is unbounded (or badly scaled). The objective function is not bounded below in the feasible region.

$\mathbf{ifail}=5$

The problem is infeasible. The general constraints cannot all be satisfied simultaneously to within the value of the optional parameter Feasibility Tolerance ($\text{default value}=\max \left({10}^{-6},\sqrt{\epsilon }\right)$, where $\epsilon$ is the machine precision).

$\mathbf{ifail}=6$

Too many iterations. The value of the optional parameter Iteration Limit ($\text{default value}=\max \left(50,5\left(n+m\right)\right)$) is too small.

$\mathbf{ifail}=7$

The reduced Hessian matrix ${\mathbf{z}}^{\mathrm{T}}HZ$ (see Section 11.2) exceeds its assigned dimension. The value of the optional parameter Superbasics Limit ($\text{default value}=\min \left(n_H+1,n\right)$) is too small.

$\mathbf{ifail}=8$

The Hessian matrix $H$ appears to be indefinite. Check that qphx has been coded correctly and that all relevant elements of $Hx$ have been assigned their correct values.

$\mathbf{ifail}=9$

An input argument is invalid for an internal call to e04nkf/e04nka.

$\mathbf{ifail}=10$

Numerical error in trying to satisfy the general constraints. The basis is very ill-conditioned.

$\mathbf{ifail}=11$

Not enough integer workspace for the basis factors. Increase leniz and rerun h02cef.

$\mathbf{ifail}=12$

Not enough real workspace for the basis factors. Increase lenz and rerun h02cef.

$\mathbf{ifail}=13$

The basis is singular after $15$ attempts to factorize it (adding slacks where necessary). Either the problem is badly scaled or the value of the optional parameter LU Factor Tolerance ($\text{default value}=100.0$) is too large.

$\mathbf{ifail}=14$

Not enough integer workspace to start solving the problem. Increase leniz to at least miniz and rerun h02cef.

$\mathbf{ifail}=15$

Not enough real workspace to start solving the problem. Increase lenz to at least minz and rerun h02cef.

$\mathbf{ifail}=16$

An internal error has occurred. Contact NAG with details of your program.

$\mathbf{ifail}=-99$

An unexpected error has been triggered by this routine. Please contact NAG.

See Section 3.9 in How to Use the NAG Library and its Documentation for further information.

$\mathbf{ifail}=-399$

Your licence key may have expired or may not have been installed correctly.

See Section 3.8 in How to Use the NAG Library and its Documentation for further information.

$\mathbf{ifail}=-999$

Dynamic memory allocation failed.

See Section 3.7 in How to Use the NAG Library and its Documentation for further information.

7

Accuracy

8

Parallelism and Performance

9

Further Comments

9.1

Description of the Printed Output

10

Example

10.1

Program Text

Program Text (h02cefe.f90)

10.2

Program Data

Program Data (h02cefe.d)

10.3

Program Results

Program Results (h02cefe.r)

11

Algorithmic Details

11.1

Overview

11.2

Definition of the Working Set and Search Direction

11.3

The Main Iteration

11.4

Miscellaneous

12

Optional Parameters

• Check Frequency
• Crash Option
• Crash Tolerance
• Defaults
• Expand Frequency
• Factorization Frequency
• Feasibility Tolerance
• Infinite Bound Size
• Infinite Step Size
• Iteration Limit
• Iters
• Itns
• List
• LU Factor Tolerance
• LU Singularity Tolerance
• LU Update Tolerance
• Maximize
• Minimize
• Monitoring File
• Nolist
• Optimality Tolerance
• Partial Price
• Pivot Tolerance
• Print Level
• Rank Tolerance
• Scale Option
• Scale Tolerance
• Superbasics Limit

Begin
Print Level = 5
End

Call h02cff(ioptns,inform)

Call h02cgf ('Print Level = 5')

12.1

Description of the Optional Parameters

• the keywords, where the minimum abbreviation of each keyword is underlined (if no characters of an optional qualifier are underlined, the qualifier may be omitted);
• a parameter value, where the letters $a$, $i$ and $r$ denote options that take character, integer and real values respectively;
• the default value is used whenever the condition $\left|i\right|\ge 100000000$ is satisfied and where the symbol $\epsilon$ is a generic notation for machine precision (see x02ajf).

13

Description of Monitoring Information