hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_mip_ilp_dense (h02bb)

Purpose

nag_mip_ilp_dense (h02bb) solves ‘zero-one’, ‘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:
Minimize
F(x) = c1x1 + c2x2 + + cnxn
F(x)=c1x1+c2x2++cnxn
subject to
n
aijxj{
=
}
bi,  i = 1,2,,m
j = 1
j= 1naijxj { = } bi,   i= 1,2,,m
ljxjuj,  j = 1,2,,n
ljxjuj,  j=1,2,,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 0011 values (i.e., lj = 0lj=0 and uj = 1uj=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 xkxk takes a noninteger value xk * xk*, two LP sub-problems are created by branching, imposing xk[xk * ]xk[xk*] and xk[xk * ] + 1xk[xk*]+1 respectively, where [xk * ][xk*] denotes the integer part of xk * xk*. 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:     itmax – int64int32nag_int scalar
An upper bound on the number of iterations for each LP problem.
2:     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:     a(lda, : :) – double array
The first dimension of the array a must be at least max (1,m)max(1,m)
The second dimension of the array must be at least nn if m > 0m>0 and at least 11 if m = 0m=0
The iith row of a must contain the coefficients of the iith general constraint, for i = 1,2,,mi=1,2,,m.
If m = 0m=0 then the array a is not referenced.
4:     bl(n + mn+m) – double array
5:     bu(n + mn+m) – double array
bl must contain the lower bounds and bu the upper bounds, for all the constraints in the following order. The first nn elements of each array must contain the bounds on the variables, and the next mm elements the bounds for the general linear constraints (if any). To specify a nonexistent lower bound (i.e., lj = lj=-), set bl(j)bigbndblj-bigbnd and to specify a nonexistent upper bound (i.e., uj = + uj=+), set bu(j)bigbndbujbigbnd. To specify the jjth constraint as an equality, set bl(j) = bu(j) = βblj=buj=β, say, where |β| < bigbnd|β|<bigbnd.
Constraints:
  • bl(j)bu(j)bljbuj, for j = 1,2,,n + mj=1,2,,n+m;
  • if bl(j) = bu(j) = βblj=buj=β, |β| < bigbnd|β|<bigbnd.
6:     intvar(n) – int64int32nag_int array
n, the dimension of the array, must satisfy the constraint n > 0n>0.
Indicates which are the integer variables in the problem. For example, if xjxj is an integer variable then intvar(j)intvarj must be set to 11, and 00 otherwise.
Constraints:
  • intvar(j) = 0intvarj=0 or 11, for j = 1,2,,nj=1,2,,n;
  • intvar(j) = 1intvarj=1 for at least one value of jj.
7:     cvec(n) – double array
n, the dimension of the array, must satisfy the constraint n > 0n>0.
The coefficients cjcj of the objective function F(x) = c1x1 + c2x2 + + cnxnF(x)=c1x1+c2x2++cnxn. The function attempts to find a minimum of F(x)F(x). If a maximum of F(x)F(x) is desired, cvec(j)cvecj should be set to cj-cj, for j = 1,2,,nj=1,2,,n, so that the function will find a minimum of F(x)-F(x).
8:     maxnod – int64int32nag_int scalar
The maximum number of nodes that are to be searched in order to find a solution (optimum integer solution). If maxnod0maxnod0 and intfst0intfst0, then the B&B tree search is continued until all the nodes have been investigated.
9:     intfst – int64int32nag_int scalar
Specifies whether to terminate the B&B tree search after the first integer solution (if any) is obtained. If intfst > 0intfst>0 then the B&B tree search is terminated at node kk say, which contains the first integer solution. For maxnod > 0maxnod>0 this applies only if kmaxnodkmaxnod.
10:   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 xjxj is near unity then xjxj is considered to be integer only if (1toliv)xj(1 + toliv)(1-toliv)xj(1+toliv).
11:   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:   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 + + and any lower bound less than or equal to bigbnd-bigbnd will be regarded as -.
13:   x(n) – double array
n, the dimension of the array, must satisfy the constraint n > 0n>0.
An initial estimate of the original LP solution.

Optional Input Parameters

1:     n – int64int32nag_int scalar
Default: The dimension of the arrays cvec, x, intvar. (An error is raised if these dimensions are not equal.)
nn, the number of variables.
Constraint: n > 0n>0.
2:     m – int64int32nag_int scalar
Default: The first dimension of the array a.
mm, the number of general linear constraints.
Constraint: m0m0.
3:     maxdpt – int64int32nag_int scalar
The maximum depth of the B&B tree used for branch and bound.
Default: 3 × n / 23×n/2
Constraint: maxdpt2maxdpt2.

Input Parameters Omitted from the MATLAB Interface

lda liwork lrwork

Output Parameters

1:     itmax – int64int32nag_int scalar
Unchanged if on entry itmax > 0itmax>0, else itmax = max (50,5 × (n + m))itmax=max(50,5×(n+m)).
2:     toliv – double scalar
Unchanged if on entry toliv > 0.0toliv>0.0, else toliv = 105toliv=10-5.
3:     tolfes – double scalar
Unchanged if on entry tolfes > 0.0tolfes>0.0, else tolfes = sqrt(ε)tolfes=ε (where εε is the machine precision).
4:     bigbnd – double scalar
Unchanged if on entry bigbnd > 0.0bigbnd>0.0, else bigbnd = 1020bigbnd=1020.
5:     x(n) – double array
With ifail = 0ifail=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 = 9ifail=9, then x contains a solution which will be an estimate of the best integer solution that was obtained by searching maxnod nodes.
6:     objmip – double scalar
With ifail = 0ifail=0 or 99, objmip contains the value of the objective function for the IP solution.
7:     iwork(liwork) – int64int32nag_int array
8:     rwork(lrwork) – double array
9:     ifail – int64int32nag_int scalar
ifail = 0ifail=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.

  ifail = 1ifail=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).
  ifail = 2ifail=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 [Further Comments]).
  ifail = 3ifail=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 AA are of order unity and are accurate only to three decimal places, the feasibility tolerance should be at least 10310-3 (see Section [Further Comments]).
  ifail = 4ifail=4
