PDF version (NAG web site
, 64bit version, 64bit version)
NAG Toolbox: nag_mip_ilp_dense (h02bb)
Purpose
nag_mip_ilp_dense (h02bb) solves ‘zeroone’, ‘general’, ‘mixed’ or ‘all’ integer programming problems using a branch and bound method. The function 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
[
itmax,
toliv,
tolfes,
bigbnd,
x,
objmip,
iwork,
rwork,
ifail] = h02bb(
itmax,
msglvl,
a,
bl,
bu,
intvar,
cvec,
maxnod,
intfst,
toliv,
tolfes,
bigbnd,
x, 'n',
n, 'm',
m, 'maxdpt',
maxdpt)
[
itmax,
toliv,
tolfes,
bigbnd,
x,
objmip,
iwork,
rwork,
ifail] = nag_mip_ilp_dense(
itmax,
msglvl,
a,
bl,
bu,
intvar,
cvec,
maxnod,
intfst,
toliv,
tolfes,
bigbnd,
x, 'n',
n, 'm',
m, 'maxdpt',
maxdpt)
Description
nag_mip_ilp_dense (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:
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
nag_opt_lp_solve (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
Parameters
Compulsory Input Parameters
 1:
$\mathrm{itmax}$ – int64int32nag_int scalar

An upper bound on the number of iterations for each LP problem.
 2:
$\mathrm{msglvl}$ – int64int32nag_int scalar

The amount of printout produced by
nag_mip_ilp_dense (h02bb).
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:
$\mathrm{a}\left(\mathit{lda},:\right)$ – double array

The first dimension of the array
a must be at least
$\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{m}}\right)$.
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$.
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.
 4:
$\mathrm{bl}\left({\mathbf{n}}+{\mathbf{m}}\right)$ – double array
 5:
$\mathrm{bu}\left({\mathbf{n}}+{\mathbf{m}}\right)$ – double array

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}}$.
 6:
$\mathrm{intvar}\left({\mathbf{n}}\right)$ – int64int32nag_int array

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}$.
 7:
$\mathrm{cvec}\left({\mathbf{n}}\right)$ – double array

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 function 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 function will find a minimum of $F\left(x\right)$.
 8:
$\mathrm{maxnod}$ – int64int32nag_int scalar

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

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}}$.
 10:
$\mathrm{toliv}$ – double scalar

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)$.
 11:
$\mathrm{tolfes}$ – double scalar

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.
 12:
$\mathrm{bigbnd}$ – double scalar

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 $.
 13:
$\mathrm{x}\left({\mathbf{n}}\right)$ – double array

An initial estimate of the original LP solution.
Optional Input Parameters
 1:
$\mathrm{n}$ – int64int32nag_int scalar

Default:
the dimension of the arrays
cvec,
x,
intvar. (An error is raised if these dimensions are not equal.)
$n$, the number of variables.
Constraint:
${\mathbf{n}}>0$.
 2:
$\mathrm{m}$ – int64int32nag_int scalar

Default:
the first dimension of the array
a.
$m$, the number of general linear constraints.
Constraint:
${\mathbf{m}}\ge 0$.
 3:
$\mathrm{maxdpt}$ – int64int32nag_int scalar
Default:
$3\times {\mathbf{n}}/2$
The maximum depth of the B&B tree used for branch and bound.
Constraint:
${\mathbf{maxdpt}}\ge 2$.
Output Parameters
 1:
$\mathrm{itmax}$ – int64int32nag_int scalar

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

Unchanged if on entry ${\mathbf{toliv}}>0.0$, else ${\mathbf{toliv}}={10}^{5}$.
 3:
$\mathrm{tolfes}$ – double scalar

Unchanged if on entry
${\mathbf{tolfes}}>0.0$, else
${\mathbf{tolfes}}=\sqrt{\epsilon}$ (where
$\epsilon $ is the
machine precision).
 4:
$\mathrm{bigbnd}$ – double scalar

Unchanged if on entry ${\mathbf{bigbnd}}>0.0$, else ${\mathbf{bigbnd}}={10}^{20}$.
 5:
$\mathrm{x}\left({\mathbf{n}}\right)$ – double array

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.
 6:
