 ```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; ENDSETSDATA: ! 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 ```