NAG CL Interface
h02ddc (handle_​solve_​minlp)

1 Purpose

2 Specification

3 Description

3.1 Alternative solvers

4 References

5 Arguments

1: $\mathbf{handle}$ – void * Input

On entry: the handle to the problem. It needs to be initialized (e.g., by e04rac) and to hold a problem formulation compatible with h02ddc. It must not be changed between calls to the NAG optimization modelling suite.

2: $\mathbf{objfun}$ – function, supplied by the user External Function

objfun must calculate the value of the nonlinear objective function $f\left(x\right)$ at a specified value of the $n$-element vector of $x$ variables. If there is no nonlinear objective (e.g., e04rec or e04rfc was called to define a linear or quadratic objective function), objfun will never be called by h02ddc and may be NULLFN.

The specification of objfun is:

copy

void  objfun (Integer nvar, const double x[], double *fx, Integer *inform, Nag_Comm *comm)

1: $\mathbf{nvar}$ – Integer Input

On entry: $n$, the current number of decision variables $x$ in the model.

2: $\mathbf{x}\left[\mathbf{nvar}\right]$ – const double Input

On entry: the vector $x$ of variable values at which the objective function is to be evaluated.

3: $\mathbf{fx}$ – double * Output

On exit: the value of the objective function at $x$.

4: $\mathbf{inform}$ – Integer * Input/Output

On entry: a non-negative value.

On exit: must be set to a value describing the action to be taken by the solver on return from objfun. Specifically, if the value is negative, then the value of fx will be discarded and the solver will terminate immediately with $\mathbf{fail}\mathbf{.}\mathbf{code}=$ NE_FAILED_START or NE_USER_NAN (the same will happen if fx is Infinity or NaN); otherwise, the solver will proceed normally.

5: $\mathbf{comm}$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to objfun.

user – double *

iuser – Integer *

p – Pointer 

The type Pointer will be void *. Before calling h02ddc you may allocate memory and initialize these pointers with various quantities for use by objfun when called from h02ddc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

3: $\mathbf{objgrd}$ – function, supplied by the user External Function

objgrd must calculate the values of the nonlinear objective function gradients $\frac{\partial f}{\partial x}$ at a specified value of the $n$-element vector of $x$ variables. If there is no nonlinear objective (e.g., e04rec or e04rfc was called to define a linear or quadratic objective function), objgrd will never be called by h02ddc and may be NULLFN.

The specification of objgrd is:

copy

void  objgrd (Integer nvar, const double x[], Integer nnzfd, double fdx[], Integer *inform, Nag_Comm *comm)

1: $\mathbf{nvar}$ – Integer Input

On entry: $n$, the current number of decision variables $x$ in the model.

2: $\mathbf{x}\left[\mathbf{nvar}\right]$ – const double Input

On entry: the vector $x$ of variable values at which the objective function gradient is to be evaluated.

3: $\mathbf{nnzfd}$ – Integer Input

On entry: the number of nonzero elements in the sparse gradient vector of the objective function, as was set in a previous call to e04rgc.

4: $\mathbf{fdx}\left[\mathit{dim}\right]$ – double Input/Output

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 idxfd in a previous call to e04rgc. $\mathbf{fdx}\left[\mathit{i}-1\right]$ will store the gradient element $\frac{\partial f}{\partial x_j}$, where $j=\mathbf{idxfd}\left[\mathit{i}-1\right]$.

5: $\mathbf{inform}$ – Integer * Input/Output

On entry: a non-negative value.

On exit: must be set to a value describing the action to be taken by the solver on return from objgrd. Specifically, if the value is negative the solution of the current problem will terminate immediately with $\mathbf{fail}\mathbf{.}\mathbf{code}=$ NE_FAILED_START or NE_USER_NAN (the same will happen if fdx contains Infinity, NaN, or unassigned elements); otherwise, computations will continue.

6: $\mathbf{comm}$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to objgrd.

user – double *

iuser – Integer *

p – Pointer 

The type Pointer will be void *. Before calling h02ddc you may allocate memory and initialize these pointers with various quantities for use by objgrd when called from h02ddc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

4: $\mathbf{confun}$ – function, supplied by the user External Function

