!LINGO model to represent or approximate (PieceLin2Dsos3)
a function of two variables, f(x,y), by
piecewise linear interpolation,
using a triangular tesselation of the 2D space,
using three SOS2 sets;
! Keywords: Piecewise linear, SOS2, Two dimensional,
Triangulation, Hydro Electric, Interpolation,
Nonconvex function;
SETS:
XSET: WX; ! The x dimension;
YSET: WY; ! The y dimension;
DSET: WD; ! The diagonal, x+y = k, dimension;
BOTH( YSET, XSET): XV, YV, FV, WGT;
ENDSETS DATA:
XSET = 1..3;
YSET = 1..3;
DSET = 1..5; ! A 3x3 grid has 5 diagonal lines;
! There are 8 triangles.;
! Graphically:
\ \ \

\ \ \
 \  \ 
\ \ \

\ \ \
 \  \ 
\ \ \

\ \ \;
! The function is linear over each triangle;
! Matrix of Data points for head(pressure), X, volume, Y,
and power output(function value) for a hydroelectric generator;
XV, YV, FV =
195 1800 20 ! 1,1;
217 1900 26 ! 1,2;
240 2000 30 ! 1,3;
195 3500 52 ! 2,1;
217 3600 61 ! 2,2;
240 4100 78 ! 2,3;
195 5100 69 ! 3,1;
217 5200 80 ! 3,2;
240 5600 93; ! 3,3;
ENDDATA
! Weights must form a convex combination;
! Weights on X values;
@SUM( XSET(k): WX(k)) = 1;
! Weights on Y values;
@SUM( YSET(k): WY(k)) = 1;
! Weights on diagonal lines;
@SUM( DSET(k): WD(k)) = 1;
! Declare the grid weights to be SOS2 sets, i.e., at most
2 can be > 0 and they must be adjacent;
@FOR( XSET(k): @SOS2( 'SX2', WX(k)));
@FOR( YSET(k): @SOS2( 'SY2', WY(k)));
@FOR( DSET(k): @SOS2( 'SD2', WD(k)));
! Tie the grid/line weights to the point weights;
@FOR( XSET(k): WX(k) = @SUM(YSET(j):WGT(j,k)));
@FOR( YSET(k): WY(k) = @SUM(XSET(i):WGT(k,i)));
! Notice that i+j1 #EQ# k defines a set of points on
a diagonal line;
@FOR( DSET(k): WD(k) = @SUM(BOTH(i,j) i+j1 #EQ# k:WGT(i,j)));
! A triangle is uniquely specified by choosing
2 adjacent vertical lines, 2 adjacent horizontal lines,
and 2 adjacent diagonal lines;
! Compute associated horizontal or X value;
[COMPX] @SUM( BOTH(i,j): XV(i,j)* WGT(i,j)) = XA;
! Compute associated vertical or Y value;
[COMPY] @SUM( BOTH(i,j): YV(i,j)* WGT(i,j)) = YA;
! Compute associated function value;
[COMPFV] @SUM( BOTH(i,j): FV(i,j)* WGT(i,j)) = FA;
! Define an arbitrary optimization problem to illustrate the method;
! An arbitrary tradeoff cost between head and volume;
[ARBOBJ] Min = YA + 15*XA;
! We need this much power;
[ARB1] FA >= 67;
! Arbitrarily put some constraints on Head;
[ARB2] XA <= 229;
[ARB3] XA >= 227;
! In the solution, notice that
only two WX are nonzero and they are adjacent,
only two WY are nonzero and they are adjacent,
only two WD are nonzero and they are adjacent;
