Lindo Systems

!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, 
   Non-convex 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 hydro-electric 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+j-1 #EQ# k defines a set of points on
     a diagonal line;
    @FOR( DSET(k): WD(k) = @SUM(BOTH(i,j)| i+j-1 #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 non-zero and they are adjacent,
   only two WY are non-zero and they are adjacent,
   only two WD are non-zero and they are adjacent;