DIRECTORY Convert, IO, LinearSolver, Real, Rope, ViewerIO;

LinearSolverImpl: CEDAR PROGRAM
IMPORTS Convert, IO, Rope, ViewerIO
EXPORTS LinearSolver = BEGIN
OPEN LinearSolver;


doesntOwnARow: INT ~ -1;
doesntOwnACol: INT ~ -1;


signalUnsatisfiable: BOOL _ TRUE;
Unsatisfiable: ERROR = CODE;
C: PUBLIC PROCEDURE [x: LinearMonomial] RETURNS [r: REF] = {
r _ NEW[LinearMonomial _ x];
};
AssertZero: PUBLIC PROCEDURE [t: Tableau, c: Constraint, propEQ: PropEQProc _ NIL] = {
IF NOT t.satisfiable THEN ERROR;
{v: Unknown _ NewRowUnknown[t]; 
IF debug THEN Debug[t, IO.PutFR["AssertZero c = %g", IO.refAny[c]]];
WHILE c # NIL DO 
g: REF LinearMonomial _ NARROW[c.first];
AddToRow[t, t.n-1, g.coefficient, g.unknown]; 
c _ c.rest 
ENDLOOP; 
KillRowVar[t, v, propEQ] }
};
AssertZero2: PUBLIC PROCEDURE [t: Tableau, c1: REAL, v1: Unknown, c2: REAL, v2: Unknown, propEQ: PropEQProc _ NIL] = { 
v: Unknown _ NewRowUnknown[t]; 
IF debug THEN Debug[t, IO.PutFR["AssertZero2 c = %g", IO.refAny[ LIST[C[[c1, v1]], C[[c2, v2]]]]]];
AddToRow[t, t.n-1, c1, v1]; 
AddToRow[t, t.n-1, c2, v2]; 
KillRowVar[t, v, propEQ] 
};
AssertZero3: PUBLIC PROCEDURE [t: Tableau, c1: REAL, v1: Unknown, c2: REAL, v2: Unknown, c3: REAL, v3: Unknown, propEQ: PropEQProc _ NIL] = { 
v: Unknown _ NewRowUnknown[t]; 
IF debug THEN Debug[t, IO.PutFR["AssertZero3 c = %g", IO.refAny[ LIST[C[[c1, v1]], C[[c2, v2]], C[[c3, v3]]]]]];
AddToRow[t, t.n-1, c1, v1]; 
AddToRow[t, t.n-1, c2, v2]; 
AddToRow[t, t.n-1, c3, v3]; 
KillRowVar[t, v, propEQ] 
};
AssertGEZero: PUBLIC PROCEDURE [t: Tableau, c: Constraint, propEQ: PropEQProc _ NIL] = {
IF NOT t.satisfiable THEN ERROR;
{v: Unknown _ NewRowUnknown[t]; 
slack: Unknown _ NewUnknown[t, c]; 
IF debug THEN Debug[t, IO.PutFR["AssertGEZero c = %g", IO.refAny[c]]];
Restrict[t, slack];
WHILE c # NIL DO 
g: REF LinearMonomial _ NARROW[c.first];
AddToRow[t, t.n-1, g.coefficient, g.unknown]; 
c _ c.rest 
ENDLOOP; 
AddToRow[t, t.n-1, -1.0, slack];
KillRowVar[t, v, propEQ] }
};
AssertGEZero2: PUBLIC PROCEDURE [t: Tableau, c1: REAL, v1: Unknown, c2: REAL, v2: Unknown, propEQ: PropEQProc _ NIL] = { 
v: Unknown _ NewRowUnknown[t]; 
slack: Unknown _ NewUnknown[t, InventName[t, "slack"]]; 
IF debug THEN Debug[t, IO.PutFR["AssertGEZero2 c = %g", IO.refAny[ LIST[C[[c1, v1]], C[[c2, v2]]]]]];
Restrict[t, slack];
AddToRow[t, t.n-1, c1, v1]; 
AddToRow[t, t.n-1, c2, v2]; 
AddToRow[t, t.n-1, -1.0, slack];
KillRowVar[t, v, propEQ] ;
};
AssertGEZero3: PUBLIC PROCEDURE [t: Tableau, c1: REAL, v1: Unknown, c2: REAL, v2: Unknown, c3: REAL, v3: Unknown, propEQ: PropEQProc _ NIL] = { 
v: Unknown _ NewRowUnknown[t]; 
slack: Unknown _ NewUnknown[t, InventName[t, "slack"]]; 
IF debug THEN Debug[t, IO.PutFR["AssertGEZero3 c = %g", IO.refAny[ LIST[C[[c1, v1]], C[[c2, v2]], C[[c3, v3]]]]]];
Restrict[t, slack];
AddToRow[t, t.n-1, c1, v1]; 
AddToRow[t, t.n-1, c2, v2]; 
AddToRow[t, t.n-1, c3, v3]; 
AddToRow[t, t.n-1, -1.0, slack];
KillRowVar[t, v, propEQ] 
};
NewUnknown: PUBLIC PROCEDURE [t: Tableau, name: REF] RETURNS [Unknown] = {
v: Unknown _ NEW[UnknownRec];
IF debug THEN Debug[t, IO.PutFR["NewUnknown %g", IO.refAny[name]]];
v.name _ name;
v.i _ doesntOwnARow; 
v.j _ t.m; 
FOR i: INT IN [0 .. t.n) DO t.a[i][t.m] _ 0 ENDLOOP; 
t.x[t.m] _ v; 
t.m _ t.m + 1;
t.maxM _ MAX[t.m, t.maxM];
RETURN [v] 
}; 
NewRowUnknown: PROCEDURE [t: Tableau] RETURNS [v: Unknown] = {
v _ NEW[UnknownRec];
v.name _ InventName[t, "rVar"];
v.i _ t.n;
v.j _ doesntOwnACol;
FOR j: INT IN [0 .. t.m) DO t.a[t.n][j] _ 0 ENDLOOP;
t.y[t.n] _ v;
t.n _ t.n + 1;
t.maxN _ MAX[t.n, t.maxN];
RETURN[v];
};
AddToRow: PROCEDURE [t: Tableau, n: Row, c: REAL, v: Unknown] = {
SELECT TRUE FROM
v.j # doesntOwnACol => t.a[n][v.j] _ t.a[n][v.j] + c;
v.i # doesntOwnARow =>
FOR j: INT IN [0 .. t.m) DO t.a[n][j] _ t.a[n][j] + t.a[v.i][j] * c ENDLOOP;
ENDCASE => ERROR -- Client called AssertZero[f] where f contains an inactive variable
};
  
