NAG Toolbox: nag_mip_iqp_sparse (h02ce)

Purpose

Syntax

Description

References

Parameters

Compulsory Input Parameters

1:     $\mathrm{n}$ – int64int32nag_int scalar

$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:     $\mathrm{m}$ – int64int32nag_int scalar

$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:     $\mathrm{iobj}$ – int64int32nag_int scalar

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}$.

4:     $\mathrm{ncolh}$ – int64int32nag_int scalar

$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}$.

5:     $\mathrm{qphx}$ – function handle or string containing name of m-file

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 nag_mip_iqp_sparse (h02ce).

[hx] = qphx(nstate, ncolh, x)

Input Parameters

1:     $\mathrm{nstate}$ – int64int32nag_int scalar

If $\mathbf{nstate}=1$, then nag_mip_iqp_sparse (h02ce) 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 nag_mip_iqp_sparse (h02ce) 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 Error Indicators and Warnings).

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

2:     $\mathrm{ncolh}$ – int64int32nag_int scalar

This is the same argument ncolh as supplied to nag_mip_iqp_sparse (h02ce).

3:     $\mathrm{x}\left(\mathbf{ncolh}\right)$ – double array

The first ncolh elements of the vector $x$.

Output Parameters

1:     $\mathrm{hx}\left(\mathbf{ncolh}\right)$ – double array

The product $Hx$.

6:     $\mathrm{a}\left(\mathbf{nz}\right)$ – double array

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

7:     $\mathrm{ha}\left(\mathbf{nz}\right)$ – int64int32nag_int array

$\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{nz}$. 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{nz}$.

8:     $\mathrm{ka}\left(\mathbf{n}+1\right)$ – int64int32nag_int array

$\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{nz}+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{nz}+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}$.

9:     $\mathrm{bl}\left(\mathbf{n}+\mathbf{m}\right)$ – double array

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

10:   $\mathrm{bu}\left(\mathbf{n}+\mathbf{m}\right)$ – double array

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

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}$.

11:   $\mathrm{start}$ – string (length ≥ 1)

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'}$.

12:   $\mathrm{names}\left(5\right)$ – cell array of strings

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 Description of Monitoring Information.)

13:   $\mathrm{crname}\left(\mathbf{nname}\right)$ – cell array of strings

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

14:   $\mathrm{ns}$ – int64int32nag_int scalar

$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.

15:   $\mathrm{xs}\left(\mathbf{n}+\mathbf{m}\right)$ – double array

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

16:   $\mathrm{intvar}\left(\mathbf{lintvr}\right)$ – int64int32nag_int array

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 function 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.

17:   $\mathrm{istate}\left(\mathbf{n}+\mathbf{m}\right)$ – int64int32nag_int array

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 nag_mip_iqp_sparse (h02ce) 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}$.

18:   $\mathrm{strtgy}$ – int64int32nag_int scalar

Defines the branching strategy adopted by the function.

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

19:   $\mathrm{leniz}$ – int64int32nag_int scalar

The dimension of the array iz.

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

20:   $\mathrm{lenz}$ – int64int32nag_int scalar

The dimension of the array z.

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 nag_file_set_unit_advisory (x04ab)). 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$. (nag_mip_iqp_sparse (h02ce) will then terminate with $\mathbf{ifail}=\mathbf{14}$.)

21:   $\mathrm{monit}$ – function handle or string containing name of m-file

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 string nag_mip_iqp_sparse_dummy_monit (h02cey).

[bstval, halt, count] = monit(intfnd, nodes, depth, obj, x, bstval, bstsol, bl, bu, n, halt, count)

Input Parameters

1:     $\mathrm{intfnd}$ – int64int32nag_int scalar

Contains the number of integer solutions obtained so far.

2:     $\mathrm{nodes}$ – int64int32nag_int scalar

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

3:     $\mathrm{depth}$ – int64int32nag_int scalar

Contains the depth reached in the tree of problems.

4:     $\mathrm{obj}$ – double scalar

Contains the solution value to the sub-problem at this node.

5:     $\mathrm{x}\left(\mathbf{n}\right)$ – double array

Contains the solution vector to the sub-problem at this node.

6:     $\mathrm{bstval}$ – double scalar

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 nag_machine_real_largest (x02al)).

7:     $\mathrm{bstsol}\left(\mathbf{n}\right)$ – double array

Contains the value of the best integer solution obtained so far.

8:     $\mathrm{bl}\left(\mathbf{n}\right)$ – double array

