COIN-OR::LEMON - Graph Library

Changeset 2312:07e46cbb7d85 in lemon-0.x for lemon/lp_base.h


Ignore:
Timestamp:
11/29/06 16:01:13 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3088
Message:

modified _setColCoeff and _setRowCoeff parameters
const simplify() for expressions

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/lp_base.h

    r2309 r2312  
    3333///\ingroup gen_opt_group
    3434namespace lemon {
    35  
     35
     36
    3637  ///Internal data structure to convert floating id's to fix one's
    3738   
     
    110111    int firstIndex() {return _first_index;}
    111112  };
    112    
     113
    113114  ///Common base class for LP solvers
    114115 
     
    129130      ///has been proved.
    130131      SOLVED = 0,
    131       ///Any other case (including the case when some user specified limit has been exceeded)
     132      ///Any other case (including the case when some user specified
     133      ///limit has been exceeded)
    132134      UNSOLVED = 1
    133135    };
     
    222224      }
    223225    };
     226
     227    static int id(const Col& col) { return col.id; }
     228 
    224229     
    225230    ///Refer to a row of the LP.
     
    246251      bool operator==(Row c) const  {return id==c.id;}
    247252      bool operator!=(Row c) const  {return id!=c.id;}
    248    };
     253    };
     254
     255    static int id(const Row& row) { return row.id; }
     256
     257  protected:
     258
     259    int _lpId(const Col& col) const {
     260      return cols.floatingId(id(col));
     261    }
     262
     263    int _lpId(const Row& row) const {
     264      return rows.floatingId(id(row));
     265    }
     266
     267
     268  public:
    249269   
    250270    ///Linear expression of variables and a constant component
     
    337357      }
    338358
     359      void simplify() const {
     360        const_cast<Expr*>(this)->simplify();
     361      }
     362
    339363      ///Removes the coefficients closer to zero than \c tolerance.
    340364      void simplify(double &tolerance) {
     
    416440      typedef Expr::Value Value;
    417441     
    418 //       static const Value INF;
    419 //       static const Value NaN;
    420 
    421442    protected:
    422443      Expr _expr;
     
    554575      }
    555576
     577      void simplify() const {
     578        const_cast<DualExpr*>(this)->simplify();
     579      }
     580
    556581      ///Removes the coefficients closer to zero than \c tolerance.
    557582      void simplify(double &tolerance) {
     
    564589      }
    565590
    566 
    567591      ///Sets all coefficients to 0.
    568592      void clear() {
     
    597621   
    598622
     623  private:
     624
     625    template <typename _Base>
     626    class MappedIterator {
     627    public:
     628
     629      typedef _Base Base;
     630
     631      typedef typename Base::iterator_category iterator_category;
     632      typedef typename Base::difference_type difference_type;
     633      typedef const std::pair<int, Value> value_type;
     634      typedef value_type reference;
     635      class pointer {
     636      public:
     637        pointer(value_type& _value) : value(_value) {}
     638        value_type* operator->() { return &value; }
     639      private:
     640        value_type value;
     641      };
     642
     643      MappedIterator(const Base& _base, const LpSolverBase& _lp)
     644        : base(_base), lp(_lp) {}
     645
     646      reference operator*() {
     647        return std::make_pair(lp._lpId(base->first), base->second);
     648      }
     649
     650      pointer operator->() {
     651        return pointer(operator*());
     652      }
     653
     654      MappedIterator& operator++() {
     655        ++base;
     656        return *this;
     657      }
     658
     659      MappedIterator& operator++(int) {
     660        MappedIterator tmp(*this);
     661        ++base;
     662        return tmp;
     663      }
     664
     665      bool operator==(const MappedIterator& it) const {
     666        return base == it.base;
     667      }
     668
     669      bool operator!=(const MappedIterator& it) const {
     670        return base != it.base;
     671      }
     672
     673    private:
     674      Base base;
     675      const LpSolverBase& lp;
     676    };
     677
    599678  protected:
     679
     680    /// STL compatible iterator for lp col
     681    typedef MappedIterator<Expr::const_iterator> LpRowIterator;
     682    /// STL compatible iterator for lp row
     683    typedef MappedIterator<DualExpr::const_iterator> LpColIterator;
    600684
    601685    //Abstract virtual functions
    602686    virtual LpSolverBase &_newLp() = 0;
    603687    virtual LpSolverBase &_copyLp(){
    604       ///\todo This should be implemented here, too,  when we have problem retrieving routines. It can be overriden.
     688      ///\todo This should be implemented here, too, when we have
     689      ///problem retrieving routines. It can be overriden.
    605690
    606691      //Starting:
     
    614699    virtual void _eraseCol(int col) = 0;
    615700    virtual void _eraseRow(int row) = 0;
    616     virtual void _getColName(int col,       std::string & name) = 0;
     701    virtual void _getColName(int col, std::string & name) = 0;
    617702    virtual void _setColName(int col, const std::string & name) = 0;
    618     virtual void _setRowCoeffs(int i,
    619                                int length,
    620                                int  const * indices,
    621                                Value  const * values ) = 0;
    622     virtual void _setColCoeffs(int i,
    623                                int length,
    624                                int  const * indices,
    625                                Value  const * values ) = 0;
     703    virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) = 0;
     704    virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e) = 0;
    626705    virtual void _setCoeff(int row, int col, Value value) = 0;
    627706    virtual void _setColLowerBound(int i, Value value) = 0;
     
    632711    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
    633712    virtual void _clearObj()=0;
    634 //     virtual void _setObj(int length,
    635 //                          int  const * indices,
    636 //                          Value  const * values ) = 0;
     713
    637714    virtual SolveExitStatus _solve() = 0;
    638715    virtual Value _getPrimal(int i) = 0;
     
    653730    //Constant component of the objective function
    654731    Value obj_const_comp;
    655    
    656 
    657 
    658    
     732       
    659733  public:
    660734
     
    745819    ///a better one.
    746820    void col(Col c,const DualExpr &e) {
    747       std::vector<int> indices;
    748       std::vector<Value> values;
    749       indices.push_back(0);
    750       values.push_back(0);
    751       for(DualExpr::const_iterator i=e.begin(); i!=e.end(); ++i)
    752         if((*i).second!=0) {
    753           indices.push_back(rows.floatingId((*i).first.id));
    754           values.push_back((*i).second);
    755         }
    756       _setColCoeffs(cols.floatingId(c.id),indices.size()-1,
    757                     &indices[0],&values[0]);
     821      e.simplify();
     822      _setColCoeffs(_lpId(c), LpColIterator(e.begin(), *this),
     823                    LpColIterator(e.end(), *this));
    758824    }
    759825
     
    850916    ///added or not.
    851917    void row(Row r, Value l,const Expr &e, Value u) {
    852       std::vector<int> indices;
    853       std::vector<Value> values;
    854       indices.push_back(0);
    855       values.push_back(0);
    856       for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
    857         if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
    858           indices.push_back(cols.floatingId((*i).first.id));
    859           values.push_back((*i).second);
    860         }
    861       _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
    862                     &indices[0],&values[0]);
    863 //       _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
    864 //       _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
    865        _setRowBounds(rows.floatingId(r.id),l-e.constComp(),u-e.constComp());
     918      e.simplify();
     919      _setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this),
     920                    LpRowIterator(e.end(), *this));
     921//       _setRowLowerBound(_lpId(r),l-e.constComp());
     922//       _setRowUpperBound(_lpId(r),u-e.constComp());
     923       _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
    866924    }
    867925
     
    871929    ///\param c is a linear expression (see \ref Constr)
    872930    void row(Row r, const Constr &c) {
    873       row(r,
    874              c.lowerBounded()?c.lowerBound():-INF,
    875              c.expr(),
    876              c.upperBounded()?c.upperBound():INF);
     931      row(r, c.lowerBounded()?c.lowerBound():-INF,
     932          c.expr(), c.upperBounded()?c.upperBound():INF);
    877933    }
    878934
     
    905961    ///\todo Please check this
    906962    void eraseCol(Col c) {
    907       _eraseCol(cols.floatingId(c.id));
     963      _eraseCol(_lpId(c));
    908964      cols.erase(c.id);
    909965    }
     
    913969    ///\todo Please check this
    914970    void eraseRow(Row r) {
    915       _eraseRow(rows.floatingId(r.id));
     971      _eraseRow(_lpId(r));
    916972      rows.erase(r.id);
    917973    }
     
    923979    std::string colName(Col c){
    924980      std::string name;
    925       _getColName(cols.floatingId(c.id), name);
     981      _getColName(_lpId(c), name);
    926982      return name;
    927983    }
     
    931987    ///\param c is the coresponding coloumn
    932988    ///\param name The name to be given
    933     void colName(Col c, const std::string & name){
    934       _setColName(cols.floatingId(c.id), name);
     989    void colName(Col c, const std::string& name){
     990      _setColName(_lpId(c), name);
    935991    }
    936992   
     
    942998
    943999    void coeff(Row r, Col c, Value val){
    944       _setCoeff(rows.floatingId(r.id),cols.floatingId(c.id), val);
     1000      _setCoeff(_lpId(r),_lpId(c), val);
    9451001    }
    9461002
     
    9511007    /// Value or -\ref INF.
    9521008    void colLowerBound(Col c, Value value) {
    953       _setColLowerBound(cols.floatingId(c.id),value);
     1009      _setColLowerBound(_lpId(c),value);
    9541010    }
    9551011   
     
    9971053    /// Value or \ref INF.
    9981054    void colUpperBound(Col c, Value value) {
    999       _setColUpperBound(cols.floatingId(c.id),value);
     1055      _setColUpperBound(_lpId(c),value);
    10001056    };
    10011057
     
    10441100    /// Value, -\ref INF or \ref INF.
    10451101    void colBounds(Col c, Value lower, Value upper) {
    1046       _setColLowerBound(cols.floatingId(c.id),lower);
    1047       _setColUpperBound(cols.floatingId(c.id),upper);
     1102      _setColLowerBound(_lpId(c),lower);
     1103      _setColUpperBound(_lpId(c),upper);
    10481104    }
    10491105   
     
    10921148//     /// Value or -\ref INF.
    10931149//     void rowLowerBound(Row r, Value value) {
    1094 //       _setRowLowerBound(rows.floatingId(r.id),value);
     1150//       _setRowLowerBound(_lpId(r),value);
    10951151//     };
    10961152//     /// Set the upper bound of a row (i.e a constraint)
     
    11001156//     /// Value or \ref INF.
    11011157//     void rowUpperBound(Row r, Value value) {
    1102 //       _setRowUpperBound(rows.floatingId(r.id),value);
     1158//       _setRowUpperBound(_lpId(r),value);
    11031159//     };
    11041160
     
    11101166    /// Value, -\ref INF or \ref INF.
    11111167    void rowBounds(Row c, Value lower, Value upper) {
    1112       _setRowBounds(rows.floatingId(c.id),lower, upper);
    1113       // _setRowUpperBound(rows.floatingId(c.id),upper);
     1168      _setRowBounds(_lpId(c),lower, upper);
     1169      // _setRowUpperBound(_lpId(c),upper);
    11141170    }
    11151171   
    11161172    ///Set an element of the objective function
    1117     void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
     1173    void objCoeff(Col c, Value v) {_setObjCoeff(_lpId(c),v); };
    11181174    ///Set the objective function
    11191175   
     
    11711227
    11721228    ///\e
    1173     Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
     1229    Value primal(Col c) { return _getPrimal(_lpId(c)); }
    11741230
    11751231    ///\e
    1176     Value dual(Row r) { return _getDual(rows.floatingId(r.id)); }
     1232    Value dual(Row r) { return _getDual(_lpId(r)); }
    11771233
    11781234    ///\e
    1179     bool isBasicCol(Col c) { return _isBasicCol(cols.floatingId(c.id)); }
     1235    bool isBasicCol(Col c) { return _isBasicCol(_lpId(c)); }
    11801236
    11811237    ///\e
     
    12141270    ///Sets the type of the given coloumn to the given type.
    12151271    void colType(Col c, ColTypes col_type) {
    1216       _colType(cols.floatingId(c.id),col_type);
     1272      _colType(_lpId(c),col_type);
    12171273    }
    12181274
     
    12211277    ///Gives back the type of the column.
    12221278    ColTypes colType(Col c){
    1223       return _colType(cols.floatingId(c.id));
     1279      return _colType(_lpId(c));
    12241280    }
    12251281
     
    14411497  ///
    14421498  inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
    1443                                       const LpSolverBase::DualExpr &b)
     1499                                          const LpSolverBase::DualExpr &b)
    14441500  {
    14451501    LpSolverBase::DualExpr tmp(a);
     
    14521508  ///
    14531509  inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
    1454                                       const LpSolverBase::DualExpr &b)
     1510                                          const LpSolverBase::DualExpr &b)
    14551511  {
    14561512    LpSolverBase::DualExpr tmp(a);
     
    14631519  ///
    14641520  inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
    1465                                       const LpSolverBase::Value &b)
     1521                                          const LpSolverBase::Value &b)
    14661522  {
    14671523    LpSolverBase::DualExpr tmp(a);
     
    14751531  ///
    14761532  inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
    1477                                       const LpSolverBase::DualExpr &b)
     1533                                          const LpSolverBase::DualExpr &b)
    14781534  {
    14791535    LpSolverBase::DualExpr tmp(b);
     
    14861542  ///
    14871543  inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
    1488                                       const LpSolverBase::Value &b)
     1544                                          const LpSolverBase::Value &b)
    14891545  {
    14901546    LpSolverBase::DualExpr tmp(a);
Note: See TracChangeset for help on using the changeset viewer.