Satisfiable: PUBLIC PROCEDURE [t: Tableau] RETURNS [BOOL] = {RETURN [t.satisfiable]};
Solution: PUBLIC PROCEDURE [t: Tableau, v: Unknown] RETURNS [REAL] =
  BEGIN
    SELECT TRUE FROM
      v = t.unity => RETURN[1];
      v.j # doesntOwnACol AND v # t.unity => RETURN[0];
      v.i # doesntOwnARow => RETURN[t.a[v.i][t.unity.j]]
    ENDCASE => ERROR
  END;
KillRowVar: PROCEDURE [t: Tableau, v: Unknown, propEQ: PropEQProc _ NIL] =
{u, champion: Unknown;
pec: PivotEffectCode;
IF debug THEN Debug[t, IO.PutFR["Kill row variable %g", IO.refAny[v.name]]];
IF ABS[t.a[v.i][t.unity.j]] < 0.0001 THEN {
allZeros: BOOLEAN _ TRUE;
FOR j: INT IN [0 .. t.m) DO
allZeros _ allZeros AND ABS[t.a[v.i][j]] < 0.0001;
ENDLOOP;
IF allZeros THEN {
t.n _ t.n-1; v_ NIL;
RETURN;
};
};
IF t.a[v.i][t.unity.j] > 0 THEN
FOR j: INT IN [0 .. t.m) DO t.a[v.i][j] _ - t.a[v.i][j] ENDLOOP;
-- Asserting -v = 0 is the same as asserting v = 0.
-- Now the sample value of v is non-positive.  Thus maximizing v will
-- move it towards zero.
[u, champion, pec] _ MaximalPivot[t, v];
SELECT TRUE FROM
pec = ToPivotAtUWouldMakeVPositive OR
pec = VIsManifestlyUnbounded =>  
{Pivot[t, champion.i, u.j]; KillColVar[t, champion, propEQ]; CheckRowEqualities[t, propEQ]};
pec = VIsMaximizedAtZero OR
pec = VIsManifestlyMaximized =>
{KillAllCols[t, v, propEQ]; CheckRowEqualities[t, propEQ]};
pec = VIsMaximizedAndNegative =>
IF signalUnsatisfiable THEN ERROR Unsatisfiable ELSE t.satisfiable _ FALSE;
ENDCASE => ERROR;
};
CheckRowEqualities: PROCEDURE [t: Tableau, propEQ: PropEQProc] = {
};
KillColVar: PROCEDURE [t: Tableau, v: Unknown, propEQ: PropEQProc _ NIL] = {
IF debug THEN Debug[t, IO.PutFR["Kill column %g", IO.refAny[v.name]]];
t.m _ t.m - 1;
IF v.j # t.m 
THEN {FOR i: INT IN [0 .. t.n) DO t.a[i][v.j] _ t.a[i][t.m] ENDLOOP; t.x[v.j] _ t.x[t.m]; t.x[t.m].j _ v.j}};

