Superbasic
Top Previous Next
Some of the solvers refer to variables that are superbasic. To solve a linear program it is sufficient to look at basic solutions or "corner points": A set of basic variables (with the number of basic variables equal to the number of constraints) is used to satisfy the constraints, and the remaining so called non-basic variables are all at either their upper or their lower bound (frequently zero).
In nonlinear programming, the optimal solution is usually not at a corner point. Some of the variables will still be at their lower or upper bounds and these variables are again called non-basic variables. The number of remaining variables will usually be larger than the number of constraints. Some solvers will split these remaining variables into basic variables, that are adjusted to satisfy the constraints (the number of basic variables is always equal to the number of constraints), and superbasic variables, that are adjusted to minimize or maximize the objective function. The number of superbasic variables is sometimes called the degrees of freedom. It is a measure of the nonlinearity of the solution around the current point.
Complementarity
Mixed complementarity model types (MCP) require a complementarity between the variables and the equations where either
a variable is nonzero and a constraint strictly binding
or
the constraint is non binding and the variable zero.
They also require the number of variables in the model to exactly match the number of equations in the model. This is discussed below.
Starting points -- initial values
One strategy one can use to improve solver performance involves use of starting points where initial values are provided for the decision variables within the problem. The specification of starting points involving good initial values for the individual variables is important in a NLP/MCP context for a number of reasons.
•
Non-convex models may have multiple solutions and the solvers generally only try to find one local one. An initial point in the right neighborhood is more likely to return a desirable solution.
Initial values that satisfy or closely satisfy many of the constraints reduce the work involved in finding a first feasible solution.
Initial values that are close to the optimal ones reduce the work required to find the optimal point and therefore the solution time.
The progress of the optimization algorithm is based on good directional information and therefore on good derivatives. The derivatives in a nonlinear model depend on the current point, and an improved initial point can improve solver performance.
Starting points are specified by assigning values to the level attribute of the variables before solution. Namely, one enters lines like
x.l(setdependency)= startingvalue;
into the code after the definition of the variables, but before the first solve.
The initial values used within one of the nonlinear solvers employed by GAMS are suggested by GAMS based on the problem formulation and the initial values provided. By default the initial value chosen for all variables is zero or the lower bound. Unfortunately, zero is in many cases is a bad initial value for a nonlinear variable. For example, an initial value of zero is especially bad if the variable appears in a product term since the initial derivative becomes zero, and it appears as if the function does not depend on the variable. Zero starting values can also cause numerical difficulties when logarithms, exponentiations or divisions are involved. Also nonzero lower bound derived starting points may not be desirable as derivatives evaluated at small lower bounds may be very large and provide the algorithm with misleading information.
Users should endeavor to supply as many sensible initial values for the nonlinear variables as possible by assignment to the level value, var.L, in GAMS as illustrated in the Basis Chapter. It may be desirable to initialize all variables to 1, or to the scale factor if employing the GAMS' scaling option. A better possibility is to select reasonable values for some variables that from the context or from prior solutions using advanced basis concepts like a GDX solution point file.
Constraint relationships can help in providing initial values. For example if the constraints
eq(i) .. x(i) = log(a(i)*y(i));
were in a model and you have assigned initial values to y.l(i), then you could provide a feasible solution by assigning x.l(i) = log(a(i)*y.l(i)).
One should try to the extent possible to assign initial values to as many as possible of the interrelated variables. Assume you have assigned a value to y.l(i) in the constraint above and have left x.l at zero. Commonly when a solver is trying to find a feasible solution, it will adjust one variable for each constraint. If the solver selects y to be adjusted (a good choice since it is away from its bounds and therefore free to move) then it will change y to the value that makes the constraint feasible and remove your starting point.
Upper and lower bounds
Lower and upper bounds in nonlinear models can
Represent constraints on the reality that is being modeled, e.g. a variable must be positive, or it must be less than or equal to 10.
Help the algorithm by preventing it from moving far away from any optimal solution and avoiding regions where problems are encountered like unreasonably large function or derivative values as well as singularities in the nonlinear functions. These bounds are called algorithmic bounds.
Facilitate solution feasibility since most solvers will honor bounds at all times, but inequalities are not necessarily satisfied at intermediate points.
Improve presolve performance since NLP solvers preprocessors incur a computational penalty when inequalities are present.
Algorithmic bounds merit further discussion. When a model contains the Log or Log10 of a variable it is generally useful to have that variable be no smaller than a given value like 1.e-3 (x.lo=1.0e-3) as the log gets very large as zero is approached and is undefined if the variable becomes negative. Similarly use of Exp of a variable in model equations implies that the variable value should be less than 20-25. Small values for variables used with negative exponents or in denominators are again not desirable. Solver performance can be improved and execution errors avoided when one introduces algorithmic bounds on variables not naturally bounded by the model formulation.
Scaling
Nonlinear programming algorithms use the derivatives of the objective function and the constraints to determine good search directions and to determine how to alter the value of the decision variable levels. They also use function values to determine if constraints are satisfied or not. The scaling of the variables and constraints, i.e. the units of measurement used for the variables and constraints, determines the relative size of the derivatives and function values. They also determine the solution levels and marginals and the search path taken by the algorithm. Proper, consistent scaling of these items is important to the success of the solution algorithm and the quality of the answer returned.
In this context proper consistent scaling means one should scale to achieve:
Solution level values for the variables fall into a range around 1, e.g. from 0.01 to 100.
Solution values of the nonzero constraint marginals that exhibit absolute values falling into a range around 1, e.g. from 0.01 to 100.
Derivatives of nonlinear terms (Jacobian elements) in the model equations that fall in absolute value around 1, e.g. from 0.01 to 100 both at the starting values and at the optimal solution.
Constants in the model equations that exhibit absolute values around 1, e.g. from 0.01 to 100.
This generally implies that user defined scaling should be employed as discussed in the Scaling GAMS Models chapter. Note some of the solvers have internal scaling procedures, but in general users can do a better job. Scaling factors involve a model level specification of the scaleopt model attribute and an individual variable-by-variable and equation-by-equation specification of the scaling factors.
Degenerate cycling blocking
Most of the commercial linear programming solvers have provisions within them to temporarily place small numbers on the right hand sides of problems if during a solution process they sense that degenerate cycling is occurring. In general, nonlinear programming solvers do not have such an internal feature. Sometimes nonlinear programming solution success and solver performance can be enhanced by making model formulation additions along those lines.
In particular, if users find that the nonlinear programming solution process exhibits a large number of iterations where the solver does not make significant progress in altering the objective function value, then some action may be in order. I have had success with speeding up the nonlinear solutions by altering the zero right hand sides in problems. In particular, sometimes I add a relatively small number to the right hand side of the equation so that instead of
f(x) <= 0
we have
f(x) <= delta*0.001
where delta is set to one if we wish the additions and zero otherwise and the 0.001 is adjusted to the size needed for the constraint. Such an addition quite frequently reduces solution time by helping the solver avoid degenerate cycling and if done correctly really does not make a qualitative difference in resultant model solution. One can also set delta to zero after an optimal solution has been achieved and resolve to clean out the effects of the small numbers.
Notes:
The magnitudes of the numbers added to the right hand side depend on the model context.
The numbers should be chosen so they do not introduce significant distortions into the problem solution.
One also should not always utilize the same number but perhaps some systematically varying number or a random number.
Such actions make the constraints easier to satisfy and helps avoid degenerate cycling.
I not only use this on problems with right hand sides of zero, but also on problems which have a lot of common and equal non zero right hand sides where I will add a small number to the right hand sides.
Advanced bases
In nonlinear models advanced bases are often helpful but there are cases where they do not contribute to shortened solution time. There are no general rules. Only experience with a problem will show how the effectiveness of the provision of an advanced basis. Nonlinear programming is the place where I've had largest gains in terms of solution time reduction with things being reduced from day to hours. Formation and usage of advanced bases are discussed in the ...
aivliska