NAG FL Interface
h02bkf (handle_​solve_​milp)

Note: this routine uses optional parameters to define choices in the problem specification. If you wish to use default settings for all of the optional parameters, then this routine need not be called. If, however, you wish to reset some or all of the settings please refer to Section 12 for a detailed description of the specification of the optional parameters.
Note: please be advised that this routine is classed as ‘experimental’ and its interface may be developed further in the future. Please see Section 4 in How to Use the NAG Library for further information.
Settings help

FL Name Style:

FL Specification Language:

1 Purpose

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

2 Specification

Fortran Interface
Subroutine h02bkf ( handle, nvar, x, rinfo, stats, monit, iuser, ruser, cpuser, ifail)
Integer, Intent (In) :: nvar
Integer, Intent (Inout) :: iuser(*), ifail
Real (Kind=nag_wp), Intent (Inout) :: x(nvar), ruser(*)
Real (Kind=nag_wp), Intent (Out) :: rinfo(100), stats(100)
Type (c_ptr), Intent (In) :: handle, cpuser
External :: monit
C Header Interface
#include <nag.h>
void  h02bkf_ (void **handle, const Integer *nvar, double x[], double rinfo[], double stats[],
void (NAG_CALL *monit)(void **handle, const double rinfo[], const double stats[], Integer iuser[], double ruser[], void **cpuser, Integer *inform),
Integer iuser[], double ruser[], void **cpuser, Integer *ifail)
The routine may be called by the names h02bkf or nagf_mip_handle_solve_milp.

3 Description

h02bkf solves a large-scale MILP problem in the following form:
minimize xn cTx subject to lA Ax uA , lx x ux , xP , (1)
where P= nint × nl is a Cartesian product of nint-dimensional integer space and nl-dimensional real space, and n = nint + nl is the number of decision variables. Here c, x, lx, ux are n-dimensional vectors, A is an m×n sparse matrix and lA, uA are m-dimensional vectors.
h02bkf 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 routines in the NAG optimization modelling suite. First, the problem handle is initialized by calling e04raf. Then some of the routines e04ref, e04rff, e04rhf or e04rjf 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 calling e04rcf. Once the problem is fully set, the handle may be passed to the solver. When the handle is not needed anymore, e04rzf should be called to destroy it and deallocate the memory held within. See Section 3.1 in the E04 Chapter Introduction for more details about the NAG optimization modelling suite.
The solver method can be modified by various optional parameters (see Section 12) which can be set by e04zmf and e04zpf anytime between the initialization of the handle by e04raf 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 optional parameters.
The optional parameter 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 Section 12 for further details.

4 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

5 Arguments