KillAllCols: PROCEDURE [t: Tableau, v:Unknown, propEQ: PropEQProc _ NIL] = {
IF debug THEN Debug[t, IO.PutFR["Kill all columns for %g", IO.refAny[v.name]]];
FOR j: INT IN [0..t.m) DO
IF j # t.unity.j AND t.a[v.i][j] # 0 THEN KillColVar[t, t.x[j], propEQ] ENDLOOP;
};
PivotEffectCode: TYPE = {
ToPivotAtUWouldMakeVPositive,
VIsMaximizedAtZero,
VIsMaximizedAndNegative,
   ToPivotAtUWouldIncreaseVButNotMakeItPositive,
VIsManifestlyUnbounded,
VIsManifestlyMaximized };

MaximalPivot: PROCEDURE [t: Tableau, v: Unknown] RETURNS [u, champion: Unknown _ NIL, pec: PivotEffectCode] = {
[u, champion, pec] _ FindPivot[t, v];
WHILE pec = ToPivotAtUWouldIncreaseVButNotMakeItPositive DO
Pivot[t, champion.i, u.j];
[u, champion, pec] _ FindPivot[t, v];
ENDLOOP;
};

FindPivot: PROCEDURE [t: Tableau, v: Unknown] RETURNS [u, champion: Unknown _ NIL, pec: PivotEffectCode] = {
SGN: PROCEDURE [x: REAL] RETURNS [REAL] = INLINE {
RETURN [IF x < 0 THEN -1.0 ELSE +1.0]
};
j: INT _ doesntOwnACol;
sgn: REAL;
FOR jj: INT IN [0 .. t.m) 
DO IF jj # t.unity.j
THEN IF (t.a[v.i][jj] # 0 AND NOT t.x[jj].restricted) OR t.a[v.i][jj] > 0
THEN {j _ jj; sgn _ SGN[t.a[v.i][jj]]}
ENDLOOP;   
IF j = doesntOwnACol THEN 
SELECT TRUE FROM
t.a[v.i][t.unity.j] < 0 => {pec _ VIsMaximizedAndNegative; RETURN};
t.a[v.i][t.unity.j] = 0 => {pec _ VIsMaximizedAtZero; RETURN};
t.a[v.i][t.unity.j] > 0 => {pec _ VIsManifestlyMaximized; RETURN};
ENDCASE => ERROR;
u _ t.x[j]; -- we will pivot in column j
{champ: INT;
score: REAL;
champ _ v.i;
score _ Real.LargestNumber;
FOR ii: INT IN [0..t.n) 
DO IF ii # v.i AND t.y[ii].restricted AND sgn * t.a[ii][j] < 0
THEN IF ABS[t.a[ii][t.unity.j] / t.a[ii][j]] < score
THEN {champ _ ii; score _ ABS[t.a[ii][t.unity.j] / t.a[ii][j]]}
ENDLOOP;
champion _ t.y[champ];
IF champ = v.i THEN {pec _ VIsManifestlyUnbounded; RETURN};
{newSampleValueOfV: REAL = t.a[champ][t.unity.j] - t.a[v.i][t.unity.j] * t.a[champ][u.j] / t.a[v.i][u.j];
SELECT TRUE FROM
newSampleValueOfV <= 0 => pec _ ToPivotAtUWouldIncreaseVButNotMakeItPositive;
newSampleValueOfV > 0  => pec _ ToPivotAtUWouldMakeVPositive
ENDCASE => ERROR}}};

Pivot: PROCEDURE [t: Tableau, k: Row, l: Col] = {
pp: REAL _ 1.0 / t.a[k][l]; -- compute reciprocal of pivot
IF debug THEN Debug[t, IO.PutFR["Pivot row %g and column %g", IO.int[k], IO.int[l]]];
t.a[k][l] _ -1.0;  -- to compensate for dividing by minus the pivot
-- swap the row and column headers 
{z: Unknown _ t.y[k];t.y[k] _ t.x[l]; t.x[l] _ z;
t.y[k].i _ k; t.y[k].j _ doesntOwnACol; t.x[l].i _ doesntOwnARow; t.x[l].j _ l};  
FOR j: INT IN [0 .. t.m) DO t.a[k][j] _ - t.a[k][j] * pp ENDLOOP;
-- divide everything in the pivot row by minus the pivot
FOR i: INT IN [0 .. t.n) DO 
IF i # k THEN 
FOR j: INT IN [0 .. t.m) DO 
IF j # l THEN 
-- i.e., for each t.a[i,j] outside the pivot row and column:
t.a[i][j] _ t.a[i][j] + t.a[i][l] * t.a[k][j];
-- note that t.a[k, j] was already divided by minus the pivot
ENDLOOP
ENDLOOP;
-- Finally process pivot column:
FOR i: INT IN [0 .. t.n) DO IF i # k THEN t.a[i][l] _ t.a[i][l] * pp ENDLOOP
};

Restrict: PUBLIC PROCEDURE [t: Tableau, v: Unknown, propEQ: PropEQProc _ NIL] = {
IF debug THEN Debug[t, IO.PutFR["Restrict variable %g", IO.refAny[v.name]]];
IF v.restricted THEN RETURN;
MakeVOwnARow[t, v];
IF v.i = doesntOwnARow THEN {v.restricted _ TRUE; RETURN};
IF t.a[v.i][t.unity.j] < 0 THEN {v.restricted _ TRUE; RETURN};
{u, champion: Unknown;
pec: PivotEffectCode;
[u, champion, pec] _ MaximalPivot[t, v];
SELECT TRUE FROM
pec = ToPivotAtUWouldMakeVPositive => {v.restricted _ TRUE; Pivot[t, champion.i, u.j]};
pec = VIsMaximizedAtZero OR
pec = VIsManifestlyMaximized => {KillAllCols[t, champion, propEQ]};
pec = VIsMaximizedAndNegative => {IF signalUnsatisfiable THEN ERROR Unsatisfiable ELSE t.satisfiable _ FALSE};
pec = VIsManifestlyUnbounded => {v.restricted _ TRUE; Pivot[t, v.i, u.j]};
ENDCASE => ERROR}};
  
Maximize: PUBLIC PROCEDURE [t: Tableau, v: Unknown] RETURNS [unbounded: BOOLEAN _ FALSE] = {
u, champion: Unknown;
pec: PivotEffectCode;
IF debug THEN Debug[t, IO.PutFR["Maximize variable %g", IO.refAny[v.name]]];
MakeVOwnARow[t, v];
IF v.i = doesntOwnARow THEN RETURN[NOT v.restricted]; 
[u, champion, pec] _ FindPivot[t, v];
DO SELECT TRUE FROM
pec = ToPivotAtUWouldMakeVPositive OR
pec = ToPivotAtUWouldIncreaseVButNotMakeItPositive =>
{Pivot[t, champion.i, u.j]; [u, champion, pec] _ FindPivot[t, v]};
ENDCASE => EXIT; ENDLOOP;
unbounded _ pec = VIsManifestlyUnbounded;
};
 
MakeVOwnARow: PROCEDURE [t: Tableau, v: Unknown] = {
champ: INT;
score: REAL;
sgn: REAL;
i: INT _ 0;
IF v.j = doesntOwnACol THEN RETURN;
WHILE i < t.n AND t.a[i][v.j] = 0.0 DO i _ i + 1 ENDLOOP;
SELECT TRUE FROM
i = t.n => RETURN;
t.a[i][v.j] > 0 => sgn _ +1;
t.a[i][v.j] < 0 => sgn _ -1
ENDCASE => ERROR;
champ _ i;
score _ Real.LargestNumber;
FOR ii: INT IN [0..t.n) 
DO IF ii # i AND t.y[ii].restricted AND sgn * t.a[ii][v.j] < 0
THEN IF ABS[t.a[ii][t.unity.j] / t.a[ii][v.j]] < score
THEN {champ _ ii; score _ ABS[t.a[ii][t.unity.j] / t.a[ii][v.j]]}
ENDLOOP;
Pivot[t, champ, v.j];
};
  
Init: PUBLIC PROCEDURE RETURNS [t: Tableau] = {
t _ NEW[TableauRec];
t.a _ NEW[ARRAY Row OF ARRAY Col OF REAL];
t.x _ NEW[ARRAY Col OF Unknown]; 
t.y _ NEW[ARRAY Row OF Unknown]; 
t.n _ t.m _ 0;
t.maxN _ t.maxM _ 0;
t.unity _ NewUnknown[t, "unity"];
t.satisfiable _ TRUE;
t.nameCount _ 0;
};


InventName: PROC [t: Tableau, r: Rope.ROPE] RETURNS [Rope.ROPE] ~ {
t.nameCount _ t.nameCount + 1;
RETURN [r.Concat[Convert.RopeFromInt[t.nameCount]]];
};


in, out: IO.STREAM; -- for debugging
debug: BOOL _ FALSE;
StartDebug: PROCEDURE  = 
{[in, out] _ ViewerIO.CreateViewerStreams["Debug LinearSolver"]; debug _ TRUE};

Debug: PROCEDURE  [t: Tableau, r: Rope.ROPE] = {
IF debug THEN {
IO.Put[out, IO.rope[r]];
Newline[];
Print[t];
IO.PutF[out, "%12gSatisfiable = %g\n", IO.rope[""], IO.bool[t.satisfiable]];
Newline[]; Newline[]}};

Print: PROCEDURE [t: Tableau]  = {
IO.PutF[out, "%12g", IO.rope[""]];
FOR j : INT IN [0 .. t.m) DO Out[t.x[j]] ENDLOOP;
Newline[];
FOR i : INT IN [0 .. t.n)
DO  Out[t.y[i]]; FOR j: INT IN [0 .. t.m) DO OutR[t.a[i][j]] ENDLOOP; Newline[]
ENDLOOP };
  
Out: PROCEDURE [r: Unknown] = {
SELECT TRUE FROM
r.name = NIL => IO.PutF[out, "%12g", IO.rope["**"]];
r.restricted => IO.PutF[out, "%11g>", IO.refAny[r.name]];
NOT r.restricted => IO.PutF[out, "%12g", IO.refAny[r.name]];
ENDCASE => ERROR};

OutR: PROCEDURE [r: REAL] = {IO.PutF[out, "%12g", IO.real[r]]};
Newline: PROCEDURE = {IO.Put[out, IO.rope["\n"]]};
END.

>LinearSolverImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Gnelson, December 11, 1983 11:48 pm
Beach, February 19, 1985 8:44:18 am PST
RowMax: INT = 100;
ColMax: INT = 100;

Row: TYPE = [0 .. RowMax);
Col: TYPE = [0 .. ColMax);
Tableau: TYPE = REF TableauRec;
TableauRec: TYPE = RECORD [
n: [0 .. RowMax],
m: [0 .. ColMax],
maxN: [0 .. RowMax],
maxM: [0 .. ColMax],
a: REF ARRAY Row OF ARRAY Col OF REAL,
a[i][j] is only relevant if i is in [0, n) and j is in [0, m).  Thus we declare a matrix of n rows by m columns, which can grow as large as RowMax by ColMax.
x: REF ARRAY Col OF Unknown,
y: REF ARRAY Row OF Unknown,
unity: Unknown,
satisfiable: BOOL,
nameCount: NAT
];

x, y, a, n, and m are together called the *Tableau*.  They represent the n constraints 

(and i: i in [0, n): y(i) = (sum j: j in [0, m): a(i, j) * x(j))).

Every active unknown appears once in either the x or y array, and does not appear in both.
The unknowns in x are called column variables, the unknowns in y are called row variables.
The module maintains the invariant that the variable unity is one of the column variables.
That is, 

(E j: j in [0, m): x(j) = unity).

The module also maintains the inverse of the arrays x and y, using the space in the records
that represent the unknowns.  The i field is the inverse of the y array, and the j field is
the inverse of the x array.  The unused inverse field is set to -1.  That is:

(A i: i in [0, n):  x(i).i = i and x(i).j = -1)
(A j: j in [0, m):  x(j).j = j and x(j).i = -1)

Notice that one solution to the constraints is 

unity = 1, 
x(j) = 0 for j in [0, n) and x(j) # unity
y(i) = a[i, unity.j] for i in [0, m)

This is the solution returned by Solution. 
Asserts c = 0, in two steps.  Step 1: create a new unknown v and assert v = c. 
This is done by creating a new row owned by v that represents c.
Step 2:  Assert v = 0. This is done by pivoting v into a column and deleting the column
Asserts c >= 0, in two steps.  Step 1: create a new unknown v, a new slack variable s (s >= 0), and assert v = c + s. 
This is done by creating a new row owned by v that represents c.
Step 2:  Assert v = 0. This is done by pivoting v into a column and deleting the column
NewUnknown is easily seen to maintain the module invariant: since the new column is zeroed out, none of the linear combinations represented by the rows are changed.
adds c*v to the linear combination represented by the nth row, 
either by incrementing one element of the row (if v owns a column) 
or by doing a row operation (if v owns a row) 
We may have a redundant constraint, silly boy! 
Back up tableau one row
kill all col vars that have a non-zero entry in v's row.
The last code is misleadingly named: it may "increase" v by zero.
To guarantee termination, some cycle-avoding 
Now v owns a row, or else it owns an empty column.
The rest of the code in this module is only for debugging.
Edited on January 14, 1984 5:50 pm, by Beach
changes to: FindPivot to avoid pivoting the unity column (sic!), KillColVar to update v.j after exchanging columns, Kill was incorrectly testing a[v.i][unity.j] < 0 so it could maximize v by moving it towards zero (changed it to > test) , MakeVOwnARow could be called by Restrict when v already owns a row (inserted a test to return if v.j = doesntOwnACol), Maximize

Edited on January 16, 1984 4:12 pm, by Beach
changes to: FindPivot to correctly compute newSampleValueOfV , Pivot, Kill, ToPivotAtUWouldIncreaseVButNotMakeItPositive, Restrict



Edited on March 19, 1984 3:32:22 pm PST, by Beach
changes to: StartDebug, DIRECTORY, LinearSolverImpl

Edited on March 26, 1984 10:19:13 am PST, by Beach
changes to: AssertGEZero, Out, AssertGEZero2, AssertGEZero3, NewRowUnknown

Edited on March 27, 1984 8:55:11 pm PST, by Beach
changes to: NewUnknown, AssertZero, AssertZero2, AssertZero3, AssertGEZero, AssertGEZero2, AssertGEZero3, AssertGEZero, AssertGEZero2, AssertGEZero3

Edited on May 5, 1984 5:43:00 pm PDT, by Beach
changes to: AssertZero, AssertZero2, AssertZero3, AssertGEZero, AssertGEZero2, AssertGEZero3, KillRowVar
Edited on September 14, 1984 5:01:44 pm PDT, by Beach
changes to: NewUnknown, AssertZero, AssertZero2, AssertZero3, AssertGEZero, AssertGEZero2, AssertGEZero3, KillRowVar, KillColVar, Pivot, Restrict, Maximize
Edited on October 15, 1984 3:55:30 pm PDT, by Beach
changes to: satisfiable, signalUnsatisfiable, Unsatisfiable, KillRowVar, Restrict, m, maxN, maxM, Unsatisfiable, AssertGEZero2, AssertGEZero3, NewUnknown, NewRowUnknown, Init, InventName, InventName, DIRECTORY, LinearSolverImpl, KillRowVar




Edited on December 8, 1984 8:47:26 pm PST, by Beach
changes to: KillAllCols
Edited on December 11, 1984 7:55:54 pm PST, by Beach
changes to: doesntOwnACol, AssertZero, AssertZero2, AssertZero3, AssertGEZero, AssertGEZero2, AssertGEZero3, NewUnknown, NewRowUnknown, AddToRow, Satisfiable, Solution, KillRowVar, CheckRowEqualities, KillColVar, KillAllCols, MaximalPivot, FindPivot, SGN (local of FindPivot), Pivot, Restrict, Maximize, MakeVOwnARow, Init, InventName, Debug, Print, Out, Pivot, Init, Debug, Print

Beach, February 19, 1985 8:43:39 am PST
changes to: KillRowVar

�ʘš
œ™Jšœ
Ïm
œ1™<Jš
œ#™#Jš
œ'™'—J˜JšÏk	œ
žœ%˜:J˜šÏnœž
˜Jšžœ
žœ˜#Jšžœž˜—Jšžœ˜J˜Jšœžœ™šœžœ™J™—Jšœžœ™šœžœ™J˜—Jšœ	žœžœ™šœžœžœ™Jš
œ™Jš
œ™J™Jš
œ™š
œžœ
žœžœ
žœžœ
žœ
™&JšÏeœ…
 œ œ
™�
—Jšœžœ
žœžœ	™Jšœžœ
žœžœ	™Jš
œ™Jšœ
ž™Jšœž™J™J™—Jšœžœ˜šœžœ˜J˜—š
œW™WJ™Jš
œB™BJ™Jš
œZ™ZJš
œZ™ZJš
œZ™ZJš
œ	™	J™Jš
œ!™!J™Jš
œ[™[Jš
œ[™[Jš
œM™MJ™Jš
œ/™/Jš
œ/™/J™Jš
œ/™/J™Jš
œ™Jš
œ)™)Jš
œ$™$J™Jš
œ+™+—J˜Jšœžœžœ
˜!Jšœžœžœ
˜
unitš
Ÿ
œžœ
ž	œžœžœ˜<Jšœžœ˜J˜—šŸ
œžœ
ž	œ2žœ˜VJš
œO™OJš
œ@™@Jš
œW™WJšžœ
žœžœ
žœ
˜ Jš
œ ˜ Jšžœžœ
žœžœ
˜Dšžœžœ
žœ
˜Jšœžœžœ
˜(Jš
œ.˜.Jš
œ˜Jšžœ˜	—Jš
œ˜Jš
œ˜—šŸœžœ
ž	œžœžœ$žœ˜wJš
œ˜Jš
žœžœ
žœžœ	žœ˜cJš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜—šŸœžœ
ž	œžœžœžœ$žœ˜Ž
Jš
œ˜Jš
žœžœ
žœžœ	žœ+˜pJš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜—šŸœžœ
ž	œ2žœ˜XJš
œv™vJš
œ@™@Jš
œW™WJšžœ
žœžœ
žœ
˜ Jš
œ ˜ Jš
œ#˜#Jšžœžœ
žœžœ
˜FJš
œ˜šžœžœ
žœ
˜Jšœžœžœ
˜(Jš
œ.˜.Jš
œ˜Jšžœ˜	—Jš
œ ˜ Jš
œ˜Jš
œ˜—šŸ
œžœ
ž	œžœžœ$žœ˜yJš
œ˜Jš
œ8˜8Jš
žœžœ
žœžœ	žœ˜eJš
œ˜Jš
œ˜Jš
œ˜Jš
œ ˜ Jš
œ˜Jš
œ˜—šŸ
œžœ
ž	œžœžœžœ$žœ˜�
Jš
œ˜Jš
œ8˜8Jš
žœžœ
žœžœ	žœ+˜rJš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ ˜ Jš
œ˜Jš
œ˜—š
Ÿ
œžœ
ž	œžœžœ˜JJšœ
žœ
˜Jšžœžœ
žœžœ˜CJš
œ˜Jš
œ˜Jš
œ˜Jš
žœžœ
žœžœžœ˜5Jš
œ˜Jš
œ˜Jšœ	žœ˜Jšžœ˜Jš
œ˜Jš
œ¤
™¤
—šŸ
œž	œžœ˜>Jšœžœ
˜Jš
œ˜Jš
œ
˜
Jš
œ˜Jš
žœžœ
žœžœžœ
˜4Jš
œ
˜
Jš
œ˜Jšœ	žœ˜Jšžœ˜
Jš
œ˜—šŸœž
œžœ˜AJš
œ?™?Jš
œC™CJš
œ.™.šžœ
žœ
ž˜Jš
œ5˜5š
œ˜Jš
žœžœ
žœžœ)žœ
˜L—Jšžœžœ
ÏcD˜U—Jš
œ˜Jš
œ˜—KšŸœžœ
ž	œžœžœžœ˜Uš
Ÿœžœ
ž	œžœžœ˜DJšœž˜Jšœžœ
žœ
ž˜Jšœžœ˜Jšœžœžœ˜7Jšœžœ˜8Jšœžœž˜Jšœžœ
˜—šŸ
œž
œ.žœ˜JJš
œ˜Jš
œ˜Jšžœžœ
žœžœ˜Lšžœ
žœžœ˜+Jš
œ/™/Jšœ
žœžœ
˜šžœžœ
žœž˜Jšœžœ
žœ˜2Jš
ž˜—šžœ
žœ˜J™Jšœžœ
˜Jšžœ
˜Jš
œ˜—Jš
œ˜—šžœž˜Jš
žœžœ
žœžœžœ
˜@Jš
¡3˜3Jš
¡E˜EJš
¡˜—Jš
œ(˜(šžœ
žœ
ž˜Jšœ#ž˜%š
œ!˜!Jš
œ\˜\—Jšœž˜š
œ˜Jš
œ;˜;—š
œ ˜ Jš
žœžœ
žœžœžœ
˜K—Jšžœž˜—Jš
œ˜—šŸœž	œ%˜BJ˜—šŸ
œž	œ/žœ˜LJšžœžœ
žœžœ˜FJš
œ˜šžœ˜
Jšžœžœžœ
žœžœžœ*˜m—J˜—šŸœž	œ.žœ˜LJš
œ8™8Jšžœžœ
žœ"žœ˜Ošžœžœ
žœ
ž˜Jš	žœžœ¡
žœžœ
˜P—J˜—šœžœ˜Jš
œ˜Jš
œ˜Jš
œ˜—š
œ0˜0Jš
œ˜Jš
œ˜Jš
œA™AJš
œ-™-J˜—šŸœž	œžœžœ˜oJš
œ%˜%šžœ4ž˜;Jš
œ˜Jš
œ%˜%Jš
ž˜—Jš
œ˜J˜—šŸ	œž	œžœžœ˜lšÐknœž	œžœžœžœžœ˜2Jšžœžœžœžœ˜%J˜—Jšœžœ˜Jšœžœ
˜
šžœžœ
žœ˜šžœ
žœ˜š
žœ
žœžœ
žœžœ˜IJšžœžœ˜&——Jšžœ˜—šžœžœ
˜šžœ
žœ
ž˜Jšœ;žœ˜CJšœ6žœ˜>Jšœ:žœ˜BJšžœžœ
˜——Jšœ¡˜(Jšœžœ
˜Jšœžœ
˜Jš
œ˜Jš
œ˜šžœžœ
žœ
˜šžœ
žœ
žœžœ˜>šžœ
žœ
žœ)˜4Jšžœžœ"˜?——Jšžœ
˜—Jš
œ˜Jšžœ
žœ žœ˜;JšœžœQ˜išžœ
žœ
ž˜Jš
œM˜MJš
œ<˜<Jšžœžœ˜—J˜—šŸœž	œ!˜1Jšœžœ¡˜:Jš
žœžœ
žœ%žœ	žœ
˜UJšœ¡0˜CJš
¡#˜#š
œ1˜1Jš
œR˜R—Jš
žœžœ
žœžœžœ
˜AJš
¡8˜8šžœžœ
žœžœ
˜šžœžœ
˜šžœžœ
žœžœ
˜šžœžœ
˜Jš
¡<˜<Jš
œ.˜.—Jš
¡=˜=Jš
ž˜——Jšžœ
˜—Jš
¡ ˜ Jš
žœžœ
žœžœ
žœžœž˜LJš
œ˜J˜—šŸœžœ/žœ˜QJšžœžœ
žœžœ˜LJšžœžœ
žœ
˜Jš
œ˜Jš
œ2™2Jšžœžœžœžœ˜:Jšžœžœžœžœ˜>Jš
œ˜Jš
œ˜Jš
œ(˜(šžœ
žœ
ž˜Jšœ6žœ˜WJšœž˜Jš
œC˜CJšœ"žœžœ
žœžœžœ˜nJšœ0žœ˜JJšžœžœ˜—Jš
œ˜—š
Ÿœžœžœ
žœžœ˜\Jš
œ˜Jš
œ˜Jšžœžœ
žœžœ˜LJš
œ˜Jšžœžœ
žœ
žœ˜6Jš
œ%˜%šžœ
žœ
žœ
ž˜Jšœ#ž˜%š
œ5˜5Jš
œB˜B—Jšžœžœžœ
˜—Jš
œ)˜)Jš
œ˜Jš
œ
˜
—šŸœž	œ˜4Jšœžœ
˜Jšœžœ
˜Jšœžœ
˜
Jšœžœ˜Jšžœžœ
žœ
˜#Jšžœ	žœžœžœ
˜9šžœ
žœ
ž˜Jšœžœ
˜Jš
œ˜Jš
œ˜Jšžœžœ
˜—Jš
œ
˜
Jš
œ˜šžœžœ
žœ
˜šžœ
žœžœžœ˜>šžœ
žœ
žœ+˜6Jšžœžœ$˜A——Jšžœ
˜—Jš
œ˜Jš
œ˜Jš
œ˜—šŸœžœ
ž	œ
žœ˜/Jšœžœ
˜Jš
œžœ
žœžœ
žœžœ
žœ˜*Jšœžœ
žœžœ˜!Jšœžœ
žœžœ˜!Jš
œ˜J˜Jš
œ!˜!Jšœžœ
˜J˜J˜—J˜J˜š
Ÿ
œžœžœžœžœ˜CJš
œ˜Jšžœ.˜4J˜J˜—š
œ:™:J˜—Jšœ	žœ
žœ¡˜$Jšœžœžœ
˜šŸ
œž	œ˜JšœIžœ˜OJ˜—šŸœž	œ
ž
œžœ˜0šžœžœ˜Jšžœ
žœ
˜Jš
œ
˜
Jš
œ	˜	Jšžœ#žœžœ˜LJš
œ˜—J˜—šŸœž	œ˜"Jšžœžœ˜"Jš
žœžœ
žœžœ
žœ
˜1Jš
œ
˜
šžœžœ
žœ˜Jšžœ
ž
œ
žœžœ
žœžœžœ˜OJšžœ˜
—Jš
œ˜—šŸœž	œ˜šžœ
žœ
ž˜Jšœ	žœžœžœ
˜4Jšœžœžœ˜9Jšžœžœžœ˜<Jšžœžœ˜—J˜—Kš
Ÿœž	œžœžœžœ˜?KšŸœž	œžœ
žœ˜2šžœ
˜J˜—™,Jš
œÏr	œ*£œ'£œu£œi£
™î—J™™,Jšœ£
œ£œ
£E™‚
—J™J™J™™1Jšœ£'™3—J™™2Jšœ£>™J—J™™1Jšœ£ˆ
™”
—J™™.Jšœ£\™h—™5Jšœ£�
™›
—™3Jšœ£ã
™ï
—J™J™J™J™™3Jšœ£™—™4Jšœ£ò
œ£i™ü—J™™'Jšœ£
™—J™—…—/ÒW$