NAG Library Routine Document
h02bbf (ilp_dense)
1
Purpose
h02bbf solves ‘zeroone’, ‘general’, ‘mixed’ or ‘all’ integer programming problems using a branch and bound method. The routine may also be used to find either the first integer solution or the optimum integer solution. It is not intended for large sparse problems.
2
Specification
Fortran Interface
Subroutine h02bbf ( 
itmax, msglvl, n, m, a, lda, bl, bu, intvar, cvec, maxnod, intfst, maxdpt, toliv, tolfes, bigbnd, x, objmip, iwork, liwork, rwork, lrwork, ifail) 
Integer, Intent (In)  ::  msglvl, n, m, lda, intvar(n), maxnod, intfst, maxdpt, liwork, lrwork  Integer, Intent (Inout)  ::  itmax, ifail  Integer, Intent (Out)  ::  iwork(liwork)  Real (Kind=nag_wp), Intent (In)  ::  a(lda,*), bl(n+m), bu(n+m), cvec(n)  Real (Kind=nag_wp), Intent (Inout)  ::  toliv, tolfes, bigbnd, x(n)  Real (Kind=nag_wp), Intent (Out)  ::  objmip, rwork(lrwork) 

C Header Interface
#include <nagmk26.h>
void 
h02bbf_ (Integer *itmax, const Integer *msglvl, const Integer *n, const Integer *m, const double a[], const Integer *lda, const double bl[], const double bu[], const Integer intvar[], const double cvec[], const Integer *maxnod, const Integer *intfst, const Integer *maxdpt, double *toliv, double *tolfes, double *bigbnd, double x[], double *objmip, Integer iwork[], const Integer *liwork, double rwork[], const Integer *lrwork, Integer *ifail) 

