(*  INPUT	: The associated datafile for Integer problem
		  is called "IntegerDatafile".

		  IntegerDatafile consists of
		  1. # of variables, N,
		  2. # of constraints, M,
		  3. Cost vector
		  4. Constraint matrix A,
		  5. Right Hand Side(RHS), vector b.

		  FIRST NUMBER in "IntegerDatafile" is the # of variables.

		  SECOND NUMBER is the # of constraints.

		  THIRD set of data represents the cost vector in the 
		  objective function.  The last number of this row is
		  the initial optimal value which is 0.

		  FOURTH set of data represents the constraint matrix A.
		  The last numbe of each row is the corresponding RHS
		  value for each constraint.

   Algorithm	: This algorithm is based on GOMORY cutting plane method.
                  
		  This algorithm solves the following INTEGER LP problem:

		  min	   SUM	(a0j * xj)
			(j=1 to n) 

		  s.t.	  SUM   (aij*xj)  <=  ai,n+1    for i=1to(M-N)
			(j=1 to n)


		  Maximum # of variables, and maximum # of constraints are
		  set to maxvar =50 and maxconstraint=50 respectively.
		  One can modify them according to their needs.

   OUTPUT	: Outputs are
		  1. Check if an integer LP is feasible and optimal 
		     solution exists. 
		  2. Determine the optimal basic variables and their
		     corresponding values.
		  3. Determine the optimal value of the objective function

   NOTE		: This GOMORY cuttinng plane algorithm is not polynomial
		  time algorithm.

		  The GOMORY cuttinng plane algorithm are most useful in
		  solving LARGE SET PARTITIONING and SET COVERING problems

		  This algorithm is less effective in solving general
		  integer programming problem.                         *)





program  Integer (input,output, IntegerDatafile,IntegerOutfile);

const   maxvar	=	50;
	maxconstraint = 50;

type	CHARFILE	=	file of char;
	ARRMN1	= array[0..maxvar+maxconstraint,1..maxvar+1] of integer;

var	M,N,N1	:	integer;
	A	:	ARRMN1;
	COUNT	:	integer;
	NOFEAS	:	boolean;
	Nextint :	integer;
	IntegerDatafile	:	CHARFILE;
        IntegerOutfile  :	CHARFILE;


procedure Infile( var	M,N,N1	:	integer;
		  var	A	:	ARRMN1;
		  var	Nextint :	integer);

var row, column : integer;

begin
  reset(IntegerDatafile);
  readln(IntegerDatafile,Nextint);
  N := Nextint;
  N1 := N + 1;
  readln(IntegerDatafile,Nextint);
  M := Nextint+N;
  for row := 0 to M do
  begin
    if row <= M-N then
    begin
      for column := 1 to N1 do
      begin
        read(IntegerDatafile,Nextint);
        A[row,column] := Nextint;
      end;
      readln(IntegerDatafile);
    end
    else
    begin
      for column := 1 to N1 do
      begin
        if row-N+1 = column then
          A[row,column] := -1
        else
          A[row,column] := 0;
      end;
    end;
  end;
end;




procedure ALLinteger(
       M,N   :integer;
   var A     :ARRMN1;
   var COUNT :integer;
   var NOFEAS:boolean);

   var C,DENOM,I,J,K,L,NP,NUM,R,R1,S,T:integer;
       B,ITER                         :boolean;

   function EUCLID(U,V:integer):integer;
      var W:integer;
   begin
      W:=U div V;
      if W*V > U then W:=W-1;
      if (W+1)*V <= U then W:=W+1;
      EUCLID:=W
   end;  (* EUCLID *)

begin
   COUNT:=0;
   NP:=N+1;
   repeat  (* until not ITER or NOFEAS *)
      COUNT:=COUNT+1;
      R:=0;
      repeat
         R:=R+1;
         ITER:=A[R,NP] < 0
      until ITER or (R = M);
      if ITER then begin
         K:=0;
         repeat
            K:=K+1;
            ITER:=A[R,K] < 0
         until ITER or (K = N);
         NOFEAS:=not ITER;
         if ITER then begin
            L:=K;
            for J:=K+1 to N do
               if A[R,J] < 0 then begin
                  I:=-1;
                  repeat
                     I:=I+1;
                     S:=A[I,J]-A[I,L]
                  until S <> 0;
                  if S < 0 then L:=J
               end;  (* if A[R,J] < 0 *)
            S:=0;
            while A[S,L]=0 do S:=S+1;
            NUM:=-A[R,L];  DENOM:=1;
            for J:=1 to N do
               if (A[R,J] < 0) and (J <> L) then begin
                  I:=S-1;  B:=true;
                  while B and (I >= 0) do begin
                     B:=A[I,J] = 0;
                     I:=I-1
                  end;
                  if B then begin
                     I:=A[S,J];  R1:=A[S,L];
                     T:=EUCLID(I,R1);
                     if (T*R1 = I) and (T > 1) then begin
                        I:=S;
                        repeat
                           I:=I+1;
                           R1:=T*A[I,L]-A[I,J]
                        until R1 <> 0;
                        if R1 > 0 then T:=T-1
                     end;  (* if (T*R1 = I) ... *)
                     C:=-A[R,J];
                     if C*DENOM > T*NUM then begin
                        NUM:=C;  DENOM:=T
                     end
                  end  (* if B *)
               end;  (* if (A[R,J] < 0) ..., for J *)
            for J:=1 to NP do
               if J <> L then begin
                  C:=EUCLID(A[R,J]*DENOM,NUM);
                  if C <> 0 then
                     for I:=0 to M do A[I,J]:=A[I,J]+C*A[I,L]
               end  (* if J <> L, for J *)
         end  (* if ITER - A[R,K] < 0 *)
      end  (* if ITER - A[R,NP] < 0 *)
   until not ITER or NOFEAS
end;  (* ALLinteger *)




procedure   Outfile( A	:    ARRMN1;
                     M,N,N1	:    integer;
  	             COUNT :     integer;
                     NOFEAS :  boolean);

var counter : integer;

begin
  rewrite(IntegerOutfile);
  writeln(IntegerOutfile,'   NOFEAS   ',NOFEAS);
  if NOFEAS = false then
  begin
    writeln(IntegerOutfile,' # of dual simplex iterations performed is ',COUNT);
    writeln(IntegerOutfile,' optimal solution is  ',A[0,N1]*-1,'    with   ');
    for counter := M-N+1 to M do
    begin
      writeln(IntegerOutfile,'  X',counter-N+1:2,' =  ',A[counter,N1]);
    end;
  end;
end;
      

begin (* main *)
  Infile(M,N,N1,A,Nextint);
  ALLinteger(M,N,A,COUNT,NOFEAS);
  Outfile(A,M,N,N1,COUNT,NOFEAS);
end.