confun must calculate the values of the $m_g$-element vector $g_i\left(x\right)$ of nonlinear constraint functions at a specified value of the $n$-element vector of $x$ variables. If no nonlinear constraints were registered in this handle, confun will never be called by h02ddc and may be specified as NULLFN.

The specification of confun is:

copy

void  confun (Integer nvar, const double x[], Integer ncnln, double gx[], Integer *inform, Nag_Comm *comm)

1: $\mathbf{nvar}$ – Integer Input

On entry: $n$, the current number of decision variables $x$ in the model.

2: $\mathbf{x}\left[\mathbf{nvar}\right]$ – const double Input

On entry: the vector $x$ of variable values at which the constraint functions are to be evaluated.

3: $\mathbf{ncnln}$ – Integer Input

On entry: $m_g$, the number of nonlinear constraints, as specified in an earlier call to e04rkc.

4: $\mathbf{gx}\left[\mathit{dim}\right]$ – double Output

On exit: the $m_g$ values of the nonlinear constraint functions at $x$.

5: $\mathbf{inform}$ – Integer * Input/Output

On entry: a non-negative value.

On exit: must be set to a value describing the action to be taken by the solver on return from confun. Specifically, if the value is negative, then the value of gx will be discarded and the solver will terminate immediately with $\mathbf{fail}\mathbf{.}\mathbf{code}=$ NE_FAILED_START or NE_USER_NAN (the same will happen if gx contains Infinity or NaN); otherwise, the solver will proceed normally.

6: $\mathbf{comm}$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to confun.

user – double *

iuser – Integer *

p – Pointer 

The type Pointer will be void *. Before calling h02ddc you may allocate memory and initialize these pointers with various quantities for use by confun when called from h02ddc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

5: $\mathbf{congrd}$ – function, supplied by the user External Function

congrd must calculate the nonzero values of the sparse Jacobian of the nonlinear constraint functions $\frac{\partial g_i}{\partial x}$ at a specified value of the $n$-element vector of $x$ variables. If there are no nonlinear constraints (e.g., e04rkc was never called with the same handle or it was called with ncnln $=0$), congrd will never be called by h02ddc and may be specified as NULLFN.

The specification of congrd is:

copy

void  congrd (Integer nvar, const double x[], Integer nnzgd, double gdx[], Integer *inform, Nag_Comm *comm)

1: $\mathbf{nvar}$ – Integer Input

On entry: $n$, the current number of decision variables $x$ in the model.

2: $\mathbf{x}\left[\mathbf{nvar}\right]$ – const double Input

On entry: the vector $x$ of variable values at which the Jacobian of the constraint functions is to be evaluated.

3: $\mathbf{nnzgd}$ – Integer Input

On entry: is the number of nonzero elements in the sparse Jacobian of the constraint functions, as was set in a previous call to e04rkc.

4: $\mathbf{gdx}\left[\mathit{dim}\right]$ – double Input/Output

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 irowgd and icolgd in an earlier call to e04rkc. $\mathbf{gdx}\left[\mathit{i}-1\right]$ will be the gradient $\frac{\partial g_j}{\partial x_k}$, where $j=\mathbf{irowgd}\left[\mathit{i}-1\right]$ and $k=\mathbf{icolgd}\left[\mathit{i}-1\right]$.

5: $\mathbf{inform}$ – Integer * Input/Output

On entry: a non-negative value.

On exit: must be set to a value describing the action to be taken by the solver on return from congrd. Specifically, if the value is negative the solution of the current problem will terminate immediately with $\mathbf{fail}\mathbf{.}\mathbf{code}=$ NE_FAILED_START or NE_USER_NAN (the same will happen if gdx contains Infinity, NaN, or unassigned elements); otherwise, computations will continue.

6: $\mathbf{comm}$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to congrd.

user – double *

iuser – Integer *

p – Pointer 

The type Pointer will be void *. Before calling h02ddc you may allocate memory and initialize these pointers with various quantities for use by congrd when called from h02ddc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

6: $\mathbf{monit}$ – function, supplied by the user External Function

monit 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 $i$th major iteration where $i$ is given by the $\mathbf{MISQP\; Monitor\; Frequency}$ (the default is $0$, monit is not called).