$\mathrm{objmip}$ – double scalar

With
${\mathbf{ifail}}={\mathbf{0}}$ or
${\mathbf{9}}$,
objmip contains the value of the objective function for the IP solution.
 7:
$\mathrm{iwork}\left(\mathit{liwork}\right)$ – int64int32nag_int array

 8:
$\mathrm{rwork}\left(\mathit{lrwork}\right)$ – double array

 9:
$\mathrm{ifail}$ – int64int32nag_int scalar
${\mathbf{ifail}}={\mathbf{0}}$ unless the function detects an error (see
Error Indicators and Warnings).
Error Indicators and Warnings
Note: nag_mip_ilp_dense (h02bb) may return useful information for one or more of the following detected errors or warnings.
Errors or warnings detected by the function:
Cases prefixed with W are classified as warnings and
do not generate an error of type NAG:error_n. See nag_issue_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
nag_mip_ilp_dense (h02bb).
 ${\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
Further Comments).
 ${\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
Further Comments).
 ${\mathbf{ifail}}=4$

The maximum number of iterations (determined by
itmax) was reached before normal termination occurred for the original LP problem (see
Further Comments).
 ${\mathbf{ifail}}=5$

Not used by this function.
 ${\mathbf{ifail}}=6$

An input argument is invalid.
 W ${\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
Further Comments).
 ${\mathbf{ifail}}=8$

The maximum depth of the B&B tree used for branch and bound (determined by
maxdpt) is too small. Increase
maxdpt and rerun
nag_mip_ilp_dense (h02bb).
 W ${\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$

The maximum depth of the B&B tree used for branch and bound (determined by
maxdpt) is too small. Increase
maxdpt and rerun
nag_mip_ilp_dense (h02bb).
 $\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
Further Comments.
 ${\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
nag_mip_ilp_dense (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.
Further Comments
The original LP problem may not have an optimum solution, i.e.,
nag_mip_ilp_dense (h02bb) 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
nag_opt_lp_solve (e04mf) 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.
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)$.
Open in the MATLAB editor:
h02bb_example
function h02bb_example
fprintf('h02bb example results\n\n');
cvec = [3; 4];
a = [ 2, 5;
2, 2;
3, 2];
big = 1e+20;
bl = [ 0; 0; big; big; 5];
bu = [big; big; 15; 5; big];
intvar = int64([1;1]);
itmax = int64(0);
msglvl = int64(1);
maxnod = int64(0);
intfst = int64(0);
toliv = 0;
tolfes = 0;
bigbnd = big;
x = [1; 1];
[itmax, toliv, tolfes, bigbnd, x, objmip, iwork, rwork, ifail] = ...
h02bb(...
itmax, msglvl, a, bl, bu, intvar, cvec, maxnod, intfst, toliv, ...
tolfes, bigbnd, x, 'maxdpt', int64(4));
h02bb example results
*** IP solver
Parameters

Linear constraints...... 3 First integer solution.. OFF
Variables............... 2 Max depth of the tree... 4
Feasibility tolerance... 1.05E08 Print level............. 1
Infinite bound size..... 1.00E+20 EPS (machine precision). 1.11E16
Integer feasibility tol. 1.00E05 Iteration limit......... 50
Max number of nodes..... NONE
** Workspace provided with MAXDPT = 4: LRWORK = 84 LIWORK = 137
** Workspace required with MAXDPT = 4: LRWORK = 84 LIWORK = 137
Total of 9 nodes investigated.
Exit IP solver  Optimum IP solution found.
Final IP objective value = 14.00000
Varbl State Value Lower Bound Upper Bound Lagr Mult Residual
V 1 UL 2.00000 0.00000 2.00000 3.000 0.000
V 2 EQ 2.00000 2.00000 2.00000 4.000 0.000
L Con State Value Lower Bound Upper Bound Lagr Mult Residual
L 1 FR 14.0000 None 15.0000 0.000 1.000
L 2 FR 0.00000 None 5.00000 0.000 5.000
L 3 FR 10.0000 5.00000 None 0.000 5.000
PDF version (NAG web site
, 64bit version, 64bit version)
© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015