h02bb solves ‘zero-one’, ‘general’, ‘mixed’ or ‘all’ integer programming problems using a branch and bound method. The method may also be used to find either the first integer solution or the optimum integer solution. It is not intended for large sparse problems.

Syntax

C#
public static void h02bb( ref int itmax, int msglvl, int n, int m, double[,] a, double[] bl, double[] bu, int[] intvar, double[] cvec, int maxnod, int intfst, int maxdpt, ref double toliv, ref double tolfes, ref double bigbnd, double[] x, out double objmip, int[] iwork, double[] rwork, H..::..h02bbOptions options, out int ifail )

public static void h02bb(
	ref int itmax,
	int msglvl,
	int n,
	int m,
	double[,] a,
	double[] bl,
	double[] bu,
	int[] intvar,
	double[] cvec,
	int maxnod,
	int intfst,
	int maxdpt,
	ref double toliv,
	ref double tolfes,
	ref double bigbnd,
	double[] x,
	out double objmip,
	int[] iwork,
	double[] rwork,
	H..::..h02bbOptions options,
	out int ifail
)

Visual Basic
Public Shared Sub h02bb ( _ ByRef itmax As Integer, _ msglvl As Integer, _ n As Integer, _ m As Integer, _ a As Double(,), _ bl As Double(), _ bu As Double(), _ intvar As Integer(), _ cvec As Double(), _ maxnod As Integer, _ intfst As Integer, _ maxdpt As Integer, _ ByRef toliv As Double, _ ByRef tolfes As Double, _ ByRef bigbnd As Double, _ x As Double(), _ <OutAttribute> ByRef objmip As Double, _ iwork As Integer(), _ rwork As Double(), _ options As H..::..h02bbOptions, _ <OutAttribute> ByRef ifail As Integer _ )

Visual Basic

Public Shared Sub h02bb ( _
	ByRef itmax As Integer, _
	msglvl As Integer, _
	n As Integer, _
	m As Integer, _
	a As Double(,), _
	bl As Double(), _
	bu As Double(), _
	intvar As Integer(), _
	cvec As Double(), _
	maxnod As Integer, _
	intfst As Integer, _
	maxdpt As Integer, _
	ByRef toliv As Double, _
	ByRef tolfes As Double, _
	ByRef bigbnd As Double, _
	x As Double(), _
	<OutAttribute> ByRef objmip As Double, _
	iwork As Integer(), _
	rwork As Double(), _
	options As H..::..h02bbOptions, _
	<OutAttribute> ByRef ifail As Integer _
)

Visual C++
public: static void h02bb( int% itmax, int msglvl, int n, int m, array<double,2>^ a, array<double>^ bl, array<double>^ bu, array<int>^ intvar, array<double>^ cvec, int maxnod, int intfst, int maxdpt, double% toliv, double% tolfes, double% bigbnd, array<double>^ x, [OutAttribute] double% objmip, array<int>^ iwork, array<double>^ rwork, H..::..h02bbOptions^ options, [OutAttribute] int% ifail )

Visual C++

public:
static void h02bb(
	int% itmax, 
	int msglvl, 
	int n, 
	int m, 
	array<double,2>^ a, 
	array<double>^ bl, 
	array<double>^ bu, 
	array<int>^ intvar, 
	array<double>^ cvec, 
	int maxnod, 
	int intfst, 
	int maxdpt, 
	double% toliv, 
	double% tolfes, 
	double% bigbnd, 
	array<double>^ x, 
	[OutAttribute] double% objmip, 
	array<int>^ iwork, 
	array<double>^ rwork, 
	H..::..h02bbOptions^ options, 
	[OutAttribute] int% ifail
)

F#
static member h02bb : itmax : int byref * msglvl : int * n : int * m : int * a : float[,] * bl : float[] * bu : float[] * intvar : int[] * cvec : float[] * maxnod : int * intfst : int * maxdpt : int * toliv : float byref * tolfes : float byref * bigbnd : float byref * x : float[] * objmip : float byref * iwork : int[] * rwork : float[] * options : H..::..h02bbOptions * ifail : int byref -> unit

static member h02bb : 
        itmax : int byref * 
        msglvl : int * 
        n : int * 
        m : int * 
        a : float[,] * 
        bl : float[] * 
        bu : float[] * 
        intvar : int[] * 
        cvec : float[] * 
        maxnod : int * 
        intfst : int * 
        maxdpt : int * 
        toliv : float byref * 
        tolfes : float byref * 
        bigbnd : float byref * 
        x : float[] * 
        objmip : float byref * 
        iwork : int[] * 
        rwork : float[] * 
        options : H..::..h02bbOptions * 
        ifail : int byref -> unit

