### Table of Contents

# Introduction

This document describes GAMS/Examiner, a tool for examining points and making an unbiased, independent assessment of their merit. In short, it checks if solutions are *really* solutions. As an example, it can take a solution point reported as optimal by a solver and examine it for primal feasibility, dual feasibility, and optimality. Examiner has a number of different modes, allowing it to check the input point from GAMS/Base as well as the solution passed by a solver back to GAMS.

Many of the tests done by Examiner (perhaps all of them!) are already being done by the GAMS solvers, so Examiner is in a sense redundant. However, the ability to make an independent, transparent check of a solver's solution is very useful in solver development, testing, and debugging. It is also useful when comparing the solutions returned by two different solvers. Finally, a tool like the Examiner allows one to examine solutions using different optimality tolerances and optimality criteria in a way that is not possible when working with the solvers directly.

GAMS/Examiner is installed automatically with your GAMS system. Without a full GAMS/Base license, examiner will run in student or demonstration mode (i.e. it will examine small models only).

# Usage

Examiner can be used with all supported model types. Since Examiner doesn't really solve any problems, it is not a good choice for a default solver, and when installing GAMS it does not appear as an option in the list of possible solver defaults. However, you can choose Examiner via the command line:

gams trnsport LP=examiner;

or via a GAMS option statement

option LP=examiner;

somewhere before the `solve`

statement.

Since Examiner is not really a solver, many of the usual GAMS options controlling solvers have no impact on it. However, the `sysout`

option is interpreted in the usual way.

The optimality checks done in Examiner are first-order optimality checks done at a given point. A discussion here of these conditions and all they imply would be redundant: any good intro text in optimization will cover them. For linear programming, first-order optimality is all one needs to prove global optimality. For nonlinear programming, these conditions may or may not be necessary or sufficient for optimality; this depends on the convexity of the feasible set and objective and the form of the constraints. For integer programming models, these checks only make sense if we turn the global problem into a local one by adding bounds to the model, essentially fixing each discrete variable to its current value: these bounds are added automatically by Examiner.

Examiner runs in two basic modes of operation: it can examine the input point passed from GAMS/Base to the solver, and it can examine the point passed from the solver back to GAMS. Each mode can be used independent of the other. By default it will operate in the first mode, examining the initial "solution" passed to it by GAMS, but only if GAMS indicates it is passing an advanced basis to the solver (cf. the GAMS User Guide and the `bratio`

option). If you wish to use the second `solver-check`

mode, you may specify an appropriate subsolver using the `subsolver`

option (see section Options). If no `subsolver`

is selected, the default solver for the model type being solved is used. In most cases you will want to use an option file to specify exactly what type of examination you wish to perform. The rules for using an option file are described in The Solver Options File.

## Solution Points: Definition

There are a number of different ways a solution point can be defined. Of course the different definitions will typically result in the same points being produced, but there are cases where this will not be precisely so. Since Examiner is intended to explore and analyze these cases, we must make these definitions precise. The following four points are defined and used in Examiner:

- The
`gamspoint`

is the input point provided by GAMS to Examiner. The GAMS input point includes level & marginal values for the rows and columns: Examiner uses these exactly as given. - The
`initpoint`

is determined by the variable levels (primal vars) and equation marginals (dual vars) provided by GAMS to Examiner. These values are used to*compute*the equation levels and variable marginals / reduced costs using the function evaluator in Examiner, rather than using the values passed in by GAMS. - The
`solupoint`

is similar to the`initpoint`

: it uses the variable levels (primal vars) and equation marginals (dual vars) to*compute*the equation levels and variable marginals. The variable levels and equation marginals used are those returned by the subsolver. - The
`solvpoint`

is the point returned by the subsolver. The subsolver returns both level and marginal values for the rows and columns: Examiner uses these, exactly as given.

## Checks Performed

There are a number of checks that can be performed on any of the solution points. By default, Examiner tries to choose the appropriate checks. For example, if a primal simplex solver returns a model status of nonoptimal, the only checks that make sense are feasibility in the primal variables and constraints. However, this automatic choice of appropriate checks is not possible when checking points passed in from GAMS/Base.

**Primal variable feasibility**: check that all primal variables are within bounds.**Primal constraint feasibility**: check that all primal constraints are satisfied.**Dual variable feasibility**: check that all dual variables are within bounds.**Dual constraint feasibility**: check that all dual constraints are satisfied.**Primal complementary slackness**: check complementarity between the primal variables and the dual constraints / reduced costs.**Dual complementary slackness**: check complementarity between the dual variables / equation marginals and the equation slacks.**Equilibrium condition complementarity**: check complementarity of the equation/variable pairs in complementarity models (MCP, MPEC).

The checks above are implemented with default tolerances. These tolerances can be changed via an option file (see section Options).

Different ways exist to check the items mentioned above. For example, different norms can be used to measure the error of the residual when checking for primal feasibility. Currently, we have only implemented one way to make these checks.

For optimization models, it is possible to define a merit function that measures how well a given point satisfies conditions 1 through 6 above. Such a function is always nonnegative, and its value represents the error between the given point and a true solution. If such an input point is well-defined (e.g. if only one point is selected for examination) then Examiner will compute the merit function value at this point and return it in the RObj model attribute.

## Scaling