The maximum number of iterations (determined by itmax) was reached before normal termination occurred for the original LP problem (see Section [Further Comments]).
  ifail = 5ifail=5
Not used by this function.
  ifail = 6ifail=6
An input parameter is invalid.
W ifail = 7ifail=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 [Further Comments]).
  ifail = 8ifail=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 nag_mip_ilp_dense (h02bb).
W ifail = 9ifail=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 = 10ifail=10
No feasible integer point was found for the number of nodes (determined by maxnod) investigated in the B&B tree.
  ifail = 11ifail=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.
  OverflowOverflow
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 [Further Comments].

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 ifail = 2ifail=2, 33 or 44 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 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 = 7ifail=7). For the second and unlikely case, a solution could not be found despite a second attempt at an LP solution.

Example

function nag_mip_ilp_dense_example
itmax = int64(0);
msglvl = int64(10);
a = [2, 5;
     2, -2;
     3, 2];
bl = [0;
     0;
     -1e+20;
     -1e+20;
     5];
bu = [1e+20;
     1e+20;
     15;
     5;
     1e+20];
intvar = [int64(1);1];
cvec = [-3;
     -4];
maxnod = int64(0);
intfst = int64(0);
toliv = 0;
tolfes = 0;
bigbnd = 1e+20;
x = [1;
     1];
[itmaxOut, tolivOut, tolfesOut, bigbndOut, xOut, objmip, iwork, rwork, ifail] = ...
     nag_mip_ilp_dense(itmax, msglvl, a, bl, bu, intvar, cvec, maxnod, intfst, toliv, ...
     tolfes, bigbnd, x, 'maxdpt', int64(4));
 itmaxOut, tolivOut, tolfesOut, bigbndOut, xOut, objmip, ifail
 

 *** H02BBF

 Parameters
 ----------

 Linear constraints......         3        First integer solution..       OFF
 Variables...............         2        Max depth of the tree...         4

 Feasibility tolerance...  1.05E-08        Print level.............        10
 Infinite bound size.....  1.00E+20        EPS (machine precision).  1.11E-16

 Integer feasibility tol.  1.00E-05        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


   *** Optimum LP solution ***   -17.50000


 Varbl State     Value     Lower Bound   Upper Bound    Lagr Mult   Residual

 V  1    FR    3.92857       0.00000         None        0.000       3.929
 V  2    FR    1.42857       0.00000         None        0.000       1.429


 L Con State     Value     Lower Bound   Upper Bound    Lagr Mult   Residual

 L  1    UL    15.0000         None        15.0000      -1.000       0.000
 L  2    UL    5.00000         None        5.00000     -0.5000     -8.8818E-16
 L  3    FR    14.6429       5.00000         None        0.000       9.643


   *** Start of tree search ***


  Node  Parent   Obj       Varbl  Value      Lower      Upper      Value   Depth
   No    Node   Value      Chosen Before     Bound      Bound      After
    2     1   No Feas Soln    1    3.93       4.00       None       4.00       1
    3     1    -16.2          1    3.93       0.00       3.00       3.00       1
    4     3    -15.5          2    1.80       2.00       None       2.00       2
    5     3    -13.0          2    1.80       0.00       1.00       1.00       2
      *** Integer solution ***


  Node  Parent   Obj       Varbl  Value      Lower      Upper      Value   Depth
   No    Node   Value      Chosen Before     Bound      Bound      After
    6     4   No Feas Soln    1    2.50       3.00       3.00       3.00       3
    7     4    -14.8          1    2.50       0.00       2.00       2.00       3
    8     7    -12.0     CO   2    2.20       3.00       None       3.00       4
    9     7    -14.0          2    2.20       2.00       2.00       2.00       4
      *** Integer solution ***

     *** End of tree search ***


 Total of     9 nodes investigated.

 Exit H02BBF - 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

