e04mk: FL CL CPP AD PY MB

NAG CL Interface
e04mkc (handle_solve_lp_simplex)

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.

Keyword Search:

NAG Library Manual, Mark 30.3

Interfaces: FL CL CPP AD PY MB

NAG CL Interface Introduction

E04 (Opt) Chapter Contents

E04 (Opt) Chapter Introduction

e04mk: FL CL CPP AD PY MB

▸▿ Contents

1 Purpose

2 Specification

▸▿ 3 Description

3.1 Structure of the Lagrangian Multipliers

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

▸▿ 9 Further Comments

9.1 Description of the Printed Output

9.2 Retrieving and Storing a Basis

9.3 Warm Starting

▸▿ 10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

11 Algorithmic Details

▸▿ 12 Optional Parameters

12.1 Description of the Optional Parameters

Settings help

CL Name Style:
Short (a00aac)
Long (impl_details)
Full (nag_info_impl_details)

1 Purpose

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

2 Specification

#include <nag.h>

void

e04mkc (void *handle, Integer nvar, double x[], Integer nnzu, double u[], double rinfo[], double stats[],

void	(monit)(void handle, const double rinfo[], const double stats[], Nag_Comm comm, Integer inform),

Nag_Comm *comm, NagError *fail)

The function may be called by the names: e04mkc or nag_opt_handle_solve_lp_simplex.

3 Description

e04mkc solves a large-scale linear optimization problem in the following form:

\begin{array}{l} \underset{x \in ℝ^{n}}{minimize} & c^{T} x & (a) \\ subject to & l_{A} \leq A x \leq u_{A} & (b) \\ l_{x} \leq x \leq u_{x}, & (c) \end{array}

(1)

where

n

is the number of decision variables and

m

is the number of linear constraints. Here

c

x

l_{x}

u_{x}

are

n

-dimensional vectors,

A

is an

m \times n

sparse matrix and

l_{A}

u_{A}

are

m

-dimensional vectors.

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

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.

e04mkc is a complement to the interior point method solver e04mtc. It is recommended to try both solvers to determine which best suits your application.

3.1 Structure of the Lagrangian Multipliers

The algorithm works internally with estimates of both the decision variables, denoted by

x

, and the Lagrangian multipliers (dual variables), denoted by

u

. The multipliers

u

are stored in the array u and conform to the structure of the constraints.

If the simple bounds have been defined (e04rhc was successfully called), the first

2 n

elements of u belong to the corresponding Lagrangian multipliers, interleaving a multiplier for the lower and the upper bound for each

x_{i}

. If any of the bounds were set to infinity, the corresponding Lagrangian multipliers are set to

0

and may be ignored.

Similarly, the following

2 m

elements of u belong to multipliers for the linear constraints (if e04rjc 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.

4 References

Huangfu Q, and Hall J.A. J. (2018) Parallelizing the dual revised simplex method Mathematical Programming Computation 10(1) 119–142

Nocedal J and Wright S J (2006) Numerical Optimization (2nd Edition) Springer Series in Operations Research, Springer, New York

5 Arguments

1: $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 e04mkc. 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]$ – double Input/Output

On entry:

x_{0}

, the initial estimates of the variables,

x

On exit: the final values of the variables,

x

4: $nnzu$ – Integer Input

On entry: the dimension of array u.

nnzu = 0

, u will not be referenced; otherwise, it needs to match the dimension of constraints defined by e04rhc and e04rjc as explained in Section 3.1.

Constraint:

nnzu \geq 0

5: $u [nnzu]$ – double Input/Output

Note: if

nnzu > 0

, u holds Lagrange multipliers (dual variables) for the bound constraints and linear constraints. If

nnzu = 0

, u will not be referenced and may be NULL.

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

u

6: $rinfo [100]$ – double Output

On exit: error measures and various indicators of the algorithm as given in the table below:

$0$	Value of the primal objective.
$1$	The maximum violation of a bound on a variable.
$2$	The sum of violations of bounds by variables.
$3$	The maximum dual feasibility violation.
$4$	The sum of dual feasibility violations.
$5$ – $99$	Reserved for future use.

7: $stats [100]$ – double Output

