lp.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/lib/abacus/optsense.h>
#include <ogdf/lib/abacus/lpvarstat.h>
#include <ogdf/lib/abacus/slackstat.h>
#include <ogdf/basic/Stopwatch.h>
 
 
namespace abacus {
 
class Master;
class SparVec;
class Row;
class Column;
 
 
 
class OGDF_EXPORT LP : public AbacusRoot {
public:
 
    enum OPTSTAT {
        Optimal,        
        Unoptimized,    
        Error,          
        Feasible,       
        Infeasible,     
        Unbounded,      
        LimitReached    
    };
 
    enum SOLSTAT {
        Available,  
        Missing     
    };
 
    enum METHOD {
        Primal,              
        Dual,                
        BarrierAndCrossover, 
        BarrierNoCrossover,  
        Approximate          
    };
 
 
    LP (Master *master) :
        master_(master),
        optStat_(Unoptimized),
        xValStatus_(Missing),
        barXValStatus_(Missing),
        yValStatus_(Missing),
        recoStatus_(Missing),
        slackStatus_(Missing),
        basisStatus_(Missing),
        nOpt_(0)
    { }
 
    virtual ~LP () { }
 
    friend OGDF_EXPORT std::ostream &operator<<(std::ostream& out, const LP& rhs);
 
    void initialize(
        OptSense sense,
        int nRow,
        int maxRow,
        int nCol,
        int maxCol,
        Array<double> &obj,
        Array<double> &lBound,
        Array<double> &uBound,
        Array<Row*> &rows) {
            _initialize(sense, nRow, maxRow, nCol, maxCol, obj, lBound, uBound, rows);
    }
 
    void initialize(
        OptSense sense,
        int nRow, int maxRow,
        int nCol, int maxCol,
        Array<double> &obj,
        Array<double> &lBound,
        Array<double> &uBound,
        Array<Row*> &rows,
        Array<LPVARSTAT::STATUS> &lpVarStat,
        Array<SlackStat::STATUS> &slackStat) {
            _initialize(sense, nRow, maxRow, nCol, maxCol, obj, lBound, uBound, rows);
            loadBasis(lpVarStat,slackStat);
    }
 
 
    virtual void loadBasis(
        Array<LPVARSTAT::STATUS> &lpVarStat,
        Array<SlackStat::STATUS> &slackStat) {
            _loadBasis(lpVarStat,slackStat);
    }
 
    OptSense sense() const { return _sense(); }
 
    void sense(const OptSense &newSense) { _sense(newSense); }
 
    int nRow() const { return _nRow(); }
 
    int maxRow() const { return _maxRow(); }
 
    int nCol() const { return _nCol(); }
 
    int maxCol() const { return _maxCol(); }
 
    int nnz() const { return _nnz(); }
 
    double obj(int i) const {
#ifdef OGDF_DEBUG
        colRangeCheck(i);
#endif
        return _obj(i);
    }
 
    double lBound(int i) const {
#ifdef OGDF_DEBUG
        colRangeCheck(i);
#endif
        return _lBound(i);
    }
 
    double uBound(int i) const {
#ifdef OGDF_DEBUG
        colRangeCheck(i);
#endif
        return _uBound(i);
    }
 
    void row(int i, Row &r) const {
#ifdef OGDF_DEBUG
        rowRangeCheck(i);
#endif
        _row(i, r);
    }
 
    double rhs(int i) const {
#ifdef ABACUSSAFE
        rowRangeCheck(i);
#endif
        return _rhs(i);
    }
 
    virtual double value() const { return _value(); }
 
    virtual double xVal(int i) const {
#ifdef OGDF_DEBUG
        colRangeCheck(i);
#endif
        return _xVal(i);
    }
 
    virtual double barXVal(int i) const {
#ifdef OGDF_DEBUG
        colRangeCheck(i);
#endif
        return _barXVal(i);
    }
 
    virtual double reco(int i) const {
#ifdef OGDF_DEBUG
        colRangeCheck(i);
#endif
        return _reco(i);
    }
 
    virtual double yVal(int c) const {
#ifdef OGDF_DEBUG
        rowRangeCheck(c);
#endif
        return _yVal(c);
    }
 
    virtual double slack(int c) const {
#ifdef OGDF_DEBUG
        rowRangeCheck(c);
#endif
        return _slack(c);
    }
 
    SOLSTAT xValStatus() const { return xValStatus_; }
 
    SOLSTAT barXValStatus() const { return barXValStatus_; }
 
    SOLSTAT yValStatus() const { return yValStatus_; }
 
    SOLSTAT recoStatus() const { return recoStatus_; }
 
    SOLSTAT slackStatus() const { return slackStatus_; }
 
