Modelling Guide

2013-02-15T22:46:11Z

Rhoro: /* Suggested Topics */

This section give tips and guidelines from the experts on how to model with Analytica.

* [[Managing Memory and CPU Time for large models]]

* [[Array Manipulation Examples and Challenge Problems]]

* [[Excel to Analytica Mappings|How to translate Excel spreadsheets into Analytica]]

* [[Debugging Hints]]

* [[Articles that refer to Analytica]]

* [[Writing Array-Abstractable Definitions]]

* [[Formulations that Preserve Linearity for Optimization]] -- for builders of Structured Optimization models

* Integrating with other software
** [[Integrating with Excel]]
** [[Integrating with R|Integrating with R: A Programming Environment for Data Analysis and Graphics]]

= [[:category:Concepts|Concepts]] =

*[[Array Abstraction]]
** [[Expressions that don't array-abstract]]
*[[Evaluation Modes]]
*[[Modules and Libraries]] : Organizing models, storing in separate files for collaboration or reuse.
*[[Expressing Uncertainty]] : Distributions, sampling methods, the Run index, etc.<br>
*[[Associative vs. Positional Indexing]]
*[[Self-Indexed Arrays]]
*[[Implicit Dimensions]] (aka Lists, null-indexed arrays, unnamed dimensions)
*[[User-Defined Functions]]
*[[Using References]]
*[[Modeling Changes over Time]]
*[[Parametric Analysis]]
*Optimization
**[[Linear and Quadratic Programming]]
**[[Non-linear Programming]]
*[[Scripting]] : Button scripts, typescript
*Special Values [[INF, NAN, Null, and Undefined]]
*[[Local Indexes]]
*[[Table Splicing]] - edit tables based on computed indexes
*[[OLE Linking]]
*[[Model building by mouse]] Enabling modelers to build models by copying nodes and drawing arrows
*[[Class|Analytica Object Classes]]
*[[Controlling When Result Are Cached]]
*[[Encoding Decision Trees]] as influence diagrams
*[[Proactive Evaluation]]
*Structured Optimization
**[[DefineOptimization]]
**[[Formulations that Preserve Linearity for Optimization]]
* [[Description_balloons#Customizing_Balloon_Content|Customizing Balloon Help]]
* [[CloudPlayerStyles_Attribute_Values|Customizing the model interface styles for Cloud Player presentation]]

= Mini-Tutorials =

Currently, the ones here are focused on features new to 4.0. But more will be coming. For more material along these lines, see the list of past Analytica User Group webinars at [[Analytica User Group]].

* Graphing
** [[Introduction to the Coordinate Index]]
*** [[Graphing a Probability Density]]
*** [[Making a Multi-D Scatter Plot]]
** [[Tornado Plots]]
** [[Gantt Charts]]
** [[Waterfall Charts]]
** [[Contour/Region Charts]]
** Substitutes for Tukey-style [[Box Plots]]

* Edit Tables
** [[Inserting Choice Controls in Edit Table Cells]]
** [[Introduction to SubTables]]

* Integration with External Programs and Data.
** [[Retrieving Content From the Web]]
** [[DbQuery/Step-by-Step_querying_Microsoft_Access|Querying an ODBC data source]]

= Suggested Topics =

Please list other areas for which you would like tips or guidelines, or add your own:

* Choosing the Sample Size

* Dynamic simulation

* Programs that do things with and to models

* How to make models transparent and easy to understand

* OLE links from individual Excel cells to non-table variables

Formulations that Preserve Linearity for Optimization

2013-02-14T22:46:40Z

Rhoro:

[[Category:Concepts]]
When creating an optimization model, there are advantages to formulating your model as a linear program (LP), avoiding non-linear relationships. Linear programs solve more robustly than non-linear programs, and usually solve faster than their non-linear counterparts even when there are mixed-integer decision variables.

Many problems that seem non-linear at the outset can be converted into a linear formulation with sufficient ingenuity, often by changing the set of decision variables used to represent the problem and its search space, and by introducing auxilliary integer and boolean variables and auxilliary constraints. In general, this transformation is not easy and requires substantial creativity and analytical skills.

This page is devoted to cataloging various cases that come up with solutions for how these can be encoded in a linear fashion.

== Piecewise linear relationships ==

Income tax is a function of taxable income, but in the US is determined according to a piecewise-linear specification (with the slope changing at different tax brackets). In other cases, a non-linear relationship between two scalar variables can be approximated by a piecewise linear curve, as in this example:

[[image:pwl_relationship.png]]

Structured optimization in Analytica processes piecewise-linear relationships automatically for you when these appear within your model through the use of the [[LinearInterp]] function. A PWL curve is specified by a set of points, ''(d,r)'', containing the break points in the curve. In Analytica, these would be arrays ''d'' and ''r'' sharing a common index ''i''. The result, ''y'' is then computed as <code>[[LinearInterp]](d,r,x,i)</code>. To be linear, the arrays ''d'' and ''r'' cannot depend on decision variables of the optimization.

Calls to [[LinearInterp]] can appear anywhere in your model. [[DefineOptimization]] processes these automatically and adds several binary and continuous auxilliary variables to the underlying optimization problem while preserving linearity.

== Semi-continuous Domains ==

A certain power plant can either be ''off'', or its power output is bounded 100MW and 500MW.

Decision PowerPlantOutput
Domain: [[Continuous]](100M,500M,orZero:true)

== Static Conditional Constraints ==

A constraint with one or more intrinsic indexes specifies an array of scalar constraints. Conditions arise where only a subset of that array should be enforced. When the condition that defines which elements of the array should be enforced does not depend on any decision variables, then we say the conditional is ''static'' - it will remain the same through the optimization search.

Let's assume the constraint with intrinsic indexes ''I'' and ''J'' is of the form:
:<code>F(x,y)<=0</code> only when ''B'' is true
where ''F(x,y)'' and ''B'' are array-valued, but ''B'' does not depend on decision variables.

To accomplish this, you can force the non-active constraints to be vacuous, or you can cause their constaint part to be [[Null]], or you can transform the constraint to include only the active components. Each will be demonstrated here.

* Make the constraint vacuous when ''B'' is false

:<code>F(x,y) <= ([[If]] B [[Then]] 0 [[Else]] [[INF]]</code>

* Make the constant be [[Null]] when ''B'' is false

:<code>F(x,y) <= ([[If]] B [[Then]] 0 [[Else]] [[Null]])</code>

* Transform to include only the active constraints.

:Index K := 1..[[Sum]](B,I,J)
:Index L := ['I','J','F']

:<code>[[MdArrayToTable]]([[If]] B [[Then]] F(x,y) [[Else]] [[Null]],K,L)[L='F'] <= 0</code>

The transformation approach minimizes the number of scalar constraints in the LP formulation, so is essentially the most efficient of these.

== Varying Conditional Constraints ==

When a constraint should be enforced only under certain conditions, and those conditions vary with the value of decision variables, this is referred to as a ''varying conditional constraint''.

In psuedo-code (but not actual Analytica syntax), a varying conditional constraint is like:
:If B(x,y) Then ( F(x,y) <= 0 )

where ''B'' is a boolean 0,1 condition that is linear in the decision variables (usually involving boolean decision variables). We write B and F in function call notation to emphasize the dependence on decision variables.

In a non-linear formulation, this can be easily captured using a vacuous constraint method:
:F(x,y) <= [[If]] B(x,y) [[Then]] 0 else [[INF]]

This formulation, however, is not linear. A solution is to write

:F(x,y) <= (1-B(x,y)) * 10M

This formulation preserves linearity and works as long as it can be guaranteed that ''F(x,y)'' would never exceed 10M. (You would adjust the big number appropriately for your problem, of course). You cannot use [[INF]] as the big number since 0*[[INF]] is [[NAN]] (not 0). It is best to keep the big number as small as possible since this has an impact on the numeric stability of the solution process.

Using this technique, a varying conditional equality constraint must be broken into two inequality constraints.
:If B(x,y) Then (F(x,y) = 0)
is encoded with these two linear constraints:
:F(x,y) <= (1-B(x,y)) * 10M
:(B(x,y)-1) * 10M <= F(x,y)

== Leave "On" for a minimum number of periods ==

If a power plant is turned on, it must remain on for a minimum of the following three time periods (i.e., is on for at least 4 consecutive time periods). This can be encoded by introducing an auxilliary boolean variable, ''PlantCommit'', when is true when we are committed to at least 3 more periods of being on.

:Decision PlantOn
:Domain: [[Boolean]]()
:Intrinsic Index: Time

:Decision PlantCommit
:Domain: [[Boolean]]()
:Intrinsic Index:Time

:Index Steps := 0..3

:Constraint: Stay_on_for_3
:Intrinsic Index: Time
:Definition: sum(PlantOn[@Time=@Time+Steps],Steps) >= 4*PlantCommit

:Constraint On_During_Commit
:Intrinsic Index:Time
:Definition: PlantCommit <= PlantOn

== Penalty for a change from a nominal value ==

You want to incur a penalty if the decision variable differs from some nominal value. For example, if you were to rebalance your portfolio, you would incur a sales commission.

:Index Holding

:Decision Allocation
:Domain: [[Continuous]](0,max_allocation)
:Intrinsic: Holding

:Variable CurAllocation
:Definition: Table(Holding)

:Decision Change
:Domain: [[Boolean]]()
:Intrinsic: Holding

:Constant Penalty_for_change := 10

:Variable Penalty
:Definition: Sum( Penalty_for_change * Change, Holding )

:Constraint Enforce_change
:Definition: -Max_allocation * Change <= Allocation-CurAllocation <= Max_allocation * Change
:Intrinsic: Holding

To see this idea encoded (in a car-dealer context), see the following example model:
[[media:Penalize_Change_in_LP.ana|Penalize_Change_in_LP.ana]]

== Mixed Complementarity, #1 ==

A simple form of mixed complementarity is the following:
::<math>x=0 \mbox{ and } 0<=F(x)\mbox{, or } 0<=x \mbox{ and } F(x)=0</math>

Geometrically, on a plot where x is on the horizontal, and the constraint is the vertical axis, this mixed complementarity constraint specifies that the solution must lie on either the positive x axis or on the positive y axis.

The above is equivalent to the following non-linear formulation:
::<math>x>=0, F(x)>=0 \mbox{ and } x\cdot F(x)=0</math>

This representation of complementarity cannot be captured exactly in a linear form (with F(x) being linear) using the mixed-integer mechanisms in Structured Optimization, but an approximation to it can be, where the approximation is:
::<math>0<=x<=U, 0<=F(x)<=U\mbox{, and } x\cdot F(x)=0</math>
or equivalently:
::<math>x=0 \mbox{ and } 0<=F(x)<=U\mbox{, or } 0<=x<=U \mbox{ and } F(x)=0</math>

In other words, we've artificially imposed an upper bound. If the constant U is made very large, then the approximation approaches the desired formulation (but for numeric stability, it is preferable to keep U as small as reasonable).

The formulation is captured with linear constraints by introducing an auxilliary boolean variable, '''''b''''':
<code>
:0 <= x <= (1-b) * U
:0 <= F(x) <= b * U
</code>

== Mixed Complementarity, #3 ==

Another general form of mixed complementarity is where one of the following must hold:
::<math>\begin{array}{ccc}
L=x & \mbox{and} & F(x)<=0 \\
L<=x<=U & \mbox{and} & F(x)=0 \\
x=U & \mbox{and} & F(x)>=0
\end{array}
</math>

Again, an approximation must be employed which adds an artificial constraint:
::<math>-K <= F(x) <= K</math>
where <math>K</math> is sufficiently large constant. With the addition of the artificial constraint, the MCP is encoded by introducing three boolean variables, <code>b1, b2,</code> and </code>b3<code>, and encoding as
<code>
:b1+b2+b3=1
:L+(U-L)*b3 <= x <= U-(U-L)*b1
:-K+K*b2 <= F(x) <= K-K*b2
</code>

= Please Contribute =

If you encounter cases like these that may be of general interest, then please add them here along with the method you found for expressing them in a linear fashion.

= See Also =

* [[DefineOptimization]]

Talk:Modeling Depreciation

2013-02-14T22:32:51Z

Rhoro: How does the Dynamic version of this work?

Can we have some explanation of how exactly the Dynamic version works? It has important advantages to it, in that it can handle the correct amortization of multiple additions to the balance, but the definition logic is quite opaque and does not lend itself to self-documentation.

Analytica Docs - User contributions [en]

Modelling Guide

Formulations that Preserve Linearity for Optimization

Talk:Modeling Depreciation