Lindo Systems

! 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;