naginterfaces.library.mip.handle_solve_milp¶
- naginterfaces.library.mip.handle_solve_milp(handle, x=None, monit=None, data=None, io_manager=None)[source]¶
handle_solve_milp
is a solver from the NAG optimization modelling suite for large-scale Mixed Integer Linear Programming (MILP) problems. It is a branch-and-cut method optimization solver based on the HiGHS software package.Note: this function uses optional algorithmic parameters, see also:
opt.handle_opt_set
,opt.handle_opt_get
.For full information please refer to the NAG Library document for h02bk
https://support.nag.com/numeric/nl/nagdoc_30.1/flhtml/h/h02bkf.html
- Parameters
- handleHandle
The handle to the problem. It needs to be initialized (e.g., by
opt.handle_init
) and to hold a problem formulation compatible withhandle_solve_milp
. It must not be changed between calls to the NAG optimization modelling suite.- xNone or float, array-like, shape , optional
The input of is reserved for future releases of the NAG Library and it is ignored at the moment.
- monitNone or callable monit(handle, rinfo, stats, data=None), optional
Note: if this argument is None then a NAG-supplied facility will be used.
is reserved for future releases of the NAG Library which will allow you to monitor the progress of the optimization.
It will never be called in the current implementation and may be None.
- Parameters
- handleHandle
The handle to the problem as provided on entry to
handle_solve_milp
. It may be used to query the model during the solve, and extract the current approximation of the solution byopt.handle_set_get_real
.- rinfofloat, ndarray, shape
Error measures and various indicators at the end of the current iteration as described in .
- statsfloat, ndarray, shape
Solver statistics at the end of the current iteration as described in , however, elements , , , , , and refer to the quantities in the last iteration rather than accumulated over all iterations through the whole algorithm run.
- dataarbitrary, optional, modifiable in place
User-communication data for callback functions.
- dataarbitrary, optional
User-communication data for callback functions.
- io_managerFileObjManager, optional
Manager for I/O in this routine.
- Returns
- xfloat, ndarray, shape
The final values of the variables .
- rinfofloat, ndarray, shape
Error measures and various indicators of the algorithm as given in the table below:
Value of the primal objective.
Value of the dual objective bound.
The absolute value of the gap between the primal and dual bounds, relative to the primal bound.
The maximum deviation from an integer value over all the discrete variables. This is an indication of the integrality violation.
The maximum violation of a bound on a variable.
The sum of violations of bounds by variables.
–
Reserved for future use.
- statsfloat, ndarray, shape
Solver statistics as given in the table below.
Total number of nodes generated.
Total number of simplex iterations performed.
Total time spent in the solver.
–
Reserved for future use.
- Other Parameters
- ‘Defaults’valueless
This special keyword may be used to reset all options to their default values. Any value given with this keyword will be ignored.
- ‘Infinite Bound Size’float
Default
This defines the ‘infinite’ bound in the definition of the problem constraints. Any upper bound greater than or equal to will be regarded as (and similarly any lower bound less than or equal to will be regarded as ). Note that a modification of this option does not influence constraints which have already been defined; only the constraints formulated after the change will be affected.
Constraint: .
- ‘Milp Abs Gap’float
Default
Tolerance on absolute gap, the absolute value of the difference between the primal objective value and the dual objective bound, to determine whether optimality has been reached.
Constraint: .
- ‘Milp Detect Symmetry’str
Default
This argument controls whether symmetry should be detected. Symmetry arises when there are multiple equivalent solutions that have the same objective function value but different variable assignments. Identifying and handling symmetry can significantly improve the efficiency and speed of the solver, and reduce memory usage. However, it’s worth noting for smaller problems, the time spent on symmetry detection and breaking may outweigh the benefits.
Constraint: or .
- ‘Milp Feasibility Tol’float
Default
The maximum acceptable absolute violation in each constraint (bound, linear or integrality constraint) at a ‘feasible’ point; i.e., a constraint is considered satisfied if its violation does not exceed ‘Milp Feasibility Tol’ . For example, if the integer variable is near unity then is considered to be integer only if .
Constraint: .
- ‘Milp Max Nodes’int
Default
The maximum number of nodes that are to be searched in the B&B tree in order to find a solution.
Constraint: .
- ‘Milp Presolve’str
Default
This argument allows you to turn the presolving of the problem off completely. If the presolver is turned off, the solver will try to handle the original problem you have given. In such a case, the presence of linear dependencies in the constraint matrix can cause numerical instabilities to occur. In normal circumstances, it is recommended to use the presolve which is the default.
Constraint: or .
- ‘Milp Random Seed’int
Default
Initial seed used for random selection in tasks such as primal heuristics and cut generation.
Constraint: .
- ‘Milp Rel Gap’float
Default
Tolerance on relative gap, to determine whether optimality has been reached.
Constraint: .
- ‘Milp Small Matrix Value’float
Default
Lower limit on the absolute value of the linear constraint coefficients in the matrix defined in [equation]. Values smaller than this will be treated as zero.
Constraint: .
- ‘Monitoring File’int
Default
If , the unit number for the secondary (monitoring) output. If set to , no secondary output is provided. The following information is output to the unit:
a listing of the options if set by ‘Print Options’;
problem statistics, the iteration log and the final status as set by ‘Monitoring Level’;
the solution if set by ‘Print Solution’.
Constraint: .
- ‘Monitoring Level’int
Default
This argument sets the amount of information detail that will be printed by the solver to the secondary output. The meaning of the levels is the same as with ‘Print Level’.
Constraint: .
- ‘Print File’int
Default
If , the unit number for the primary output of the solver. If , the primary output is completely turned off independently of other settings. The default value is the advisory message unit number at the time of the options initialization, e.g., at the initialization of the handle. The following information is output to the unit:
a listing of options if set by ‘Print Options’;
problem statistics, the iteration log and the final status from the solver as set by ‘Print Level’;
the solution if set by ‘Print Solution’.
Constraint: .
- ‘Print Level’int
Default
This argument defines how detailed information should be printed by the solver to the primary output.
Output
No output from the solver
The Header and Summary
, , ,
Additionally, the Iteration log
Constraint: .
- ‘Print Options’str
Default
If , a listing of options will be printed to the primary and secondary output.
Constraint: or .
- ‘Print Solution’str
Default
If , the final values of the primal variables are printed on the primary and secondary outputs.
Constraint: or .
- ‘Task’str
Default
This argument specifies the required direction of the optimization. If , the objective function (if set) is ignored and the algorithm stops as soon as a feasible point is found with respect to the given tolerance. If no objective function is set, ‘Task’ reverts to ‘FEASIBLE POINT’ automatically.
Constraint: , or .
- ‘Time Limit’float
Default
This argument specifies a limit in seconds that the solver can use to solve one problem. If during the convergence check this limit is exceeded, the solver will terminate with = 23 error message.
Constraint: .
- Raises
- NagValueError
- (errno )
has not been initialized.
- (errno )
does not belong to the NAG optimization modelling suite, has not been initialized properly or is corrupted.
- (errno )
has not been initialized properly or is corrupted.
- (errno )
This solver does not support the model defined in the handle.
- (errno )
The problem is already being solved.
- (errno )
On entry, , expected .
Constraint: must match the current number of variables of the model in the .
- (errno )
The problem was found to be primal infeasible.
- (errno )
The problem was found to be dual infeasible.
- (errno )
The problem seems to be primal or dual infeasible, the algorithm was stopped.
- Warns
- NagAlgorithmicWarning
- (errno )
Maximum number of nodes exceeded.
- NagAlgorithmicMajorWarning
- (errno )
The solver terminated after the maximum time allowed was exhausted.
- (errno )
No feasible solution was found for the number of nodes investigated in the B&B tree.
- Notes
handle_solve_milp
solves a large-scale MILP problem in the following form:where is a Cartesian product of -dimensional integer space and -dimensional real space, and is the number of decision variables. Here , , , are -dimensional vectors, is an sparse matrix and , are -dimensional vectors.
handle_solve_milp
solves mixed integer linear programming problems stored as a handle. The handle points to an internal data structure which defines the problem and serves as a means of communication for functions in the NAG optimization modelling suite. First, the problem handle is initialized by callingopt.handle_init
. Then some of the functionsopt.handle_set_linobj
,opt.handle_set_quadobj
,opt.handle_set_simplebounds
oropt.handle_set_linconstr
may be called to formulate the objective function, bounds of the variables, and the block of linear constraints, respectively. Marking a set of variables as being integer-valued is achieved by callingopt.handle_set_property
. Once the problem is fully set, the handle may be passed to the solver. When the handle is not needed anymore,opt.handle_free
should be called to destroy it and deallocate the memory held within. See the E04 Introduction for more details about the NAG optimization modelling suite.The solver method can be modified by various options (see Other Parameters) which can be set by
opt.handle_opt_set
andopt.handle_opt_set_file
anytime between the initialization of the handle byopt.handle_init
and a call to the solver. Once the solver has finished, options may be modified for the next solve. The solver may be called repeatedly with various options.The option ‘Task’ may be used to switch the problem to maximization or to ignore the objective function and find only a feasible point.
Several options may have significant impact on the performance of the solver. Even if the defaults were chosen to suit the majority of problems, it is recommended to experiment in order to find the most suitable set of options for a particular problem, see Other Parameters for further details.
- References
Dakin, R J, 1965, A tree search algorithm for mixed integer programming problems, Comput. J. (8), 250–255
Huangfu, Q, and Hall, J.A. J., 2018, Parallelizing the dual revised simplex method, Mathematical Programming Computation (10(1)), 119–142
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