NAG C Library Function Document

nag_ip_bb (h02bbc)

1

Purpose

2

Specification

3

Description

3.1

Suitability of BB Method for MIQP Problems

3.2

Maximization Problems

4

References

5

Arguments

1:    $\mathbf{n}$ – IntegerInput

On entry: $n$, the number of variables.

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

2:    $\mathbf{m}$ – IntegerInput

On entry: $m$, the number of general linear constraints.

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

3:    $\mathbf{a}\left[\mathbf{m}\times \mathbf{tda}\right]$ – const doubleInput

Note: the $\left(i,j\right)$th element of the matrix $A$ is stored in $\mathbf{a}\left[\left(i-1\right)\times \mathbf{tda}+j-1\right]$.

On entry: the $\mathit{i}$th row of a must contain the coefficients of the $\mathit{i}$th general linear constraint, for $\mathit{i}=1,2,\dots ,m$.

If $\mathbf{m}=0$, the array a is not referenced and may be NULL.

4:    $\mathbf{tda}$ – IntegerInput

On entry: the stride separating matrix column elements in the array a.

Constraint: if $\mathbf{m}>0$, $\mathbf{tda}\ge \mathbf{n}$

5:    $\mathbf{bl}\left[\mathbf{n}+\mathbf{m}\right]$ – const doubleInput

6:    $\mathbf{bu}\left[\mathbf{n}+\mathbf{m}\right]$ – const doubleInput

On entry: 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$ elements the bounds for the general linear constraints (if any). To specify a nonexistent lower bound (i.e., $l_j=-\infty$), set $\mathbf{bl}\left[j-1\right]\le -\mathbf{options}\mathbf{.}\mathbf{inf\_bound}$, and to specify a nonexistent upper bound (i.e., $u_j=+\infty$), set $\mathbf{bu}\left[j-1\right]\ge \mathbf{options}\mathbf{.}\mathbf{inf\_bound}$, where $\mathbf{options}\mathbf{.}\mathbf{inf\_bound}$ is one of the optional parameters (default value ${10}^{20}$, see Section 11.2). To specify the $j$th constraint as an equality, set $\mathbf{bl}\left[j-1\right]=\mathbf{bu}\left[j-1\right]=\beta$, say, where $\left|\beta \right|<\mathbf{options}\mathbf{.}\mathbf{inf\_bound}$.

Constraint: $\mathbf{bl}\left[\mathit{j}\right]\le \mathbf{bu}\left[\mathit{j}\right]$, for $\mathit{j}=0,1,\dots ,\mathbf{n}+\mathbf{m}-1$.

7:    $\mathbf{intvar}\left[\mathbf{n}\right]$ – const Nag_BooleanInput

On entry: indicates which are the integer variables in the problem. For example, if $x_j$ is an integer variable then $\mathbf{intvar}\left[j-1\right]$ must be set to $1$, and 0 otherwise. The degenerate case, in which all elements of intvar are zero, is allowed. In this case, nag_ip_bb (h02bbc) solves a single LP or QP problem (depending on the problem type as specified by the optional parameter $\mathbf{options}\mathbf{.}\mathbf{prob}$, see Section 11.2).

Constraint: $\mathbf{intvar}\left[\mathit{j}\right]=0\text{ or }1$, for $\mathit{j}=0,1,\dots ,\mathbf{n}-1$.

8:    $\mathbf{cvec}\left[\mathbf{n}\right]$ – const doubleInput

On entry: the coefficients $c_j$ of the explicit linear term of the objective function when the problem is of type MILP, MIQP2 or MIQP4. The default problem type is MILP; other problem types can be specified using the optional parameter $\mathbf{options}\mathbf{.}\mathbf{prob}$, see Section 11.2.

If the problem is of type MIQP1 or MIQP3, cvec is not referenced and may be NULL.

9:    $\mathbf{h}\left[\mathbf{n}\times \mathbf{tdh}\right]$ – const doubleInput

On entry: h may be used to store the quadratic term $H$ of the MIQP objective function if desired. The elements of h are accessed only by the function qphess; thus, h is not accessed if the problem is of the type MILP (the default) and may be NULL.

The number of rows of h is denoted by $n_H$ and its default value is equal to $n$. (The optional parameter $\mathbf{options}\mathbf{.}\mathbf{hrows}$ may be used to specify a value of $n_H<n$; see Section 11.2).