Contains the current lower bounds on the variables at this point.

9:     $\mathrm{bu}\left(\mathbf{n}\right)$ – double array

Contains the current upper bounds on the variables at this point.

10:   $\mathrm{n}$ – int64int32nag_int scalar

Contains the number of variables in the minimization problem.

11:   $\mathrm{halt}$ – logical scalar

Will have the value false.

12:   $\mathrm{count}$ – int64int32nag_int scalar

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.

Output Parameters

1:     $\mathrm{bstval}$ – double scalar

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 nag_mip_iqp_sparse (h02ce) to the largest machine representable number (see nag_machine_real_largest (x02al)). 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 Description). 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.

2:     $\mathrm{halt}$ – logical scalar

If halt is set to true, nag_opt_qpconvex1_sparse_solve (e04nk) 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}=\mathit{true}$ can save considerable unnecessary computation.

3:     $\mathrm{count}$ – int64int32nag_int scalar

Optional Input Parameters

1:     $\mathrm{nz}$ – int64int32nag_int scalar

Default: the dimension of the arrays a, ha. (An error is raised if these dimensions are not equal.)

The number of nonzero elements in $A$.

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

2:     $\mathrm{nname}$ – int64int32nag_int scalar

Default: the dimension of the array crname.

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}$.

3:     $\mathrm{lintvr}$ – int64int32nag_int scalar

Default: the dimension of the array intvar.

$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$.

4:     $\mathrm{mdepth}$ – int64int32nag_int scalar

Default: $2\times \mathbf{n}+20$

Specifies the maximum depth the tree of sub-problems may be developed.

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

Output Parameters

1:     $\mathrm{ns}$ – int64int32nag_int scalar

The final number of superbasics. This will be zero for FP and LP problems.

2:     $\mathrm{xs}\left(\mathbf{n}+\mathbf{m}\right)$ – double array

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

3:     $\mathrm{istate}\left(\mathbf{n}+\mathbf{m}\right)$ – int64int32nag_int array

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 Description of the Printed Output), 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 Description of the Printed Output) if $\mathbf{Scale\; Option}=0$).

4:     $\mathrm{miniz}$ – int64int32nag_int scalar

The minimum value of leniz required to start solving the problem. If $\mathbf{ifail}=\mathbf{14}$, nag_mip_iqp_sparse (h02ce) 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.)

5:     $\mathrm{minz}$ – int64int32nag_int scalar

The minimum value of lenz required to start solving the problem. If $\mathbf{ifail}=\mathbf{15}$, nag_mip_iqp_sparse (h02ce) 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.)

6:     $\mathrm{obj}$ – double scalar

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.

7:     $\mathrm{clamda}\left(\mathbf{n}+\mathbf{m}\right)$ – double array

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.

8:     $\mathrm{ifail}$ – int64int32nag_int scalar

$\mathbf{ifail}=\mathbf{0}$ unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

W  $\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 ${\mathit{z}}^{\mathrm{T}}HZ$ (see Definition of the Working Set and Search Direction) 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 nag_opt_qpconvex1_sparse_solve (e04nk).

   $\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 nag_mip_iqp_sparse (h02ce).

   $\mathbf{ifail}=12$

Not enough real workspace for the basis factors. Increase lenz and rerun nag_mip_iqp_sparse (h02ce).

   $\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 nag_mip_iqp_sparse (h02ce).

   $\mathbf{ifail}=15$

Not enough real workspace to start solving the problem. Increase lenz to at least minz and rerun nag_mip_iqp_sparse (h02ce).

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

   $\mathbf{ifail}=-399$

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

   $\mathbf{ifail}=-999$

Dynamic memory allocation failed.

Accuracy

Further Comments

Description of the Printed Output

Example

Open in the MATLAB editor: h02ce_example

function h02ce_example


fprintf('h02ce example results\n\n');

n     = int64(7);
m     = int64(8);
iobj  = m;
ncolh = n;
big   = 1.e25;

a = [ 1.00  0.15  0.03  0.02  0.02  0.70  0.02   -200 ...
      1.00  0.04  0.05  0.04  0.03  0.75  0.06  -2000 ...
      1.00  0.02  0.08  0.01        0.80  0.08  -2000 ...
      1.00  0.04  0.02  0.02        0.75  0.12  -2000 ...
      1.00  0.02  0.06  0.02  0.01  0.80  0.02  -2000 ...
      1.00  0.01  0.01              0.97  0.01    400 ...
      1.00  0.03                          0.97    400];
