Lindo Systems
MODEL:
! Enumerate the extreme points (EnumrXtrmB.lng)
of a linearly constrained region using K-Best feature of LINGO.
Assumptions:
Objective is MIN,
Constraints are already in equality form,
! Note, the number of extreme points can be large, of the order of
n!/(m!*(n-m)!), where
n= number of variables, and m= number of constraints;
! Keywords: Alternative optima, Corner point, Enumeration, Extreme point, K-Best solutions;
CALC:
! Number of desired extreme points.;
N = 3;
! Enable LINGO's K-Best solver to find the N extreme points.;
@SET( 'KBESTS', N);
ENDCALC
SETS:
ROW: RHS;
COL: OBJ, X, UBX, ZX;
RXC( ROW, COL): A;
ENDSETS
DATA:
! Case Xueyu;
! It has two alternative optima;
! Names of rows;
!CX; ROW = CON1 CON2 CON3 CON4;
!CX; RHS = -6 4 8 6;
!CX; COL =
X1 X2 SLK1 SLK2 SLK3 SLK4;
! Upper bounds;
!CX; UBX=
999 999 999 999 999 999 ;
!CX; OBJ =
-2 -1 0 0 0 0;
! Constraint coefficients;
!CX; A =
-3 -2 1 0 0 0
2 -1 0 1 0 0
2 1 0 0 1 0
-1 2 0 0 0 1
;
! Case 1: Variant of Astro-Cosmo problem.
! It has two alternative optima;
! Max = 15 A + 30 C
A <= 60,
C <= 50,
A + 2 C <= 120,
The last three variables in the tableau,
cols 3-5, are the slack variables;
! ROW = ALIM CLIM LABOR;
! RHS = 60 50 120;
! Names of columns;
! COL = A__ C__ S_1 S_2 S_3;
! OBJ = -15 -30 0 0 0;
! Upper bounds;
! UBX = 60 50 999 999 999;
! Names of rows;
! Matrix coefficients, including Obj and RHS;
! A =
1 0 1 0 0
0 1 0 1 0
1 2 0 0 1 ;
! Case 2: Variant of extended Astro-Cosmo problem.
! It has two alternative optima;
! Max = 15 A + 30 C + 44 D,
A + D <= 60,
C + D <= 50,
A + 2 C + 3 D <= 120,
! Names of rows;
! ROW = ALIM CLIM LABOR;
! RHS = 60 50 120;
! The last three variables in the tableau,
cols 4-6, are the slack variables;
! Names of columns;
! COL= A__ C__ D__ S_1 S_2 S_3 ;
! OBJ= -15 -30 -44 0 0 0 ;
! Upper bounds;
! UBX = 60 50 40 999 999 999;
! Constraint coefficients;
! A =
1 0 1 1 0 0
0 1 1 0 1 0
1 2 3 0 0 1
;
! Case 3: Example from Dyer and Proll, Math. Programming, vol. 12, 1977;
! It has 10 extreme points;
! ROW= ROW1 ROW2 ROW3 ROW4 ROW5;
! RHS= 5 16 3 17 10;
! COL= X1 X2 X3 X4 X5 X6 X7 X8 ;
! OBJ= 0 0 0 0 0 0 0 0;
! UBX= 99 99 99 99 99 99 99 99;
! Constraint coefficients;
! A = 3 2 -1 1 0 0 0 0
3 2 4 0 1 0 0 0
3 0 -4 0 0 1 0 0
2.25 4 3 0 0 0 1 0
1 2 1 0 0 0 0 1
;
! Case 4: Example from chapter 6 of Optimization Modeling with LINGO.
! It has two alternative optima;
!Find all extreme points with profit contribution >= 9800;
! Names of rows;
!C4 ROW= MACH CAP HOURS SHIP PROD1 PROD2 PROD3 PCTARG;
!C4 RHS= 35 35 36 600 218 114 111 9800;
!C4 COL =
B34 B38 B48 B58 B42 B52 SLK1 SLK2 SLK3 SLK4 SLK5 SLK6 SLK7 SLK8;
!C4 OBJ=
-15.89 -17.89 -16.5 -15.22 -17.5 -16.22 0 0 0 0 0 0 0 0;
! Upper bounds;
!C4 UBX=
999 999 999 999 999 999 999 999 999 999 999 999 999 999;
! Constraint coefficients;
!C4 A =
0.11111 0.11111 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0.16667 0 0.16667 0 0 1 0 0 0 0 0 0
0 0 0 0.22222 0 0.22222 0 0 1 0 0 0 0 0
1 1 1 1 1 1 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0 0 0 -1 0 0 0
0 1 1 1 0 0 0 0 0 0 0 -1 0 0
0 0 0 0 1 1 0 0 0 0 0 0 -1 0
15.89 17.89 16.5 15.22 17.5 16.22 0 0 0 0 0 0 0 -1
;
ENDDATA
MIN = OBV;
@FREE( OBV);
OBV = @sum( col( j) : OBJ( j)*X( j));
@FOR( ROW( i) :
@SUM( col( j) : A(i,j)*X( j)) = RHS(i);
);
! A basic feasible solution will have at most NCON
variables > 0, where NCON = number of constraints;
! Add binary variables to enforce this condition;
@FOR( COL( j):
X( j) <= UBX( j) * ZX( j);
@BIN( ZX( j));
);
! The number of constraints;
NCON = @SIZE( ROW);
! In an extreme point (basic) solution, the number of nonzero variables
is <= number of constraints;
@SUM( COL( j): ZX( j)) = NCON;
END