View source for Formulations that Preserve Linearity for Optimization

[[Category:Optimization]]

__TOC__

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 auxiliary integer and boolean variables and auxiliary 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 [[LinearInterp]](d, r, x, i).  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.  

:<code>Decision PowerPlantOutput</code>
:<code>Domain: Continuous(100M, 500M, orZero: true)</code>

== 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 <code>I</code> and <code>J</code> is of the form:
:<code>F(x, y)<=0</code>     only when <code>B</code> is true

where ''F(x, y)'' and ''B'' are array-valued, but <code>B</code> does not depend on decision variables.  

To accomplish this, you can force the non-active constraints to be vacuous, or you can cause their constraint 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 <code>B</code> is false

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

* Make the constant be [[Null]] when <code>B</code> is false

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

* Transform to include only the active constraints.

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

:<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:
:<code>If B(x, y) Then (F(x, y) <= 0)</code>

where <code>B</code> is a boolean 0,1 condition that is linear in the decision variables (usually involving boolean decision variables).  We write <code>B</code> and <code>F</code> 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:
:<code>F(x, y) <= If B(x, y) Then 0 else INF</code>

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

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

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.  
:<code>If B(x, y) Then (F(x, y) = 0)</code>

is encoded with these two linear constraints:
:<code>F(x, y) <= (1 - B(x, y))*10M</code>
:<code>(B(x, y) -1)*10M <= F(x, y)</code>

== 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 auxiliary boolean variable, <code>PlantCommit</code>, when is true when we are committed to at least 3 more periods of being on.  

:<code>Decision PlantOn</code>
:<code>Domain: Boolean()</code>
:<code>Intrinsic Index: Time</code>

:<code>Decision PlantCommit</code>
:<code>Domain: Boolean()</code>
:<code>Intrinsic Index:Time</code>

:<code>Index Steps := 0..3</code>

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

:<code>Constraint On_During_Commit</code>
:<code>Intrinsic Index: Time</code>
:<code>Definition: PlantCommit <= PlantOn</code>

== 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 re-balance your portfolio, you would incur a sales commission.

:<code>Index Holding</code>

:<code>Decision Allocation</code>
:<code>Domain: Continuous(0, max_allocation)</code>
:<code>Intrinsic: Holding</code>

:<code>Variable CurAllocation</code>
:<code>Definition: Table(Holding)</code>

:<code>Decision Change</code>
:<code>Domain: Boolean()</code>
:<code>Intrinsic: Holding</code>

:<code>Constant Penalty_for_change := 10</code>

:<code>Variable Penalty</code>
:<code>Definition: Sum(Penalty_for_change * Change, Holding)</code>

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

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

== 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 auxiliary boolean variable, <code>b</code>:

:<code>0 <= x <= (1 - b) * U</code>
:<code>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</code>
:<code>L + (U - L)*b3 <= x <= U - (U -  L)*b1</code>
:<code>-K  + K*b2 <= F(x) <= K - K*b2</code>

== B := Max(A,I) ==

When you have the relationship <code>B</code> is defined as <code>Max(A,I)</code> within your model, this can often be linearized by adding <code>B</code> as another decision variable in the LP, and then adding a new constraint:
:<code>A <= B</code>
and set the constraint's intrinsic index to be <code>I</code>.

This will work IF your objective creates an incentive for <code>B</code> to be as small as possible. In many models, this often is the case, since you are often minimizing a net cost, and more <code>B</code> would drive up costs. So if you are in this case, it is easy.

It should be clear that the same idea works for <code>B := Min(A,I)</code>, as long as the Objective incentivizes <code>B</code> to be as large as possible.

When you don't have this natural incentive in the right direction, you can add in a type of [[#Varying Conditional Constraints|varying conditional constraint]].  Introduce another boolean decision variable <code>Bi</code>, with intrinsic index <code>I</code>.  This will be set true in the solution for the position where the <code>Max(A,I)</code> found the max. Then add these two constraints (the first one replaces the constraint above):
:<code>A <= B <= A + (1-Bi)*10M</code>
and
:<code>Sum(Bi,I)=1</code>
where the constant <code>10M</code> needs to exceed the spread of values in <code>A</code>.

By adding <code>B</code> as a decision variable to your LP and adding the constraint(s), you've linearized the <code>Max(A,I)</code> expression for the optimizer when the LP is solved. You should leave the definition of <code>B</code> as <code>Max(A,I)</code>, so that when you evaluate your model outside of optimization, you still compute the Max. This also helps to document your logic in a natural way.

== 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]]
* [[LinearInterp]]