naginterfaces.library.mip.handle_​solve_​minlp

naginterfaces.library.mip.handle_solve_minlp(handle, x, objfun=None, objgrd=None, confun=None, congrd=None, monit=None, data=None, io_manager=None)[source]

handle_solve_minlp is a solver from the NAG optimization modelling suite for Mixed Integer Nonlinear Programming (MINLP) problems.

Note: this function uses optional algorithmic parameters, see also: opt.handle_opt_set, opt.handle_init, opt.handle_opt_get.

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

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/h/h02ddf.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 with handle_solve_minlp. It must not be changed between calls to the NAG optimization modelling suite.

xfloat, array-like, shape

, the initial estimates of the variables .

objfunNone or callable (fx, inform) = objfun(x, inform, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

must calculate the value of the nonlinear objective function at a specified value of the -element vector of variables.

If there is no nonlinear objective (e.g., opt.handle_set_linobj or opt.handle_set_quadobj was called to define a linear or quadratic objective function), will never be called by handle_solve_minlp and may be None.

Parameters
xfloat, ndarray, shape

The vector of variable values at which the objective function is to be evaluated.

informint

A non-negative value.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns
fxfloat

The value of the objective function at .

informint

Must be set to a value describing the action to be taken by the solver on return from . Specifically, if the value is negative, then the value of will be discarded and the solver will terminate immediately with = 21 or 25 (the same will happen if is Infinity or NaN); otherwise, the solver will proceed normally.

objgrdNone or callable inform = objgrd(x, fdx, inform, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

must calculate the values of the nonlinear objective function gradients at a specified value of the -element vector of variables.

If there is no nonlinear objective (e.g., opt.handle_set_linobj or opt.handle_set_quadobj was called to define a linear or quadratic objective function), will never be called by handle_solve_minlp and may be None.

Parameters
xfloat, ndarray, shape

The vector of variable values at which the objective function gradient is to be evaluated.

fdxfloat, ndarray, shape , to be modified in place

On entry: the elements should only be assigned and not referenced.

On exit: the values of the nonzero elements in the sparse gradient vector of the objective function, in the order specified by in a previous call to opt.handle_set_nlnobj. will store the gradient element , where .

informint

A non-negative value.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns
informint

Must be set to a value describing the action to be taken by the solver on return from . Specifically, if the value is negative the solution of the current problem will terminate immediately with = 21 or 25 (the same will happen if contains Infinity, NaN, or unassigned elements); otherwise, computations will continue.

confunNone or callable (gx, inform) = confun(x, ncnln, inform, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

must calculate the values of the -element vector of nonlinear constraint functions at a specified value of the -element vector of variables.

If no nonlinear constraints were registered in this , will never be called by handle_solve_minlp and may be None.

Parameters
xfloat, ndarray, shape

The vector of variable values at which the constraint functions are to be evaluated.

ncnlnint

, the number of nonlinear constraints, as specified in an earlier call to opt.handle_set_nlnconstr.

informint

A non-negative value.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns
gxfloat, array-like, shape

The values of the nonlinear constraint functions at .

informint

Must be set to a value describing the action to be taken by the solver on return from . Specifically, if the value is negative, then the value of will be discarded and the solver will terminate immediately with = 21 or 25 (the same will happen if contains Infinity or NaN); otherwise, the solver will proceed normally.

congrdNone or callable inform = congrd(x, gdx, inform, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

must calculate the nonzero values of the sparse Jacobian of the nonlinear constraint functions at a specified value of the -element vector of variables.

If there are no nonlinear constraints (e.g., opt.handle_set_nlnconstr was never called with the same or it was called with ), will never be called by handle_solve_minlp and may be None.

Parameters
xfloat, ndarray, shape

The vector of variable values at which the Jacobian of the constraint functions is to be evaluated.

gdxfloat, ndarray, shape , to be modified in place

On entry: the elements should only be assigned and not referenced.

On exit: the nonzero values of the Jacobian of the nonlinear constraints, in the order specified by and in an earlier call to opt.handle_set_nlnconstr. will be the gradient , where and .

informint

A non-negative value.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns
informint

Must be set to a value describing the action to be taken by the solver on return from . Specifically, if the value is negative the solution of the current problem will terminate immediately with = 21 or 25 (the same will happen if contains Infinity, NaN, or unassigned elements); otherwise, computations will continue.

monitNone or callable monit(x, rinfo, stats, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

is provided to enable you to monitor the progress of the optimization and optionally to terminate the solver early if necessary.

It is invoked at the end of every th major iteration where is given by the ‘MISQP Monitor Frequency’ (the default is , is not called).

may be None.

Parameters
xfloat, ndarray, shape

, the values of the decision variables at the current iteration.

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 .

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 at the end of the final iteration as given in the table below:

Objective function value .

Reserved for future use.

statsfloat, ndarray, shape

Solver statistics at the end of the final iteration as given in the table below:

Number of function evaluations.

Reserved for future use.

Number of gradient evaluations.

Number of calls to the QP solver.

Reserved for future use.

Number of branch-and-bound nodes.

Total time spent in solver (including user-supplied function calls).

Total time spent evaluating objective function.

Total time spent evaluating objective gradient.

Total time spent evaluating constraint functions.

Total time spent evaluating constraint Jacobian.

Total number of inner iterations.

Total number of iterations.

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

‘MISQP Branching Rule’str

Default

This option specifies the branching rule for branch-and-bound search.

Maximum fractional branching.

Minimum fractional branching.

‘MISQP Continuous Trust Radius’float

Default

This argument sets the initial continuous trust region radius, ; the initial trial step for the SQP approximation must satisfy .

‘MISQP Descent’float

Default

This sets the initial descent argument, .

Larger values of allow penalty argument to increase faster, which can lead to faster convergence.

‘MISQP Descent Factor’float

Default

This argument defines the factor for decreasing the internal descent argument, , between iterations.

‘MISQP Feasible Steps’int

Default

This argument defines the maximum number of feasible steps without improvements.

Feasibility is measured by , where is defined by the option ‘MISQP Stop Tolerance’.

‘MISQP Improved Bounds’str

Default

When , this option specifies whether to calculate improved bounds.

‘MISQP Integer Trust Radius’float

Default

This argument sets the initial integer trust region radius, ; the initial trial step for the SQP approximation must satisfy .

‘MISQP Iteration Limit’int

Default

This argument sets the maximum number of iterations to be performed by handle_solve_minlp. Setting the option too low might lead to = 22.

‘MISQP Maximum Restarts’int

Default

This argument defines the maximum number of restarts that allow the mixed integer SQP algorithm to return to a better solution.

Setting a value higher than the default might lead to better results at the expense of function evaluations.

‘MISQP Modify Hessian’str

Default

This option specifies whether to modify the Hessian approximation in an attempt to get more accurate search directions. Calculation time is increased when the number of integer variables is large.

‘MISQP Monitor Frequency’int

Default

This argument specifies the frequency on which to call the monitor function . If zero, the monitor function will not be called.

Constraint: .

‘MISQP Node Selection’str

Default

This option specifies the node selection strategy for branch-and-bound search.

Large tree search; this method is the slowest as it solves all subproblem QPs independently.

Uses warm starts and less memory.

Uses more warm starts. If warm starts are applied, they can speed up the solution of mixed integer subproblems significantly when solving almost identical QPs.

‘MISQP Non Monotone’int

Default

This argument defines the maximum number of successive iterations considered for the non-monotone trust region algorithm, allowing the penalty function to increase.

‘MISQP Penalty’float

Default

This sets the initial penalty argument, .

‘MISQP Penalty Factor’float

Default

This argument defines the factor for increasing the internal penalty argument, , when the trust regions cannot be enlarged at a trial step.

‘MISQP QP Accuracy’float

Default

This argument defines the termination tolerance of the relaxed quadratic program subproblems.

‘MISQP Scale Continuous Vars’str

Default

This option specifies whether to internally scale continuous variable values.

‘MISQP Scale Objective’str

Default

This option specifies whether to internally scale objective function values greater than ‘MISQP Scale Objective Bound’.

‘MISQP Scale Objective Bound’float

Default

When , absolute objective function values greater than this argument are internally scaled.

‘MISQP Stop Tolerance’float

Default

This argument sets the requested accuracy for determining feasible points during iterations and for halting the method when the predicted improvement in objective function is less than ‘MISQP Stop Tolerance’.

‘MISQP Subproblem Max Nodes’int

Default

This argument defines the maximum number of branch-and-bound steps for solving the mixed integer quadratic problems.

‘MISQP Warm Starts’int

Default

This argument defines the maximum number of warm starts within the mixed integer QP solver. See ‘MISQP Node Selection’.

‘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

Only the final status and the objective value

Problem statistics, one line per iteration showing the progress of the solution with respect to the convergence measures, final status and statistics

, ,

As level and additionally inner iteration log with further details.

‘Print Options’str

Default

If , a listing of options will be printed to the primary output.

Constraint: or .

‘Print Solution’str

Default

If , the final values of the solution vector are printed on the primary and secondary outputs.

Constraint: or .

‘Stats Time’str

Default

This argument allows you to turn on timings of various parts of the algorithm to give a better overview of where most of the time is spent. This might be helpful for a choice of different solving approaches. It is possible to choose between CPU and wall clock time. Choice ‘YES’ is equivalent to ‘WALL CLOCK’.

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

‘Verify Derivatives’str

Default

This argument specifies whether the function should perform numerical checks on the consistency of the user-supplied gradient functions and . If any discrepancies are found, = 26 is returned. It is recommended that such checks are enabled when first developing the formulation of the problem, however, the verification process results in a significant increase in the number of the function evaluations and thus it shouldn’t be used in production code.

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 )

The problem is already being solved.

(errno )

This solver does not support the model defined in the handle.

(errno )

The information supplied does not match with that previously stored.

On entry, must match that given during initialization of the , i.e., .

(errno )

Please provide a proper function.

(errno )

Please provide a proper function.

(errno )

Please provide a proper function.

(errno )

Please provide a proper function.

(errno )

On entry, there are no binary or integer variables.

(errno )

The current starting point is unusable.

(errno )

User-provided objective gradient is likely to be incorrect.

(errno )

User-provided constraint gradient is likely to be incorrect.

(errno )

Termination at an infeasible iterate; if the problem is feasible, try a different starting value.

(errno )

The solver detected an infeasible problem.

Warns
NagAlgorithmicMajorWarning
(errno )

Termination with zero integer trust region for integer variables; try a different starting value.

Option .;

(errno )

User requested termination during a monitoring step.

(errno )

Maximum number of iterations exceeded.

(errno )

The solver terminated after the maximum time allowed was exhausted.

(errno )

More than the maximum number of feasible steps without improvement in the objective function. If the maximum number of feasible steps is small, say less than , try increasing it. Option .;

(errno )

The optimization failed due to numerical difficulties. Set option for more information.;

(errno )

Invalid number detected in user-supplied function.

Notes

handle_solve_minlp solves Mixed Integer Nonlinear Programming (MINLP) problems using a modified Sequential Quadratic Programming (SQP) method. The problem is assumed to be stated in the following general form:

where

is the number of decision variables, of which are continuous and are integer or binary,

is the number of the nonlinear constraints and , and are -dimensional vectors,

is the number of the quadratic constraints,

is the number of the linear constraints and is a by matrix, and are -dimensional vectors,

there are box constraints and and are -dimensional vectors.

handle_solve_minlp serves as a solver for 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, typically by calling opt.handle_init. Then some of the components of the model need to be defined by calling one or more of the following functions based on the component type:

the objective function : linear (opt.handle_set_linobj or opt.handle_set_quadobj), quadratic (opt.handle_set_quadobj, opt.handle_set_qconstr or opt.handle_set_qconstr_fac) or nonlinear (opt.handle_set_nlnobj),

bound constraints on the variables (opt.handle_set_simplebounds),

one or more blocks of linear constraints (opt.handle_set_linconstr),

quadratic constraints (opt.handle_set_qconstr and opt.handle_set_qconstr_fac for quadratics in a factorized form),

general nonlinear constraints (opt.handle_set_nlnconstr),

integrality of variables (opt.handle_set_property).

When the nonlinear objective function is specified using opt.handle_set_nlnobj, and will be used to compute values and gradients of the objective function. Similarly, and will be used to compute values and gradients of the nonlinear constraint functions specified by opt.handle_set_nlnconstr.

No assumptions are made regarding except that it is twice continuously differentiable with respect to continuous elements of . It is not assumed that integer variables are relaxable. In other words, problem functions are evaluated only at integer points.

Partial derivatives of and are not required for the integer variables. They can hence be omitted entirely when specifying the sparsity pattern of the derivatives in calls to opt.handle_set_nlnobj and opt.handle_set_nlnconstr, respectively. Gradients with respect to integer variables are approximated by difference formulae and those provided by the user will be ignored.

Once the problem is fully described, the handle may be passed to the solver handle_solve_minlp. When the handle is no longer needed, opt.handle_free should be called to destroy it and deallocate the memory held within. There are other ways that the problem model can be defined and/or updated, see the E04 Introduction for more details about the NAG optimization modelling suite.

The algorithm behaviour can be modified by various options (see Other Parameters) which can be set by opt.handle_opt_set and opt.handle_opt_set_file anytime between the initialization of the handle and a call to the solver. Once the solver has finished, options or the model may be modified for the next solve. The solver may be called repeatedly with various starting points and/or options. Option getter opt.handle_opt_get can be called to retrieve the current value of any option.

The option ‘Task’ may be used to switch the problem to maximization.

Several options may have a significant impact on the performance of the solver. Even if the defaults were chosen to suit the majority of problems, it is recommended that you experiment in order to find the most suitable set of options for a particular problem, see Algorithmic Details and Other Parameters for further details.

Alternative solvers

handle_solve_minlp is a generic solver which can solve a great variety of integer problems, however, a dedicated solver might work better in the following case.

If is linear, , and is absent, [equation] is a mixed integer linear program (MILP) and handle_solve_milp() is recommended.

References

Exler, O, Lehmann, T and Schittkowski, K, 2013, A comparative study of SQP-type algorithms for nonlinear and nonconvex mixed-integer optimization, Mathematical Programming Computation (4), 383–412

Mann, A, 1986, GAMS/MINOS: Three examples, Department of Operations Research Technical Report, Stanford University

Powell, M J D, 1983, On the quadratic programming algorithm of Goldfarb and Idnani, Report DAMTP 1983/Na 19, University of Cambridge, Cambridge

Yuan, Y-x and Sun, W, 2006, Optimization Theory and Methods, Springer–Verlag