If the problem is of type MIQP1 or MIQP2, the first $n_H$ rows and columns of h must contain the leading $n_H$ by $n_H$ rows and columns of the symmetric Hessian matrix. Only the diagonal and upper triangular elements of the leading $n_H$ rows and columns of h are referenced. The remaining elements need not be assigned.

For problems of type MIQP3 and MIQP4, the first $n_H$ rows of h must contain an $n_H$ by $n$ upper trapezoidal factor of the Hessian matrix. The factor need not be of full rank, i.e., some of the diagonals 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 $n_H$ rows of $H$ are assumed to be zero and need not be assigned.

In some cases, you need not use h to store $H$ explicitly (see the specification of function qphess).

10:  $\mathbf{tdh}$ – IntegerInput

On entry: the stride separating matrix column elements in the array h.

Constraint: $\mathbf{tdh}\ge \mathbf{n}$ or at least the value of the optional parameter $\mathbf{options}\mathbf{.}\mathbf{hrows}$ if it is set. This constraint is enforced only for problems of type MIQP in which the qphess argument is null.

11:  $\mathbf{qphess}$ – function, supplied by the userExternal Function

In general, you need not provide a version of qphess, because a ‘default’ function is included in the NAG C Library. If the default function is required then the NAG defined null function pointer, NULLFN, should be supplied in the call to nag_ip_bb (h02bbc). The algorithm of nag_ip_bb (h02bbc) requires only the product of $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 matrix $H$ explicitly.

qphess is not referenced for problems of type MILP (the default), in which case qphess should be replaced by NULLFN.

The specification of qphess is:

void  qphess (Integer n, Integer jthcol, const double h[], Integer tdh, const double x[], double hx[], Nag_Comm *comm)

1:    $\mathbf{n}$ – IntegerInput

On entry: $n$, the number of variables.

2:    $\mathbf{jthcol}$ – IntegerInput

On entry: jthcol specifies whether or not the vector $x$ is a column of the identity matrix.

$\mathbf{jthcol}=j>0$

The vector $x$ is the $j$th column of the identity matrix, and hence $Hx$ is the $j$th column of $H$, which can sometimes be computed very efficiently 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.

$\mathbf{jthcol}=0$

$x$ has no special form.

3:    $\mathbf{h}\left[\mathbf{n}\times \mathbf{tdh}\right]$ – const doubleInput

On entry: the matrix $H$ of the QP objective function. The matrix element $H_{ij}$ is contained in $\mathbf{h}\left[\left(i-1\right)\times tdh+j-1\right]$ for $i=1,2,\dots ,n$ and $j=1,2,\dots ,n$. In some situations, it may be desirable to compute $Hx$ without accessing h – for example, if $H$ is sparse or has special structure. (This is illustrated in the function qphess in Section 10.) The arguments h and tdh may then refer to any convenient array.

4:    $\mathbf{tdh}$ – IntegerInput

On entry: the stride separating matrix column elements in the array h.

5:    $\mathbf{x}\left[\mathbf{n}\right]$ – const doubleInput

On entry: the vector $x$.

6:    $\mathbf{hx}\left[\mathbf{n}\right]$ – doubleOutput

On exit: the product $Hx$.

7:    $\mathbf{comm}$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to qphess.

flag – IntegerInput/Output

On entry: qphess is called with $\mathbf{comm}\mathbf{\to }\mathbf{flag}$ set to a non-negative number.

On exit: if qphess resets $\mathbf{comm}\mathbf{\to }\mathbf{flag}$ to some negative number then nag_ip_bb (h02bbc) will terminate immediately with the error indicator NE_USER_STOP. If fail is supplied to nag_ip_bb (h02bbc), $\mathbf{fail}\mathbf{.}\mathbf{errnum}$ will be set to your setting of $\mathbf{comm}\mathbf{\to }\mathbf{flag}$.

first – Nag_BooleanInput

On entry: will be set to Nag_TRUE on the first call to qphess and Nag_FALSE for all subsequent calls.

nf – IntegerInput

On entry: the number of calls made to qphess including the current one.

user – double *

iuser – Integer *

p – Pointer 

The type Pointer will be void * with a C compiler that defines void * and char * otherwise.

