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)[source]

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.

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

https://www.nag.com/numeric/nl/nagdoc_28.5/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

Note: the required extent for this argument in dimension 2 is determined as follows: if : ; if : ; otherwise: .

The th row of must contain the coefficients of the th general constraint, for .

If then the array is not referenced.

blfloat, array-like, shape

must contain the lower bounds and the upper bounds, for all the constraints in the following order. The first elements of each array must contain the bounds on the variables, and the next elements the bounds for the general linear constraints (if any). To specify a nonexistent lower bound (i.e., ), set and to specify a nonexistent upper bound (i.e., ), set . To specify the th constraint as an equality, set , say, where .

bufloat, array-like, shape

must contain the lower bounds and the upper bounds, for all the constraints in the following order. The first elements of each array must contain the bounds on the variables, and the next elements the bounds for the general linear constraints (if any). To specify a nonexistent lower bound (i.e., ), set and to specify a nonexistent upper bound (i.e., ), set . To specify the th constraint as an equality, set , say, where .

intvarint, array-like, shape

Indicates which are the integer variables in the problem. For example, if is an integer variable then must be set to , and otherwise.

cvecfloat, array-like, shape

The coefficients of the objective function . The function attempts to find a minimum of . If a maximum of is desired, should be set to , for , so that the function will find a minimum of .

maxnodint

The maximum number of nodes that are to be searched in order to find a solution (optimum integer solution). If and , 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 then the B&B tree search is terminated at node say, which contains the first integer solution. For this applies only if .

tolivfloat

The integer feasibility tolerance; i.e., an integer variable is considered to take an integer value if its violation does not exceed . For example, if the integer variable is near unity then is considered to be integer only if .

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 .

bigbndfloat

The ‘infinite’ bound size in the definition of the problem constraints. More precisely, any upper bound greater than or equal to will be regarded as and any lower bound less than or equal to will be regarded as .

xfloat, array-like, shape

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 .

maxdptNone or int, optional

Note: if this argument is None then a default value will be used, determined as follows: .

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 , else .

tolivfloat

Unchanged if on entry , else .

tolfesfloat

Unchanged if on entry , else (where is the machine precision).

bigbndfloat

Unchanged if on entry , else .

xfloat, ndarray, shape

With no exception or warning is raised, contains a solution which will be an estimate of either the optimum integer solution or the first integer solution, depending on the value of . If = 9, then contains a solution which will be an estimate of the best integer solution that was obtained by searching nodes.

objmipfloat

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

Raises
NagValueError
(errno )

The problem does not have a feasible integer solution.

(errno )

The solution is unbounded.

(errno )

The does not have a feasible solution.

(errno )

Iteration limit reached without finding a solution.

(errno )

On entry, there were infinite or inconsistent bounds given in arrays and . For further advisory details set .

(errno )

On entry, the dimension of [‘iwork’] is too small: . [‘iwork’] must be of dimension (at least) .

(errno )

On entry, the dimension of [‘rwork’] is too small: . [‘rwork’] must be of dimension (at least) .

(errno )

On entry, .

Constraint: .

(errno )

On entry, , .

Constraint: or .

(errno )

On entry, .

Constraint: .

(errno )

On entry, .

Constraint: .

(errno )

Increase and rerun ilp_dense.

(errno )

is too small to solve the problem: .

(errno )

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

(errno )

Not enough workspace to solve problem.

Warns
NagAlgorithmicWarning
(errno )

Search of a branch was terminated due to iteration limit.

(errno )

The 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

subject to

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 values (i.e., and ) 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 takes a noninteger value , two LP sub-problems are created by branching, imposing and respectively, where denotes the integer part of . 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