1: handle Type (c_ptr) Input
On entry: the handle to the problem. It needs to be initialized (e.g., by e04raf) and to hold a problem formulation compatible with h02bkf. It must not be changed between calls to the NAG optimization modelling suite.
2: nvar Integer Input
On entry: n, the current number of decision variables x in the model.
3: x(nvar) Real (Kind=nag_wp) array Input/Output
On entry: the input of x is reserved for future releases of the NAG Library and it is ignored at the moment.
On exit: the final values of the variables x.
4: rinfo(100) Real (Kind=nag_wp) array Output
On exit: error measures and various indicators of the algorithm as given in the table below:
1 Value of the primal objective.
2 Value of the dual objective bound.
3 The absolute value of the gap between the primal and dual bounds, relative to the primal bound.
4 The maximum deviation from an integer value over all the discrete variables. This is an indication of the integrality violation.
5 The maximum violation of a bound on a variable.
6 The sum of violations of bounds by variables.
7100 Reserved for future use.
5: stats(100) Real (Kind=nag_wp) array Output
On exit: solver statistics as given in the table below.
1 Total number of nodes generated.
2 Total number of simplex iterations performed.
3 Total time spent in the solver.
4100 Reserved for future use.
6: monit Subroutine, supplied by the NAG Library or the user. External Procedure
monit 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 monit may be the dummy subroutine h02bku included in the NAG Library.
The specification of monit is:
Fortran Interface
Subroutine monit ( handle, rinfo, stats, iuser, ruser, cpuser, inform)
Integer, Intent (Inout) :: iuser(*), inform
Real (Kind=nag_wp), Intent (In) :: rinfo(100), stats(100)
Real (Kind=nag_wp), Intent (Inout) :: ruser(*)
Type (c_ptr), Intent (In) :: handle, cpuser
C Header Interface
void  monit (void **handle, const double rinfo[], const double stats[], Integer iuser[], double ruser[], void **cpuser, Integer *inform)
1: handle Type (c_ptr) Input
On entry: the handle to the problem as provided on entry to h02bkf. It may be used to query the model during the solve, and extract the current approximation of the solution by e04rxf.
2: rinfo(100) Real (Kind=nag_wp) array Input
On entry: error measures and various indicators at the end of the current iteration as described in rinfo.
3: stats(100) Real (Kind=nag_wp) array Input
On entry: solver statistics at the end of the current iteration as described in stats, however, elements 2, 3, 5, 9, 10, 11 and 15 refer to the quantities in the last iteration rather than accumulated over all iterations through the whole algorithm run.
4: iuser(*) Integer array User Workspace
5: ruser(*) Real (Kind=nag_wp) array User Workspace
6: cpuser Type (c_ptr) User Workspace
monit is called with the arguments iuser, ruser and cpuser as supplied to h02bkf. You should use the arrays iuser and ruser, and the data handle cpuser to supply information to monit.
7: 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; otherwise, computations will continue.
monit must either be a module subprogram USEd by, or declared as EXTERNAL in, the (sub)program from which h02bkf is called. Arguments denoted as Input must not be changed by this procedure.
7: iuser(*) Integer array User Workspace
8: ruser(*) Real (Kind=nag_wp) array User Workspace
9: cpuser Type (c_ptr) User Workspace
iuser, ruser and cpuser are not used by h02bkf, but are passed directly to monit and may be used to pass information to this routine. If you do not need to reference cpuser, it should be initialized to c_null_ptr.
10: ifail Integer Input/Output
On entry: ifail must be set to 0, −1 or 1 to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of 0 causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of −1 means that an error message is printed while a value of 1 means that it is not.
If halting is not appropriate, the value −1 or 1 is recommended. If message printing is undesirable, then the value 1 is recommended. Otherwise, the value −1 is recommended since useful values can be provided in some output arguments even when ifail0 on exit. When the value -1 or 1 is used it is essential to test the value of ifail on exit.
On exit: ifail=0 unless the routine detects an error or a warning has been flagged (see Section 6).

6 Error Indicators and Warnings

If on entry ifail=0 or −1, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
Note: in some cases h02bkf may return useful information.
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.
The problem is already being solved.
This solver does not support the model defined in the handle.
On entry, nvar=value, expected value=value.
Constraint: nvar must match the current number of variables of the model in the handle.
Maximum number of nodes exceeded.
The solution returned is the best solution for the number of nodes investigated in the B&B tree.
The solver terminated after the maximum time allowed was exhausted.
Maximum number of seconds exceeded. Use optional parameter Time Limit to change the limit.
No feasible solution was found for the number of nodes investigated in the B&B tree.
The problem was found to be primal infeasible.
The problem was found to be dual infeasible.
This means the primal unboundness was detected.
The problem seems to be primal or dual infeasible, the algorithm was stopped.
An unexpected error has been triggered by this routine. Please contact NAG.
See Section 7 in the Introduction to the NAG Library FL Interface for further information.
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library FL Interface for further information.
Dynamic memory allocation failed.
See Section 9 in the Introduction to the NAG Library FL Interface for further information.

7 Accuracy

The accuracy of the solution is determined by optional parameters Milp Feasibility Tol, Milp Abs Gap and Milp Rel Gap.
If ifail=0 on the final exit, the returned point satisfies feasibility and gap conditions to the requested accuracy and thus it is a good estimate of the solution. If the maximum number of nodes set by Milp Max Nodes is exceeded, the best solution for the number of nodes investigated will be returned.

8 Parallelism and Performance

Background information to multithreading can be found in the Multithreading documentation.
h02bkf is not thread safe and should not be called from a multithreaded user program. Please see Section 1 in FL Interface Multithreading for more information on thread safety.
h02bkf makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

9 Further Comments

9.1 Description of the Printed Output

