Enhancements to Optimizer in Analytica 4.0

Revision as of 05:39, 4 January 2007 by Lchrisman (talk | contribs) (Slicing of the objective, lhs, etc., and the Over parameter)

(Back to What's new in Analytica 4.0?)

Selecting an external engine

The functions LpDefine, QpDefine, and NlpDefine now have an optional engine parameter, which can be used to specify an external add-on engine such as Knitro, Mosek, Xpress, etc. For example: 

NlpDefine( ... ; Engine : "KNITRO" )

would use the Knitro engine to solve the non-linear optimization problem. In order to use this feature, the Knitro engine must be properly installed and a license for it acquired. These configurations are described in Using a Solver Add-on Engine.

If the Engine parameter is not explicitly specifyed, LpDefine, QpDefine or NlpDefine will use the internal default solver engine that is deemed most appropriate for the problem. To determine which engine has been selected for a given problem previously defined, use: 

SolverInfo( "engine", lp )

New Functions

  • SolverInfo allows you to retrieve the components of a previously-defined LP/QP/NLP, or to obtain information about a solver engine. The function is described at SolverInfo.

Generalized Access to Solver Engine Parameters

Each solver engine in general has its own unique set of parameters that can be used to control its search. For example, the parameters used by Knitro only partially overlap the parameters used by the built-in evolutionary algorithm. To be able to take full advantage of Knitro, you need to be able to access all its parameters. If a third-party engine becomes available after Analytica 4.0 is released, it may have additional parameters.

The solver engine parameters have previously been exposed to the Analytica end-user as optional parameters to LpDefine, QpDefine and NlpDefine. Since these definitions are fixed, it doesn't provide a fully flexible mechanism for accessing and setting the solver parameters. For this reason, a new method for specifying solver control settings has been added to LpDefine, QpDefine and NlpDefine.

To change a single setting, you identify the parameter and its setting using optional parameters, e.g.: 

 NlpDefine( ..., parameter: "PopulationSize", setting: 50 )

Note: LpDefine, QpDefine and NlpDefine all provide optional parameter and setting arguments in the same fashion.

To set multiple settings, you must supply one or two arrays. There are two methods for doing this. The first is to specify one array for the parameter argument, another for the setting argument, such that the two arrays have the same dimensionality. For example: 

 Index SettingNum := [1,2,3];
 Variable ParamArr := Table(SettingNum)("MultiStart","TopoSearch","PopulationSize")
 Variable SettingArr := Table(SettingNum)(1,1,10)
 Variable The_Nlp := NlpDefine( ..., parameter: ParamArr, setting: SettingArr )

With this usage, ParamArr may have any number of indexes in common, they need not be one-dimensional. All settings (at any coordinate) are used. A special case of this places the parameter names in the index: 

 Index ParamNames := ["MultiStart","TopoSearch","PopulationSize"]
 Variable SettingArr := Table(ParamNames)(1,1,10)
 Variable The_Nlp := NlpDefine( ..., parameter: ParamNames, setting: SettingArr )

This arrangement does not work if ParamNames is a self-indexed table (or any other self-indexed array) where the parameter names reside in the self-index values. This is because the parameter value, not index value, is passed in.

When the setting parameter is guaranteed to be 1-dimensional, and the parameter names are in the index labels, the parameters argument can be omitted entirely. In the above example, The_Nlp could equally be defined using 

NlpDefine( ..., setting: SettingArr )

The one caveat with this is that an error will result if SettingArr is not exactly one-dimensional after array abstraction. If the SettingArr contains any indexes that are iterated over by array abstraction (because of other parameters), those dimensions will be sliced from SettingArr. Therefore, a two or three dimensional SettingArr can be provided, as long as multiple instances of optimization problems are being defined via array abstraction. It is best to ensure that your ParamNames dimension does not appear as a dimension of other parameters, otherwise it would also be abstracted over and you'd end up with a zero-dimensional array after array abstraction (hence an error).

Often the most convenient method for specifying search parameters is to set up a self-indexed table, where the index labels are the parameter names and the cell values are the settings. This is an instance of the previous technique, in which the settings parameter is specified, but the parameter argument is omitted. E.g.: 

IndexVals of Parms := ["MultiStart","TopoSearch","PopulationSize"]
Definition of Parms := Table(Self)(1,1,10)
Variable The_NLP := NlpDefine( ..., Setting:Parms )

Again, notice that the Parameter argument is not explicitly specified.

To view the current search control settings used in a particular LP, QP, or NLP, the function: 

 SolverInfo( "Setting", lp )

returns a 1-D array, in which a local index ".Parameter" contains the parameter name, and the array value contains the current setting. In general, the local index may contain a different set of parameters than those provided in the Parameter argument to LpDefine. There may be additional ones since in general only a subset will be specified explicitly, and if parameters that don't apply to the current engine appear in the Parameter argument to LpDefine, then those won't appear in the result from SolverInfo.

To access the default parameter settings for a given solver engine, use: 

 SolverInfo( Engine: engname, Item: "Setting" )

The largest and smallest allowable values for each setting can also be obtained using: 

 SolverInfo( Engine: engname, Item: ["Setting","Min Setting","Max Setting"] )

Descriptions of what parameter settings do is found in the Frontline Premium Solver for Excel manual.

FindIIS

Two parameters have been added to Function FindIIS, which now has the declaration: 

FindIIS( lp : LP_TYPE ; newlp : optional boolean = false ; constraintsOnly : optional boolean )

where:

  • lp : an LP instance previously defined using LpDefine. FindIIS cannot be used with QPs or NLPs.
  • newlp: When true, a new LP instance is returned. When false, a subset of the constraints is returned.
  • constraintsOnly: When true, the lower and upper variable bounds are not relaxed.

FindIIS can now return a new LP instance, having fewer constraints or variable bounds so as to ensure the problem has a feasible solution. When an LP is returned, you access the modified variable bounds or constraint set using: 

SolverInfo( iis, "lb" )
SolverInfo( iis, "ub" )
SolverInfo( iis, "Constraints" )

When newlp is false, the constraintsOnly is implied to be true, and the function returns a subset of the Constraints index. FindIIS(lp,false) is equivalent to: 

SolverInfo( FindIIS(lp,true,true), "Constraints" )

The previous version of FindIIS returned only a subset of the Constraints index, which provided no method in which reduced variable bounds could be returned. Therefore, the previous version did not relax variable bounds.

When newlp is true, constraintsOnly defaults to false. Note: FindIIS(lp,true) should always be able to find a feasible problem, while Find(lp,false) does not have this guarantee (i.e., when the variable bounds are not consistent).

Multiple File Formats

LpWrite, LpRead, and LpWriteIIS now all contain an optional format parameter, and can read/write to three different file formats: 

LpWrite( lp : LP_Type, filename : text ; format : optional text = "LP" )
LpWriteIIS( lp : Lp_type, filename : text ; format : optional text = "LP" )
LpRead( filename : text ; Vars,Constraint : optional IndexType ; format : optional text = "LP" )

Possible file formats are: "LP", "MPS", and "LPFML".

Quadratic Constraints

Previously, a QP could have a quadratic objective function, but constraints had to be linear. QpDefine now permits quadratic constraints. The built-in SOCP engine in Frontline 7.0 can handle quadratic constraints, and the external MOSEK engine add-on can handle these at an improved performance level.

To define quadratic constraints, the quadratic component is specified in the lhsQ parameter, indexed by Vars, Vars2 and Constraints. The linear part of the constraint is defined in the lhs parameter (as before) indexed by Vars and Constraints. For example, consider the following problem: 

Minimize   x^2 + y^2 - 2*x
Subject to:
  x^2 + 4*x*y + 6*y <= 36
  y^2 + 4*x - 2*y <= 0
where
  x >= 0, y >= 0

The optimum for this problem is at x=.1286, y=0.3031, objective=-0.1488.

We define indexes as follows: 

Index Vars := ['x','y']
Index Vars2 := CopyIndex(Vars)
Index Constraints := ['c1','c2']

The objective is given by: 

Variable c := Table(Vars)(-2,0)
Variable Q :=
Vars
Vars2 x y
x 1 0
y 0 1

The left-hand side is given by:

Variable Lhs :=
Vars
Constraints x y
c1 0 6
c2 4 -2
Variable LhsQ :=
Constraints
c1 c2
Vars Vars
Vars2 x y x y
x 1 4 0 0
y 4 0 0 1 
Variable Rhs := Table(Constraints)(36,0)

The problem is then formulated as: 

QpDefine( Vars, Vars2, Constraints, c:c, q:Q, lhs:Lhs, rhs:Rhs, sense:'<', lb:0, maximize:false )

Grouped Integer Variables

The optimizer now supports a new type of integer constraint -- group exclusive.

A group of N integer variables assigns an integer 1..N to each of the N variables such that they are constrained to have unique values. For example, if a group contains {x1, x2, x3}, then x1=1, x2=2, x3=3 is acceptible, as is x1=3, x2=1, x3=2. But x1=2, x2=3, x3=2 is not acceptible, since the values are not unique.

There can be multiple groups. For example, consider this set of constraints: 

Group 1: {x1,x2,x3}
Group 2: {x4,x5}
Constraints:
   x1 - x4 = 0
   x3 - x5 = 0
   x1 + 2*x5 = 4

This system has a single feasible solution: {x1=2, x2=3, x3=1, x4=2, x5=1}.

To specify that a variable belongs to a group, its ctype is set to 'G'. If there is more than one group, then the parameter 

 group : optional numeric[Vars]

must be specified to LpDefine, QpDefine, NlpDefine. For example: 

Variable VarGroups := Table(Vars)(1,1,1,2,2)
Variable ub := Table(Vars)(3,3,3,2,2)
Variable lp := LpDefine( Vars, ..., ctype: 'G', group: VarGroups, lb:1, ub:ub )

The constraints are specified the usual fashion and thus are omitted in the above for conciseness. Here we have two variable groups, numbered 1 and 2, with membership of each variable in each group specified by the group parameter.

Trace Files for NLP optimization

When a non-linear optimization performs poorly, it is often necessary to look at the path the search took to diagnose the reasons. To make this easier, Ana:NlpDefine has a new parameter, TraceFile. Tracefile accepts a filename (full path or relative to Ana:CurrentDataDirectory). When specified, Analytica records the independent decision vector and each explicitly computed item at each search step (e.g., objective, LHS, gradient, jacobian, objHessian, lhsHessian).

After an optimization has been run, the tab-separated file can be viewed in a text editor.

Increased Array Abstraction in NLPs

Suppose you have an objective, obj = f(x,b), where x is your decision vector and b is another parameter. Nominally, f(x,b) evaluates to a scalar -- which gives the optimization search one objective to minimize.

However, suppose another dimension is added to b, which might happen in a what-if analysis for example. Now objective is an array, which means we effectively have multiple simultaneous optimization problems. However, this abstraction is not automatically covered by array abstraction. Getting a large model of f(x,b) to array abstract in such a case can be quite difficult, and can require major restructuring and loss of transparency.

A new feature in NlpDefine makes it a little easier to cope with this problem. Analytica will slice the computed objective based on the array abstraction context (the same holds for other computed functions, like lhs, gradient, jacobian). You can also explicitly specify array-abstraction dimensions using an Over parameter (so you'll get a separate NLP instance for each case).

With the knowledge that b contains the extra problematic dimensions, we add include an Over parameter to NlpDefine, e.g. 

NlpDefine( ..., Over: b )

Now if the dimensions of b appears in the computed objective, lhs, gradient or jacobian, only the slice corresponding to the current NLP instance will be used.

If the spurious dimensions appear in other parameters, the over parameter is not necessary. For example, the dimensions of b appears as spurious dimensions in lhs, but also appear in rhs (which is fully evaluated at problem definition), then Analytica will automatically take only the lhs slice corresponding to the current context.

Although this feature provides a way to manually get over some abstractions issues, the feature itself is quite weak since there is a lot of computation that gets "thrown away". Future enhancements should address that as well.

Comments


You are not allowed to post comments.