On exit: solver statistics as given in the table below.

$0$	Total number of simplex iterations performed.
$1$	Total time spent in the solver.
$2$ – $99$	Reserved for future use.

8: $monit$ – 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:

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

1: $handle$ – void * Input

On entry: the handle to the problem as provided on entry to e04mkc. It may be used to query the model during the solve, and extract the current approximation of the solution by e04rxc.

2: $rinfo [100]$ – const double Input

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

3: $stats [100]$ – const double 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: $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 e04mkc you may allocate memory and initialize these pointers with various quantities for use by monit when called from e04mkc (see Section 3.1.1 in the Introduction to the NAG Library CL Interface).

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

9: $comm$ – Nag_Comm *

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

10: $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 $⟨ value ⟩$ had an illegal value.
NE_DIM_MATCH: On entry, $nnzu = ⟨ value ⟩$ .
nnzu does not match the size of the Lagrangian multipliers for constraints.
The correct value is $0$ for no constraints.

On entry, $nnzu = ⟨ value ⟩$ .
nnzu does not match the size of the Lagrangian multipliers for constraints.
The correct value is either $0$ or $⟨ 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, $nvar = ⟨ value ⟩$ , expected $value = ⟨ value ⟩$ .
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 $Time Limit$ to change the limit.
NE_TOO_MANY_ITER: Maximum number of iterations exceeded.
NE_UNBOUNDED: The problem was found to be dual infeasible.
This means the primal unboundness was detected.

7 Accuracy

The accuracy of the solution is determined by optional parameters

Simplex Primal Feasibility Tol

and

Simplex Dual Feasibility Tol

fail . code =

NE_NOERROR on the final exit, the returned point satisfies feasibility to the requested accuracy and thus it is a good estimate of the solution.

8 Parallelism and Performance

Background information to multithreading can be found in the Multithreading documentation.

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

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:

Header
Optional parameters list (if $Print Options = YES$ )
Problem statistics
Iteration log
Summary
Solution (if $Print Solution = YES$ )

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

Print Level \geq 2

, 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

Print Level \geq 2

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

  Iteration        Objective     Infeasibilities num(sum)
          0    -5.1000178844e-02 Pr: 6(0.166925) 0s
          8     2.3596482085e-02 Pr: 0(0) 0s

Summary

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

Print Solution = X

, 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  -1.00000E-02   -1.00000E-02    1.00000E-02
     2  -1.00000E-01   -1.00000E-01    1.50000E-01
     3  -1.00000E-02    3.00000E-02    3.00000E-02
     4  -4.00000E-02    2.00000E-02    2.00000E-02
     5  -1.00000E-01   -6.74853E-02    5.00000E-02
     6  -1.00000E-02   -2.28013E-03         inf
     7  -1.00000E-02   -2.34528E-04         inf

Print Solution = YES

ALL

, the values of the dual variables are also printed. It should look as follows:

 Box bounds dual variables:
   idx   Lower bound       Value       Upper bound       Value
     1  -1.00000E-02    3.30098E-01    1.00000E-02    0.00000E+00
     2  -1.00000E-01    1.43844E-02    1.50000E-01    0.00000E+00
     3  -1.00000E-02    0.00000E+00    3.00000E-02    9.09967E-02
     4  -4.00000E-02    0.00000E+00    2.00000E-02    7.66124E-02
     5  -1.00000E-01    0.00000E+00    5.00000E-02    0.00000E+00
     6  -1.00000E-02    0.00000E+00         inf       0.00000E+00
     7  -1.00000E-02    0.00000E+00         inf       0.00000E+00

 Linear constraints dual variables:
   idx   Lower bound       Value       Upper bound       Value
     1  -1.30000E-01    0.00000E+00   -1.30000E-01    1.43111E+00
     2       -inf       0.00000E+00   -4.90000E-03    0.00000E+00
     3       -inf       0.00000E+00   -6.40000E-03    0.00000E+00
     4       -inf       0.00000E+00   -3.70000E-03    0.00000E+00
     5       -inf       0.00000E+00   -1.20000E-03    0.00000E+00
     6  -9.92000E-02    1.50098E+00         inf       0.00000E+00
     7  -3.00000E-03    1.51661E+00    2.00000E-03    0.00000E+00

