naginterfaces.library.mip.ilp_​mpsx

naginterfaces.library.mip.ilp_mpsx(infile, maxn, maxm, optim, xbldef, xbudef, maxdpt, msglvl, liwork, lrwork, comm, io_manager=None)

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

For full information please refer to the NAG Library document for h02bf

https://support.nag.com/numeric/nl/nagdoc_30/flhtml/h/h02bff.html

Parameters

infileint

The unit number (see unit_from_fileobj()) associated with the MPSX data file.

maxnint

An upper limit for the number of variables in the problem.

maxmint

An upper limit for the number of constraints (including the objective) in the problem.

optimstr, length 3

Specifies the direction of the optimization. $optim$ must be set to ‘MIN’ for minimization and to ‘MAX’ for maximization.

xbldeffloat

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.

xbudeffloat

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

maxdptint

For an IP problem, $maxdpt$ must specify the maximum depth of the branch and bound tree.

msglvlint

The amount of printout produced by opt.lp_solve or ilp_dense(), as indicated below. For a description of the printed output see Further Comments or Description of Printed Output for ilp_dense (as appropriate). All output is written to the file object associated with the advisory I/O unit (see FileObjManager).

For an LP problem (opt.lp_solve):

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 (ilp_dense()):

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.

liworkint

The dimension of the array $iwork$.

lrworkint

The dimension of the array $rwork$.

commdict, communication object, modified in place

Communication structure.

This argument must have been initialized by a prior call to opt.nlp1_init with $\text{rname}=\text{'opt.lp\_solve'}$.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

nint

$n$, the actual number of variables in the problem.

mint

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

xfloat, ndarray, shape $\left(maxn\right)$

The solution to the problem, stored in $x\left[0\right],x\left[1\right],\dots ,x[n-1]$. $x[\text{i}-1]$ is the value of the variable whose MPSX name is stored in $crname[\text{i}-1]$, for $\text{i}=1,2,\dots ,n$.

crnamestr, length 8, ndarray, shape $(maxn+maxm)$

The first $n$ elements contain the MPSX names for the variables in the problem.

iworkint, ndarray, shape $\left(liwork\right)$

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 Parameters for opt.lp_solve and Parameters for ilp_info (as appropriate).

rworkfloat, ndarray, shape $\left(lrwork\right)$

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 Parameters for opt.lp_solve and Parameters for ilp_info (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$.

Raises

NagValueError

(errno $i<0$)

Either $maxm$ and/or $maxn$ are too small or the MPSX data file is nonstandard and/or corrupt.

(errno $2$)

The LP solution is unbounded.

(errno $3$)

The LP does not have a feasible solution.

(errno $4$)

Iteration limit reached without finding a solution.

(errno $5$)

On entry, not enough real workspace to solve problem: $lrwork=⟨value⟩$ $lrwork$ must be at least $⟨value⟩$.

(errno $5$)

On entry, not enough integer workspace to solve problem: $liwork=⟨value⟩$ $liwork$ must be at least $⟨value⟩$.

(errno $5$)

On entry, $maxdpt=⟨value⟩$.

Constraint: $maxdpt\ge 2$.

(errno $5$)

On entry, not enough real workspace to read data file: $lrwork=⟨value⟩$.

(errno $5$)

On entry, not enough integer workspace to read data file: $liwork=⟨value⟩$.

(errno $5$)

On entry, $optim=⟨value⟩$.

Constraint: $optim=\text{'MIN'}$ or $\text{'MAX'}$.

(errno $5$)

On entry, $xbldef=⟨value⟩$ and $xbudef=⟨value⟩$.

Constraint: $xbldef\le xbudef$.

(errno $5$)

On entry, $maxm=⟨value⟩$.

Constraint: $maxm\ge 1$.

(errno $5$)

On entry, $maxn=⟨value⟩$.

Constraint: $maxn\ge 1$.

(errno $5$)

On entry, $infile=⟨value⟩$.

Constraint: $0\le infile\le 2147483647$.

(errno $6$)

A serious error has occurred. Check all function calls and array dimensions.

(errno $8$)

Increase $maxdpt$ and rerun ilp_mpsx.

(errno $8$)

$maxdpt$ is too small to solve the problem: $maxdpt=⟨value⟩$.

(errno $9$)

The IP solution returned is the best solution for the number of nodes investigated in the branch and bound tree.

(errno $10$)

No feasible solution was found for the number of nodes investigated in the branch and bound tree.

(errno $11$)

Not enough workspace to solve problem.

Warns

NagAlgorithmicWarning

(errno $1$)

Weak LP solution.

(errno $1$)

The problem does not have a feasible integer solution.

(errno $7$)

Search of a branch was terminated due to iteration limit.

Notes

No equivalent traditional C interface for this routine exists in the NAG Library.

ilp_mpsx solves Linear Programming (LP) or integer programming (IP) problems specified in MPSX (see IBM (1971)) input format. It calls either opt.lp_solve (to solve an LP problem) or ilp_dense() and ilp_info() (to solve an IP problem); these functions are designed to solve problems of the form

$$\begin{array}{c}{minimize}_{x\in R^n}{c}^{T}x\text{subject to}l\le \left(\begin{array}{c}x\\ Ax\end{array}\right)\le u\end{array}$$

where $c$ is an $n$-element vector and $A$ is an $m\times n$ matrix (i.e., there are $n$ variables and $m$ general linear constraints). ilp_dense() is used if at least one of the variables is restricted to take an integer value at the optimum solution. The document for ilp_mpsx_convert() 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. ilp_mpsx also prints the solution to the problem using the row and column names specified in the MPSX data file (by calling ilp_print()).

References

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