    SOLSTAT basisStatus() const { return basisStatus_; }
 
    int nOpt() const { return nOpt_; }
 
    virtual bool infeasible() const {
        return ( optStat_ == Infeasible );
    }
 
 
    virtual int getInfeas(int &infeasRow, int &infeasCol, double *bInvRow) const {
        return _getInfeas(infeasRow,infeasCol,bInvRow);
    }
 
    virtual LPVARSTAT::STATUS lpVarStat(int i) const {
#ifdef OGDF_DEBUG
        colRangeCheck(i);
#endif
        return _lpVarStat(i);
    }
 
    virtual SlackStat::STATUS slackStat(int i) const {
#ifdef OGDF_DEBUG
        rowRangeCheck(i);
#endif
        return _slackStat(i);
    }
 
    virtual OPTSTAT optimize(METHOD method);
 
    void remRows(ArrayBuffer<int> &ind) {
        initPostOpt();
        _remRows(ind);
    }
 
    void addRows(ArrayBuffer<Row*> &newRows);
 
    void remCols(ArrayBuffer<int> &cols) {
        initPostOpt();
        _remCols(cols);
    }
 
    void addCols(ArrayBuffer<Column*> &newCols);
 
    void changeRhs(Array<double> &newRhs) {
        initPostOpt();
        _changeRhs(newRhs);
    }
 
    virtual void changeLBound(int i, double newLb);
 
    virtual void changeUBound(int i, double newUb);
 
    virtual int pivotSlackVariableIn(ArrayBuffer<int> &rows);
 
    void rowRealloc(int newSize) {
        _rowRealloc(newSize);
    }
 
    void colRealloc(int newSize) {
        _colRealloc(newSize);
    }
 
 
    int writeBasisMatrix(const char *fileName);
 
    int setSimplexIterationLimit(int limit) {
        return _setSimplexIterationLimit(limit);
    }
 
    int getSimplexIterationLimit(int &limit) const {
        return _getSimplexIterationLimit(limit);
    }
 
    ogdf::StopwatchCPU* lpSolverTime() { return &lpSolverTime_; }
 
protected:
 
    void colsNnz(int nRow, Array<Row*> &rows, Array<int> &nnz);
 
    void rows2cols(int nRow, Array<Row*> &rows,
        Array<SparVec*> &cols);
 
    void rowRangeCheck(int r) const;
 
    void colRangeCheck(int i) const;
 
    virtual OptSense _sense() const = 0;
    virtual void _sense(const OptSense &newSense) = 0;
 
    virtual int      _nRow()  const = 0;
 
    virtual int      _maxRow() const = 0;
 
    virtual int      _nCol() const = 0;
 
    virtual int      _maxCol() const = 0;
 
    virtual int      _nnz() const = 0;
 
    virtual double   _obj(int i) const = 0;
 
    virtual double   _lBound(int i) const = 0;
 
    virtual double   _uBound(int i) const = 0;
 
    virtual double   _rhs(int i) const = 0;
 
    virtual void     _row(int i, Row &r) const = 0;
 
    virtual void    _initialize(OptSense sense, int nRow, int maxRow,
        int nCol, int maxCol,
        Array<double> &obj, Array<double> &lBound,
        Array<double> &uBound, Array<Row*> &rows) = 0;
 
    virtual void _loadBasis(Array<LPVARSTAT::STATUS> &lpVarStat,
        Array<SlackStat::STATUS> &slackStat) = 0;
 
    virtual OPTSTAT _primalSimplex()                   = 0;
 
    virtual OPTSTAT _dualSimplex()                     = 0;
 
    virtual OPTSTAT _barrier(bool doCrossover)         = 0;
 
    virtual OPTSTAT _approx()                    = 0;
 
    virtual double _value() const = 0;
 
    virtual double _xVal(int i) const  = 0;
    virtual double _barXVal(int i) const  = 0;
 
    virtual double _reco(int i) const  = 0;
 
    virtual double _slack(int i) const = 0;
 
    virtual double _yVal(int i) const  = 0;
 
    virtual LPVARSTAT::STATUS _lpVarStat(int i) const = 0;
 
    virtual SlackStat::STATUS _slackStat(int i) const = 0;
 
    virtual int _getInfeas(int &infeasRow, int &infeasCol,
        double *bInvRow) const = 0;
 
    virtual void _remRows(ArrayBuffer<int> &ind)         = 0;
 
    virtual void _addRows(ArrayBuffer<Row*> &newRows)    = 0;
 
    virtual void _remCols(ArrayBuffer<int> &vars)        = 0;
 
    virtual void _addCols(ArrayBuffer<Column*> &newCols) = 0;
 
