NAG FL Interface
h02bff (ilp_mpsx)
1
Purpose
h02bff solves linear or integer programming problems specified in MPSX input format. It is not intended for large sparse problems.
2
Specification
Fortran Interface
Subroutine h02bff ( 
infile, maxn, maxm, optim, xbldef, xbudef, maxdpt, msglvl, n, m, x, crname, iwork, liwork, rwork, lrwork, ifail) 
Integer, Intent (In) 
:: 
infile, maxn, maxm, maxdpt, msglvl, liwork, lrwork 
Integer, Intent (Inout) 
:: 
ifail 
Integer, Intent (Out) 
:: 
n, m, iwork(liwork) 
Real (Kind=nag_wp), Intent (In) 
:: 
xbldef, xbudef 
Real (Kind=nag_wp), Intent (Out) 
:: 
x(maxn), rwork(lrwork) 
Character (3), Intent (In) 
:: 
optim 
Character (8), Intent (Out) 
:: 
crname(maxn+maxm) 

C Header Interface
#include <nag.h>
void 
h02bff_ (const Integer *infile, const Integer *maxn, const Integer *maxm, const char *optim, const double *xbldef, const double *xbudef, const Integer *maxdpt, const Integer *msglvl, Integer *n, Integer *m, double x[], char crname[], Integer iwork[], const Integer *liwork, double rwork[], const Integer *lrwork, Integer *ifail, const Charlen length_optim, const Charlen length_crname) 

C++ Header Interface
#include <nag.h> extern "C" {
void 
h02bff_ (const Integer &infile, const Integer &maxn, const Integer &maxm, const char *optim, const double &xbldef, const double &xbudef, const Integer &maxdpt, const Integer &msglvl, Integer &n, Integer &m, double x[], char crname[], Integer iwork[], const Integer &liwork, double rwork[], const Integer &lrwork, Integer &ifail, const Charlen length_optim, const Charlen length_crname) 
}

The routine may be called by the names h02bff or nagf_mip_ilp_mpsx.
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
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
Arguments

1:
$\mathbf{infile}$ – Integer
Input

On entry: the unit number associated with the MPSX data file.
Constraint:
$0\le {\mathbf{infile}}\le 99$.

2:
$\mathbf{maxn}$ – Integer
Input

On entry: an upper limit for the number of variables in the problem.
Constraint:
${\mathbf{maxn}}\ge 1$.

3:
$\mathbf{maxm}$ – Integer
Input

On entry: an upper limit for the number of constraints (including the objective) in the problem.
Constraint:
${\mathbf{maxm}}\ge 1$.

