naginterfaces.library.opt.handle_​solve_​lp_​simplex

naginterfaces.library.opt.handle_solve_lp_simplex(handle, x, u=None, monit=None, data=None, io_manager=None)

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

Note: this function uses optional algorithmic parameters, see also: handle_opt_set(), handle_opt_get().

For full information please refer to the NAG Library document for e04mk

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/e04/e04mkf.html

Parameters

handleHandle

The handle to the problem. It needs to be initialized (e.g., by handle_init()) and to hold a problem formulation compatible with handle_solve_lp_simplex. It must not be changed between calls to the NAG optimization modelling suite.

xfloat, array-like, shape $\left(\text{nvar}\right)$

$x_0$, the initial estimates of the variables, $x$.

uNone or float, array-like, shape $\left(\text{nnzu}\right)$, optional

Note: if $\text{nnzu}>0$, $u$ holds Lagrange multipliers (dual variables) for the bound constraints and linear constraints. If $\text{nnzu}=0$, $u$ will not be referenced.

Optionally provides the initial estimates of Lagrange multipliers. If there are no initial estimates available, then set to zero.

monitNone or callable monit(handle, rinfo, stats, data=None), optional

Note: if this argument is None then a NAG-supplied facility will be used.

$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 None.

Parameters

handleHandle

The handle to the problem as provided on entry to handle_solve_lp_simplex. It may be used to query the model during the solve, and extract the current approximation of the solution by handle_set_get_real().

rinfofloat, ndarray, shape $\left(100\right)$

Error measures and various indicators at the end of the current iteration as described in $rinfo$.

statsfloat, ndarray, shape $\left(100\right)$

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.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

dataarbitrary, optional

User-communication data for callback functions.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

xfloat, ndarray, shape $\left(\text{nvar}\right)$

The final values of the variables, $x$.

ufloat, ndarray, shape $\left(\text{nnzu}\right)$

The final values of the variables $u$.

rinfofloat, ndarray, shape $\left(100\right)$

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.

statsfloat, ndarray, shape $\left(100\right)$

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.

Other Parameters

‘Defaults’valueless

This special keyword may be used to reset all options to their default values. Any value given with this keyword will be ignored.

‘Infinite Bound Size’float

Default $={10}^{20}$

This defines the ‘infinite’ bound $\text{bigbnd}$ in the definition of the problem constraints. Any upper bound greater than or equal to $\text{bigbnd}$ will be regarded as $+\infty$ (and similarly any lower bound less than or equal to $-\text{bigbnd}$ will be regarded as $-\infty$). Note that a modification of this option does not influence constraints which have already been defined; only the constraints formulated after the change will be affected.