Before calling nag_ip_bb (h02bbc) these pointers may be allocated memory and initialized with various quantities for use by qphess when called from nag_ip_bb (h02bbc).

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

Note: qphess should be tested separately before being used in conjunction with nag_ip_bb (h02bbc). The input arrays h and x must not be changed by qphess.

12:  $\mathbf{x}\left[\mathbf{n}\right]$ – doubleInput/Output

On entry: an initial estimate of the solution of the first sub-problem (the problem as described in Section 3).

If optional parameter $\mathbf{options}\mathbf{.}\mathbf{branch\_dir}=\mathrm{Nag\_Branch\_InitX}$ (which is not the default value), then the initial values in x of the integer variables influence the branching procedure in the BB algorithm. Typically, an estimate of the values of the integer variables in the IP solution would be provided in this case. See Section 11.2 for details.

On exit: with $\mathbf{fail}\mathbf{.}\mathbf{code}=\mathrm{NE\_NOERROR}$, x contains a solution which will be an estimate of either the optimum integer solution or the first integer solution, depending on the value of optional parameter $\mathbf{options}\mathbf{.}\mathbf{first\_soln}$. If $\mathbf{fail}\mathbf{.}\mathbf{code}=\mathbf{NW\_MIP\_MAX\_NODES\_INT\_SOL}$, NW_MIP_MAX_DEPTH_INT_SOL, NW_MIP_MAX_ITER_INT_SOL, or NE_MIP_HESS_TOO_BIG_INT_SOL then x contains a solution which may not be the optimal IP solution because nag_ip_bb (h02bbc) was unable to investigate all of the nodes. See Section 6 for more details.

13:  $\mathbf{objf}$ – double *Output

On exit: with $\mathbf{fail}\mathbf{.}\mathbf{code}=\mathrm{NE\_NOERROR}$, NW_MIP_MAX_NODES_INT_SOL, NW_MIP_MAX_DEPTH_INT_SOL, NW_MIP_MAX_ITER_INT_SOL, or NE_MIP_HESS_TOO_BIG_INT_SOL, objf contains the value of the objective function for the IP solution.

14:  $\mathbf{options}$ – Nag_H02_Opt *Input/Output

On entry/exit: a pointer to a structure of type Nag_H02_Opt whose members are optional parameters for nag_ip_bb (h02bbc). These structure members offer the means of adjusting some of the argument values of the algorithm and on output will supply further details of the results. A description of the members of options is given below in Section 11.

The options structure also allows names to be assigned to the variables and constraints of the problem, which are then used in solution output. In particular, if the problem is defined by an MPSX file, the function nag_ip_mps_read (h02buc) may be used to read the file, and to store the variable and constraint names in options for use by nag_ip_bb (h02bbc).

If any of these optional parameters are required then the structure options should be declared and initialized by a call to nag_ip_init (h02xxc) and supplied as an argument to nag_ip_bb (h02bbc). However, if the optional parameters are not required the NAG defined null pointer, H02_DEFAULT, can be used in the function call.

15:  $\mathbf{comm}$ – Nag_Comm *Input/Output

Note: comm is a NAG defined type (see Section 3.3.1.1 in How to Use the NAG Library and its Documentation).

On entry/exit: structure containing pointers for communication to the user-supplied function, qphess, and the optional user-defined printing function. See the description of qphess and Section 11.3.1 for details. If you do not need to make use of this communication feature the null pointer NAGCOMM_NULL may be used in the call to nag_ip_bb (h02bbc); comm will then be declared internally for use in calls to user-supplied functions.

16:  $\mathbf{fail}$ – NagError *Input/Output

The NAG error argument (see Section 3.7 in How to Use the NAG Library and its Documentation).

6

Error Indicators and Warnings

NE_2_INT_ARG_LT

On entry, $\mathbf{tda}=〈\mathit{\text{value}}〉$ while $\mathbf{n}=〈\mathit{\text{value}}〉$. These arguments must satisfy $\mathbf{tda}\ge \mathbf{n}$.

On entry, $\mathbf{tdh}=〈\mathit{\text{value}}〉$ while $\mathbf{n}=〈\mathit{\text{value}}〉$. These arguments must satisfy $\mathbf{tdh}\ge \mathbf{n}$.

