NAG CL Interface
h02bkc (handle_solve_milp)
Note: this function uses optional parameters to define choices in the problem specification and in the details of the algorithm. If you wish to use default
settings for all of the optional parameters, you need only read Sections 1 to 10 of this document. If, however, you wish to reset some or all of the settings please refer to Section 11 for a detailed description of the algorithm and to Section 12 for a detailed description of the specification of the optional parameters.
1
Purpose
h02bkc 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
The function may be called by the names: h02bkc or nag_mip_handle_solve_milp.
3
Description
h02bkc 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.
h02bkc 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 calling
e04rac. Then some of the functions
e04rec,
e04rfc,
e04rhc or
e04rjc 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
e04rcc. Once the problem is fully set, the handle may be passed to the solver. When the handle is not needed anymore,
e04rzc should be called to destroy it and deallocate the memory held within. See
Section 4.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
e04zmc and
e04zpc anytime between the initialization of the handle by
e04rac 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 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:
– 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
h02bkc. It
must not be changed between calls to the
NAG optimization modelling suite.
-
2:
– Integer
Input
-
On entry: , the current number of decision variables in the model.
-
3:
– double
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 .
-
4:
– double
Output
-
On exit: 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. |
-
5:
– double
Output
-
On exit: 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. |
-
6:
– function, supplied by the user
External Function
-
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
The specification of
monit is:
-
1:
– void *
Input
-
On entry: the handle to the problem as provided on entry to
h02bkc. It may be used to query the model during the solve, and extract the current approximation of the solution by
e04rxc.
-
2:
– const double
Input
-
On entry: error measures and various indicators at the end of the current iteration as described in
rinfo.
-
3:
– const double
Input
-
On entry: solver statistics at the end of the current iteration as described in
stats, however, elements
,
,
,
,
,
and
refer to the quantities in the last iteration rather than accumulated over all iterations through the whole algorithm run.
-
4:
– 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
h02bkc you may allocate memory and initialize these pointers with various quantities for use by
monit when called from
h02bkc (see
Section 3.1.1 in the Introduction to the
NAG Library CL Interface).
-
5:
– 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.
-
7:
– Nag_Comm *
-
The
NAG communication argument (see
Section 3.1.1 in the Introduction to the
NAG Library CL Interface).
-
8:
– 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 had an illegal value.
- 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
-
The problem was found to be primal infeasible.
- 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_MAYBE_INFEASIBLE
-
The problem seems to be primal or dual infeasible, the algorithm was stopped.
- 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_PHASE
-
The problem is already being solved.
- NE_REF_MATCH
-
On entry,
, expected
.
Constraint:
nvar must match the current number of variables of the model in the
handle.
- 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 to change the limit.
- NE_UNBOUNDED
-
The problem was found to be dual infeasible.
This means the primal unboundness was detected.
- NW_MIP_MAX_ITER_INT_SOL
-
Maximum number of nodes exceeded.
The solution returned is the best solution for the number of nodes investigated in the B&B tree.
- NW_MIP_MAX_NODES_NO_INT_SOL
-
No feasible solution was found for the number of nodes investigated in the B&B tree.
7
Accuracy
The accuracy of the solution is determined by optional parameters , and .
If NE_NOERROR 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 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.
h02bkc 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 function. Please also consult the
Users' Note for your implementation for any additional implementation-specific information.
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 and . Optional parameters , and 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 (
,
), six sections are printed to the standard output:
- Header
- Optional parameters list (if )
- Problem statistics
- Iteration log
- Summary
- Solution (if )
Header
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
e04zpc. 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 * dProblem statistics
If
, 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 LinearIteration log
If
, 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.0sSummary
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
fail value and is followed by the final primal objective values and dual objective bound as well as the error measures and iteration count.
Solution
If
, 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 h02bkc to solve a small MILP problem:
maximize
subject to the bounds
and the general constraints
where
and
are integer variables.
The optimal solution is
and the objective function value is
.
10.1
Program Text
10.2
Program Data
10.3
Program Results
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
takes a non-integer value
, then two LP sub-problems are created by
branching. One sub-problem imposes
, and the other imposes
, 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 a dual revised simplex method, see
Huangfu and Hall (2018) for more details.
11.1
Stopping Criteria
Let
and
denote the primal objective value and the dual objective bound, respectively. Then the optimality is measured by
The iteration is considered nearly optimal, and the B&B algorithm is stopped when the following conditions
are satisfied, and the feasibility violation is below the tolerance set by
. Here
and
may be set using
and
, respectively.
12
Optional Parameters
Several optional parameters in h02bkc define choices in the problem specification or the algorithm logic. In order to reduce the number of formal arguments of h02bkc 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
e04zmc 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
), their value can be retrieved by
e04znc. 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:
- the keywords;
- a parameter value,
where the letters , and denote options that take character, integer and real values respectively;
- the default value, where the symbol is a generic notation for machine precision (see X02AJC), and represents the largest representable integer value (see X02BBC).
All options accept the value 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 Size | | 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 optional parameter does not influence constraints which have already been defined; only the constraints formulated after the change will be affected.
Constraint: .
| Milp Abs Gap | | 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 | | Default |
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: or .
| Milp Feasibility Tol | | 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 . For example, if the integer variable is near unity then is considered to be integer only if .
Constraint: .
| Milp Max Nodes | | 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 | | Default |
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: or .
| Milp Random Seed | | Default |
Initial seed used for random selection in tasks such as primal heuristics and cut generation.
Constraint: .
| Milp Rel Gap | | Default |
Tolerance on relative gap, to determine whether optimality has been reached.
Constraint: .
| Milp Small Matrix Value | | Default |
Lower limit on the absolute value of the linear constraint coefficients in the matrix
defined in
(1). Values smaller than this will be treated as zero.
Constraint: .
| Monitoring File | | Default |
(See
Section 3.1.1 in the Introduction to the
NAG Library CL Interface for further information on
NAG data types.)
If
, the
Nag_FileID number (as returned from
x04acc)
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 optional parameters if set by ;
-
–problem statistics, the iteration log and the final status as set by ;
-
–the solution if set by .
Constraint: .
| Monitoring Level | | Default |
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 .
Constraint: .
| Print File | | Default
|
(See
Section 3.1.1 in the Introduction to the
NAG Library CL Interface for further information on
NAG data types.)
If
, the
Nag_FileID number (as returned from
x04acc,
stdout as the default)
for the primary output of the solver. If
, the primary output is completely turned off independently of other settings. The following information is output to the unit:
-
–a listing of optional parameters if set by ;
-
–problem statistics, the iteration log and the final status from the solver as set by ;
-
–the solution if set by .
Constraint: .
This parameter 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 | | Default |
If , a listing of optional parameters will be printed to the primary and secondary output.
Constraint: or .
| Print Solution | | Default |
If , the final values of the primal variables are printed on the primary and secondary outputs.
Constraint: or .
This parameter 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, reverts to automatically.
Constraint: , or .
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
NE_TIME_LIMIT error message.
Constraint: .