monit may be specified as NULLFN.

The specification of monit is:

copy

void  monit (Integer nvar, const double x[], Integer *inform, const double rinfo[], const double stats[], Nag_Comm *comm)

1: $\mathbf{nvar}$ – Integer Input

On entry: $n$, the current number of decision variables $x$ in the model.

2: $\mathbf{x}\left[\mathbf{nvar}\right]$ – const double Input

On entry: $x^i$, the values of the decision variables $x$ at the current iteration.

3: $\mathbf{inform}$ – Integer * Input/Output

On entry: a non-negative value.

On exit: must be set to a value describing the action to be taken by the solver on return from monit. Specifically, if the value is negative the solution of the current problem will terminate immediately with $\mathbf{fail}\mathbf{.}\mathbf{code}=$ NE_USER_STOP; otherwise, computations will continue.

4: $\mathbf{rinfo}\left[100\right]$ – const double Input

On entry: error measures and various indicators at the end of the current iteration as described in rinfo.

5: $\mathbf{stats}\left[100\right]$ – const double Input

On entry: solver statistics at the end of the current iteration as described in stats.

6: $\mathbf{comm}$ – Nag_Comm *

Pointer to structure of type Nag_Comm; the following members are relevant to monit.

user – double *

iuser – Integer *

p – Pointer 

The type Pointer will be void *. Before calling h02ddc you may allocate memory and initialize these pointers with various quantities for use by monit when called from h02ddc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

7: $\mathbf{nvar}$ – Integer Input

On entry: $n$, the current number of decision variables $x$ in the model.

8: $\mathbf{x}\left[\mathbf{nvar}\right]$ – double Input/Output

On entry: $x^0$, the initial estimates of the variables $x$.

On exit: the final values of the variables $x$.

9: $\mathbf{rinfo}\left[100\right]$ – double Output

On exit: error measures and various indicators at the end of the final iteration as given in the table below:

$0$	Objective function value $f\left(x\right)$.
$1$–$99$	Reserved for future use.

10: $\mathbf{stats}\left[100\right]$ – double Output

On exit: solver statistics at the end of the final iteration as given in the table below:

$0$	Number of function evaluations.
$1$–$2$	Reserved for future use.
$3$	Number of gradient evaluations.
$4$	Number of calls to the QP solver.
$5$	Reserved for future use.
$6$	Number of branch-and-bound nodes.
$7$	Total time spent in solver (including user-supplied function calls).
$8$	Total time spent evaluating objective function.
$9$	Total time spent evaluating objective gradient.
$10$	Total time spent evaluating constraint functions.
$11$	Total time spent evaluating constraint Jacobian.
$12$	Total number of inner iterations.
$13$	Total number of iterations.
$14$–$99$	Reserved for future use.

11: $\mathbf{comm}$ – Nag_Comm *