On entry, $\mathbf{tdh}=〈\mathit{\text{value}}〉$ while $\mathbf{options}\mathbf{.}\mathbf{hrows}=〈\mathit{\text{value}}〉$. These arguments must satisfy $\mathbf{tdh}\ge \mathbf{options}\mathbf{.}\mathbf{hrows}$.

NE_ALLOC_FAIL

Dynamic memory allocation failed.

NE_BAD_PARAM

On entry, argument $\mathbf{options}\mathbf{.}\mathbf{branch\_dir}$ had an illegal value.

On entry, argument $\mathbf{options}\mathbf{.}\mathbf{nodsel}$ had an illegal value.

On entry, argument $\mathbf{options}\mathbf{.}\mathbf{print\_level}$ had an illegal value.

On entry, argument $\mathbf{options}\mathbf{.}\mathbf{prob}$ had an illegal value.

On entry, argument $\mathbf{options}\mathbf{.}\mathbf{varsel}$ had an illegal value.

NE_BOUND

The lower bound for variable $〈\mathit{\text{value}}〉$ (array element $\mathbf{bl}\left[〈\mathit{\text{value}}〉\right]$) is greater than the upper bound.

NE_BOUND_LCON

The lower bound for linear constraint $〈\mathit{\text{value}}〉$ (array element $\mathbf{bl}\left[〈\mathit{\text{value}}〉\right]$) is greater than the upper bound.

NE_CVEC_NULL

$\mathbf{options}\mathbf{.}\mathbf{prob}=〈\mathit{\text{value}}〉$ but argument $\mathbf{cvec}=$ NULL.

NE_H_NULL

$\mathbf{options}\mathbf{.}\mathbf{prob}=〈\mathit{\text{value}}〉$, qphess is NULL but argument h is also NULL. If the default function for qphess is to be used for this problem then an array must be supplied in argument h.

NE_INT_ARG_LT

On entry, $\mathbf{m}=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{m}\ge 0$.

On entry, $\mathbf{n}=〈\mathit{\text{value}}〉$.
Constraint: $\mathbf{n}\ge 1$.

NE_INTERNAL_ERROR

An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.

NE_INVALID_INT_RANGE_1

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{hrows}$ is not valid. Correct range is $\mathbf{n}\ge \mathbf{options}\mathbf{.}\mathbf{hrows}\ge 0$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{max\_depth}$ is not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{max\_depth}\ge 2$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{max\_df}$ is not valid. Correct range is $\mathbf{n}\ge \mathbf{options}\mathbf{.}\mathbf{max\_df}\ge 1$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{max\_iter}$ is not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{max\_iter}\ge 0$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{max\_nodes}$ is not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{max\_nodes}=\mathtt{ALL\_NODES}$ or $\mathbf{options}\mathbf{.}\mathbf{max\_nodes}\ge 1$.

NE_INVALID_REAL_RANGE_F

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{feas\_tol}$ is not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{feas\_tol}>0.0$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{inf\_bound}$ is not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{inf\_bound}>0.0$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{soln\_tol}$ is not valid. Correct range is $\mathbf{options}\mathbf{.}\mathbf{soln\_tol}\ge 0.0$.

NE_INVALID_REAL_RANGE_FF

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{int\_tol}$ is not valid. Correct range is $0.0<\mathbf{options}\mathbf{.}\mathbf{int\_tol}<1.0$.

Value $〈\mathit{\text{value}}〉$ given to $\mathbf{options}\mathbf{.}\mathbf{rank\_tol}$ is not valid. Correct range is $0.0\le \mathbf{options}\mathbf{.}\mathbf{rank\_tol}<1.0$.

NE_MIP_HESS_TOO_BIG_INT_SOL

Reduced Hessian exceeds assigned dimension during BB tree search. $\mathbf{options}\mathbf{.}\mathbf{max\_df}=〈\mathit{\text{value}}〉$. An IP solution was found.
This error can only occur with MIQP problems. Whilst attempting to solve a node during the BB tree search, the QP algorithm needed to expand the reduced Hessian when it was already at its maximum dimension, as specified by the optional parameter $\mathbf{options}\mathbf{.}\mathbf{max\_df}$. No further nodes were examined. An IP solution was found but it may not be optimal.
The value of the argument $\mathbf{options}\mathbf{.}\mathbf{max\_df}$ is too small. Rerun nag_ip_bb (h02bbc) with a larger value. The IP objective obtained should be assigned to $\mathbf{options}\mathbf{.}\mathbf{int\_obj\_bound}$ to aid the BB tree search in the repeated run.

