NAG Library Routine Document

h02bbf  (ilp_dense)

1

Purpose

2

Specification

3

Description

4

References

5

Arguments

1:     $\mathbf{itmax}$ – IntegerInput/Output

On entry: an upper bound on the number of iterations for each LP problem.

On exit: unchanged if on entry $\mathbf{itmax}>0$, else $\mathbf{itmax}=\max \left(50,5\times \left(\mathbf{n}+\mathbf{m}\right)\right)$.

2:     $\mathbf{msglvl}$ – IntegerInput

On entry: the amount of printout produced by h02bbf, as indicated below (see Section 5.1 for a description of the printed output). All output is written to the current advisory message unit (as defined by x04abf).

Value	Definition
0	No output.
1	The final IP solution only.
5	One line of output for each node investigated and the final IP solution.
10	The original LP solution (first node), one line of output for each node investigated and the final IP solution.

3:     $\mathbf{n}$ – IntegerInput

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

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

4:     $\mathbf{m}$ – IntegerInput

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

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

5:     $\mathbf{a}\left(\mathbf{lda},*\right)$ – Real (Kind=nag_wp) arrayInput

Note: the second dimension of the array a must be at least $\mathbf{n}$ if $\mathbf{m}>0$ and at least $1$ if $\mathbf{m}=0$.

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

If $\mathbf{m}=0$ then the array a is not referenced.

6:     $\mathbf{lda}$ – IntegerInput

On entry: the first dimension of the array a as declared in the (sub)program from which h02bbf is called.

Constraint: $\mathbf{lda}\ge \max \left(1,\mathbf{m}\right)$.

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

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

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\right)\le -\mathbf{bigbnd}$ and to specify a nonexistent upper bound (i.e., $u_j=+\infty$), set $\mathbf{bu}\left(j\right)\ge \mathbf{bigbnd}$. 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|<\mathbf{bigbnd}$.

Constraints:

• $\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|<\mathbf{bigbnd}$.

9:     $\mathbf{intvar}\left(\mathbf{n}\right)$ – Integer arrayInput

On entry: indicates which are the integer variables in the problem. For example, if $x_{\mathit{j}}$ is an integer variable then $\mathbf{intvar}\left(\mathit{j}\right)$ must be set to $1$, and $0$ otherwise.

Constraints:

• $\mathbf{intvar}\left(\mathit{j}\right)=0$ or $1$, for $\mathit{j}=1,2,\dots ,\mathbf{n}$;
• $\mathbf{intvar}\left(\mathit{j}\right)=1$ for at least one value of $\mathit{j}$.

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

On entry: the coefficients $c_j$ of the objective function $F\left(x\right)=c_1{x}_1+c_2{x}_2+\dots +c_n{x}_n$. The routine attempts to find a minimum of $F\left(x\right)$. If a maximum of $F\left(x\right)$ is desired, $\mathbf{cvec}\left(\mathit{j}\right)$ should be set to $-c_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,n$, so that the routine will find a minimum of $-F\left(x\right)$.

11:   $\mathbf{maxnod}$ – IntegerInput

On entry: the maximum number of nodes that are to be searched in order to find a solution (optimum integer solution). If $\mathbf{maxnod}\le 0$ and $\mathbf{intfst}\le 0$, then the B&B tree search is continued until all the nodes have been investigated.

12:   $\mathbf{intfst}$ – IntegerInput

On entry: specifies whether to terminate the B&B tree search after the first integer solution (if any) is obtained. If $\mathbf{intfst}>0$ then the B&B tree search is terminated at node $k$ say, which contains the first integer solution. For $\mathbf{maxnod}>0$ this applies only if $k\le \mathbf{maxnod}$.

13:   $\mathbf{maxdpt}$ – IntegerInput

On entry: the maximum depth of the B&B tree used for branch and bound.

Suggested value: $\mathbf{maxdpt}=3\times \mathbf{n}/2$.

Constraint: $\mathbf{maxdpt}\ge 2$.

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

On entry: the integer feasibility tolerance; i.e., an integer variable is considered to take an integer value if its violation does not exceed toliv. For example, if the integer variable $x_j$ is near unity then $x_j$ is considered to be integer only if $\left(1-\mathbf{toliv}\right)\le x_j\le \left(1+\mathbf{toliv}\right)$.

On exit: unchanged if on entry $\mathbf{toliv}>0.0$, else $\mathbf{toliv}={10}^{-5}$.

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

On entry: the maximum acceptable absolute violation in each constraint at a ‘feasible’ point (feasibility tolerance); i.e., a constraint is considered satisfied if its violation does not exceed tolfes.

On exit: unchanged if on entry $\mathbf{tolfes}>0.0$, else $\mathbf{tolfes}=\sqrt{\epsilon }$ (where $\epsilon$ is the machine precision).

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

On entry: the ‘infinite’ bound size in the definition of the problem constraints. More precisely, any upper bound greater than or equal to bigbnd will be regarded as $+\infty$ and any lower bound less than or equal to $-\mathbf{bigbnd}$ will be regarded as $-\infty$.

