H02BFF (PDF version)
H Chapter Contents
H Chapter Introduction
NAG Library Manual

NAG Library Routine Document

H02BFF

Note:  before using this routine, please read the Users' Note for your implementation to check the interpretation of bold italicised terms and other implementation-dependent details.

+ Contents

    1  Purpose
    7  Accuracy

1  Purpose

H02BFF solves linear or integer programming problems specified in MPSX input format. It is not intended for large sparse problems.

2  Specification

SUBROUTINE H02BFF ( INFILE, MAXN, MAXM, OPTIM, XBLDEF, XBUDEF, MAXDPT, MSGLVL, N, M, X, CRNAME, IWORK, LIWORK, RWORK, LRWORK, IFAIL)
INTEGER  INFILE, MAXN, MAXM, MAXDPT, MSGLVL, N, M, IWORK(LIWORK), LIWORK, LRWORK, IFAIL
REAL (KIND=nag_wp)  XBLDEF, XBUDEF, X(MAXN), RWORK(LRWORK)
CHARACTER(3)  OPTIM
CHARACTER(8)  CRNAME(MAXN+MAXM)

3  Description

H02BFF solves linear programming (LP) or integer programming (IP) problems specified in MPSX (see IBM (1971)) input format. It calls either E04MFF/E04MFA (to solve an LP problem) or H02BBF and H02BZF (to solve an IP problem); these routines are designed to solve problems of the form
minimizexRncTx  subject to  l x Ax u
where c is an n-element vector and A is an m by n matrix (i.e., there are n variables and m general linear constraints). H02BBF is used if at least one of the variables is restricted to take an integer value at the optimum solution. The document for H02BUF should be consulted for a detailed description of the MPSX format.
In the MPSX data file the first free row, that is a row defined with the row type N, is taken as the objective row. Similarly, if there are more than one RHS, RANGES or BOUNDS sets, then the first set is used for the optimization. H02BFF also prints the solution to the problem using the row and column names specified in the MPSX data file (by calling H02BVF).

4  References

IBM (1971) MPSX – Mathematical programming system Program Number 5734 XM4 IBM Trade Corporation, New York

5  Parameters

1:     INFILE – INTEGERInput
On entry: the unit number associated with the MPSX data file.
Constraint: 0INFILE99.
2:     MAXN – INTEGERInput
On entry: an upper limit for the number of variables in the problem.
Constraint: MAXN1.
3:     MAXM – INTEGERInput
On entry: an upper limit for the number of constraints (including the objective) in the problem.
Constraint: MAXM1.
4:     OPTIM – CHARACTER(3)Input
On entry: specifies the direction of the optimization. OPTIM must be set to 'MIN' for minimization and to 'MAX' for maximization.
Constraint: OPTIM='MIN' or 'MAX'.
5:     XBLDEF – REAL (KIND=nag_wp)Input
On entry: the default lower bound to be used for the variables in the problem when none is specified in the BOUNDS section of the MPSX data file. For a standard LP or IP problem XBLDEF would normally be set to zero.
6:     XBUDEF – REAL (KIND=nag_wp)Input
On entry: the default upper bound to be used for the variables in the problem when none is specified in the BOUNDS section of the MPSX data file. For a standard LP or IP problem XBUDEF would normally be set to ‘infinity’ (i.e., XBUDEF1020).
Constraint: XBUDEFXBLDEF.
7:     MAXDPT – INTEGERInput
On entry: for an IP problem, MAXDPT must specify the maximum depth of the branch and bound tree.
Constraint: MAXDPT2.
For an LP problem, MAXDPT is not referenced
8:     MSGLVL – INTEGERInput
On entry: the amount of printout produced by E04MFF/E04MFA or H02BBF, as indicated below. For a description of the printed output see Section 8.2 in E04MFF/E04MFA or Section 5.1 in H02BBF (as appropriate). All output is written to the current advisory message unit (as defined by X04ABF).
For an LP problem (E04MFF/E04MFA):
Value Definition
0 No output.
1 The final solution only.
5 One line of output for each iteration (no printout of the final solution).
10 The final solution and one line of output for each iteration.
For an IP problem (H02BBF):
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) with dummy names for the rows and columns, one line of output for each node investigated and the final IP solution with MPSX names for the rows and columns.
9:     N – INTEGEROutput
On exit: n, the actual number of variables in the problem.
10:   M – INTEGEROutput
On exit: m, the actual number of general linear constraints in the problem.
11:   X(MAXN) – REAL (KIND=nag_wp) arrayOutput
On exit: the solution to the problem, stored in X1,X2,,XN. Xi is the value of the variable whose MPSX name is stored in CRNAMEi, for i=1,2,,N.
12:   CRNAME(MAXN+MAXM) – CHARACTER(8) arrayOutput
On exit: the first N elements contain the MPSX names for the variables in the problem.
13:   IWORK(LIWORK) – INTEGER arrayOutput
On exit: the first (N+M) elements contain ISTATE (the status of the constraints in the working set at the solution). Further details can be found in Section 5 in E04MFF/E04MFA or H02BZF (as appropriate).
14:   LIWORK – INTEGERInput
On entry: the dimension of the array IWORK as declared in the (sub)program from which H02BFF is called.
Constraints:
  • for an LP problem, LIWORK4×MAXN+MAXM+3;
  • for an IP problem, LIWORK25+MAXN+MAXM×MAXDPT+7×MAXN+2× MAXM+4.