NE_MIP_HESS_TOO_BIG_NO_INT_SOL

Reduced Hessian exceeds assigned dimension during BB tree search. $\mathbf{options}\mathbf{.}\mathbf{max\_df}=〈\mathit{\text{value}}〉$. No IP solution was found.
This error can only occur with MIQP problems. Whilst attempting to solve a node during the BB tree search, the QP algorithm needed to expand the reduced Hessian when it was already at its maximum dimension, as specified by the optional parameter $\mathbf{options}\mathbf{.}\mathbf{max\_df}$. No further nodes were examined. No IP solution was found amongst the nodes examined.
The value of the argument $\mathbf{options}\mathbf{.}\mathbf{max\_df}$ is too small. Rerun nag_ip_bb (h02bbc) with a larger value.

NE_MIP_ROOT_HESS_TOO_BIG

Reduced Hessian exceeds assigned dimension at root node. $\mathbf{options}\mathbf{.}\mathbf{max\_df}=〈\mathit{\text{value}}〉$.
This error can only occur with MIQP problems. Whilst attempting to solve the root node, the QP algorithm needed to expand the reduced Hessian when it was already at its maximum dimension, as specified by the optional parameter $\mathbf{options}\mathbf{.}\mathbf{max\_df}$.
The value of the argument $\mathbf{options}\mathbf{.}\mathbf{max\_df}$ is too small. Rerun nag_ip_bb (h02bbc) with a larger value.

NE_MIP_ROOT_INFEAS

The root node of the BB tree is infeasible.
A feasible point could not be found for the original LP or QP problem, i.e., it was not possible to satisfy all the constraints to within the feasibility tolerance (determined by optional parameter $\mathbf{options}\mathbf{.}\mathbf{feas\_tol}$). If the data for the constraints are accurate only to the absolute precision $\sigma$, you should ensure that the value of the feasibility tolerance is greater than $\sigma$. For example, if all elements of $A$ are of order unity and are accurate only to three decimal places, the feasibility tolerance should be at least ${10}^{-3}$ (see Section 9).

NE_MIP_ROOT_MAX_ITER

The maximum number of iterations (determined by optional parameter $\mathbf{options}\mathbf{.}\mathbf{max\_iter}$) was reached before normal termination occurred for the original LP or QP problem (see Section 9).

The maximum number of iterations, $〈\mathit{\text{value}}〉$, was performed before normal termination occurred for the root node of the BB tree.

NE_MIP_ROOT_UNBOUNDED

The root node of the BB tree appears to be unbounded.
See Section 12 for advice.

NE_NAME_TOO_LONG

The character string pointed to by $\mathbf{options}\mathbf{.}\mathbf{crnames}\left[〈\mathit{\text{value}}〉\right]$ is too long. It should be no longer than 8 characters.

NE_NOT_APPEND_FILE

Cannot open file $〈\mathit{string}〉$ for appending.

NE_NOT_CLOSE_FILE

Cannot close file $〈\mathit{string}〉$.

NE_OPT_NOT_INIT

Options structure not initialized.

NE_PRIORITY_NULL

$\mathbf{options}\mathbf{.}\mathbf{varsel}=\mathrm{Nag\_Use\_Priority}$ but $\mathbf{options}\mathbf{.}\mathbf{priority}$ is NULL.

NE_USER_STOP

User requested termination, user flag value $=〈\mathit{\text{value}}〉$.
This exit occurs if you set $\mathbf{comm}\mathbf{\to }\mathbf{flag}$ to a negative value in qphess. If fail is supplied the value of $\mathbf{fail}\mathbf{.}\mathbf{errnum}$ will be the same as your setting of $\mathbf{comm}\mathbf{\to }\mathbf{flag}$.

NE_WRITE_ERROR

Error occurred when writing to file $〈\mathit{string}〉$.

NW_MIP_MAX_DEPTH_INT_SOL