ha = int64([1 2 3 4 5 6 7 8 ...
              1 2 3 4 5 6 7 8 ...
              1 2 3 4   6 7 8 ...
              1 2 3 4   6 7 8 ...
              1 2 3 4 5 6 7 8 ...
              1 2 3     6 7 8  ...
              1 2         7 8]);
ka = [int64(1) 9 17 24 31 39 45 49];
bl = [   0      0    400    100      0     0    0  ...
      2000   -big   -big   -big   -big  1500  250 -big];
bu = [ 200   2500    800    700   1500   big  big  ...
      2000     60    100     40     30   big  300  big];
start = 'C';
names = {'        ', '        ', '        ', '        ', '        '};
crname = {'...x1...', '...x2...', '...x3...', '...x4...', '...x5...'  ...
          '...x6...', '...x7...', '..row1..', '..row2..', '..row3..'  ...
          '..row4..', '..row5..', '..row6..', '..row7..', '..cost..'};
ns = int64(0);
xs = zeros(n+m,1);
intvar = [int64(2) 3 4 5 6 7 -1 0 0 0];
istate = zeros(n+m, 1, 'int64');
strtgy = int64(3);
leniz  = int64(100000);
lenz   = int64(100000);

% Print Options
h02cg('Nolist');
h02cg('Print level = 0');

[ns, xs, istate, miniz, minz, obj, clamda, ifail] = ...
h02ce( ...
       n, m, iobj, ncolh, @qphx, a, ha, ka, bl, bu, start, names, ...
       crname, ns, xs, intvar, istate, strtgy, leniz, lenz, @monit);


fprintf('Optimal Integer Value is = %20.8e\n',obj);
disp('Components are:');
for j=1:7
  fprintf('x(%2d) = %12.8f\n',j,xs(j));
end



function [hx] = qphx(nstate, ncolh, x)
  hx = zeros(ncolh,1);
  hx(1) = 2*x(1);
  hx(2) = 2*x(2);
  hx(3) = 2*(x(3)+x(4));
  hx(4) = hx(3);
  hx(5) = 2*x(5);
  hx(6) = 2*(x(6)+x(7));
  hx(7) = hx(6);

function [bstval, halt, count] = monit(intfnd,nodes,depth,obj,x,bstval, ...
                                       bstsol,bl,bu,n,halt,count)
                                      halt = false;
  if intfnd == 0
    bstval = -1847510;
  elseif intfnd>count
    fprintf('New integer solution found\n');
    fprintf('  Nodes solved so far: %20d\n', nodes);
    fprintf('  Reached depth:       %20d\n', depth);
    fprintf('  Solution value at current node: %13.5e\n', obj);
    fprintf('  Solution vector at current node:\n');
    fprintf('     %13.5e\n',x);
    fprintf('  Current best function value: %13.5e\n', bstval);
    fprintf('  Current best solution:\n');
    fprintf('     %13.5e\n',bstsol);
    fprintf('  Current lower and upper bounds:\n');
    fprintf('    %13.5e    %13.5e\n', [bl' bu']');
    fprintf('\n');
  end
  count = intfnd;

h02ce example results

New integer solution found
  Nodes solved so far:                  272
  Reached depth:                         18
  Solution value at current node:  -1.84752e+06
  Solution vector at current node:
       0.00000e+00
       3.55000e+02
       6.45000e+02
       1.64000e+02
       4.10000e+02
       2.75000e+02
       1.51000e+02
  Current best function value:  -1.84752e+06
  Current best solution:
       0.00000e+00
       3.55000e+02
       6.45000e+02
       1.64000e+02
       4.10000e+02
       2.75000e+02
       1.51000e+02
  Current lower and upper bounds:
      0.00000e+00      2.00000e+02
      3.55000e+02      3.55000e+02
      4.00000e+02      6.45000e+02
      1.64000e+02      1.64000e+02
      0.00000e+00      1.50000e+03
      0.00000e+00      1.00000e+25
      0.00000e+00      1.00000e+25

Optimal Integer Value is =      -1.84751800e+06
Components are:
x( 1) =   0.00000000
x( 2) = 355.00000000
x( 3) = 645.00000000
x( 4) = 164.00000000
x( 5) = 410.00000000
x( 6) = 275.00000000
x( 7) = 151.00000000

Algorithmic Details

Overview

Definition of the Working Set and Search Direction

The Main Iteration

Miscellaneous

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

h02cg('Print Level = 5')

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 nag_machine_precision (x02aj)).

Description of Monitoring Information