By default, Examiner makes its checks on the original, unscaled model. In many cases, however, it is important to take scaling into account. Consider the effect of row scaling on the simple constraint \(x^2 \le 9\) where \(x = 3.5\). Multiplying this constraint through by large or small constants changes the amount of the constraint violation proportionately, but the distance to feasibility is not changed. Applying row scaling to the original model eliminates this problem.

Most solvers scale a model before solving it, so any feasibility or optimality checks and tolerances are applied to the scaled model. The process of unscaling the model can result in a loss of feasibility or optimality. Even though we do not have access to the scales applied by the solver and cannot precisely construct the same scaled model, we can get a better idea of how the solver performed by looking at a model scaled by Examiner than by looking at the original.

It is also interesting to see what the model scaling looks like, even if we do not apply the scales to do the Examiner checks. If the row scales are in a nice range, say [.1,100], we can have some confidence that the model is well-scaled. In contrast, if the row scales are in the range `[1,1e8]`

we may question the precision of the solution provided.

For each row, Examiner computes the true row scale as

\[ \max (\Vert RHS_i \Vert ,\max_j( \Vert A_{ij} \Vert \cdot \max(1,\Vert x_j \Vert))) \]

In this way variables with a large level value lead to large scale factors. To make the scale factor independent of the variable values, use an option file line of `"AbsXScale 0"`

. This replaces the term \(\max(1,\Vert x_j \Vert)\) above with \(1\).

Since the user may wish to limit the size of the scale factors applied, the true row scales are projected onto the scale factor bounds to get the applied scale factors. The scale factors are applied when making a scaled check by dividing the rows by the scale factors and multiplying the corresponding Lagrange multipliers by these same factors. When making unscaled checks information about the true scales is still included in the output to give the user a hint about potential scaling issues.

Note that the scaled and unscaled checks are made independently. By default only the unscaled checks are performed. If you turn the scaled checks on via an option file line `"scaled 1"`

, this will not turn off the unscaled checks. You will need an option file line of `"unscaled 0"`

to turn off unscaled checks.

# Options

The following options control the behavior of GAMS/Examiner. Many of these are boolean (i.e. on/off) options. In this case, zero indicates off, nonzero on. For details on how to create and use an option file, see the section on the Solver Option File.

## General Options

Option | Description | Default |
---|---|---|

absXScale | Whether to make scale factors dependent on x values. If on, the matrix coefficients are multiplied by max(1,abs(x)) when computing the scale factors. If off, the matrix coefficients are taken as is. See Section Scaling. | `1` |

dumpGamsPoint | Whether to dump the GamsPoint to a basis file in GAMS source format. | `0` |

dumpInitPoint | Whether to dump the InitPoint to a basis file in GAMS source format. | `0` |

dumpSoluPoint | Whether to dump the SoluPoint to a basis file in GAMS source format. | `0` |

dumpSolvPoint | Whether to dump the SolvPoint to a basis file in GAMS source format. | `0` |

examineGamsPoint | Whether to examine the GamsPoint. | `0` |

examineInitPoint | Whether to examine the InitPoint. By default, this option is on if GAMS/Base passes an advanced basis, and off otherwise. | `auto` |

examineSoluPoint | Whether to examine the SoluPoint. By default, this option is on if a subsolver has been selected, and off otherwise. | `auto` |

examineSolvPoint | Whether to examine the SolvPoint. By default, this option is on if a subsolver has been selected, and off otherwise. | `auto` |

fCheckAll | If set, forces all checks on or off. | `auto` |

fCheckATTR | If set, forces the model attributes check on or off. | `auto` |

fCheckDCMP | If set, forces the dual complementary slackness check on or off. | `auto` |

fCheckDCON | If set, forces the dual constraint feasibility check on or off. | `auto` |

fCheckDVAR | If set, forces the dual variable feasibility check on or off. | `auto` |

fCheckPCMP | If set, forces the primal complementary slackness check on or off. | `auto` |

fCheckPCON | If set, forces the primal constraint feasibility check on or off. | `auto` |

fCheckPVAR | If set, forces the primal variable feasibility check on or off. | `auto` |

objvarAutoAdjust | Adjust objective variable to satisfy objective equation | `0` |

perpSys | Controls output during examination of solution points. If on, print out the point in a way that allows for easy visual inspection and verification of the KKT or first order optimality conditions. First, the primal level values and bounds are printed next to the reduced costs. Next, the duals levels and bounds are printed next to the row slacks. | `0` |

returnGamsPoint | Whether to return the GamsPoint as a solution to GAMS/Base. | `0` |

returnInitPoint | Whether to return the InitPoint as a solution to GAMS/Base. | `auto` |

returnSoluPoint | Whether to return the SoluPoint as a solution to GAMS/Base. | `auto` |

returnSolvPoint | Whether to return the SolvPoint as a solution to GAMS/Base. | `auto` |

scaled | Whether to apply checks to a scaled version of the model. | `0` |

scaleLB | Lower bound for applied row scales. | `1` |

scaleUB | Upper bound for applied row scales. | `maxdouble` |

showSlacks | explicitly show the infeasibilities or slacks for failed checks | `0` |

subSolver | Indicates what subsolver to run. By default, the subsolver used is the default subsolver for the model type in question. | `auto` |

subSolverOpt | optfile value to pass to the subsolver | `auto` |

trace | If set, trace information will be computed and appended to this file. | `none` |

unScaled | Whether to apply checks to the original, unscaled version of the model. | `1` |