//  This file contains the definition of the class linearProgram 
//  which is a C++ version of Minit.
//
//  The code was originally in Algol 60 and was published in Collected
//  Algorithms from CACM (alg #333) by Rudolfo C. Salazar and Subrata
//  K. Sen in 1968 under the title MINIT (MINimum ITerations) algorithm
//  for Linear Programming.
//
//  It was directly translated into C by Badri Lokanathan, Dept. of EE,
//  University of Rochester, with no modification to code structure. 
//
//  The C++ interface was created by E. Mayoraz in March 96.


#ifndef LinearProgram_h
#define LinearProgram_h 


#include "../Basics/basic.h"
#include "../Matrices/Matrix.h"



#define	MAXIMIZE	+1
#define MINIMIZE	-1



class linearProgram {
   public:
      //////////////////
      // Constructors //
      //////////////////
   
      /////////////////////////////////////////////////////////////////////////
      // The following 4 constructors provide the simplest way of constructing 
      // a Linear Program. The LP must be fully specified at the construction,
      // it can either be given in a standard or a general form, and with real
      // or integer parameters.

      linearProgram (// LP in standard form: max cx | Ax <= b, x >= 0 
	 Array<double>& c, 	// objective function (1,nbVar)
	 Array<double>& A,	// constraint matrix (nbConstr,nbVar)
	 Array<double>& b);    	// right-hand-side (1,nbConstr)

      linearProgram (// LP in standard form: max cx | Ax <= b, x >= 0 
	 Array<int>& c, 	// objective function (1,nbVar)
	 Array<int>& A,		// constraint matrix (nbConstr,nbVar)
	 Array<int>& b);    	// right-hand-side (1,nbConstr)

      linearProgram (// LP in general form: min/max cx | Ax R b, x >= 0
	 int objSense,		// MINIMIZE or MAXIMIZE 
	 Array<double>& c,     	// objective function (1,nbVar)
	 Array<double>& A, 	// constraint matrix (nbConstr,nbVar)
	 Array<char>& R,    	// relation type 'L','E','G' (nbConstr)
	 Array<double>& b);    	// right-hand-side (1,nbConstr) 

      linearProgram (// LP in general form: min/max cx | Ax R b, x >= 0
	 int objSense,		// MINIMIZE or MAXIMIZE 
	 Array<int>& c,     	// objective function (1,nbVar)
	 Array<int>& A, 	// constraint matrix (nbConstr,nbVar)
	 Array<char>& R,	// relation type 'L','E','G' (nbConstr)
	 Array<int>& b);    	// right-hand-side (1,nbConstr) 

      linearProgram ();

      /////////////////////////////////////////////////////////////////////////
      // Any Linear Program can always be completely redefined by one of the
      // following operator.

      void newLP (// load a new LP of the form: min/max cx | Ax R b, x >= 0 
	 int objSense,		// MINIMIZE or MAXIMIZE 
	 Array<double>& c,     	// objective function (1,nbVar)
	 Array<double>& A, 	// constraint matrix (nbConstr,nbVar)
	 Array<char>& R,	// relation type 'L','E','G' (nbConstr)
	 Array<double>& b);    	// right-hand-side (1,nbConstr) 
      // Return 0 in case of error.

      void newLP (// load a new LP of the form: min/max cx | Ax R b, x >= 0
	 int objSense,		// MINIMIZE or MAXIMIZE 
	 Array<int>& c,     	// objective function (1,nbVar)
	 Array<int>& A, 	// constraint matrix (nbConstr,nbVar)
	 Array<char>& R,    	// relation type 'L','E','G' (nbConstr)
	 Array<int>& b);    	// right-hand-side (1,nbConstr) 
      // Return 0 in case of error.


      ///////////////
      // Operators //
      ///////////////

      int solve (		// solve the LP 
	 double& optValue);	// optimal value found 

      int solve (		// solve the LP 
	 double& optValue,	// optimal value found 
	 Matrix<double>& primal);// solution for the primal 

      int solve (		// solve the LP 
	 double& optValue,	// optimal value found 
	 Matrix<double>& primal,// solution for the primal 
	 Matrix<double>& dual);	// solution for the dual
      // The status of the optimization is returned:
      //	0   : optimal solution found
      //	1,2 : no solution
      //	3   : primal has unbounded solution

      friend ostream& operator << (	// output the LP
	 ostream& s, 		// output stream used and returned
	 const linearProgram&lp);// myself

      /////////////////////////////////////////////////////////////////////////


   private:
      int k, m, mL, mG, mE, n, lcol, L, im, jmin, jm, imax, debug;
      boolean maxim;
      float td, gmin, phimax;
      Matrix<int> imin, jmax, ind, ind1, chk, permRow;
      Matrix<double> e, thmin, delmax;

      int rowtrans(int p, int q);
      void progamma();
      void prophi();
      int  phase1();
      void tab();

}; 




#endif