The NAG communication argument (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

12: $\mathbf{fail}$ – NagError * Input/Output

The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

6 Error Indicators and Warnings

NE_ALLOC_FAIL

Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.

NE_BAD_PARAM

On entry, argument $⟨\mathit{\text{value}}⟩$ had an illegal value.

NE_DERIV_ERRORS

User-provided constraint gradient is likely to be incorrect. This error indicates that the user-supplied gradient vector gdx has entries that do not match with a finite-differences approximation of it.

User-provided objective gradient is likely to be incorrect. This error indicates that the user-supplied gradient vector fdx has entries that do not match with a finite-differences approximation of it.

NE_FAILED_START

The current starting point is unusable.

Either inform was set to a negative value within the user-supplied functions objfun, objgrd, confun or congrd, or the values returned contain Infinity, NaN, or unassigned elements.

NE_HANDLE

The supplied handle does not define a valid handle to the data structure for the NAG optimization modelling suite. It has not been properly initialized or it has been corrupted.

NE_INFEASIBLE

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

The solver detected an infeasible problem.

NE_INTERNAL_ERROR

An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.

NE_NO_IMPROVEMENT

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 $5$, try increasing it. Optional parameter $\mathbf{MISQP\; Feasible\; Steps}=⟨\mathit{\text{value}}⟩$.;

NE_NO_LICENCE

Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.

NE_NULL_ARGUMENT

The problem requires the confun values. Please provide a proper confun function.

The problem requires the congrd derivatives. Please provide a proper congrd function.

The problem requires the objfun values. Please provide a proper objfun function.

The problem requires the objgrd derivatives. Please provide a proper objgrd function.

NE_NUM_DIFFICULTIES

The optimization failed due to numerical difficulties. Set optional parameter $\mathbf{Print\; Level}=3$ for more information.;

NE_PHASE

The problem is already being solved.

NE_REF_MATCH

The information supplied does not match with that previously stored.
On entry, $\mathbf{nvar}=⟨\mathit{\text{value}}⟩$ must match that given during initialization of the handle, i.e., $⟨\mathit{\text{value}}⟩$.

NE_SETUP_ERROR

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

NE_TIME_LIMIT

The solver terminated after the maximum time allowed was exhausted.

Maximum number of seconds exceeded. Use optional parameter $\mathbf{Time\; Limit}$ to change the limit.

NE_TOO_MANY_ITER

Maximum number of iterations exceeded.

The $\mathbf{MISQP\; Iteration\; Limit}$ limit was exceeded before a solution with the requested accuracy could be found. Check the iteration log to be sure that progress was being made. If so, rerun the problem after increasing this optional parameter.

NE_USER_NAN

Invalid number detected in user-supplied function.

Either inform was set to a negative value within the user-supplied functions objfun, objgrd, confun or congrd, or the values returned contain Infinity, NaN, or unassigned elements.

NE_USER_STOP

User requested termination during a monitoring step. inform was set to a negative value in monit.

NE_ZERO_COEFF

Termination with zero integer trust region for integer variables; try a different starting value.
Optional parameter $\mathbf{MISQP\; Integer\; Trust\; Radius}=⟨\mathit{\text{value}}⟩$.;

NE_ZERO_VARS

On entry, there are no binary or integer variables.

7 Accuracy

8 Parallelism and Performance

9 Further Comments

9.1 Description of the Printed Output

 ---------------------------------------------------
  H02DD, Mixed-integer nonlinear programming solver
 ---------------------------------------------------

Begin of Options
    Print File                    =                   6     * d
    Print Level                   =                   2     * U
    Print Options                 =                 Yes     * U
    Print Solution                =                 All     * U

    Infinite Bound Size           =         1.00000E+20     * d
    Task                          =            Minimize     * d
    Stats Time                    =                 Yes     * U
    Time Limit                    =         1.00000E+06     * d
    Verify Derivatives            =                 Yes     * U

    ...
    Misqp Improved Bounds         =                  No     * d
    Misqp Integer Trust Radius    =         1.00000E+01     * d
    Misqp Iteration Limit         =                 500     * d
    Misqp Maximum Restarts        =                   2     * d
    Misqp Modify Hessian          =                 Yes     * d
    Misqp Monitor Frequency       =                   1     * U
    Misqp Node Selection          =         Depth First     * d
    Misqp Non Monotone            =                  10     * d
    ...
End of Options

Problem Statistics
  No of variables                  8
    integer                        4
      inc. binary                  4
    free (unconstrained)           0
    bounded                        8
  No of lin. constraints           5
  No of nln. constraints           2
  Objective function       Nonlinear

 Verification of the objective gradients
   Col         X        DX         Gradient    Approximation  Test  Itns
     1  1.00E+00  2.43E-07   1.20000000E+01   1.20000000E+01    OK     1
     2  1.00E+00  1.98E-07   2.00000000E+01   2.00000000E+01    OK     1
     3  1.00E+00  1.54E-07   2.00000000E+01   2.00000000E+01    OK     1
 
   All     4 objective gradients out of the     4
   set in cols     1 through     8 seem to be ok.
 
   The largest relative error was    4.61E-11 in element     1
 
 
 Verification of the constraint gradients
   Col         X        DX   Row         Gradient    Approximation  Test  Itns
     1  1.00E+00  2.65E-06     1   8.00000000E+00   8.00000000E+00    OK     3
     2  1.00E+00  2.65E-06     1   9.00000000E+00   9.00000000E+00    OK     3
     3  1.00E+00  2.65E-06     1   1.10000000E+01   1.20000000E+01  BAD?     3  Linear or odd?
     4  1.00E+00  2.65E-06     1   7.00000000E+00   7.00000000E+00    OK     3
 
   There seem to be     1 incorrect constraint gradients out of the     8
   set in cols     1 through     8
 
   The largest relative error was    8.33E-02 in row    1, column    3

   Output in the following order:
 
     IT    - iteration number
     F     - objective function value
     MCV   - maximum constraint violation
     SIGMA - penalty parameter
     IL    - number inner loops
     DMAXC - maximum norm of continuous step D_C
     D1B   - 1-norm of binary step DELTA_B
     DMAXI - maximum norm of integer step D_I
 
   IT       F         MCV      SIGMA    IL   DMAXC      D1B      DMAXI
 -----------------------------------------------------------------------
    1  0.10000D+01  0.10D+01  0.10D+04   1  0.10D-02  0.20D+01  0.00D+00
    2  0.13846D+00  0.15D-15  0.10D+04   1  0.67D-03  0.10D+01  0.00D+00
    3  0.16239D+00  0.11D-37  0.10D+04   1  0.67D-03  0.20D+01  0.00D+00
    ...

 -------------------------------------------------------------------------------
 Status: converged, an optimal solution was found
 -------------------------------------------------------------------------------
 
 Objective function value at solution:  2.92500E+00
 
 Number of function evaluations:                 118
 Number of gradient evaluations:                  22
 Number of calls of QP solver:                    35
 Number of B&B nodes:                            183

 Timing:
   Total time spent                               0.19 sec
   Total time in objective function               0.00 sec (  1.5%)
   Total time in objective gradient               0.00 sec (  0.5%)
   Total time in constraint functions             0.00 sec (  2.6%)
   Total time in constraint Jacobian              0.00 sec (  0.0%)

 Primal variables:
   idx   Lower bound       Value       Upper bound     Gradient
     1   0.00000E+00    3.75000E-01    1.00000E+06    1.95000E+00
     2   0.00000E+00    5.25000E-01    1.00000E+06    9.75000E+00
     3   0.00000E+00    1.00000E+00    1.00000E+00        NaN        I
     4   0.00000E+00    1.00000E+00    1.00000E+00        NaN        B
     5   0.00000E+00    1.00000E+00    1.00000E+00        NaN        B

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

11 Algorithmic Details

12 Optional Parameters

• Defaults
• Infinite Bound Size
• MISQP Branching Rule
• MISQP Continuous Trust Radius
• MISQP Descent
• MISQP Descent Factor
• MISQP Feasible Steps
• MISQP Improved Bounds
• MISQP Integer Trust Radius
• MISQP Iteration Limit
• MISQP Maximum Restarts
• MISQP Modify Hessian
• MISQP Monitor Frequency
• MISQP Node Selection
• MISQP Non Monotone
• MISQP Penalty
• MISQP Penalty Factor
• MISQP QP Accuracy
• MISQP Scale Continuous Vars
• MISQP Scale Objective
• MISQP Scale Objective Bound
• MISQP Stop Tolerance
• MISQP Subproblem Max Nodes
• MISQP Warm Starts
• Print File
• Print Level
• Print Options
• Print Solution
• Stats Time
• Task
• Time Limit
• Verify Derivatives

12.1 Description of the Optional Parameters

• the keywords;
• a parameter value, where the letters $a$, $i$ and $r$ denote options that take character, integer and real values respectively.
• the default value, where the symbol $\epsilon$ is a generic notation for machine precision (see X02AJC).

$\mathbf{MISQP\; Branching\; Rule}=\mathrm{MAXIMUM}$

Maximum fractional branching.

$\mathbf{MISQP\; Branching\; Rule}=\mathrm{MINIMUM}$

Minimum fractional branching.

$\mathbf{MISQP\; Node\; Selection}=\mathrm{BEST\; OF\; ALL}$

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

$\mathbf{MISQP\; Node\; Selection}=\mathrm{BEST\; OF\; TWO}$

Uses warm starts and less memory.

$\mathbf{MISQP\; Node\; Selection}=\mathrm{DEPTH\; FIRST}$

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.