itmaxOut =

                   50


tolivOut =

   1.0000e-05


tolfesOut =

   1.0537e-08


bigbndOut =

   1.0000e+20


xOut =

     2
     2


objmip =

   -14


ifail =

                    0


function h02bb_example
itmax = int64(0);
msglvl = int64(10);
a = [2, 5;
     2, -2;
     3, 2];
bl = [0;
     0;
     -1e+20;
     -1e+20;
     5];
bu = [1e+20;
     1e+20;
     15;
     5;
     1e+20];
intvar = [int64(1);1];
cvec = [-3;
     -4];
maxnod = int64(0);
intfst = int64(0);
toliv = 0;
tolfes = 0;
bigbnd = 1e+20;
x = [1;
     1];
[itmaxOut, tolivOut, tolfesOut, bigbndOut, xOut, objmip, iwork, rwork, ifail] = ...
     h02bb(itmax, msglvl, a, bl, bu, intvar, cvec, maxnod, intfst, toliv, ...
     tolfes, bigbnd, x, 'maxdpt', int64(4));
 itmaxOut, tolivOut, tolfesOut, bigbndOut, xOut, objmip, ifail
 

 *** H02BBF

 Parameters
 ----------

 Linear constraints......         3        First integer solution..       OFF
 Variables...............         2        Max depth of the tree...         4

 Feasibility tolerance...  1.05E-08        Print level.............        10
 Infinite bound size.....  1.00E+20        EPS (machine precision).  1.11E-16

 Integer feasibility tol.  1.00E-05        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


   *** Optimum LP solution ***   -17.50000


 Varbl State     Value     Lower Bound   Upper Bound    Lagr Mult   Residual

 V  1    FR    3.92857       0.00000         None        0.000       3.929
 V  2    FR    1.42857       0.00000         None        0.000       1.429


 L Con State     Value     Lower Bound   Upper Bound    Lagr Mult   Residual

 L  1    UL    15.0000         None        15.0000      -1.000       0.000
 L  2    UL    5.00000         None        5.00000     -0.5000     -8.8818E-16
 L  3    FR    14.6429       5.00000         None        0.000       9.643


   *** Start of tree search ***


  Node  Parent   Obj       Varbl  Value      Lower      Upper      Value   Depth
   No    Node   Value      Chosen Before     Bound      Bound      After
    2     1   No Feas Soln    1    3.93       4.00       None       4.00       1
    3     1    -16.2          1    3.93       0.00       3.00       3.00       1
    4     3    -15.5          2    1.80       2.00       None       2.00       2
    5     3    -13.0          2    1.80       0.00       1.00       1.00       2
      *** Integer solution ***


  Node  Parent   Obj       Varbl  Value      Lower      Upper      Value   Depth
   No    Node   Value      Chosen Before     Bound      Bound      After
    6     4   No Feas Soln    1    2.50       3.00       3.00       3.00       3
    7     4    -14.8          1    2.50       0.00       2.00       2.00       3
    8     7    -12.0     CO   2    2.20       3.00       None       3.00       4
    9     7    -14.0          2    2.20       2.00       2.00       2.00       4
      *** Integer solution ***

     *** End of tree search ***


 Total of     9 nodes investigated.

 Exit H02BBF - 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

itmaxOut =

                   50


tolivOut =

   1.0000e-05


tolfesOut =

   1.0537e-08


bigbndOut =

   1.0000e+20


xOut =

     2
     2


objmip =

   -14


ifail =

                    0



PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013