
/*
**  This file forms part of the GOBLIN C++ Class Library.
**
**  Written by Bernhard Schmidt and Christian Fremuth-Paeger, January 2003.
**  
**  Copying, compiling, distribution and modification
**  of this source code is permitted only in accordance
**  with the GOBLIN general licence information.
*/             

//*********************************************************************//
//  LP-Solver for LPs                                                  //
//          min/max c^tx under L <= Ax <= U, l <= x <= u               //
//  Variable labeling:    0,...,lAct-1                                 //
//  Restriction labeling: 0,...,kAct+lAct-1                            //
//    (restriction i is L_i <= A_ix <= U_i for i<kAct                  //
//    and l_i <= x <= u_i for i>= kAct)                                //
//*********************************************************************//


#if !defined(_LPSOLVE_H_)

#define _LPSOLVE_H_

#include <ilpWrap.h>
#include <matrix.h>
#include <dictionary.h>

const double EPSILON=1e-10;
const double DELTA=1e-6;
const double TOLERANCE=1e-7;

class goblinLPSolver : public virtual goblinILPWrapper
{
private:

    TRestr kAct;            // Number of active restrictions
    TRestr kMax;            // Maximum number of restrictions
    TRestr lAct;            // Number of active variables
    TRestr lMax;            // Maximum number of variables
    
    goblinHashTable<TIndex,TFloat>* coeff;
                            // Sparse matrix representation
                            
    TFloat* cost;           // Cost coefficients
    TFloat* uBound;         // Upper bounds (Restrictions)
    TFloat* lBound;         // Lower bounds (Restrictions)
    TFloat* uRange;         // Upper bounds (Variables)
    TFloat* lRange;         // Lower bounds (Variables)
    TVarType* varType;      // Specify integer variables
    char** restrLabel;      // Restriction labels
    char** varLabel;        // Variable names

    goblinDictionary<TVar>*   varIndex;   // Map variable labels to indices
    goblinDictionary<TRestr>* restrIndex; // Map restriction labels to indeics
                            
    TDirection dir;         // Direction of optimality
    
    TFloat cCost;           // Constant for cost coefficients
    TFloat cUBound;         // Constant for upper bounds (Restrictions)
    TFloat cLBound;         // Constant for lower bounds (Restrictions)
    TFloat cURange;         // Constant for upper bounds (Variables)
    TFloat cLRange;         // Constant for lower bounds (Variables)
    TVarType cVarType;      // Specify integer variables
    
    TRestrType* restrType;  // Identify rows in basis
    TRestr*     index;      // Mapping variables to rows in basis
    TVar*       revIndex;   // Mapping rows in basis to variables
    TFloat*     x;          // Primal solution induced by current basis
    TFloat*     y;          // Dual solution induced by current basis

    denseMatrix<TIndex,TFloat> *baseInv;   // Inverse of basis matrix
    denseMatrix<TIndex,TFloat> *keptInv;   // Kept for basis evaluations

    bool    baseInitial;    // Indicates the default basis (lower ranges)
    bool    baseValid;      // Is the basis inverse up to date?
    bool    dataValid;      // Are the solutions up to date?

public:

    goblinLPSolver(TRestr,TVar,TIndex,TDirection,
        goblinController & = goblinDefaultContext) throw();
    goblinLPSolver(char* impFileName,
        goblinController &thisContext = goblinDefaultContext)
        throw(ERFile,ERParse);
    ~goblinLPSolver() throw();

    unsigned long   Allocated() throw();
    unsigned long   Size() throw();
    virtual void*   BackCast() {return (void*)this;};
    
    
    // *************************************************************** //
    //                      Instance Manipulation                      //
    // *************************************************************** //

    TVar    AddVar(TFloat,TFloat,TFloat,TVarType = VAR_FLOAT) throw(ERRejected);
    TRestr  AddRestr(TFloat,TFloat) throw(ERRejected);

    void    DeleteVar(TVar) throw(ERRange,ERRejected);
    void    DeleteRestr(TRestr) throw(ERRange);

    void    SetURange(TVar,TFloat) throw(ERRange);
    void    SetLRange(TVar,TFloat) throw(ERRange);
    void    SetUBound(TRestr,TFloat) throw(ERRange);
    void    SetLBound(TRestr,TFloat) throw(ERRange);
    void    SetCoeff(TRestr,TVar,TFloat) throw(ERRange);
    void    SetCost(TVar,TFloat) throw(ERRange);
    void    SetVarType(TVar,TVarType) throw(ERRange);
    void    SetVarLabel(TVar,char*,TOwnership = OWNED_BY_SENDER)
                throw(ERRange,ERRejected);
    void    SetRestrLabel(TRestr,char*,TOwnership = OWNED_BY_SENDER)
                throw(ERRange,ERRejected);

    void    SetDirection(TDirection dd) throw() {dir = dd;};

    void    Resize(TRestr,TVar,TIndex) throw(ERRange);
    void    Strip() throw() {Resize(kAct,lAct,coeff->NZ());};

    
    // *************************************************************** //
    //                      Retrieval Operations                       //
    // *************************************************************** //
    
