NAG FL Interface e04mkf (handle_solve_lp_simplex)
Note:this routine usesoptional parametersto 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.
e04mkf is a solver from the NAG optimization modelling suite for large-scale Linear Programming (LP) problems. It is a simplex method optimization solver based on the HiGHS software package.
The routine may be called by the names e04mkf or nagf_opt_handle_solve_lp_simplex.
3Description
e04mkf solves a large-scale linear optimization problem in the following form:
(1)
where is the number of decision variables and is the number of linear constraints. Here , , , are -dimensional vectors, is an sparse matrix and , are -dimensional vectors.
e04mkf solves 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,e04rhfore04rjf may be called to formulate the objective function, bounds of the variables, and the block of linear constraints, respectively. 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 e04zmfande04zpf 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.
e04mkf is a complement to the interior point method solver e04mtf. It is recommended to try both solvers to determine which best suits your application.
3.1Structure of the Lagrangian Multipliers
The algorithm works internally with estimates of both the decision variables, denoted by , and the Lagrangian multipliers (dual variables), denoted by . The multipliers are stored in the array u and conform to the structure of the constraints.
If the simple bounds have been defined (e04rhf was successfully called), the first elements of u belong to the corresponding Lagrangian multipliers, interleaving a multiplier for the lower and the upper bound for each . If any of the bounds were set to infinity, the corresponding Lagrangian multipliers are set to and may be ignored.
Similarly, the following elements of u belong to multipliers for the linear constraints (if e04rjf has been successfully called). The organization is the same, i.e., the multipliers for each constraint for the lower and upper bounds are alternated and zeros are used for any missing (infinite bound) constraints.
Some solvers merge multipliers for both lower and upper inequality into one element whose sign determines the inequality. Negative multipliers are associated with the upper bounds and positive with the lower bounds. An equivalent result can be achieved with this storage scheme by subtracting the upper bound multiplier from the lower one. This is also consistent with equality constraints.
4References
Huangfu Q, and
Hall J.A. J.
(2018)
Parallelizing the dual revised simplex method
Mathematical Programming Computation10(1)
119–142
Nocedal J and Wright S J (2006) Numerical Optimization (2nd Edition) Springer Series in Operations Research, Springer, New York
5Arguments
1: – 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 e04mkf. It must not be changed between calls to the NAG optimization modelling suite.
2: – IntegerInput
On entry: , the current number of decision variables in the model.
3: – Real (Kind=nag_wp) arrayInput/Output
On entry: , the initial estimates of the variables, .
If , u will not be referenced; otherwise, it needs to match the dimension of constraints defined by e04rhfande04rjf as explained in Section 3.1.
Constraint:
.
5: – Real (Kind=nag_wp) arrayInput/Output
Note: if , u holds Lagrange multipliers (dual variables) for the bound constraints and linear constraints. If , u will not be referenced.
On entry: optionally provides the initial estimates of Lagrange multipliers. If there are no initial estimates available, then set to zero.
On exit: the final values of the variables .
6: – Real (Kind=nag_wp) arrayOutput
On exit: error measures and various indicators of the algorithm as given in the table below:
Value of the primal objective.
The maximum violation of a bound on a variable.
The sum of violations of bounds by variables.
The maximum dual feasibility violation.
The sum of dual feasibility violations.
–
Reserved for future use.
7: – Real (Kind=nag_wp) arrayOutput
On exit: solver statistics as given in the table below.
Total number of simplex iterations performed.
Total time spent in the solver.
–
Reserved for future use.
8: – 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 e04mku included in the NAG Library.
On entry: the handle to the problem as provided on entry to e04mkf. It may be used to query the model during the solve, and extract the current approximation of the solution by e04rxf.
2: – Real (Kind=nag_wp) arrayInput
On entry: error measures and various indicators at the end of the current iteration as described in rinfo.
3: – Real (Kind=nag_wp) arrayInput
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: – Integer arrayUser Workspace
5: – Real (Kind=nag_wp) arrayUser Workspace
6: – Type (c_ptr)User Workspace
monit is called with the arguments iuser, ruser and cpuser as supplied to e04mkf. You should use the arrays iuser and ruser, and the data handle cpuser to supply information to monit.
7: – IntegerInput/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 e04mkf is called. Arguments denoted as Input must not be changed by this procedure.
9: – Integer arrayUser Workspace
10: – Real (Kind=nag_wp) arrayUser Workspace
11: – Type (c_ptr)User Workspace
iuser, ruser and cpuser are not used by e04mkf, 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.
12: – IntegerInput/Output
On entry: ifail must be set to , or to set behaviour on detection of an error; these values have no effect when no error is detected.
A value of causes the printing of an error message and program execution will be halted; otherwise program execution continues. A value of means that an error message is printed while a value of means that it is not.
If halting is not appropriate, the value or is recommended. If message printing is undesirable, then the value is recommended. Otherwise, the value is recommended since useful values can be provided in some output arguments even when on exit. When the value or is used it is essential to test the value of ifail on exit.
On exit: unless the routine detects an error or a warning has been flagged (see Section 6).
6Error Indicators and Warnings
If on entry or , 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 e04mkf 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, , expected .
Constraint: nvar must match the current number of variables of the model in the handle.
On entry, . nnzu does not match the size of the Lagrangian multipliers for constraints. The correct value is for no constraints.
On entry, . nnzu does not match the size of the Lagrangian multipliers for constraints. The correct value is either or .
Maximum number of iterations exceeded.
The solver terminated after the maximum time allowed was exhausted.
Maximum number of seconds exceeded. Use optional parameter Time Limit to change the limit.
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.
If on the final exit, the returned point satisfies feasibility to the requested accuracy and thus it is a good estimate of the solution.
8Parallelism and Performance
Background information to multithreading can be found in the Multithreading documentation.
e04mkf 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.
Parallel strategies of the dual simplex method are available, see Simplex Strategy for more details.
9Further Comments
9.1Description 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 (, ), 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:
---------------------------------------
E04MK, Simplex method for LP 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:
Simplex Presolve = Yes * d
Simplex Start Type = Cold * d
Simplex Strategy = Dual Serial * d
Simplex Random Seed = 0 * d
Simplex Iteration Limit = 100 * U
Simplex Primal Feasibility Tol= 1.00000E-07 * d
Problem statistics
If , statistics on the original problems are printed, for example:
Problem Statistics
No of variables 7
free (unconstrained) 0
bounded 7
No of lin. constraints 7
nonzeroes 41
Objective function Linear
Iteration log
If , the solver prints the status of each iteration. The output shows the current primal objective function value, the number of variables violating a bound, the sum of violations of bounds by variables and time spent. The output might look as follows:
Once the solver finishes, a detailed summary is produced:
------------------------------------------------------------------------------
Status: converged, an optimal solution found
------------------------------------------------------------------------------
Final objective value 2.359648E-02
Primal infeasibility 0.000000E+00
Dual infeasibility 0.000000E+00
Iterations 8
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.
Solution
If , the values of the primal variables and their bounds on the primary and secondary outputs. It might look as follows:
A basis refers to a partitioning of the primal and slack variables. This partitioning plays a fundamental role in the underlying simplex algorithms of e04mkf.
e04mkf stores in the handle under the label ‘BASIS’ (or ‘WARM START BASIS’) the final state of the primal and slack variables. It also retrieves this information from the handle when a warm start is requested using optional parameter , see Section 9.3.
The stored integer array is of length , where is the number of linear constraints, and the values describe the state of the primal variables x and the slacks as follows:
BASIS()
State of variable
Usual value
0
Nonbasic
lower bound, including fixed variables
1
Basic
between lower and upper bounds
2
Nonbasic
upper bound
3
Nonbasic
free variable
4
Nonbasic
no specific bound information
The basis can be stored or retrieved from the handle with e04rwf using or and .
9.3Warm Starting
Warm starting a problem refers to providing a starting point x and additional information used by the solver to start the optimization process, for example, by providing information on which variables are active or nonbasic and thus hinting on the possible final active-set or providing a good initial guess for the final values of the Lagrange multipliers.
In order to warm start e04mkf, it is necessary to
(i)provide on the call to e04mkf the initial guess ;
(ii)provide on the call to e04mkf the initial guess for the Lagrange multipliers u. If nnzu then the solver will access array u and so it must be provided. If nothing is known about the multipliers then u should be set to zero in the call to e04mkf;
(iii)store in the handle (under the label ‘BASIS’ or ‘WARM START BASIS’) a valid basis vector of length . See Section 9.2;
(iv)request the solver to attempt a warm start by setting optional parameter .
If optional parameter but e04mkf does not find the required information or it is inconsistent, then it will revert to a cold start.
Note:e04mkf at exit (if the information is available) stores the basis arrays into the handle under the label ‘BASIS’. A next call to e04mkf with the same handle along with , and the latest x and u, should trigger a warm start successfully. It will also notify the source of the warm starting information with a message similar to:
Warm start information loaded successfully from handle.
Handle [WARM START BASIS] data origin: solver
Which indicates that the warm start information was successfully loaded. It also informs that the basis information was provided by the solver itself, say, from a previous call to e04mkf.
10Example
This example demonstrates how to use e04mkf to solve a small LP problem:
All iterates of the simplex method are vertices of the feasible polytope. Most steps consist of a move from one vertex to an adjacent one for which the basis differs in exactly one component. The matrix is partitioned into a nonsingular basis submatrix and a nonbasis submatrix. Then by setting the nonbasis variables to zero, the basis variables can be calculated by the LU factorization. Based on the Lagrangian multipliers and pricing, a column of basis is replaced by a variable from the nonbasis matrix. Dual simplex method starts with a feasible point for the dual problem and then uses the same concept of matrix splitting etc. Dual simplex is often faster on many practical problems. There are many important aspects of an implementation of the simplex method, such as the underlying linear algebra, selection of the entering variable and handling of degenerate steps, see Huangfu and Hall (2018) and Nocedal and Wright (2006) for more details.
12Optional Parameters
Several optional parameters in e04mkf define choices in the problem specification or the algorithm logic. In order to reduce the number of formal arguments of e04mkf 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 ), 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.
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 x02ajf), and represents the largest representable integer value (see x02bbf).
All options accept the value to return single options to their default states.
Keywords and character values are case and white space insensitive.
Defaults
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: .
Simplex 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 .
Simplex Start Type
Default
Defines whether to perform a cold or warm start. If warm start data is not provided or is considered to have an unexpected size or content, then the solver will revert to perform a cold start on the problem. See Section 9.3 on how to correctly warm start a problem.
Constraint: or .
Simplex Strategy
Default
This parameter controls the strategy employed by the simplex algorithm implemetation. By default the dual simplex solver runs in serial. Unless a Linear Programming (LP) problem has significantly more variables than constraints, the parallel dual simplex solver is unlikely to be worth using. If a parallel strategy is chosen, e04mkf will use half the available threads on the machine and automatically choose maximum level of concurrency.
Meaning
The solver chooses the strategy automatically
Dual simplex method running in serial
Dual simplex method with Parallelization Across Multiple Iterations
Dual simplex method with Single Iteration Parallelism
Primal simplex method running in serial
Constraint: , , , or .
Simplex Random Seed
Default
Initial seed used for random permutation and factor accuracy assessment.
Constraint: .
Simplex Iteration Limit
Default
The maximum number of iterations to be performed by e04mkf. Setting the option too low might lead to .
Constraint: .
Simplex 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: .
Simplex Primal Feasibility Tol
Default
The maximum acceptable absolute violation in each primal constraint (bound and linear constraint) at a ‘feasible’ point; i.e., a primal constraint is considered satisfied if its violation does not exceed Simplex Primal Feasibility Tol . For example, a variable is considered to be feasible with respect to the bound constraint only if .
Constraint: .
Simplex Dual Feasibility Tol
Default
Similar to Simplex Primal Feasibility Tol, this parameter defines the maximum acceptable absolute violation in each dual constraint (bound and linear constraint) at a ‘feasible’ point; i.e., a dual constraint is considered satisfied if its violation does not exceed Simplex Dual Feasibility Tol .
Constraint: .
Monitoring File
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 optional parameters if set by Print Options;
–problem statistics, the iteration log and the final status as set by Monitoring Level;
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: .
Print File
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 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:
–a listing of optional parameters if set by Print Options;
–problem statistics, the iteration log and the final status from the solver as set by Print Level;
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.
If or , in addition to the primal variables, the final values of the dual variables are printed on the primary and secondary outputs.
Constraint: , , or .
Task
Default
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, Task reverts to automatically.
Constraint: , or .
Time Limit
Default
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 error message.