3
Description
h02bbf is capable of solving certain types of integer programming (IP) problems using a branch and bound (B&B) method, see
Taha (1987). In order to describe these types of integer programs and to briefly state the B&B method, we define the following linear programming (LP) problem:
If, in
(1), it is required that (some or) all the variables take integer values, then the integer program is of type (
mixed or)
all general IP problem. If additionally, the integer variables are restricted to take only
$0$–
$1$ values (i.e.,
${l}_{j}=0$ and
${u}_{j}=1$) then the integer program is of type (mixed or all)
zeroone IP problem.
The B&B method applies directly to these integer programs. The general idea of B&B (for a full description see
Dakin (1965) or
Mitra (1973)) is to solve the problem without the integral restrictions as an LP problem (first
node). If in the optimal solution an integer variable
${x}_{k}$ takes a noninteger value
${x}_{k}^{*}$, two LP subproblems are created by
branching, imposing
${x}_{k}\le \left[{x}_{k}^{*}\right]$ and
${x}_{k}\ge \left[{x}_{k}^{*}\right]+1$ respectively, where
$\left[{x}_{k}^{*}\right]$ denotes the integer part of
${x}_{k}^{*}$. This method of branching continues until the first integer solution (
bound) is obtained. The hanging nodes are then solved and investigated in order to prove the optimality of the solution. At each node, an LP problem is solved using
e04mff/e04mfa.
4
References
Dakin R J (1965) A tree search algorithm for mixed integer programming problems Comput. J. 8 250–255
Mitra G (1973) Investigation of some branch and bound strategies for the solution of mixed integer linear programs Math. Programming 4 155–170
Taha H A (1987) Operations Research: An Introduction Macmillan, New York
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}}=\mathrm{max}\phantom{\rule{0.125em}{0ex}}\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 \mathrm{max}\phantom{\rule{0.125em}{0ex}}\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 {\mathrm{min}\phantom{\rule{0.125em}{0ex}}\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
The level of printed output from
h02bbf is controlled by you (see the description of
msglvl in
Section 5).
When ${\mathbf{msglvl}}>0$, the summary printout at the end of execution of h02bbf includes a listing of the status of every variable and constraint. Note that default names are assigned to all variables and constraints. The following describes the printout for each variable.
Varbl 
gives the name (V) and index $\mathit{j}$, for $\mathit{j}=1,2,\dots ,n$, of the variable.

State 
gives the state of the variable (FR if neither bound is in the working set, EQ if a fixed variable, LL if on its lower bound, UL if on its upper bound, TF if temporarily fixed at its current value). If Value lies outside the upper or lower bounds by more than the Feasibility Tolerance, State will be ++ or  respectively. 
Value 
is the value of the variable at the final iterate. 
Lower Bound 
is the lower bound specified for the variable. (None indicates that ${\mathbf{bl}}\left(j\right)\le {\mathbf{bigbnd}}$.) Note that if ${\mathbf{intvar}}\left(j\right)=1$, then the printed value of Lower Bound for the $j$th variable may not be the same as that originally supplied in ${\mathbf{bl}}\left(j\right)$.

Upper Bound 
is the upper bound specified for the variable. (None indicates that ${\mathbf{bu}}\left(j\right)\ge {\mathbf{bigbnd}}$.) Note that if ${\mathbf{intvar}}\left(j\right)=1$, then the printed value of Upper Bound for the $j$th variable may not be the same as that originally supplied in ${\mathbf{bu}}\left(j\right)$.

Lagr Mult 
is the value of the Lagrangemultiplier for the associated bound constraint. This will be zero if State is FR or TF. If $x$ is optimal, the multiplier should be nonnegative if State is LL, and nonpositive if State is UL. 
Residual 
is the difference between the variable Value and the nearer of its bounds ${\mathbf{bl}}\left(j\right)$ and ${\mathbf{bu}}\left(j\right)$.

The meaning of the printout for general constraints is the same as that given above for variables, with ‘variable’ replaced by ‘constraint’, ${\mathbf{bl}}\left(j\right)$ and ${\mathbf{bu}}\left(j\right)$ are replaced by ${\mathbf{bl}}\left(n+j\right)$ and ${\mathbf{bu}}\left(n+j\right)$ respectively, and with the following change in the heading.
L Con 
gives the name (L) and index $\mathit{j}$, for $\mathit{j}=1,2,\dots ,m$, of the constraint.

When ${\mathbf{msglvl}}>1$, the summary printout at the end of every node during the execution of h02bbf is a listing of the outcome of forcing an integer variable with a noninteger value to take a value within its specified lower and upper bounds.
Node No 
is the current node number of the B&B tree being investigated. 
Parent Node 
is the parent node number of the current node. 
Obj Value 
is the final objective function value. If a node does not have a feasible solution then No Feas Soln is printed instead of the objective function value. If a node whose optimum solution exceeds the best integer solution so far is encountered (i.e., it does not pay to explore the subproblem any further), then its objective function value is printed together with a CO (Cut Off). 
Varbl Chosen 
is the index of the integer variable chosen for branching. 
Value Before 
is the noninteger value of the integer variable chosen. 
Lower Bound 
is the lower bound value that the integer variable is allowed to take. 
Upper Bound 
is the upper bound value that the integer variable is allowed to take. 
Value After 
is the value of the integer variable after the current optimization. 
Depth 
is the depth of the B&B tree at the current node. 
6
Error Indicators and Warnings
If on entry
${\mathbf{ifail}}=0$ or
$1$, explanatory error messages are output on the current error message unit (as defined by
x04aaf).
Note: h02bbf may return useful information for one or more of the following detected errors or warnings.
Errors or warnings detected by the routine:
 ${\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 subproblem 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
h02bbf implements a numerically stable active set strategy and returns solutions that are as accurate as the condition of the problem warrants on the machine.
8
Parallelism and Performance
h02bbf is not thread safe and should not be called from a multithreaded user program. Please see
Section 3.12.1 in How to Use the NAG Library and its Documentation for more information on thread safety.
h02bbf makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the
X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the
Users' Note for your implementation for any additional implementationspecific information.
The original LP problem may not have an optimum solution, i.e.,
h02bbf terminates with
${\mathbf{ifail}}={\mathbf{2}}$,
${\mathbf{3}}$ or
${\mathbf{4}}$ or overflow may occur. In this case, you are recommended to relax the integer restrictions of the problem and try to find the optimum LP solution by using
e04mff/e04mfa instead.
In the B&B method, it is possible for an LP subproblem to terminate without finding a solution. This may occur due to the number of iterations exceeding the maximum allowed. Therefore the B&B tree search for that particular branch cannot be continued. Thus the returned solution may not be optimal. (${\mathbf{ifail}}={\mathbf{7}}$). For the second and unlikely case, a solution could not be found despite a second attempt at an LP solution.
10
Example
This example solves the integer programming problem:
maximize
subject to the bounds
and to the general constraints
where
${x}_{1}$ and
${x}_{2}$ are integer variables.
The initial point, which is feasible, is
and
$F\left({x}_{0}\right)=7$.
The optimal solution is
and
$F\left({x}^{*}\right)=14$.
Note that maximizing $F\left(x\right)$ is equivalent to minimizing $F\left(x\right)$.
10.1
Program Text
Program Text (h02bbfe.f90)
10.2
Program Data
Program Data (h02bbfe.d)
10.3
Program Results
Program Results (h02bbfe.r)