    virtual void _changeRhs(Array<double> &newRhs)  = 0;
 
    virtual void _changeLBound(int i, double newLb) = 0;
 
    virtual void _changeUBound(int i, double newUb) = 0;
 
    virtual int _pivotSlackVariableIn(ArrayBuffer<int> &rows) = 0;
 
    virtual void _rowRealloc(int newSize) = 0;
 
    virtual void _colRealloc(int newSize) = 0;
 
    virtual int _setSimplexIterationLimit(int limit) = 0;
 
    virtual int _getSimplexIterationLimit(int &limit) const = 0;
 
    Master *master_;
 
    OPTSTAT optStat_;
 
    SOLSTAT xValStatus_;
    SOLSTAT barXValStatus_;
 
    SOLSTAT yValStatus_;
 
    SOLSTAT recoStatus_;
 
    SOLSTAT slackStatus_;
 
    SOLSTAT basisStatus_;
 
    int nOpt_;
    ogdf::StopwatchCPU lpSolverTime_;
 
private:
 
    void initPostOpt() {
        optStat_= Unoptimized;
        xValStatus_= barXValStatus_= recoStatus_= Missing;
        slackStatus_= yValStatus_= basisStatus_= Missing;
    }
 
    LP(const LP &rhs);
    const LP &operator=(const LP &rhs);
};
 
 
#if 0
inline OptSense LP::sense() const
{
    return _sense();
}
 
inline void LP::sense(const OptSense &newSense)
{
    _sense(newSense);
}
 
inline int LP::nRow() const
{
    return _nRow();
}
 
inline int LP::maxRow() const
{
    return _maxRow();
}
 
inline int LP::nCol() const
{
    return _nCol();
}
 
inline int LP::maxCol() const
{
    return _maxCol();
}
 
inline int LP::nnz() const
{
    return _nnz();
}
 
inline double LP::obj(int i) const
{
#ifdef OGDF_DEBUG
    colRangeCheck(i);
#endif
    return _obj(i);
}
 
inline double LP::lBound(int i) const
{
#ifdef OGDF_DEBUG
    colRangeCheck(i);
#endif
    return _lBound(i);
}
 
inline double LP::uBound(int i) const
{
#ifdef OGDF_DEBUG
    colRangeCheck(i);
#endif
    return _uBound(i);
}
 
inline void LP::row(int i, Row &r) const
{
#ifdef OGDF_DEBUG
    rowRangeCheck(i);
#endif
    _row(i, r);
}
 
inline double LP::rhs(int i) const
{
#ifdef ABACUSSAFE
    rowRangeCheck(i);
#endif
    return _rhs(i);
}
 
inline double LP::value() const
{
    return _value();
}
 
inline double LP::xVal(int i)
{
#ifdef OGDF_DEBUG
    colRangeCheck(i);
#endif
    return _xVal(i);
}
 
inline double LP::barXVal(int i)
{
#ifdef OGDF_DEBUG
    colRangeCheck(i);
#endif
    return _barXVal(i);
}
 
inline double LP::reco(int i)
{
#ifdef OGDF_DEBUG
    colRangeCheck(i);
#endif
    return _reco(i);
}
 
inline double LP::yVal(int c)
{
#ifdef OGDF_DEBUG
    rowRangeCheck(c);
#endif
    return _yVal(c);
}
 
inline double LP::slack(int c)
{
#ifdef OGDF_DEBUG
    rowRangeCheck(c);
#endif
    return _slack(c);
}
 
inline LP::SOLSTAT LP::xValStatus() const
{
    return xValStatus_;
}
 
inline LP::SOLSTAT LP::barXValStatus() const
{
    return barXValStatus_;
}
 
inline LP::SOLSTAT LP::recoStatus() const
{
    return recoStatus_;
}
 
inline LP::SOLSTAT LP::yValStatus() const
{
    return yValStatus_;
}
 
inline LP::SOLSTAT LP::slackStatus() const
{
    return slackStatus_;
}
 
inline LP::SOLSTAT LP::basisStatus() const
{
    return basisStatus_;
}
 
inline int LP::nOpt() const
{
    return nOpt_;
}
 
inline bool LP::infeasible() const
{
    if (optStat_ == Infeasible) return true;
    else                        return false;
}
 
inline LPVARSTAT::STATUS LP::lpVarStat(int i)
{
#ifdef OGDF_DEBUG
    colRangeCheck(i);
#endif
    return _lpVarStat(i);
}
 
inline SlackStat::STATUS LP::slackStat(int i)
{
#ifdef OGDF_DEBUG
    rowRangeCheck(i);
#endif
    return _slackStat(i);
}
#endif
 
}