An IP solution was found but the search has been terminated because the maximum allowed tree depth (as determined by optional parameter $\mathbf{options}\mathbf{.}\mathbf{max\_depth}$) has been reached.
Increase $\mathbf{options}\mathbf{.}\mathbf{max\_depth}$ and rerun nag_ip_bb (h02bbc). The IP objective obtained should be assigned to $\mathbf{options}\mathbf{.}\mathbf{int\_obj\_bound}$ to aid the BB tree search in the repeated run.

NW_MIP_MAX_DEPTH_NO_INT_SOL

The maximum allowed tree depth (as determined by optional parameter $\mathbf{options}\mathbf{.}\mathbf{max\_depth}$) has been reached before any integer solution has been found.
Increase $\mathbf{options}\mathbf{.}\mathbf{max\_depth}$ and rerun nag_ip_bb (h02bbc).

NW_MIP_MAX_ITER_INT_SOL

The IP solution found may not be the optimum. The search had to be terminated in at least one branch of the BB tree because the iteration limit was reached.
It was not possible to solve at least one node of the BB tree, which means that the tree search could not be completed. An IP solution was found but a better one may be present in the unsearched portion of the tree. See Section 9 for more information.

NW_MIP_MAX_ITER_NO_INT_SOL

No IP solution was found but the search had to be terminated in at least one branch of the BB tree because the iteration limit was reached.
It was not possible to solve at least one node of the BB tree, which means that the tree search could not be completed. No IP solution was found but one may be present in the unsearched portion of the tree. See Section 9 for more information.

NW_MIP_MAX_NODES_INT_SOL

The IP solution found is the best for the number of nodes (as determined by optional parameter $\mathbf{options}\mathbf{.}\mathbf{max\_nodes}$) investigated in the BB tree.
Increase $\mathbf{options}\mathbf{.}\mathbf{max\_nodes}$ and rerun nag_ip_bb (h02bbc). The IP objective obtained should be assigned to $\mathbf{options}\mathbf{.}\mathbf{int\_obj\_bound}$ to aid the BB tree search in the repeated run.

NW_MIP_MAX_NODES_NO_INT_SOL

No integer solution was found for the number of nodes (as determined by $\mathbf{options}\mathbf{.}\mathbf{max\_nodes}$) investigated in the BB tree.
Increase $\mathbf{options}\mathbf{.}\mathbf{max\_nodes}$ and rerun nag_ip_bb (h02bbc).

NW_MIP_NO_INT_SOL

No feasible IP solution was found, i.e., it was not possible to satisfy all the integer variables to within optional parameter $\mathbf{options}\mathbf{.}\mathbf{int\_tol}$.
It may be appropriate to increase $\mathbf{options}\mathbf{.}\mathbf{int\_tol}$ and rerun nag_ip_bb (h02bbc).

NW_OVERFLOW_WARN

Serious ill-conditioning in the working set after adding constraint $〈\mathit{\text{value}}〉$. Overflow may occur in subsequent iterations.
If overflow occurs preceded by this warning then serious ill-conditioning has probably occurred in the working set when adding a constraint during the solution of a node in the BB tree. It may be possible to avoid the difficulty by increasing the magnitude of the optional parameter $\mathbf{options}\mathbf{.}\mathbf{feas\_tol}$ and rerunning the program. If the problem recurs even after this change, see Section 9.

7

Accuracy

8

Parallelism and Performance

9

Further Comments

10

Example

10.1

Program Text

Program Text (h02bbce.c)

10.2

Program Data

Program Data (h02bbce.d)

10.3

Program Results

Program Results (h02bbce.r)

11

Optional Parameters

11.1

Optional Parameter Checklist and Default Values

11.2

Description of the Optional Parameters

void (*print_fun)(const Nag_Search_State *st, Nag_Comm *comm);

11.3

Description of Printed Output

11.3.1

Output of results via a user-defined printing function

void (*print_fun)(const Nag_Search_State *st, Nag_Comm *comm);

node_num – Integer

The current node number of the BB tree being investigated.

parent_node – Integer

The parent node number of the current node.

node_status – Nag_NodeStatus

The status of the current node. The possible values of $\mathbf{st}\mathbf{\to }\mathbf{node\_status}$ and their meanings are as follows:

