naginterfaces.library.mip.ilp_​dense

naginterfaces.library.mip.ilp_dense(itmax, msglvl, a, bl, bu, intvar, cvec, maxnod, intfst, toliv, tolfes, bigbnd, x, comm, maxdpt=None, io_manager=None)

ilp_dense 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.

Deprecated since version 29.3.0.0: ilp_dense is deprecated. Please use handle_solve_milp() instead. See also the Replacement Calls document.

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

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

Parameters

itmaxint

An upper bound on the number of iterations for each LP problem.

msglvlint

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

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.

afloat, array-like, shape $(m,:)$

Note: the required extent for this argument in dimension 2 is determined as follows: if $m>0$: $n$; if $m=0$: $1$; otherwise: $0$.

The $\text{i}$th row of $a$ must contain the coefficients of the $\text{i}$th general constraint, for $\text{i}=1,2,\dots ,m$.

If $m=0$ then the array $a$ is not referenced.

blfloat, array-like, shape $(n+m)$

$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 $bl\left[j\right]\le -bigbnd$ and to specify a nonexistent upper bound (i.e., $u_j=+\infty$), set $bu\left[j\right]\ge bigbnd$. To specify the $j$th constraint as an equality, set $bl\left[j\right]=bu\left[j\right]=\beta$, say, where $\left|\beta \right|<bigbnd$.

bufloat, array-like, shape $(n+m)$

$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 $bl\left[j\right]\le -bigbnd$ and to specify a nonexistent upper bound (i.e., $u_j=+\infty$), set $bu\left[j\right]\ge bigbnd$. To specify the $j$th constraint as an equality, set $bl\left[j\right]=bu\left[j\right]=\beta$, say, where $\left|\beta \right|<bigbnd$.

intvarint, array-like, shape $\left(n\right)$

Indicates which are the integer variables in the problem. For example, if $x_{\text{j}}$ is an integer variable then $intvar\left[\text{j}\right]$ must be set to $1$, and $0$ otherwise.

cvecfloat, array-like, shape $\left(n\right)$

The coefficients $c_j$ of the objective function $F\left(x\right)=c_1{x}_1+c_2{x}_2+\cdots +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, $cvec\left[\text{j}\right]$ should be set to $-c_{\text{j}}$, for $\text{j}=1,2,\dots ,n$, so that the function will find a minimum of $-F\left(x\right)$.

maxnodint

The maximum number of nodes that are to be searched in order to find a solution (optimum integer solution). If $maxnod\le 0$ and $intfst\le 0$, then the B&B tree search is continued until all the nodes have been investigated.

intfstint

Specifies whether to terminate the B&B tree search after the first integer solution (if any) is obtained. If $intfst>0$ then the B&B tree search is terminated at node $k$ say, which contains the first integer solution. For $maxnod>0$ this applies only if $k\le maxnod$.

tolivfloat

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 $(1-toliv)\le x_j\le (1+toliv)$.

tolfesfloat

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$.

bigbndfloat

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 $-bigbnd$ will be regarded as $-\infty$.

xfloat, array-like, shape $\left(n\right)$

An initial estimate of the original LP solution.

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'}$.

maxdptNone or int, optional

Note: if this argument is None then a default value will be used, determined as follows: $3\times n/2$.

The maximum depth of the B&B tree used for branch and bound.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

itmaxint

Unchanged if on entry $itmax>0$, else $itmax=max(50,5\times (n+m))$.

tolivfloat

Unchanged if on entry $toliv>0.0$, else $toliv={10}^{-5}$.

tolfesfloat

Unchanged if on entry $tolfes>0.0$, else $tolfes=\sqrt{ϵ}$ (where $ϵ$ is the machine precision).

bigbndfloat

Unchanged if on entry $bigbnd>0.0$, else $bigbnd={10}^{20}$.

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

With no exception or warning is raised, $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 $errno$ = 9, then $x$ contains a solution which will be an estimate of the best integer solution that was obtained by searching $maxnod$ nodes.

objmipfloat

With the function exits successfully or $errno$ = 9, $objmip$ contains the value of the objective function for the IP solution.

Raises

NagValueError

(errno $1$)

The problem does not have a feasible integer solution.

(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 $6$)

On entry, there were $⟨value⟩$ infinite or inconsistent bounds given in arrays $bl$ and $bu$. For further advisory details set $msglvl>2$.

(errno $6$)

On entry, the dimension of $comm$[‘iwork’] is too small: $\text{liwork}=⟨value⟩$. $comm$[‘iwork’] must be of dimension (at least) $⟨value⟩$.

(errno $6$)

On entry, the dimension of $comm$[‘rwork’] is too small: $\text{lrwork}=⟨value⟩$. $comm$[‘rwork’] must be of dimension (at least) $⟨value⟩$.

(errno $6$)

On entry, $maxdpt=⟨value⟩$.

Constraint: $maxdpt\ge 2$.

(errno $6$)

On entry, $i=⟨value⟩$, $intvar[i-1]=⟨value⟩$.

Constraint: $intvar=0$ or $1$.

(errno $6$)

On entry, $m=⟨value⟩$.

Constraint: $m\ge 0$.

(errno $6$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $8$)

Increase $maxdpt$ and rerun ilp_dense.

(errno $8$)

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

(errno $10$)

No feasible solution was found for the number of nodes investigated in the B&B tree.

(errno $11$)

Not enough workspace to solve problem.

Warns

NagAlgorithmicWarning

(errno $7$)

Search of a branch was terminated due to iteration limit.

(errno $9$)

The $IP$ solution returned is the best solution for the number of nodes investigated in the B&B tree.

Notes

In the NAG Library the traditional C interface for this routine uses a different algorithmic base. Please contact NAG if you have any questions about compatibility.

ilp_dense 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\left(x\right)=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$$

subject to

$$\begin{array}{c}\sum _{j=1}^n{a}_{ij}{x}_j\left\{\begin{array}{c}=\\ \le \\ \ge \end{array}\right\}{b}_i\text{,}i=1,2,\dots ,m\end{array}$$

$$l_j\le x_j\le u_j\text{,}j=1,2,\dots ,n$$

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) 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) and 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^{\ast }$, two LP sub-problems are created by branching, imposing $x_k\le \left[x_k^{\ast }\right]$ and $x_k\ge \left[x_k^{\ast }\right]+1$ respectively, where $\left[x_k^{\ast }\right]$ denotes the integer part of $x_k^{\ast }$. 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 opt.lp_solve.

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

See also

naginterfaces.library.examples.mip.ilp_dense_ex.main()