Parameters

itmax: Type: System..::..Int32%
On entry: an upper bound on the number of iterations for each LP problem.
On exit: unchanged if on entry $itmax > 0$ , else $itmax = \max (50, 5 \times (n + m))$ .

msglvl

Type: System..::..Int32

On entry: the amount of printout produced by h02bb, as indicated below (see [Description of Printed Output] for a description of the printed output). All output is written to the current advisory message unit (as defined by (X04ABF not in this release)).

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.

n: Type: System..::..Int32
On entry: $n$ , the number of variables.

Constraint: $n > 0$ .

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

Constraint: $m \geq 0$ .

a: Type: array<System..::..Double,2>[,](,)[,][,]
An array of size [dim1, dim2]
Note: dim1 must satisfy the constraint: $dim1 \geq \max (1, m)$
Note: the second dimension of the array a must be at least $n$ if $m > 0$ and at least $1$ if $m = 0$ .
On entry: the $i$ th row of a must contain the coefficients of the $i$ th general constraint, for $i = 1, 2, \dots, m$ .
If $m = 0$ then the array a is not referenced.

bl

Type: array<System..::..Double>[]()[][]

An array of size [

n + m

]

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

bl [j] \leq - bigbnd

and to specify a nonexistent upper bound (i.e.,

u_{j} = + \infty

), set

bu [j] \geq bigbnd

. To specify the

j

th constraint as an equality, set

bl [j] = bu [j] = β

, say, where

|β| < bigbnd

Constraints:

$bl [j] \leq bu [j]$ , for $j = 0, 1, \dots, n + m - 1$ ;
if $bl [j] = bu [j] = β$ , $|β| < bigbnd$ .

bu

Type: array<System..::..Double>[]()[][]

An array of size [

n + m

]

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

bl [j] \leq - bigbnd

and to specify a nonexistent upper bound (i.e.,

u_{j} = + \infty

), set

bu [j] \geq bigbnd

. To specify the

j

th constraint as an equality, set

bl [j] = bu [j] = β

, say, where

|β| < bigbnd

Constraints:

$bl [j] \leq bu [j]$ , for $j = 0, 1, \dots, n + m - 1$ ;
if $bl [j] = bu [j] = β$ , $|β| < bigbnd$ .

intvar

Type: array<System..::..Int32>[]()[][]

An array of size [n]

On entry: indicates which are the integer variables in the problem. For example, if

x_{j}

is an integer variable then

intvar [j]

must be set to

1

, and

0

otherwise.

Constraints:

$intvar [j] = 0$ or $1$ , for $j = 0, 1, \dots, n - 1$ ;
$intvar [j] = 1$ for at least one value of $j$ .

cvec: Type: array<System..::..Double>[]()[][]
An array of size [n]
On entry: the coefficients $c_{j}$ of the objective function $F (x) = c_{1} x_{1} + c_{2} x_{2} + \dots + c_{n} x_{n}$ . The method attempts to find a minimum of $F (x)$ . If a maximum of $F (x)$ is desired, $cvec [j]$ should be set to $- c_{j}$ , for $j = 1, 2, \dots, n$ , so that the method will find a minimum of $- F (x)$ .

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

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

maxdpt: Type: System..::..Int32
On entry: the maximum depth of the B&B tree used for branch and bound.
Suggested value: $maxdpt = 3 \times n / 2$ .

Constraint: $maxdpt \geq 2$ .

toliv: Type: System..::..Double%
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 $(1 - toliv) \leq x_{j} \leq (1 + toliv)$ .
On exit: unchanged if on entry $toliv > 0.0$ , else $toliv = 10^{- 5}$ .

tolfes: Type: System..::..Double%
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 $tolfes > 0.0$ , else $tolfes = \sqrt{ε}$ (where $ε$ is the machine precision).

bigbnd: Type: System..::..Double%
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 $- bigbnd$ will be regarded as $- \infty$ .
On exit: unchanged if on entry $bigbnd > 0.0$ , else $bigbnd = 10^{20}$ .

x: Type: array<System..::..Double>[]()[][]
An array of size [n]
On entry: an initial estimate of the original LP solution.
On exit: with $ifail = 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 $ifail = 9$ , then x contains a solution which will be an estimate of the best integer solution that was obtained by searching maxnod nodes.

objmip: Type: System..::..Double%
On exit: with $ifail = 0$ or $9$ , objmip contains the value of the objective function for the IP solution.