Constraint: $\text{‘Infinite Bound Size'}\ge 1000$.

‘Simplex Presolve’str

Default $=\text{'YES'}$

This argument 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: $\text{‘Simplex Presolve'}=\text{'YES'}$ or $\text{'NO'}$.

‘Simplex Start Type’str

Default $=\text{'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 Warm Starting on how to correctly warm start a problem.

Constraint: $\text{‘Simplex Start Type'}=\text{'COLD'}$ or $\text{'WARM'}$.

‘Simplex Strategy’str

Default $=\text{'DUAL SERIAL'}$

This argument 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, handle_solve_lp_simplex 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: $\text{‘Simplex Strategy'}=\text{'AUTO'}$, $\text{'DUAL SERIAL'}$, $\text{'DUAL PAMI'}$, $\text{'DUAL SIP'}$ or $\text{'PRIMAL'}$.

‘Simplex Random Seed’int

Default $=0$

Initial seed used for random permutation and factor accuracy assessment.

Constraint: $\text{‘Simplex Random Seed'}\ge 0$.

‘Simplex Iteration Limit’int

Default $=\text{Imax}$

The maximum number of iterations to be performed by handle_solve_lp_simplex. Setting the option too low might lead to $errno$ = 22.

Constraint: $\text{‘Simplex Iteration Limit'}\ge 0$.

‘Simplex Small Matrix Value’float

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: $\text{‘Simplex Small Matrix Value'}\ge {10}^{-12}$.

‘Simplex Primal Feasibility Tol’float

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\le x_j\le u_j$ only if $(l_j-r)\le x_j\le (u_j+r)$.

Constraint: $\text{‘Simplex Primal Feasibility Tol'}>{10}^{-10}$.

‘Simplex Dual Feasibility Tol’float

Default $={10}^{-7}$

Similar to ‘Simplex Primal Feasibility Tol’, this argument 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: $\text{‘Simplex Dual Feasibility Tol'}>{10}^{-10}$.

‘Monitoring File’int

Default $=-1$

If $i\ge 0$, 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:

• a listing of the options 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: $\text{‘Monitoring File'}\ge -1$.

‘Monitoring Level’int

Default $=4$

This argument 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\le \text{‘Monitoring Level'}\le 5$.

‘Print File’int

Default $=\text{advisory message unit number}$

If $i\ge 0$, the unit number for the primary output of the solver. If $\text{‘Print File'}=-1$, the primary output is completely turned off independently of other settings. The default value is the advisory message unit number at the time of the options initialization, e.g., at the initialization of the handle. The following information is output to the unit:

• a listing of options 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: $\text{‘Print File'}\ge -1$.

‘Print Level’int

Default $=2$

This argument 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\le \text{‘Print Level'}\le 5$.

‘Print Options’str

Default $=\text{'YES'}$

If $\text{‘Print Options'}=\text{'YES'}$, a listing of options will be printed to the primary and secondary output.

Constraint: $\text{‘Print Options'}=\text{'YES'}$ or $\text{'NO'}$.

‘Print Solution’str

Default $=\text{'NO'}$

If $\text{‘Print Solution'}=\text{'X'}$, the final values of the primal variables are printed on the primary and secondary outputs.

If $\text{‘Print Solution'}=\text{'YES'}$ or $\text{'ALL'}$, in addition to the primal variables, the final values of the dual variables are printed on the primary and secondary outputs.

Constraint: $\text{‘Print Solution'}=\text{'YES'}$, $\text{'NO'}$, $\text{'X'}$ or $\text{'ALL'}$.

‘Task’str

Default $=\text{'MINIMIZE'}$

This argument specifies the required direction of the optimization. If $\text{‘Task'}=\text{'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: $\text{‘Task'}=\text{'MINIMIZE'}$, $\text{'MAXIMIZE'}$ or $\text{'FEASIBLE POINT'}$.

‘Time Limit’float

Default $={10}^6$

This argument 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 $errno$ = 23 error message.

Constraint: $\text{‘Time Limit'}>0$.

Raises

NagValueError

(errno $1$)

$handle$ has not been initialized.

(errno $1$)

$handle$ does not belong to the NAG optimization modelling suite, has not been initialized properly or is corrupted.

(errno $1$)

$handle$ has not been initialized properly or is corrupted.

(errno $2$)

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

(errno $2$)

The problem is already being solved.

(errno $4$)

On entry, $\text{nvar}=⟨value⟩$, expected $value=⟨value⟩$.

Constraint: $\text{nvar}$ must match the current number of variables of the model in the $handle$.

(errno $5$)

On entry, $\text{nnzu}=⟨value⟩$.

$\text{nnzu}$ does not match the size of the Lagrangian multipliers for constraints.

The correct value is either $0$ or $⟨value⟩$.

(errno $5$)

On entry, $\text{nnzu}=⟨value⟩$.

$\text{nnzu}$ does not match the size of the Lagrangian multipliers for constraints.

The correct value is $0$ for no constraints.

(errno $51$)

The problem was found to be primal infeasible.

(errno $52$)

The problem was found to be dual infeasible.

(errno $53$)

The problem seems to be primal or dual infeasible, the algorithm was stopped.

Warns

NagAlgorithmicMajorWarning

(errno $22$)

Maximum number of iterations exceeded.

(errno $23$)

The solver terminated after the maximum time allowed was exhausted.

Notes

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

$$\begin{array}{c}\begin{array}{ccc}{minimize}_{x\in R^n}& c^{T}x& \text{(a)}\\ \text{subject to}& l_A\le Ax\le u_A& \text{(b)}\\ & l_x\le x\le u_x\text{,}& \text{(c)}\end{array}\end{array}$$

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.

handle_solve_lp_simplex 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 handle_init(). Then some of the functions handle_set_linobj(), handle_set_quadobj(), handle_set_simplebounds() or handle_set_linconstr() 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, handle_free() should be called to destroy it and deallocate the memory held within. See the E04 Introduction for more details about the NAG optimization modelling suite.

The solver method can be modified by various options (see Other Parameters) which can be set by handle_opt_set() and handle_opt_set_file() anytime between the initialization of the handle by handle_init() 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 options.

The option ‘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 Other Parameters for further details.

handle_solve_lp_simplex is a complement to the interior point method solver handle_solve_lp_ipm(). It is recommended to try both solvers to determine which best suits your application.

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 (handle_set_simplebounds() was successfully called), the first $2n$ 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 $2m$ elements of $u$ belong to multipliers for the linear constraints (if handle_set_linconstr() 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.

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

See also

naginterfaces.library.examples.opt.handle_solve_lp_simplex_ex.main()