9.2 Retrieving and Storing a Basis

A basis refers to a partitioning of the primal and slack variables. This partitioning plays a fundamental role in the underlying simplex algorithms of e04mkc.

e04mkc 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

Simplex Start Type = WARM

, see Section 9.3.

The stored integer array is of length

nvar + m

, where

m

is the number of linear constraints, and the values describe the state of the primal variables x and the slacks as follows:

BASIS( $i$ )	State of variable $i$	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 e04rwc using

cmdstr ='BASIS'

'WARM START BASIS'

and

liarr = nvar + m

9.3 Warm 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 e04mkc, it is necessary to

(i)provide on the call to e04mkc the initial guess $x_{0}$ ;
(ii)provide on the call to e04mkc the initial guess for the Lagrange multipliers u. If nnzu $> 0$ 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 e04mkc;
(iii)store in the handle (under the label ‘BASIS’ or ‘WARM START BASIS’) a valid basis vector of length $nvar + m$ . See Section 9.2;
(iv)request the solver to attempt a warm start by setting optional parameter $Simplex Start Type = WARM$ .

If optional parameter

Simplex Start Type = WARM

but e04mkc does not find the required information or it is inconsistent, then it will revert to a cold start.

Note: e04mkc at exit (if the information is available) stores the basis arrays into the handle under the label ‘BASIS’. A next call to e04mkc with the same handle along with

Simplex Start Type = WARM

, 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 e04mkc.

10 Example

This example demonstrates how to use e04mkc to solve a small LP problem:

minimize

- 0.02 x_{1} - 0.2 x_{2} - 0.2 x_{3} - 0.2 x_{4} - 0.2 x_{5} + 0.04 x_{6} + 0.04 x_{7}

subject to the bounds

\begin{matrix} - 0.01 \leq x_{1} \leq 0.01 \\ - 0.1 \leq x_{2} \leq 0.15 \\ - 0.01 \leq x_{3} \leq 0.03 \\ - 0.04 \leq x_{4} \leq 0.02 \\ - 0.1 \leq x_{5} \leq 0.05 \\ - 0.01 \leq x_{6} \\ - 0.01 \leq x_{7} \end{matrix}

and the general constraints

\begin{matrix} x_{1} & + & x_{2} & + & x_{3} & + & x_{4} & + & x_{5} & + & x_{6} & + & x_{7} & = & - 0.13 \\ 0.15 x_{1} & + & 0.04 x_{2} & + & 0.02 x_{3} & + & 0.04 x_{4} & + & 0.02 x_{5} & + & 0.01 x_{6} & + & 0.03 x_{7} & \leq & - 0.0049 \\ 0.03 x_{1} & + & 0.05 x_{2} & + & 0.08 x_{3} & + & 0.02 x_{4} & + & 0.06 x_{5} & + & 0.01 x_{6} & \leq & - 0.0064 \\ 0.02 x_{1} & + & 0.04 x_{2} & + & 0.01 x_{3} & + & 0.02 x_{4} & + & 0.02 x_{5} & \leq & - 0.0037 \\ 0.02 x_{1} & + & 0.03 x_{2} & + & 0.01 x_{5} & \leq & - 0.0012 \\ - 0.0992 & \leq & 0.70 x_{1} & + & 0.75 x_{2} & + & 0.80 x_{3} & + & 0.75 x_{4} & + & 0.80 x_{5} & + & 0.97 x_{6} \\ - 0.003 & \leq & 0.02 x_{1} & + & 0.06 x_{2} & + & 0.08 x_{3} & + & 0.12 x_{4} & + & 0.02 x_{5} & + & 0.01 x_{6} & + & 0.97 x_{7} & \leq & 0.002 . \end{matrix}

11 Algorithmic Details

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

A

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.

12 Optional Parameters

Several optional parameters in e04mkc define choices in the problem specification or the algorithm logic. In order to reduce the number of formal arguments of e04mkc 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

AUTO

), 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.

