! LINGO model to represent or approximate (PieceLin2DL.lng)
a function of two variables
via piecewise linear interpolation,
using a triangular tesselation of the 2D space,
using a minimum number of binary variables, i.e.,
~ log( number of cells);
! Keywords: Piecewise Linear, Interpolation, Hydro Electric, Triangulation,
Non-convex Function, Linearization;
SETS:
HSET; ! The horizontal dimension;
VSET; ! The vertical dimension;
HXV( VSET, HSET): HV, VV, FV, WGT;
ENDSETS DATA:
HSET = 1..3;
VSET = 1..3;
! Matrix of Data points for head(pressure), volume
and power output(function value) for a hydro-electric generator;
HV, VV, FV =
195 1800 20 ! Row 1;
195 3500 52
195 5100 69
217 1900 26 ! Row 2;
217 3600 61
217 5200 80
240 2000 30 ! Row 3;
240 4100 78
240 5600 93
;
ENDDATA
! Approach: the two dimensional space is partitioned
via triangulation, i.e., partitioned into triangles.
Use linear interpolation within a cell.
Triangles are used, as opposed to say, quadrilaterals,
because a point within a triangle is uniquely determined
by weights on the three corner points. With quadrilaterals
there are alternate weightings that give the same x,y values,
but different function values.
! Parameters:
HV(i,j) = horizontal or X or Head value at data point i,j,
VV(i,j) = vertical or Y or flow volume value at data point i,j,
FV(i,j) = function value or power at data point i,j,
! Variables:
WGT(i,j) = weight given to data point i,j;
! The appropriate diagram with 3*3 = 9 points
and 2*2*2 = 8 triangle cells:
_______
| /|\ |
| / | \ |
i |/__|__\|
|\ | /|
| \ | / |
|__\|/__|
j
;
! YH = 1 if chosen cell is above middle horizontal line,
YV = 1 if chosen cell is right of middle vertical line,
YC = 1 if chosen cell is in center diamond.
else 0.
Observe that specifying values for all of YH, YV, YC
will imply a unique cell out of the 8 possible triangles;
! Weights must form a convex combination;
[CNVX] @SUM( HXV(i,j): WGT(i,j)) = 1;
! Compute associated horizontal or X value;
[COMPX] @SUM( HXV(i,j): HV(i,j)* WGT(i,j)) = HA;
! Compute associated vertical or Y value;
[COMPY] @SUM( HXV(i,j): VV(i,j)* WGT(i,j)) = VA;
! Compute associated function value;
[COMPFV] @SUM( HXV(i,j): FV(i,j)* WGT(i,j)) = FA;
! Choice must be binary, all or nothing;
@BIN(YH); @BIN(YV); @BIN(YC);
! Implications of setting YV;
WGT(1,3) + WGT(2,3) + WGT(3,3) <= YV;
WGT(1,1) + WGT(2,1) + WGT(3,1) <= 1-YV;
! Implications of setting YH;
WGT(3,1) + WGT(3,2) + WGT(3,3) <= YH;
WGT(1,1) + WGT(1,2) + WGT(1,3) <= 1-YH;
! Implications of setting YC;
WGT(2,2) <= YC;
WGT(1,1) + WGT(3,1) + WGT(1,3) + WGT(3,3) <= 1-YC;
! Define an arbitrary optimization problem to illustrate the method;
! An arbitrary tradeoff cost between head and volume;
[ARBOBJ] Min = VA + 15*HA;
! We need this much power;
[ARB1] FA >= 67;
! Arbitrarily put some constraints on Head;
[ARB2] HA <= 229;
[ARB3] HA >= 227;
|