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_29.3/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 (seeFileObjManager
).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