    TRestr  K() throw() {return kAct;};
    TVar    L() throw() {return lAct;};
    TIndex  NZ() throw() {return coeff->NZ();};
    
    TFloat  Cost(TVar) throw(ERRange);
    TFloat  Coeff(TRestr,TVar) throw(ERRange);
    TFloat  URange(TVar) throw(ERRange);
    TFloat  LRange(TVar) throw(ERRange);
    TFloat  UBound(TRestr) throw(ERRange);
        // UBound(i) = upper bound of restriction i, i=0,...,kAct+lAct-1
    TFloat  LBound(TRestr) throw(ERRange);
        // LBound(i) = lower bound of restriction i, i=0,...,kAct+lAct-1
    TVarType    VarType(TVar) throw(ERRange);
    char*   VarLabel(TVar,TOwnership = OWNED_BY_RECEIVER) throw(ERRange);
    char*   RestrLabel(TRestr,TOwnership = OWNED_BY_RECEIVER) throw(ERRange);
    TVar    VarIndex(char*) throw();
    TRestr  RestrIndex(char*) throw();

    bool    CCost()    throw() {return (cost==NULL);};
    bool    CURange()  throw() {return (uRange==NULL);};
    bool    CLRange()  throw() {return (lRange==NULL);};
    bool    CUBound()  throw() {return (uBound==NULL);};
    bool    CLBound()  throw() {return (lBound==NULL);};
    bool    CVarType() throw() {return (varType==NULL);};

    TDirection  Direction() throw() {return dir;};

    
    // *************************************************************** //
    //                    Basic dependent information                  //
    // *************************************************************** //

    TRestrType  RestrType(TRestr) throw(ERRange);
    TRestr  Index(TVar) throw(ERRange);
    TVar    RevIndex(TRestr) throw(ERRange);
    
    void    SetRestrType(TRestr,TLowerUpper) throw(ERRange,ERRejected);
    void    SetIndex(TRestr,TVar,TLowerUpper) throw(ERRange,ERRejected);

    void    ResetBasis() throw();
        // Sets variable range restrictions as basis, all RestrType BASIC_LB
    bool    Initial() throw() {return baseInitial;};

private:

    void    EvaluateBasis() throw(ERRejected);
    void    DefaultBasisInverse() throw(ERRejected);
    void    BasisUpdate(TRestr,TVar) throw(ERRange,ERRejected);
            // Updates baseInv after a call of Pivot
    void    SolutionUpdate() throw(ERRejected);
            // Updates primal and dual solution
	    
    void    PrimallyFeasibleBasis() throw();      
            // Modifies bounds!!! (have to be restored!)
    TVar    PricePrimal() throw(ERRejected);
    TRestr  QTestPrimal(TVar) throw(ERRejected);
    
    void    DuallyFeasibleBasis() throw();  
            // Modifies costs!!!  (have to be restored!)            
    TRestr  PriceDual() throw(ERRejected);
    TVar    QTestDual(TRestr) throw(ERRejected);
    
public:

    TFloat  X(TVar) throw(ERRange);
    TFloat  Y(TRestr,TLowerUpper) throw(ERRange);

    TFloat  Tableau(TVar,TRestr) throw();
        // Tableau(i,j)=A_j(A_B)^(-1)e_i					     
    TFloat  BaseInverse(TVar,TVar) throw(ERRange);

    
    // *************************************************************** //
    //                           Algorithms                            //
    // *************************************************************** //

    void    Pivot(TRestr,TVar,TLowerUpper) throw(ERRange,ERRejected);

    bool    StartPrimal() throw();
    TFloat  SolvePrimal() throw();

    bool    StartDual() throw();    
    TFloat  SolveDual() throw();

};


// Entry function and package information

class nativeLPModule : public virtual goblinILPModule
{
public:

    nativeLPModule() throw() : goblinDataObject(goblinDefaultContext) {};

    goblinILPWrapper*
        NewInstance(TRestr k,TVar l,TIndex nz,goblinILPWrapper::TDirection dir,
            goblinController& thisContext) throw(ERRange)
            {return new goblinLPSolver(k,l,nz,dir,thisContext);};

    goblinILPWrapper*
        ReadInstance(char* impFileName,goblinController& thisContext)
            throw(ERRange)
            {return new goblinLPSolver(impFileName,thisContext);};

    goblinILPWrapper*
        Reinterprete(void* X) throw(ERRange)
        {return (goblinLPSolver*)X;};
    
    virtual ~nativeLPModule() throw() {};

    virtual char*   Authors() throw()
        {return "Bernhard Schmidt, Christian Fremuth Paeger";};
    virtual int     MajorRelease() throw() {return 1;};
    virtual int     MinorRelease() throw() {return 0;};
    virtual char*   PatchLevel() throw()   {return "";};
    virtual char*   BuildDate() throw()    {return "2003/05/01";};
    virtual char*   License() throw()      {return "LGPL";};

};


#endif