$\mathrm{Nag\_NS\_NotBranched}$	the node has been solved but the branch cannot yet be eliminated from the search.
$\mathrm{Nag\_NS\_Integer}$	an integer solution was found at this node. There is no need to search this branch further.
$\mathrm{Nag\_NS\_Bounded}$	the objective value exceeds the upper bound on the optimal IP solution. There is no need to search this branch further.
$\mathrm{Nag\_NS\_Infeasible}$	the problem was infeasible at this node. There is no need to search this branch further.
$\mathrm{Nag\_NS\_Terminated}$	the iteration limit was exceeded at this node. The search has to be terminated prematurely for this branch.

objf – double

If $\mathbf{st}\mathbf{\to }\mathbf{node\_status}=\mathbf{Nag\_NS\_NotBranched}\text{, }\mathbf{Nag\_NS\_Integer}\text{ or }\mathbf{Nag\_NS\_Bounded}$, then objf holds the objective value.

branch_index – Integer

The index in $x$ of the variable chosen for branching.

x_lo – double

The lower bound on the branching variable.

x_up – double

The upper bound on the branching variable.

x_before – double

The non-integer value of the branching variable before the node was solved.

x_after – double

The value of the branching variable after the node was solved.

depth – Integer

The depth of the BB tree at the current node.

endstate – Nag_EndState

The state of termination of the sub-problem solver at the root node. Some of these states result in immediate termination of the algorithm. If this is the case, then no valid solution is available. The other states allow the algorithm to proceed with the BB tree search. Possible values of $\mathbf{st}\mathbf{\to }\mathbf{endstate}$ and their correspondence, if any, to the exit value of fail from nag_ip_bb (h02bbc) are:

Value of $\mathbf{st}\mathbf{\to }\mathbf{endstate}$	Value of fail
$\mathrm{Nag\_Optimal}$	(BB search may proceed)
$\mathrm{Nag\_Deadpoint}$	(BB search may proceed)
$\mathrm{Nag\_Weakmin}$	(BB search may proceed)
$\mathrm{Nag\_Unbounded}$	NE_MIP_ROOT_UNBOUNDED
$\mathrm{Nag\_Infeasible}$	NE_MIP_ROOT_INFEAS
$\mathrm{Nag\_Too\_Many\_Iter}$	NE_MIP_ROOT_MAX_ITER
$\mathrm{Nag\_Hess\_Too\_Big}$	NE_MIP_ROOT_HESS_TOO_BIG

n – Integer

The number of variables.

m – Integer

The number of linear constraints.

objf – double

The value of the objective function.

x – double

The components $\mathbf{x}\left[\mathit{j}-1\right]$ of the solution $x$, for $\mathit{j}=1,2,\dots ,\mathbf{st}\mathbf{\to }\mathbf{n}$.

ax – double

If $\mathbf{st}\mathbf{\to }\mathbf{m}>0$, $\mathbf{st}\mathbf{\to }\mathbf{ax}\left[\mathit{j}-1\right]$ contains the components of the linear constraint vector, for $\mathit{j}=1,2,\dots ,\mathbf{st}\mathbf{\to }\mathbf{m}$.

state – Integer

Contains the status of the $\mathbf{st}\mathbf{\to }\mathbf{n}$ variables and $\mathbf{st}\mathbf{\to }\mathbf{m}$ general linear constraints. See Section 11.2 for a description of the possible status values.

lambda – double

Contains the $\mathbf{st}\mathbf{\to }\mathbf{n}+\mathbf{st}\mathbf{\to }\mathbf{m}$ values of the Lagrange multipliers.

bl – double

Contains the $\mathbf{st}\mathbf{\to }\mathbf{n}+\mathbf{st}\mathbf{\to }\mathbf{m}$ lower bounds on the variables.

bu – double

Contains the $\mathbf{st}\mathbf{\to }\mathbf{n}+\mathbf{st}\mathbf{\to }\mathbf{m}$ upper bounds on the variables.

endstate – Nag_EndState

The state of termination of nag_ip_bb (h02bbc). Possible values of $\mathbf{st}\mathbf{\to }\mathbf{endstate}$ and their correspondence to the exit value of fail are shown below.