4:
$\mathbf{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:
${\mathbf{optim}}=\text{'MIN'}$ or $\text{'MAX'}$.

5:
$\mathbf{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:
$\mathbf{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.,
${\mathbf{xbudef}}\ge {10}^{20}$).
Constraint:
${\mathbf{xbudef}}\ge {\mathbf{xbldef}}$.

7:
$\mathbf{maxdpt}$ – Integer
Input

On entry: for an IP problem,
maxdpt must specify the maximum depth of the branch and bound tree.
Constraint:
${\mathbf{maxdpt}}\ge 2$.
For an LP problem,
maxdpt is not referenced

8:
$\mathbf{msglvl}$ – Integer
Input

On entry: the amount of printout produced by
e04mff/e04mfa or
h02bbf, as indicated below. For a description of the printed output see
Section 9.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:
$\mathbf{n}$ – Integer
Output

On exit: $n$, the actual number of variables in the problem.

10:
$\mathbf{m}$ – Integer
Output

On exit: $m$, the actual number of general linear constraints in the problem.

11:
$\mathbf{x}\left({\mathbf{maxn}}\right)$ – Real (Kind=nag_wp) array
Output

On exit: the solution to the problem, stored in ${\mathbf{x}}\left(1\right),{\mathbf{x}}\left(2\right),\dots ,{\mathbf{x}}\left({\mathbf{n}}\right)$.
${\mathbf{x}}\left(\mathit{i}\right)$ is the value of the variable whose MPSX name is stored in ${\mathbf{crname}}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,{\mathbf{n}}$.

12:
$\mathbf{crname}\left({\mathbf{maxn}}+{\mathbf{maxm}}\right)$ – Character(8) array
Output

On exit: the first
n elements contain the MPSX names for the variables in the problem.

13:
$\mathbf{iwork}\left({\mathbf{liwork}}\right)$ – Integer array
Output

On exit: the first (
${\mathbf{n}}+{\mathbf{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:
$\mathbf{liwork}$ – Integer
Input

On entry: the dimension of the array
iwork as declared in the (sub)program from which
h02bff is called.
Constraints:
 for an LP problem, ${\mathbf{liwork}}\ge 4\times {\mathbf{maxn}}+{\mathbf{maxm}}+3$;
 for an IP problem, ${\mathbf{liwork}}\ge \left(25+{\mathbf{maxn}}+{\mathbf{maxm}}\right)\times {\mathbf{maxdpt}}+7\times {\mathbf{maxn}}+2\times \phantom{\rule{0ex}{0ex}}{\mathbf{maxm}}+4$.

15:
$\mathbf{rwork}\left({\mathbf{lrwork}}\right)$ – Real (Kind=nag_wp) array
Output

On exit: the first (
${\mathbf{n}}+{\mathbf{m}}$) elements contain BL (the lower bounds), the next (
${\mathbf{n}}+{\mathbf{m}}$) elements contain BU (the upper bounds) and the next (
${\mathbf{n}}+{\mathbf{m}}$) elements contain CLAMDA (the Lagrangemultipliers). 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 arguments
xbldef and
xbudef.

16:
$\mathbf{lrwork}$ – Integer
Input

On entry: the dimension of the array
rwork as declared in the (sub)program from which
h02bff is called.
Constraints:
 for an LP problem, ${\mathbf{lrwork}}\ge 2\times \mathrm{MIN}{\left({\mathbf{maxn}},{\mathbf{maxm}}+1\right)}^{2}+{\mathbf{maxm}}\times {\mathbf{maxn}}+\phantom{\rule{0ex}{0ex}}12\times {\mathbf{maxn}}+9\times {\mathbf{maxm}}$;
 for an IP problem,
${\mathbf{lrwork}}\ge {\mathbf{maxdpt}}\times \left({\mathbf{maxn}}+1\right)+2\times \mathrm{MIN}{\left({\mathbf{maxn}},{\mathbf{maxm}}+1\right)}^{2}+{\mathbf{maxm}}\times \phantom{\rule{0ex}{0ex}}{\mathbf{maxn}}+19\times {\mathbf{maxn}}+15\times {\mathbf{maxm}}$.

17:
$\mathbf{ifail}$ – Integer
Input/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 4 in the Introduction to the NAG Library FL Interface 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, if you are not familiar with this argument, the recommended value is
$0$.
When the value $\mathbf{1}\text{or}\mathbf{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).
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).
Errors or warnings detected by the routine:
 ${\mathbf{ifail}}=1$

The problem does not have a feasible integer solution.
Weak LP solution.
 ${\mathbf{ifail}}=2$

The LP solution is unbounded.
 ${\mathbf{ifail}}=3$

The LP does not have a feasible solution, i.e., it was not possible to satisfy all the constraints to within the feasibility tolerance (defined internally as
$\sqrt{\mathit{machineprecision}}$). See
Section 9.
 ${\mathbf{ifail}}=4$

Iteration limit (defined internally as
$\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(50,5\left(n+m\right)\right)$) reached without finding a solution. (See
Section 9.)
 ${\mathbf{ifail}}=5$

On entry, ${\mathbf{infile}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: $0\le {\mathbf{infile}}\le 99$.
On entry, ${\mathbf{maxdpt}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{maxdpt}}\ge 2$.
On entry, ${\mathbf{maxm}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{maxm}}\ge 1$.
On entry, ${\mathbf{maxn}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{maxn}}\ge 1$.
On entry, not enough integer workspace to read data file: ${\mathbf{liwork}}=\u2329\mathit{\text{value}}\u232a$.
On entry, not enough integer workspace to solve problem:
${\mathbf{liwork}}=\u2329\mathit{\text{value}}\u232a$ liwork must be at least
$\u2329\mathit{\text{value}}\u232a$.
On entry, not enough real workspace to read data file: ${\mathbf{lrwork}}=\u2329\mathit{\text{value}}\u232a$.
On entry, not enough real workspace to solve problem:
${\mathbf{lrwork}}=\u2329\mathit{\text{value}}\u232a$ lrwork must be at least
$\u2329\mathit{\text{value}}\u232a$.
On entry, ${\mathbf{optim}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{optim}}=\text{'MIN'}$ or $\text{'MAX'}$.
On entry, ${\mathbf{xbldef}}=\u2329\mathit{\text{value}}\u232a$ and ${\mathbf{xbudef}}=\u2329\mathit{\text{value}}\u232a$.
Constraint: ${\mathbf{xbldef}}\le {\mathbf{xbudef}}$.
 ${\mathbf{ifail}}=6$

A serious error has occurred.
Check all subroutine calls and array dimensions.
 ${\mathbf{ifail}}=7$

Search of a branch was terminated due to iteration limit.
The solution returned may not be optimal. See
Section 9.
 ${\mathbf{ifail}}=8$

Increase
maxdpt and rerun
h02bff.
maxdpt is too small to solve the problem:
${\mathbf{maxdpt}}=\u2329\mathit{\text{value}}\u232a$.
 ${\mathbf{ifail}}=9$

The IP solution returned is the best solution for the number of nodes investigated in the branch and bound tree.
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 9.
 ${\mathbf{ifail}}=10$

No feasible solution was found for the number of nodes investigated in the branch and bound tree.
 ${\mathbf{ifail}}=11$

Not enough workspace to solve problem.
 ${\mathbf{ifail}}=i\text{}<0$

Either
maxm and/or
maxn are too small or the MPSX data file is nonstandard and/or corrupt.This corresponds to
${\mathbf{ifail}}=i$ in
Section 6 in
h02buf.
 ${\mathbf{ifail}}=99$
An unexpected error has been triggered by this routine. Please
contact
NAG.
See
Section 7 in the Introduction to the NAG Library FL Interface for further information.
 ${\mathbf{ifail}}=399$
Your licence key may have expired or may not have been installed correctly.
See
Section 8 in the Introduction to the NAG Library FL Interface for further information.
 ${\mathbf{ifail}}=999$
Dynamic memory allocation failed.
See
Section 9 in the Introduction to the NAG Library FL Interface for further information.
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
Parallelism and Performance
h02bff is not thread safe and should not be called from a multithreaded user program. Please see
Section 1 in FL Interface Multithreading for more information on thread safety.
h02bff 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.
For an LP problem only:
 If ${\mathbf{ifail}}={\mathbf{2}}$ on exit, you can obtain more information by making separate calls to h02buf, e04mff/e04mfa and h02bvf (in that order). Note that this will (by default) cause the final LP solution to be printed twice on the current advisory message unit (see x04abf), once with dummy names for the rows and columns and once with usersupplied names. To suppress the printout of the final LP solution with dummy names for the rows and columns, include the statement
Call e04mhf/e04mha(' Print Level = 5 ')
prior to calling e04mff/e04mfa.
 If ${\mathbf{ifail}}={\mathbf{3}}$ on exit, you are recommended to reset the value of the feasibility tolerance and rerun h02bff. (Further advice is given under the description of ${\mathbf{ifail}}={\mathbf{3}}$ in Section 6 in e04mff/e04mfa.) For example, to reset the value of the feasibility tolerance to $0.01$, include the statement
Call e04mhf/e04mha(' Feasibility Tolerance = 0.01 ')
prior to calling h02bff.
 If ${\mathbf{ifail}}={\mathbf{4}}$ on exit, you are recommended to increase the maximum number of iterations allowed before termination and rerun h02bff. For example, to increase the maximum number of iterations to $500$, include the statement
Call e04mhf/e04mha(' Iteration Limit = 500 ')
prior to calling h02bff.
Note that
h02buf uses an ‘infinite’ bound size of
${10}^{20}$ in the definition of
$l$ and
$u$. In other words, any element of
$u$ greater than or equal to
${10}^{20}$ will be regarded as
$+\infty $ (and similarly any element of
$l$ less than or equal to
${10}^{20}$ will be regarded as
$\infty $). If this value is deemed to be inappropriate, you are recommended to reset the value of the ‘infinite’ bound size and make any necessary changes to BL and/or BU prior to calling
e04mff/e04mfa. For example, to reset the value of the ‘infinite’ bound size to
$10000$, include the statement
Call e04mhf/e04mha(' Infinite Bound Size = 1.0E+4 ')
prior to calling
e04mff/e04mfa.
For an IP problem only:
 If ${\mathbf{ifail}}={\mathbf{2}}$, ${\mathbf{3}}$, ${\mathbf{4}}$, ${\mathbf{7}}$ or ${\mathbf{9}}$ on exit, you can obtain more information by making separate calls to h02bbf, h02buf, h02bvf and h02bzf (in that order).
Note that
h02buf uses an ‘infinite’ bound size of
${10}^{20}$ in the definition of
$l$ and
$u$. In other words, any element of
$u$ greater than or equal to
${10}^{20}$ will be regarded as
$+\infty $ (and similarly any element of
$l$ less than or equal to
${10}^{20}$ will be regarded as
$\infty $). If this value is deemed to be inappropriate, you are recommended to reset the value of the argument
bigbnd (as described in
h02bbf) and make any necessary changes to BL and/or BU prior to calling
h02bbf.
10
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 socalled 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
subject to
where

$c={\left(\begin{array}{cccccc}3& 24& 13& 9& 20& 19\end{array}\right)}^{\mathrm{T}},x={\left({x}_{1},{x}_{2},{x}_{3},{x}_{4},{x}_{5},{x}_{6}\right)}^{\mathrm{T}}\text{,}$

${x}_{1},{x}_{2}$ and ${x}_{6}$ are real,

${x}_{3},{x}_{4}$ and ${x}_{5}$ are integer,

 $A=\left(\begin{array}{rrrrrr}110& 205& 160& 160& 420& 260\\ 4& 32& 13& 8& 4& 14\\ 2& 12& 54& 285& 22& 80\end{array}\right)\text{, \hspace{1em}}b=\left(\begin{array}{r}2000\\ 55\\ 800\end{array}\right)$ and
 $u={\left(\begin{array}{cccccc}4& 3& 2& 8& 2& 2\end{array}\right)}^{\mathrm{T}}$.
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 10.2.
10.1
Program Text
10.2
Program Data
10.3
Program Results