This is a note about BRATIO, a very exotic GAMS option related to providing an advanced basis to a Simplex-based LP (or NLP) solver.

#### Marginals

For every variable and equation used in a model, GAMS stores the level (.L) and marginal (.M). The level is just its value. I.e. to print results, we can write

displayx.l(i,j);

The marginals correspond to **duals** for equations and **reduced costs** for variables. Printing is similar:

displaycapacity.m(wh);

The levels and marginals are typically populated (or updated) by the solver. If not set, their default values are zero. This makes sense as GAMS stores everything in **sparse** data structures. That means a variable with default values will not use any memory. This is a property we use extensively in large models: only a small fraction of variables

production(product,variant,facility,time)

maybe actually used e.g. because a facility can only produce certain products/variants.

#### Nonlinear models: initial values

x.l(i,j) = 100;

optionnlp=ipopt;

solvechain using nlp minimizing energy;

solvechain using nlp minimizing energy;

If we run this we see:

S O L V E S U M M A R Y MODEL
chain OBJECTIVE
energy **** SOLVER STATUS 1 Normal Completion RESOURCE USAGE, LIMIT 29.531 10000000000.000 |

S O L V E S U M M A R Y MODEL
chain
OBJECTIVE energy **** SOLVER STATUS 1 Normal Completion RESOURCE USAGE, LIMIT 0.078 10000000000.000 |

We see the first solve takes 30 seconds and 362 iterations. The second solve took 0.1 seconds and 0 iterations. IPOPT immediately sees we are giving it an optimal solution.

This scheme also works when we mix solvers (e..g the first solve with CONOPT), or when we make some changes in the model.

#### Linear programming: advanced basis

**basis information**. This data tells the solver which variables and equations are basic (to be determined by the solver by solving a linear system) or non-basic (temporarily fixed at one of the bounds). GAMS will pass on, besides levels, marginal indicators for the rows and columns. They look like:

- x.m (or e.m) is zero: the variable or equation is
**basic** - x.m (or e.m) is non-zero or EPS: the variable or equation is
**non-basic**.

Detail: the levels may be used to determine if a non-basic variable/equation is "at-lower" or "at-upper". The levels are not used for basic variables.

- The number of basic variables and equations is equal to the number of equations.
- The number of non-basic variables and equations is equal to the number of variables in the model.

optionlp=cbc;

solveone minimizing cost using lp;

solveone minimizing cost using lp;

S O L V E S U M M A R Y MODEL
one
OBJECTIVE cost **** SOLVER STATUS 1 Normal Completion RESOURCE USAGE, LIMIT 0.033 10000000000.000 |

Calling CBC main solution
routine... |

Calling CBC main solution
routine... |

optionlp=cplexsolveone minimizing cost using lp;solveone minimizing cost using lp;

#### Use cases

- changing some coefficients in the model
- adding some constraints
- deleting some constraints

- solving different models that share a portion of the equations and variables
- setting the marginals directly [2,3]

#### Accept or reject a basis

**BRATIO**option in play. Let \(m\) be the number of equations in the model, and let \(nbr\) the number of nonzero marginals for these equations (that is the number of non-basic rows), then we accept the basis if: \[nbr \gt \mathit{BRATIO} \times m\] The default value of BRATIO is 0.25. This makes some sense: if the number of basic rows is too large (with zero row marginals), we likely have changed the model too much (remember that the default value for a marginal is zero).

- option BRATIO=1; means: ignore the basis and let the solver start from scratch. Hopefully, the solver can "crash" a good basis [4].
- option BRATIO=0; indicates: always accept the basis, and pass it on to the solver [2,3].

This description is somewhat incorrect: the BRATIO option only looks at row marginals. For a proper basis (number of basics equal to the number of rows), we have that the number of non-basic rows is equal to the number of basic columns. However, for an incomplete or overspecified basis, this is not the case.The value specified for`bRatio`

will cause a basis to be discarded if the number of basic variables is smaller than`bRatio`

times the number of equations.

#### Notes

- When solving multiple large LP scenarios, it may make sense to use an interior point (barrier) algorithm for the first solve, followed by a number of simplex solves.
- Similarly, if the scenarios are NLPs, it may help to use an interior point solver for the first scenario or base case (e.g. using IPOPT or KNITRO), followed by an active set method for the other scenarios (e.g. using CONOPT or SNOPT).
- I usually don't worry about BRATIO, but in some cases, I set it to zero (accept basis) or one (ignore basis).
- For MIP models, BRATIO is usually not applicable or useful. Most MIP models spend a small fraction in the first LP and a MIP presolve will likely destroy a basis.
- BRATIO is very unique to GAMS. To my knowledge no other tool has something like this.

#### References

- What is this EPS in a GAMS solution? https://yetanothermathprogrammingconsultant.blogspot.com/2017/09/what-is-this-eps-in-gams-solution.html
- Solving sparse systems of equations with an optimizer: a basis trick, https://yetanothermathprogrammingconsultant.blogspot.com/2018/02/solving-sparse-systems-of-equations.html
- Inverting a matrix by LP, https://yetanothermathprogrammingconsultant.blogspot.com/2021/04/inverting-matrix-by-lp.html
- B.A. Murtagh, Advanced Linear Programming (McGraw-Hill, New York, 1981).

## No comments:

## Post a Comment