Value of $\mathbf{st}\mathbf{\to }\mathbf{endstate}$	Value of fail
$\mathrm{Nag\_MIP\_Best\_ISol}$ or
$\mathrm{Nag\_MIP\_Stop\_First\_ISol}$	NE_NOERROR
$\mathrm{Nag\_MIP\_No\_ISol}$	NW_MIP_NO_INT_SOL
$\mathrm{Nag\_MIP\_Root\_Unbounded}$	NE_MIP_ROOT_UNBOUNDED
$\mathrm{Nag\_MIP\_Root\_Infeasible}$	NE_MIP_ROOT_INFEAS
$\mathrm{Nag\_MIP\_Root\_Max\_Itn}$	NE_MIP_ROOT_MAX_ITER
$\mathrm{Nag\_MIP\_Root\_Big\_Hess}$	NE_MIP_ROOT_HESS_TOO_BIG
$\mathrm{Nag\_MIP\_Max\_Itn\_ISol}$	NW_MIP_MAX_ITER_INT_SOL
$\mathrm{Nag\_MIP\_Max\_Itn\_No\_ISol}$	NW_MIP_MAX_ITER_NO_INT_SOL
$\mathrm{Nag\_MIP\_Big\_Hess\_ISol}$	NE_MIP_HESS_TOO_BIG_INT_SOL
$\mathrm{Nag\_MIP\_Big\_Hess\_No\_ISol}$	NE_MIP_HESS_TOO_BIG_NO_INT_SOL
$\mathrm{Nag\_MIP\_Max\_Nodes\_ISol}$	NW_MIP_MAX_NODES_INT_SOL
$\mathrm{Nag\_MIP\_Max\_Nodes\_No\_ISol}$	NW_MIP_MAX_NODES_NO_INT_SOL
$\mathrm{Nag\_MIP\_Max\_Depth\_ISol}$	NW_MIP_MAX_DEPTH_INT_SOL
$\mathrm{Nag\_MIP\_Max\_Depth\_No\_ISol}$	NW_MIP_MAX_DEPTH_NO_INT_SOL

n – Integer

The number of variables.

m – Integer

The number of linear constraints.

nnodes – Integer

The number of nodes examined during the BB tree search.

objf – double

The value of the objective function.

x – double

The components $\mathbf{x}\left[\mathit{j}-1\right]$ of the solution $x$, for $\mathit{j}=1,2,\dots ,\mathbf{st}\mathbf{\to }\mathbf{n}$.

ax – double

If $\mathbf{st}\mathbf{\to }\mathbf{m}>0$, $\mathbf{st}\mathbf{\to }\mathbf{ax}\left[\mathit{j}-1\right]$ contains the components of the linear constraint vector, for $\mathit{j}=1,2,\dots ,\mathbf{st}\mathbf{\to }\mathbf{m}$.

state – Integer

Contains the status of the $\mathbf{st}\mathbf{\to }\mathbf{n}$ variables and $\mathbf{st}\mathbf{\to }\mathbf{m}$ general linear constraints. See Section 11.2 for a description of the possible status values.

lambda – double

Contains the $\mathbf{st}\mathbf{\to }\mathbf{n}+\mathbf{st}\mathbf{\to }\mathbf{m}$ values of the Lagrange multipliers.

bl – double

Contains the $\mathbf{st}\mathbf{\to }\mathbf{n}+\mathbf{st}\mathbf{\to }\mathbf{m}$ lower bounds on the variables.

bu – double

Contains the $\mathbf{st}\mathbf{\to }\mathbf{n}+\mathbf{st}\mathbf{\to }\mathbf{m}$ upper bounds on the variables.

rootnode_sol_prt – Nag_Boolean

Will be Nag_TRUE when the print function is called with the solution of the root node.

node_prt – Nag_Boolean

Will be Nag_TRUE when the print function is called with the result of the most recently solved node.

sol_prt – Nag_Boolean

Will be Nag_TRUE when the print function is called with the final solution.

user – double

iuser – Integer

p – Pointer 

Pointers for communication of user information. If used they must be allocated memory either before entry to nag_ip_bb (h02bbc) or during a call to qphess or $\mathbf{options}\mathbf{.}\mathbf{print\_fun}$. The type Pointer will be void * with a C compiler that defines void * and char * otherwise.

12

Further Description

12.1

Overview

12.2

Selection of Node and Branching Variable

12.3

Further Reducing the Size of the BB Search Tree