The solver can print information to give an overview of the problem and of the progress of the computation. The output may be sent to two independent streams (files) which are set by optional parameters Print File and Monitoring File. Optional parameters Print Level, Print Solution and Print Options determine the exposed level of detail. This allows, for example, a detailed log file to be generated while the condensed information is displayed on the screen.
By default (Print File=6, Print Level=2), six sections are printed to the standard output:
The header is a message indicating the start of the solver. It should look like:
 H02BK, Solver for MILP problems
Optional parameters list
The list shows all options of the solver, each displayed on one line. The output contains the option name, its current value and an indicator for how it was set. The options unchanged from the default setting are noted by ‘d’, options you set are noted by ‘U’, and options reset by the solver are noted by ‘S’. Note that the output format is compatible with the file format expected by e04zpf. The output might look as follows:
     Milp Presolve                 =                 Yes     * d
     Milp Random Seed              =                   0     * d
     Milp Feasibility Tol          =         1.00000E-07     * U
     Milp Rel Gap                  =         1.00000E-04     * d
Problem statistics
If Print Level2, statistics on the original problems are printed, for example:
 Problem Statistics
   No of variables                  5
     integer                        3
       inc. binary                  1
     free (unconstrained)           0
     bounded                        2
   No of lin. constraints           2
     nonzeroes                      4
   Objective function          Linear
Iteration log
If Print Level2, the solver prints the status of each iteration, the output shows the number of nodes processed and in queue, the number of leaves in the B&B tree and the number of leaves explored, best bound and best primal objective function value and their gap, the number of cuts in the cut pool, number of cuts in the current linear model, size of the conflict pool, iteration count and time spent. The output might look as follows:
Solving MIP model with:
   2 rows
   5 cols (0 binary, 3 integer, 0 implied int., 0 continuous)
   4 nonzeros

        Nodes      |    B&B Tree     |            Objective Bounds             |  Dynamic Constraints |       Work
     Proc. InQueue |  Leaves   Expl. | BestBound       BestSol             Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -27.8           1.79769313e+308     inf        0      0      0         0     0.0s
Once the solver finishes, a detailed summary is produced:
Status: converged, an optimal solution found
Final primal objective value         1.390000E+01
Final dual objective bound           1.390000E+01
Primal infeasibility                 0.000000E+00
Integrality Violation                0.000000E+00
Optimality gap                       0.000000E+00
Total number of nodes                           1
Total LP iterations                             2
It starts with the status line of the overall result which matches the ifail value and is followed by the final primal objective values and dual objective bound as well as the error measures and iteration count.
If Print Solution=YES, the values of the primal variables and their bounds on the primary and secondary outputs. It might look as follows:
Primal variables:
  idx   Lower bound       Value       Upper bound
    1   0.00000E+00    1.00000E+00         inf
    2   0.00000E+00    4.00000E+00         inf

10 Example

This example demonstrates how to use h02bkf to solve a small MILP problem:
5.5x1 +2.1x2  
subject to the bounds
x10 x20  
and the general constraints
-x1 + 0.5x2 2 8x1 + 2x2 17  
where x1 and x2 are integer variables.
The optimal solution is
and the objective function value is 13.9.

10.1 Program Text

Program Text (h02bkfe.f90)

10.2 Program Data

Program Data (h02bkfe.d)

10.3 Program Results

Program Results (h02bkfe.r)

11 Algorithmic Details

The branch-and-bound (B&B) method applies directly to (1) as the basic framework. The general idea of B&B (for a full description see Dakin (1965) or Mitra (1973)) is to solve the problem without the integral restrictions as an LP problem (first node). In the optimal solution, if an integer variable xk takes a non-integer value xk*, then two LP sub-problems are created by branching. One sub-problem imposes xk[xk*], and the other imposes xk[xk*]+1, where [xk*] denotes the integer part of xk*. 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 a dual revised simplex method, see Huangfu and Hall (2018) for more details.

11.1 Stopping Criteria

Let z and z_ denote the primal objective value and the dual objective bound, respectively. Then the optimality is measured by
gabs |z-z_| , absolute gap, grel |z-z_| |z| , relative gap.  
The iteration is considered nearly optimal, and the B&B algorithm is stopped when the following conditions
gabs ε1   and   grel ε2  
are satisfied, and the feasibility violation is below the tolerance set by Milp Feasibility Tol. Here ε1 and ε2 may be set using Milp Abs Gap and Milp Rel Gap, respectively.