On exit: unchanged if on entry $\mathbf{bigbnd}>0.0$, else $\mathbf{bigbnd}={10}^{20}$.

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

On entry: an initial estimate of the original LP solution.

On exit: with $\mathbf{ifail}=\mathbf{0}$, 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 intfst. If $\mathbf{ifail}=\mathbf{9}$, then x contains a solution which will be an estimate of the best integer solution that was obtained by searching maxnod nodes.

18:   $\mathbf{objmip}$ – Real (Kind=nag_wp)Output

On exit: with $\mathbf{ifail}=\mathbf{0}$ or $\mathbf{9}$, objmip contains the value of the objective function for the IP solution.

19:   $\mathbf{iwork}\left(\mathbf{liwork}\right)$ – Integer arrayCommunication Array

20:   $\mathbf{liwork}$ – IntegerInput

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

Constraint: $\mathbf{liwork}\ge \left(25+\mathbf{n}+\mathbf{m}\right)\times \mathbf{maxdpt}+5\times \mathbf{n}+\mathbf{m}+4$.

21:   $\mathbf{rwork}\left(\mathbf{lrwork}\right)$ – Real (Kind=nag_wp) arrayCommunication Array

22:   $\mathbf{lrwork}$ – IntegerInput

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

Constraint: $\mathbf{lrwork}\ge \mathbf{maxdpt}\times \left(\mathbf{n}+1\right)+2\times {\min \left(\mathbf{n},\mathbf{m}+1\right)}^2+14\times \mathbf{n}+12\times \mathbf{m}$.

If $\mathbf{msglvl}>0$, the amounts of workspace provided and required (with $\mathbf{maxdpt}=3\times \mathbf{n}/2$) are printed. As an alternative to computing maxdpt, liwork and lrwork from the formulas given above, you may prefer to obtain appropriate values from the output of a preliminary run with the values of maxdpt, liwork and lrwork set to $1$. If however only liwork and lrwork are set to $1$, then the appropriate values of these arguments for the given value of maxdpt will be computed and printed unless $\mathbf{maxdpt}<2$. In both cases h02bbf will then terminate with $\mathbf{ifail}=\mathbf{6}$.

23:   $\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, because for this routine the values of the output arguments may be useful even if $\mathbf{ifail}\ne \mathbf{0}$ on exit, the recommended value is $-1$. When the value $-\mathbf{1}\text{ or }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).

5.1

Description of Printed Output

6

Error Indicators and Warnings

$\mathbf{ifail}=1$

No feasible integer point was found, i.e., it was not possible to satisfy all the integer variables to within the integer feasibility tolerance (determined by toliv). Increase toliv and rerun h02bbf.

$\mathbf{ifail}=2$

The original LP solution appears to be unbounded. This value of ifail implies that a step as large as bigbnd would have to be taken in order to continue the algorithm (see Section 9).

$\mathbf{ifail}=3$

No feasible point was found for the original LP problem, i.e., it was not possible to satisfy all the constraints to within the feasibility tolerance (determined by tolfes). 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).

$\mathbf{ifail}=4$

The maximum number of iterations (determined by itmax) was reached before normal termination occurred for the original LP problem (see Section 9).

$\mathbf{ifail}=5$

Not used by this routine.

$\mathbf{ifail}=6$

An input argument is invalid.

$\mathbf{ifail}=7$

The IP solution reported is not the optimum IP solution. In other words, the B&B tree search for at least one of the branches had to be terminated since an LP sub-problem in the branch did not have a solution (see Section 9).

$\mathbf{ifail}=8$

The maximum depth of the B&B tree used for branch and bound (determined by maxdpt) is too small. Increase maxdpt (along with liwork and/or lrwork if appropriate) and rerun h02bbf.

$\mathbf{ifail}=9$

The IP solution reported is the best IP solution for the number of nodes (determined by maxnod) investigated in the B&B tree.

$\mathbf{ifail}=10$

No feasible integer point was found for the number of nodes (determined by maxnod) investigated in the B&B tree.

$\mathbf{ifail}=11$

Although the workspace sizes are sufficient to meet the documented restriction, they are not sufficiently large to accommodate an internal partition of the workspace that meets the requirements of the problem. Increase the workspace sizes.

The maximum depth of the B&B tree used for branch and bound (determined by maxdpt) is too small. Increase maxdpt (along with liwork and/or lrwork if appropriate) and rerun h02bbf.

$\mathbf{\text{Overflow}}$

It may be possible to avoid the difficulty by increasing the magnitude of the feasibility tolerance (tolfes) and rerunning the program. If the message recurs even after this change, see Section 9.

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

10

Example

10.1

Program Text

Program Text (h02bbfe.f90)

10.2

Program Data

Program Data (h02bbfe.d)

10.3

Program Results

Program Results (h02bbfe.r)