15:   RWORK(LRWORK) – REAL (KIND=nag_wp) arrayOutput
On exit: the first (N+M) elements contain BL (the lower bounds), the next (N+M) elements contain BU (the upper bounds) and the next (N+M) elements contain CLAMDA (the Lagrange-multipliers). Further details can be found in Section 5 in E04MFF/E04MFA or H02BZF (as appropriate). Note that for an IP problem the contents of BL and BU may not be the same as those originally specified in the MPSX data file and/or via the parameters XBLDEF and XBUDEF.
16:   LRWORK – INTEGERInput
On entry: the dimension of the array RWORK as declared in the (sub)program from which H02BFF is called.
Constraints:
  • for an LP problem, LRWORK2×MIN MAXN,MAXM+1 2+MAXM×MAXN+ 12×MAXN+9×MAXM;
  • for an IP problem,
    LRWORKMAXDPT×MAXN+1+2×MIN MAXN,MAXM+1 2+MAXM× MAXN+19×MAXN+15×MAXM.
17:   IFAIL – INTEGERInput/Output
On entry: IFAIL must be set to 0, -1​ or ​1. If you are unfamiliar with this parameter you should refer to Section 3.3 in the Essential Introduction for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value -1​ or ​1 is recommended. If the output of error messages is undesirable, then the value 1 is recommended. Otherwise, if you are not familiar with this parameter, the recommended value is 0. When the value -1​ or ​1 is used it is essential to test the value of IFAIL on exit.
On exit: IFAIL=0 unless the routine detects an error or a warning has been flagged (see Section 6).

6  Error Indicators and Warnings

If on entry IFAIL=0 or -1, explanatory error messages are output on the current error message unit (as defined by X04AAF).
Errors or warnings detected by the routine:
IFAIL=i and IFAIL<0
Either MAXM and/or MAXN are too small or the MPSX data file is nonstandard and/or corrupt. This corresponds to IFAIL=-i in Section 6 in H02BUF.
IFAIL=1
X is a weak local minimum. This means that the solution is not unique.
IFAIL=2
The solution appears to be unbounded. This value of IFAIL implies that a step as large as XBUDEF would have to be taken in order to continue the algorithm. See Section 8.
IFAIL=3
No feasible point was found, i.e., it was not possible to satisfy all the constraints to within the feasibility tolerance (defined internally as machine precision). See Section 8.
IFAIL=4
The maximum number of iterations (defined internally as max50,5n+m) was reached before normal termination occurred. See Section 8.
IFAIL=5
An input parameter is invalid. Refer to the printed output to determine which parameter must be redefined.
IFAIL=6 (E04MFF/E04MFA or H02BBF)
A serious error has occurred in an internal call to one of the specified routines. Check all subroutine calls and array dimensions.
For an IP problem only:
IFAIL=7
The solution returned may not be optimal. See Section 8.
IFAIL=8
MAXDPT is too small. Try increasing its value (along with that of LIWORK and/or LRWORK if appropriate) and rerun H02BFF.
IFAIL=9
No feasible integer point was found, i.e., it was not possible to satisfy all the integer variables to within the integer feasibility tolerance (defined internally as 10-5). See Section 8.

7  Accuracy

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

8  Further Comments

For an LP problem only:
For an IP problem only:

9  Example

This example solves the same problem as the example for H02BUF, except that it treats it as an IP problem.
One of the applications of integer programming is to the so-called diet problem. Given the nutritional content of a selection of foods, the cost of each food, the amount available of each food and the consumer's minimum daily nutritional requirements, the problem is to find the cheapest combination. This gives rise to the following problem:
minimize
cTx
subject to
Axb, 0xu,
where
The rows of A correspond to energy, protein and calcium and the columns of A correspond to oatmeal, chicken, eggs, milk, pie and bacon respectively.
The MPSX data representation of this problem is given in Section 9.2.

9.1  Program Text

Program Text (h02bffe.f90)

9.2  Program Data

Program Options (h02bffe.opt)

9.3  Program Results

Program Results (h02bffe.r)


H02BFF (PDF version)
H Chapter Contents
H Chapter Introduction
NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2012