Defaults
Infinite Bound Size
Monitoring File
Monitoring Level
Print File
Print Level
Print Options
Print Solution
Simplex Dual Feasibility Tol
Simplex Iteration Limit
Simplex Presolve
Simplex Primal Feasibility Tol
Simplex Random Seed
Simplex Small Matrix Value
Simplex Start Type
Simplex Strategy
Task
Time Limit

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 $a$ , $i$ and $r$ 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 $Imax$ represents the largest representable integer value (see X02BBC).

All options accept the value

DEFAULT

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

r

Default

= 10^{20}

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

+ \infty

(and similarly any lower bound less than or equal to

- bigbnd

will be regarded as

- \infty

). 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 Size \geq 1000

Simplex Presolve

a

Default

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

Simplex Presolve = YES

NO

Simplex Start Type

a

Default

= COLD

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:

Simplex Start Type = COLD

WARM

Simplex Strategy

a

Default

= DUAL SERIAL

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, e04mkc will use half the available threads on the machine and automatically choose maximum level of concurrency.

$a$	Meaning
$AUTO$	The solver chooses the strategy automatically
$DUAL SERIAL$	Dual simplex method running in serial
$DUAL PAMI$	Dual simplex method with Parallelization Across Multiple Iterations
$DUAL SIP$	Dual simplex method with Single Iteration Parallelism
$PRIMAL$	Primal simplex method running in serial

Constraint:

Simplex Strategy = AUTO

DUAL SERIAL

DUAL PAMI

DUAL SIP

PRIMAL

Simplex Random Seed

i

Default

= 0

Initial seed used for random permutation and factor accuracy assessment.

Constraint:

Simplex Random Seed \geq 0

Simplex Iteration Limit

i

Default

= Imax

The maximum number of iterations to be performed by e04mkc. Setting the option too low might lead to

fail . code =

NE_TOO_MANY_ITER.

Constraint:

Simplex Iteration Limit \geq 0

Simplex Small Matrix Value

r

Default

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

Simplex Small Matrix Value \geq 10^{−12}

Simplex Primal Feasibility Tol

r

Default

= 10^{−7}

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

r

. For example, a variable

x_{j}

is considered to be feasible with respect to the bound constraint

l_{j} \leq x_{j} \leq u_{j}

only if

(l_{j} - r) \leq x_{j} \leq (u_{j} + r)

Constraint:

Simplex Primal Feasibility Tol > 10^{−10}

Simplex Dual Feasibility Tol

r

Default

= 10^{−7}

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

r

Constraint:

Simplex Dual Feasibility Tol > 10^{−10}

Monitoring File

i

Default

= −1

(See Section 3.1.1 in the Introduction to the NAG Library CL Interface for further information on NAG data types.)

i \geq 0

, the Nag_FileID number (as returned from x04acc) for the secondary (monitoring) output. If set to

−1

, 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$ ;
–the solution if set by $Print Solution$ .

Constraint:

Monitoring File \geq −1

Monitoring Level

i

Default

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

0 \leq Monitoring Level \leq 5

Print File

i

Default

= Nag_FileID number associated with stdout

(See Section 3.1.1 in the Introduction to the NAG Library CL Interface for further information on NAG data types.)

i \geq 0

, the Nag_FileID number (as returned from x04acc, stdout as the default) for the primary output of the solver. If

Print File = −1

, 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 $Print Options$ ;
–problem statistics, the iteration log and the final status from the solver as set by $Print Level$ ;
–the solution if set by $Print Solution$ .

Constraint:

Print File \geq −1

Print Level

i

Default

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

0 \leq Print Level \leq 5

Print Options

a

Default

= YES

Print Options = YES

, a listing of optional parameters will be printed to the primary and secondary output.

Constraint:

Print Options = YES

NO

Print Solution

a

Default

= NO

Print Solution = X

, the final values of the primal variables are printed on the primary and secondary outputs.

Print Solution = YES

ALL

, in addition to the primal variables, the final values of the dual variables are printed on the primary and secondary outputs.

Constraint:

Print Solution = YES

NO

X

ALL

Task

a

Default

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

Constraint:

Task = MINIMIZE

MAXIMIZE

FEASIBLE POINT

Time Limit

r

Default

= 10^{6}

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