Formulations that Preserve Linearity for Optimization
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 variabels.
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:
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.
This type of relationship can be encoded by introducing a few auxilliary variables and constraints as follows:
Decision PowerPlantOn Domain: Boolean() Decision: PowerPlantOutput Domain: Continuous(0,500M) Constraint PowerPlantOutput_Lb := 100M Constraint: Zero_When_Off Definition: PowerPlantOutput <= PowerPlantOn * DomainUpperBound(PowerPlantOutput) Constraint: Exceeds_LB_When_On Definition: PowerPlantOn * PowerPlantOutput_Lb <= PowerPlantOutput
You then must include PowerPlantOn and PowerPlantOutput as decision variables to DefineOptimization, and Zero_When_Off and Exceeds_LB_When_On as constraints.
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:
F(x,y)<=0
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
- Make the constant be Null when B is false
- Transform to include only the active constraints.
- Index K := 1..Sum(B,I,J)
- Index L := ['I','J','F']
MdArrayToTable(If B Then F(x,y) Else Null,K,L)[L='F'] <= 0
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:
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
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.
Enable comment auto-refresher