iwork: Type: array<System..::..Int32>[]()[][]
An array of size [liwork]
the dimension of the array iwork.
On entry: the dimension of the array iwork as declared in the (sub)program from which h02bb is called.

Constraint: $liwork \geq (25 + n + m) \times maxdpt + 5 \times n + m + 4$ .

rwork: Type: array<System..::..Double>[]()[][]
An array of size [lrwork]
the dimension of the array rwork.
On entry: the dimension of the array rwork as declared in the (sub)program from which h02bb is called.

Constraint: $lrwork \geq maxdpt \times (n + 1) + 2 \times {\min (n, m + 1)}^{2} + 14 \times n + 12 \times m$ .
If $msglvl > 0$ , the amounts of workspace provided and required (with $maxdpt = 3 \times 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 parameters for the given value of maxdpt will be computed and printed unless $maxdpt < 2$ . In both cases h02bb will then terminate with $ifail = 6$ .

options: Type: NagLibrary..::..H..::..h02bbOptions
An Object of type H.h02bbOptions. Used to configure optional parameters to this method.

ifail: Type: System..::..Int32%
On exit: $ifail = 0$ unless the method detects an error or a warning has been flagged (see [Error Indicators and Warnings]).

Description

h02bb 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:

Minimize

F (x) = c_{1} x_{1} + c_{2} x_{2} + \dots + c_{n} x_{n}

subject to

\sum_{j = 1}^{n} a_{i j} x_{j} \{\begin{matrix} = \\ \leq \\ \geq \end{matrix}\} b_{i}, i = 1, 2, \dots, m

l_{j} \leq x_{j} \leq u_{j}, j = 1, 2, \dots, n

(1)

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) zero-one 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 sub-problems are created by branching, imposing

x_{k} \leq [x_{k}^{*}]

and

x_{k} \geq [x_{k}^{*}] + 1

respectively, where

[x_{k}^{*}]

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

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

Error Indicators and Warnings

Note: h02bb may return useful information for one or more of the following detected errors or warnings.

Errors or warnings detected by the method:

Some error messages may refer to parameters that are dropped from this interface (LDA) In these cases, an error in another parameter has usually caused an incorrect value to be inferred.

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

$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 [Further Comments]).

$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 $σ$ , you should ensure that the value of the feasibility tolerance is greater than $σ$ . 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 [Further Comments]).

$ifail = 4$: The maximum number of iterations (determined by itmax) was reached before normal termination occurred for the original LP problem (see [Further Comments]).

$ifail = 5$: Not used by this method.

$ifail = 6$: An input parameter is invalid.

$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 [Further Comments]).

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

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

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

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

$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 [Further Comments].

$ifail = -9000$: An error occured, see message report.
$ifail = -6000$: Invalid Parameters $〈value〉$
$ifail = -4000$: Invalid dimension for array $〈value〉$
$ifail = -8000$: Negative dimension for array $〈value〉$
$ifail = -6000$: Invalid Parameters $〈value〉$

Accuracy

h02bb implements a numerically stable active set strategy and returns solutions that are as accurate as the condition of the problem warrants on the machine.

Parallelism and Performance

None.

Further Comments

The original LP problem may not have an optimum solution, i.e., h02bb terminates with

ifail = 2

3

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 e04mf instead.

In the B&B method, it is possible for an LP sub-problem 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. (

ifail = 7

). For the second and unlikely case, a solution could not be found despite a second attempt at an LP solution.

Example

This example solves the integer programming problem:

maximize

F (x) = 3 x_{1} + 4 x_{2}

subject to the bounds

\begin{matrix} x_{1} \geq 0 \\ x_{2} \geq 0 \end{matrix}

and to the general constraints

\begin{array}{l} 2 x_{1} + 5 x_{2} \leq 15 \\ 2 x_{1} - 2 x_{2} \leq 5 \\ 3 x_{1} + 2 x_{2} \geq 5 \end{array}

where

x_{1}

and

x_{2}

are integer variables.

The initial point, which is feasible, is

x_{0} = {(1, 1)}^{T},

and

F (x_{0}) = 7

The optimal solution is

x^{*} = {(2, 2)}^{T},

and

F (x^{*}) = 14

Note that maximizing

F (x)

is equivalent to minimizing

- F (x)

Example program (C#): h02bbe.cs

Example program data: h02bbe.d

Example program results: h02bbe.r

Syntax

Parameters

Description

References

Error Indicators and Warnings

Accuracy

Parallelism and Performance

Further Comments

Example

See Also