12 Optional Parameters

Several optional parameters in h02bkf define choices in the problem specification or the algorithm logic. In order to reduce the number of formal arguments of h02bkf these optional parameters have associated default values that are appropriate for most problems. Therefore, you need only specify those optional parameters whose values are to be different from their default values.
The remainder of this section can be skipped if you wish to use the default values for all optional parameters.
The optional parameters can be changed by calling e04zmf anytime between the initialization of the handle and the call to the solver. Modification of the optional parameters during intermediate monitoring stops is not allowed. Once the solver finishes, the optional parameters can be altered again for the next solve.
If any options are set by the solver (typically those with the choice of AUTO), their value can be retrieved by e04znf. If the solver is called again, any such arguments are reset to their default values and the decision is made again.
The following is a list of the optional parameters available. A full description of each optional parameter is provided in Section 12.1.

12.1 Description of the Optional Parameters

For each option, we give a summary line, a description of the optional parameter and details of constraints.
The summary line contains:
All options accept the value DEFAULT to return single options to their default states.
Keywords and character values are case and white space insensitive.
This special keyword may be used to reset all optional parameters to their default values. Any value given with this keyword will be ignored.
Infinite Bound SizerDefault =1020
This defines the ‘infinite’ bound bigbnd in the definition of the problem constraints. Any upper bound greater than or equal to bigbnd will be regarded as + (and similarly any lower bound less than or equal to -bigbnd will be regarded as -). Note that a modification of this optional parameter does not influence constraints which have already been defined; only the constraints formulated after the change will be affected.
Constraint: Infinite Bound Size1000.
Milp Abs GaprDefault =10−6
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 Abs Gapε.
Milp Detect SymmetryaDefault =YES
This parameter 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: Milp Detect Symmetry=YES or NO.
Milp Feasibility TolrDefault =10−6
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 r. For example, if the integer variable xj is near unity then xj is considered to be integer only if (1-r)xj(1+r).
Constraint: Milp Feasibility Tol>10−10.
Milp Max NodesiDefault =Imax
The maximum number of nodes that are to be searched in the B&B tree in order to find a solution.
Constraint: Milp Max Nodes0.
Milp PresolveaDefault =YES
This parameter 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: Milp Presolve=YES or NO.
Milp Random SeediDefault =0
Initial seed used for random selection in tasks such as primal heuristics and cut generation.
Constraint: Milp Random Seed0.
Milp Rel GaprDefault =10−4
Tolerance on relative gap, to determine whether optimality has been reached.
Constraint: Milp Rel Gapε.
Milp Small Matrix ValuerDefault =10−9
Lower limit on the absolute value of the linear constraint coefficients in the matrix A defined in (1). Values smaller than this will be treated as zero.
Constraint: Milp Small Matrix Value10−12.
Monitoring FileiDefault =−1
If i0, the unit number for the secondary (monitoring) output. If set to −1, no secondary output is provided. The following information is output to the unit:
Constraint: Monitoring File−1.
Monitoring LeveliDefault =4
This parameter 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: 0Monitoring Level5.
Print FileiDefault =advisory message unit number
If i0, the unit number for the primary output of the solver. If Print File=−1, the primary output is completely turned off independently of other settings. The default value is the advisory message unit number as defined by x04abf at the time of the optional parameters initialization, e.g., at the initialization of the handle. The following information is output to the unit:
Constraint: Print File−1.
Print LeveliDefault =2
This parameter defines how detailed information should be printed by the solver to the primary output.
i Output
0 No output from the solver
1 The Header and Summary
2, 3, 4, 5 Additionally, the Iteration log
Constraint: 0Print Level5.
Print OptionsaDefault =YES
If Print Options=YES, a listing of optional parameters will be printed to the primary and secondary output.
Constraint: Print Options=YES or NO.
Print SolutionaDefault =NO
If Print Solution=YES, the final values of the primal variables are printed on the primary and secondary outputs.
Constraint: Print Solution=YES or NO.
TaskaDefault =MINIMIZE
This parameter specifies the required direction of the optimization. If Task=FEASIBLE POINT, 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.
Time LimitrDefault =106
This parameter 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 ifail=23 error message.
Constraint: Time Limit>0.