COIN-OR::LEMON - Graph Library

Changeset 2364:3a5e67bd42d2 in lemon-0.x


Ignore:
Timestamp:
02/15/07 20:15:14 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3175
Message:

Lp row and col getter function
lp section reader and writer for lemon IO

Location:
lemon
Files:
10 edited

Legend:

Unmodified
Added
Removed
  • lemon/lp_base.h

    r2363 r2364  
    5050   
    5151  public:
    52 
     52   
    5353    ///Possible outcomes of an LP solving procedure
    5454    enum SolveExitStatus {
     
    123123      friend class LpSolverBase;
    124124      friend class MipSolverBase;
     125      explicit Col(int _id) : id(_id) {}
    125126    public:
    126127      typedef Value ExprValue;
     
    166167      int id;
    167168      friend class LpSolverBase;
     169      explicit Row(int _id) : id(_id) {}
    168170    public:
    169171      typedef Value ExprValue;
     
    178180    };
    179181
     182    class RowIt : public Row {
     183      LpSolverBase *_lp;
     184    public:
     185      RowIt() {}
     186      RowIt(LpSolverBase &lp) : _lp(&lp)
     187      {
     188        _lp->rows.firstFix(id);
     189      }
     190      RowIt(const Invalid&) : Row(INVALID) {}
     191      RowIt &operator++()
     192      {
     193        _lp->rows.nextFix(id);
     194        return *this;
     195      }
     196    };
     197
    180198    static int id(const Row& row) { return row.id; }
    181199
     
    188206    int _lpId(const Row& row) const {
    189207      return rows.floatingId(id(row));
     208    }
     209
     210    Col _item(int id, Col) const {
     211      return Col(cols.fixId(id));
     212    }
     213
     214    Row _item(int id, Row) const {
     215      return Row(rows.fixId(id));
    190216    }
    191217
     
    582608  private:
    583609
    584     template <typename _Base>
    585     class MappedIterator {
     610    template <typename _Expr>
     611    class MappedOutputIterator {
    586612    public:
    587613
    588       typedef _Base Base;
     614      typedef std::insert_iterator<_Expr> Base;
     615
     616      typedef std::output_iterator_tag iterator_category;
     617      typedef void difference_type;
     618      typedef void value_type;
     619      typedef void reference;
     620      typedef void pointer;
     621     
     622      MappedOutputIterator(const Base& _base, const LpSolverBase& _lp)
     623        : base(_base), lp(_lp) {}
     624
     625      MappedOutputIterator& operator*() {
     626        return *this;
     627      }
     628
     629      MappedOutputIterator& operator=(const std::pair<int, Value>& value) {
     630        *base = std::make_pair(lp._item(value.first, typename _Expr::Key()),
     631                               value.second);
     632        return *this;
     633      }
     634
     635      MappedOutputIterator& operator++() {
     636        ++base;
     637        return *this;
     638      }
     639
     640      MappedOutputIterator operator++(int) {
     641        MappedOutputIterator tmp(*this);
     642        ++base;
     643        return tmp;
     644      }
     645
     646      bool operator==(const MappedOutputIterator& it) const {
     647        return base == it.base;
     648      }
     649
     650      bool operator!=(const MappedOutputIterator& it) const {
     651        return base != it.base;
     652      }
     653
     654    private:
     655      Base base;
     656      const LpSolverBase& lp;
     657    };
     658
     659    template <typename Expr>
     660    class MappedInputIterator {
     661    public:
     662
     663      typedef typename Expr::const_iterator Base;
    589664
    590665      typedef typename Base::iterator_category iterator_category;
     
    600675      };
    601676
    602       MappedIterator(const Base& _base, const LpSolverBase& _lp)
     677      MappedInputIterator(const Base& _base, const LpSolverBase& _lp)
    603678        : base(_base), lp(_lp) {}
    604679
     
    611686      }
    612687
    613       MappedIterator& operator++() {
     688      MappedInputIterator& operator++() {
    614689        ++base;
    615690        return *this;
    616691      }
    617692
    618       MappedIterator& operator++(int) {
    619         MappedIterator tmp(*this);
     693      MappedInputIterator operator++(int) {
     694        MappedInputIterator tmp(*this);
    620695        ++base;
    621696        return tmp;
    622697      }
    623698
    624       bool operator==(const MappedIterator& it) const {
     699      bool operator==(const MappedInputIterator& it) const {
    625700        return base == it.base;
    626701      }
    627702
    628       bool operator!=(const MappedIterator& it) const {
     703      bool operator!=(const MappedInputIterator& it) const {
    629704        return base != it.base;
    630705      }
     
    638713
    639714    /// STL compatible iterator for lp col
    640     typedef MappedIterator<Expr::const_iterator> LpRowIterator;
     715    typedef MappedInputIterator<Expr> ConstRowIterator;
    641716    /// STL compatible iterator for lp row
    642     typedef MappedIterator<DualExpr::const_iterator> LpColIterator;
     717    typedef MappedInputIterator<DualExpr> ConstColIterator;
     718
     719    /// STL compatible iterator for lp col
     720    typedef MappedOutputIterator<Expr> RowIterator;
     721    /// STL compatible iterator for lp row
     722    typedef MappedOutputIterator<DualExpr> ColIterator;
    643723
    644724    //Abstract virtual functions
     
    660740    virtual void _getColName(int col, std::string & name) = 0;
    661741    virtual void _setColName(int col, const std::string & name) = 0;
    662     virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) = 0;
    663     virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e) = 0;
     742    virtual void _setRowCoeffs(int i, ConstRowIterator b,
     743                               ConstRowIterator e) = 0;
     744    virtual void _getRowCoeffs(int i, RowIterator b) = 0;
     745    virtual void _setColCoeffs(int i, ConstColIterator b,
     746                               ConstColIterator e) = 0;
     747    virtual void _getColCoeffs(int i, ColIterator b) = 0;
    664748    virtual void _setCoeff(int row, int col, Value value) = 0;
    665749    virtual Value _getCoeff(int row, int col) = 0;
    666 
    667750    virtual void _setColLowerBound(int i, Value value) = 0;
    668751    virtual Value _getColLowerBound(int i) = 0;
     
    787870    void col(Col c,const DualExpr &e) {
    788871      e.simplify();
    789       _setColCoeffs(_lpId(c), LpColIterator(e.begin(), *this),
    790                     LpColIterator(e.end(), *this));
     872      _setColCoeffs(_lpId(c), ConstColIterator(e.begin(), *this),
     873                    ConstColIterator(e.end(), *this));
     874    }
     875
     876    ///Get a column (i.e a dual constraint) of the LP
     877
     878    ///\param r is the column to get
     879    ///\return the dual expression associated to the column
     880    DualExpr col(Col c) {
     881      DualExpr e;
     882      _getColCoeffs(_lpId(c), ColIterator(std::inserter(e, e.end()), *this));
     883      return e;
    791884    }
    792885
     
    884977    void row(Row r, Value l,const Expr &e, Value u) {
    885978      e.simplify();
    886       _setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this),
    887                     LpRowIterator(e.end(), *this));
    888        _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
     979      _setRowCoeffs(_lpId(r), ConstRowIterator(e.begin(), *this),
     980                    ConstRowIterator(e.end(), *this));
     981      _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
    889982    }
    890983
     
    896989      row(r, c.lowerBounded()?c.lowerBound():-INF,
    897990          c.expr(), c.upperBounded()?c.upperBound():INF);
     991    }
     992
     993   
     994    ///Get a row (i.e a constraint) of the LP
     995
     996    ///\param r is the row to get
     997    ///\return the expression associated to the row
     998    Expr row(Row r) {
     999      Expr e;
     1000      _getRowCoeffs(_lpId(r), RowIterator(std::inserter(e, e.end()), *this));
     1001      return e;
    8981002    }
    8991003
     
    11781282    }
    11791283
     1284    ///Get the objective function
     1285
     1286    ///\return the objective function as a linear expression of type \ref Expr.
     1287    Expr obj() {
     1288      Expr e;
     1289      for (ColIt it(*this); it != INVALID; ++it) {
     1290        double c = objCoeff(it);
     1291        if (c != 0.0) {
     1292          e.insert(std::make_pair(it, c));
     1293        }
     1294      }
     1295      return e;
     1296    }
     1297   
     1298
    11801299    ///Maximize
    11811300    void max() { _setMax(); }
  • lemon/lp_cplex.cc

    r2363 r2364  
    110110 
    111111  ///\warning Data at index 0 is ignored in the arrays.
    112   void LpCplex::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e)
     112  void LpCplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e)
    113113  {
    114114    std::vector<int> indices;
     
    116116    std::vector<Value> values;
    117117
    118     for(LpRowIterator it=b; it!=e; ++it) {
     118    for(ConstRowIterator it=b; it!=e; ++it) {
    119119      indices.push_back(it->first);
    120120      values.push_back(it->second);
     
    125125                            &rowlist[0], &indices[0], &values[0]);
    126126  }
    127  
    128   void LpCplex::_setColCoeffs(int i, LpColIterator b, LpColIterator e)
     127
     128  void LpSoplex::_getRowCoeffs(int i, RowIterator b) {
     129    /// \todo implement
     130  }
     131 
     132  void LpCplex::_setColCoeffs(int i, ConstColIterator b, ConstColIterator e)
    129133  {
    130134    std::vector<int> indices;
     
    132136    std::vector<Value> values;
    133137
    134     for(LpColIterator it=b; it!=e; ++it) {
     138    for(ConstColIterator it=b; it!=e; ++it) {
    135139      indices.push_back(it->first);
    136140      values.push_back(it->second);
     
    140144    status = CPXchgcoeflist(env, lp, values.size(),
    141145                            &indices[0], &collist[0], &values[0]);
     146  }
     147
     148  void LpSoplex::_getColCoeffs(int i, ColIterator b) {
     149    /// \todo implement
    142150  }
    143151 
  • lemon/lp_cplex.h

    r2361 r2364  
    6363    virtual void _getColName(int col,       std::string & name);
    6464    virtual void _setColName(int col, const std::string & name);
    65     virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e);
    66     virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e);
     65    virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
     66    virtual void _getRowCoeffs(int i, RowIterator b);
     67    virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
     68    virtual void _getColCoeffs(int i, ColIterator b);
    6769    virtual void _setCoeff(int row, int col, Value value);
    6870    virtual Value _getCoeff(int row, int col);
  • lemon/lp_glpk.cc

    r2363 r2364  
    127127  }
    128128 
    129   void LpGlpk::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e)
     129  void LpGlpk::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e)
    130130  {
    131131    std::vector<int> indices;
     
    135135    values.push_back(0);
    136136
    137     for(LpRowIterator it=b; it!=e; ++it) {
     137    for(ConstRowIterator it=b; it!=e; ++it) {
    138138      indices.push_back(it->first);
    139139      values.push_back(it->second);
     
    142142    lpx_set_mat_row(lp, i, values.size() - 1, &indices[0], &values[0]);
    143143  }
    144  
    145   void LpGlpk::_setColCoeffs(int i, LpColIterator b, LpColIterator e) {
     144
     145  void LpGlpk::_getRowCoeffs(int i, RowIterator b)
     146  {
     147    int length = lpx_get_mat_row(lp, i, 0, 0);
     148   
     149    std::vector<int> indices(length + 1);
     150    std::vector<Value> values(length + 1);
     151   
     152    lpx_get_mat_row(lp, i, &indices[0], &values[0]);
     153   
     154    for (int i = 1; i <= length; ++i) {
     155      *b = std::make_pair(indices[i], values[i]);
     156      ++b;
     157    }
     158  }
     159 
     160  void LpGlpk::_setColCoeffs(int i, ConstColIterator b, ConstColIterator e) {
    146161
    147162    std::vector<int> indices;
     
    151166    values.push_back(0);
    152167
    153     for(LpColIterator it=b; it!=e; ++it) {
     168    for(ConstColIterator it=b; it!=e; ++it) {
    154169      indices.push_back(it->first);
    155170      values.push_back(it->second);
     
    159174  }
    160175
     176  void LpGlpk::_getColCoeffs(int i, ColIterator b)
     177  {
     178    int length = lpx_get_mat_col(lp, i, 0, 0);
     179   
     180    std::vector<int> indices(length + 1);
     181    std::vector<Value> values(length + 1);
     182   
     183    lpx_get_mat_col(lp, i, &indices[0], &values[0]);
     184   
     185    for (int i = 1; i <= length; ++i) {
     186      *b = std::make_pair(indices[i], values[i]);
     187      ++b;
     188    }
     189  }
    161190
    162191  void LpGlpk::_setCoeff(int row, int col, Value value)
     
    224253    int length=lpx_get_mat_row(lp, row, 0, 0);
    225254   
    226     std::vector<int> indices(length + 2);
    227     std::vector<Value> values(length + 2);
     255    std::vector<int> indices(length + 1);
     256    std::vector<Value> values(length + 1);
    228257   
    229258    lpx_get_mat_row(lp, row, &indices[0], &values[0]);
  • lemon/lp_glpk.h

    r2328 r2364  
    5858    virtual void _getColName(int col,       std::string & name);
    5959    virtual void _setColName(int col, const std::string & name);
    60     virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e);
    61     virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e);
     60    virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
     61    virtual void _getRowCoeffs(int i, RowIterator b);
     62    virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
     63    virtual void _getColCoeffs(int i, ColIterator b);
    6264    virtual void _setCoeff(int row, int col, Value value);
    6365    virtual Value _getCoeff(int row, int col);
  • lemon/lp_skeleton.cc

    r2328 r2364  
    5959 
    6060 
    61   void LpSkeleton::_setRowCoeffs(int, LpRowIterator, LpRowIterator) {
     61  void LpSkeleton::_setRowCoeffs(int, ConstRowIterator, ConstRowIterator) {
     62  }
     63
     64  void LpSkeleton::_getRowCoeffs(int, RowIterator) {
    6265  }
    6366 
    64   void LpSkeleton::_setColCoeffs(int, LpColIterator, LpColIterator) {
     67  void LpSkeleton::_setColCoeffs(int, ConstColIterator, ConstColIterator) {
     68  }
     69
     70  void LpSkeleton::_getColCoeffs(int, ColIterator) {
    6571  }
    6672
  • lemon/lp_skeleton.h

    r2363 r2364  
    5050
    5151    /// \e
    52     virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e);
     52    virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
    5353    /// \e
    54     virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e);
     54    virtual void _getRowCoeffs(int i, RowIterator b);
     55    /// \e
     56    virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
     57    /// \e
     58    virtual void _getColCoeffs(int i, ColIterator b);
    5559   
    5660    /// Set one element of the coefficient matrix
  • lemon/lp_soplex.cc

    r2363 r2364  
    100100 
    101101
    102   void LpSoplex::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) {
     102  void LpSoplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e) {
    103103    for (int j = 0; j < soplex->nCols(); ++j) {
    104104      soplex->changeElement(i, j, 0.0);
    105105    }
    106     for(LpRowIterator it = b; it != e; ++it) {
     106    for(ConstRowIterator it = b; it != e; ++it) {
    107107      soplex->changeElement(i, it->first, it->second);
    108108    }
    109109    solved = false;
    110110  }
    111  
    112   void LpSoplex::_setColCoeffs(int j, LpColIterator b, LpColIterator e) {
     111
     112  void LpSoplex::_getRowCoeffs(int i, RowIterator b) {
     113    const soplex::SVector& vec = soplex->rowVector(i);
     114    for (int k = 0; k < vec.size(); ++k) {
     115      *b = std::make_pair(vec.index(k), vec.value(k));
     116      ++b;
     117    }
     118  }
     119 
     120  void LpSoplex::_setColCoeffs(int j, ConstColIterator b, ConstColIterator e) {
    113121    for (int i = 0; i < soplex->nRows(); ++i) {
    114122      soplex->changeElement(i, j, 0.0);
    115123    }
    116     for(LpColIterator it = b; it != e; ++it) {
     124    for(ConstColIterator it = b; it != e; ++it) {
    117125      soplex->changeElement(it->first, j, it->second);
    118126    }
    119127    solved = false;
     128  }
     129
     130  void LpSoplex::_getColCoeffs(int i, ColIterator b) {
     131    const soplex::SVector& vec = soplex->colVector(i);
     132    for (int k = 0; k < vec.size(); ++k) {
     133      *b = std::make_pair(vec.index(k), vec.value(k));
     134      ++b;
     135    }
    120136  }
    121137 
  • lemon/lp_soplex.h

    r2363 r2364  
    7373    virtual void _getColName(int col, std::string & name);
    7474    virtual void _setColName(int col, const std::string & name);
    75     virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e);
    76     virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e);
     75    virtual void _setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e);
     76    virtual void _getRowCoeffs(int i, RowIterator b);
     77    virtual void _setColCoeffs(int i, ConstColIterator b, ConstColIterator e);
     78    virtual void _getColCoeffs(int i, ColIterator b);
    7779    virtual void _setCoeff(int row, int col, Value value);
    7880    virtual Value _getCoeff(int row, int col);
  • lemon/lp_utils.h

    r2363 r2364  
    6969  private:
    7070
     71    enum SubSection {
     72      CONSTRAINTS, BOUNDS, OBJECTIVE
     73    };
     74
    7175    enum Relation {
    7276      LE, EQ, GE
    7377    };
    7478
    75     std::istream& readConstraint(std::istream& is, LpSolverBase::Constr& c) {
     79    std::istream& readConstraint(std::istream& is) {
     80      LpSolverBase::Constr c;
    7681      char x;
    7782      LpSolverBase::Expr e1, e2;
     
    8388      is >> std::ws;
    8489      readExpression(is, e2);
     90      is >> std::ws;
    8591      if (!is.get(x)) {
    8692        if (op1 == LE) {
     93          if (e1.size() == 0) {
     94            c = e2 >= e1;
     95          } else {
     96            c = e1 <= e2;
     97          }
    8798          c = e1 <= e2;
    8899        } else if (op1 == GE) {
    89           c = e1 >= e2;
    90         } else {
    91           c = e1 == e2;
     100          if (e1.size() == 0) {
     101            c = e2 <= e1;
     102          } else {
     103            c = e1 >= e2;
     104          }
     105        } else {
     106          if (e1.size() == 0) {
     107            c = e2 == e1;
     108          } else {
     109            c = e1 == e2;
     110          }
    92111        }
    93112      } else {
     
    109128          c = e1.constComp() >= e2 >= e3.constComp();
    110129        }
    111       }
     130        is >> std::ws;
     131        if (is.get(x)) {
     132          throw DataFormatError("Wrong variable bounds format");
     133        }
     134      }
     135      lp.addRow(c);
     136      return is;
     137    }
     138
     139    std::istream& readObjective(std::istream& is) {
     140      is >> std::ws;
     141      std::string sense;
     142      is >> sense;
     143      if (sense != "min" && sense != "max") {
     144        throw DataFormatError("Wrong objective function format");
     145      }
     146      LpSolverBase::Expr expr;
     147      is >> std::ws;
     148      readExpression(is, expr);
     149      lp.setObj(expr);
     150      if (sense == "min") {
     151        lp.min();
     152      } else {
     153        lp.max();
     154      }
     155      return is;
     156    }
     157
     158    std::istream& readBounds(std::istream& is) {
     159      LpSolverBase::Col c;
     160      char x;
     161      is >> std::ws;
     162      if (!is.get(x)) {
     163        throw DataFormatError("Wrong variable bounds format");
     164      }
     165      if (varFirstChar(x)) {
     166        is.putback(x);
     167        readCol(is, c);
     168        is >> std::ws;
     169        Relation op1;
     170        readRelation(is, op1);
     171        double v;
     172        readNum(is, v);
     173        if (op1 == EQ) {
     174          lp.colLowerBound(c, v);
     175          lp.colUpperBound(c, v);
     176        } else if (op1 == LE) {
     177          lp.colUpperBound(c, v);
     178        } else {
     179          lp.colLowerBound(c, v);
     180        }
     181        is >> std::ws;
     182        if (is.get(x)) {
     183          throw DataFormatError("Wrong variable bounds format");
     184        }
     185      } else {
     186        is.putback(x);
     187        double v;
     188        readNum(is, v);
     189        is >> std::ws;
     190        Relation op1;
     191        readRelation(is, op1);
     192        is >> std::ws;
     193        readCol(is, c);
     194        is >> std::ws;
     195        if (is.get(x)) {
     196          is.putback(x);
     197          is >> std::ws;
     198          Relation op2;
     199          readRelation(is, op2);
     200          double w;
     201          is >> std::ws;
     202          readNum(is, w);
     203          if (op2 != op1 || op1 == EQ) {
     204            throw DataFormatError("Wrong range format");
     205          }
     206          if (op1 == LE) {
     207            lp.colLowerBound(c, v);
     208            lp.colUpperBound(c, w);
     209          } else {
     210            lp.colLowerBound(c, w);
     211            lp.colUpperBound(c, v);
     212          }
     213          if (is.get(x)) {
     214            throw DataFormatError("Wrong variable bounds format");
     215          }
     216        } else {
     217          if (op1 == EQ) {
     218            lp.colLowerBound(c, v);
     219            lp.colUpperBound(c, v);
     220          } else if (op1 == LE) {
     221            lp.colLowerBound(c, v);
     222          } else {
     223            lp.colUpperBound(c, v);
     224          }
     225        }
     226      }
     227      return is;
    112228    }
    113229
     
    278394    static bool varChar(char c) {
    279395      return (c >= '0' && c <= '9') ||
    280         (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    281     }
    282 
    283 
    284     void addConstraint(const LpSolverBase::Constr& constr) {
    285       if (constr.expr().size() != 1) {
    286         lp.addRow(constr);
    287       } else {
    288         Lp::Expr e = constr.expr();
    289         LpSolverBase::Col col = e.begin()->first;
    290         double coeff = e.begin()->second;
    291         double lb = LpSolverBase::NaN;
    292         double ub = LpSolverBase::NaN;
    293         if (coeff > 0) {
    294           if (constr.upperBounded()) {
    295             lb = (constr.lowerBound() - e.constComp()) / coeff;
    296           }
    297           if (constr.lowerBounded()) {
    298             ub = (constr.upperBound() - e.constComp()) / coeff;
    299           }
    300         } else if (coeff < 0) {
    301           if (constr.upperBounded()) {
    302             lb = (constr.upperBound() - e.constComp()) / coeff;
    303           }
    304           if (constr.lowerBounded()) {
    305             ub = (constr.lowerBound() - e.constComp()) / coeff;
    306           }
    307         } else {
    308           lb = -LpSolverBase::INF;
    309           ub = LpSolverBase::INF;
    310         }
    311         lp.colLowerBound(col, lb);
    312         lp.colUpperBound(col, ub);
    313       }
     396        (c >= 'a' && c <= 'z') ||
     397        (c >= 'A' && c <= 'Z') ||
     398        c == '[' || c == ']';
    314399    }
    315400   
     
    321406    virtual void read(std::istream& is) {
    322407      std::string line;
     408      SubSection sub = CONSTRAINTS;
    323409      while (getline(is, line)) {
    324410        std::istringstream ls(line);
    325         std::string sense;
    326         ls >> sense;
    327         if (sense == "min" || sense == "max") {
    328           LpSolverBase::Expr expr;
    329           ls >> std::ws;
    330           readExpression(ls, expr);
    331           lp.setObj(expr);
    332           if (sense == "min") {
    333             lp.min();
    334           } else {
    335             lp.max();
    336           }
     411        std::string type;
     412        ls >> type;
     413        if (type == "constraints") {
     414          sub = CONSTRAINTS;
     415        } else if (type == "bounds") {
     416          sub = BOUNDS;
     417        } else if (type == "objective") {
     418          sub = OBJECTIVE;
    337419        } else {
    338420          ls.str(line);
    339           LpSolverBase::Constr constr;
    340           ls >> std::ws;
    341           readConstraint(ls, constr);
    342           addConstraint(constr);
     421          switch (sub) {
     422          case CONSTRAINTS:
     423            readConstraint(ls);
     424            break;
     425          case BOUNDS:
     426            readBounds(ls);
     427            break;
     428          case OBJECTIVE:
     429            readObjective(ls);
     430            break;
     431          }
    343432        }       
    344433      }
     
    361450
    362451
    363 //   class LpWriter : public LemonWriter::SectionWriter {
    364 //     typedef LemonWriter::SectionWriter Parent;
    365 //   public:
    366 
    367 
    368 //     /// \brief Constructor.
    369 //     ///
    370 //     /// Constructor for LpWriter. It creates the LpWriter and attach
    371 //     /// it into the given LemonWriter. The lp writer will add
    372 //     /// variables, constraints and objective function to the
    373 //     /// given lp solver.
    374 //     LpWriter(LemonWriter& _writer, LpSolverBase& _lp,
    375 //              const std::string& _name = std::string())
    376 //       : Parent(_writer), lp(_lp), name(_name) {}
    377 
    378 
    379 //     /// \brief Destructor.
    380 //     ///
    381 //     /// Destructor for NodeSetWriter.
    382 //     virtual ~LpWriter() {}
    383 
    384 //   private:
    385 //     LpWriter(const LpWriter&);
    386 //     void operator=(const LpWriter&);
     452  class LpWriter : public LemonWriter::SectionWriter {
     453    typedef LemonWriter::SectionWriter Parent;
     454  public:
     455
     456
     457    /// \brief Constructor.
     458    ///
     459    /// Constructor for LpWriter. It creates the LpWriter and attach
     460    /// it into the given LemonWriter. The lp writer will add
     461    /// variables, constraints and objective function to the
     462    /// given lp solver.
     463    LpWriter(LemonWriter& _writer, LpSolverBase& _lp,
     464             const std::string& _name = std::string())
     465      : Parent(_writer), lp(_lp), name(_name) {}
     466
     467
     468    /// \brief Destructor.
     469    ///
     470    /// Destructor for NodeSetWriter.
     471    virtual ~LpWriter() {}
     472
     473  private:
     474    LpWriter(const LpWriter&);
     475    void operator=(const LpWriter&);
    387476 
    388 //   protected:
    389 
    390 //     /// \brief Gives back true when the SectionWriter can process
    391 //     /// the section with the given header line.
    392 //     ///
    393 //     /// It gives back the header line of the \c \@lp section.
    394 //     virtual std::string header() {
    395 //       std::ostringstream ls(line);
    396 //       ls << "@lp " << name;
    397 //       return ls.str();
    398 //     }
    399 
    400 //   private:
    401 
    402 //     std::ostream& writeConstraint(std::ostream& is, LpSolverBase::Constr& c) {
    403 //       char x;
    404 
     477  protected:
     478
     479    /// \brief Gives back true when the SectionWriter can process
     480    /// the section with the given header line.
     481    ///
     482    /// It gives back the header line of the \c \@lp section.
     483    virtual std::string header() {
     484      std::ostringstream ls;
     485      ls << "@lp " << name;
     486      return ls.str();
     487    }
     488
     489  private:
     490
     491    void createCols() {
     492      int num = 1;
     493
     494      std::map<std::string, LpSolverBase::Col> inverse;
     495
     496      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
     497        std::string name = lp.colName(it);
     498        if (!name.empty() && inverse.find(name) == inverse.end()) {
     499          cols.insert(std::make_pair(it, name));
     500          inverse.insert(std::make_pair(name, it));
     501        } else {
     502          std::ostringstream ls;
     503          ls << "var" << num;
     504          ++num;
     505          cols.insert(std::make_pair(it, ls.str()));
     506          inverse.insert(std::make_pair(ls.str(), it));
     507        }
     508      }
     509    }
     510   
     511    void writeExpression(std::ostream& os, const LpSolverBase::Expr& e) {
     512      bool first = true;
     513      for (LpSolverBase::Expr::const_iterator jt = e.begin();
     514           jt != e.end(); ++jt) {
     515        if (jt->second < 0.0) {
     516          os << "- ";
     517          if (jt->second != -1.0) {
     518            os << -jt->second << " * ";
     519          }
     520        } else if (jt->second > 0.0) {
     521          if (!first) {
     522            os << "+ ";
     523          }
     524          if (jt->second != 1.0) {
     525            os << jt->second << " * ";
     526          }         
     527        }
     528        first = false;
     529        os << cols[jt->first] << " ";
     530      }
     531      if (e.constComp() < 0.0) {
     532        os << "- " << -e.constComp() << " ";
     533      } else if (e.constComp() > 0.0) {
     534        if (!first) {
     535          os << "+ ";
     536        }
     537        os << e.constComp() << " ";
     538      }
     539    }
     540
     541  protected:
     542
     543    /// \brief Writer function of the section.
     544    ///
     545    /// It writes the content of the section.
     546    virtual void write(std::ostream& os) {
     547      createCols();
     548
     549      os << "constraints" << std::endl;
    405550     
    406 //       LpSolverBase::Expr e1, e2;
    407 //       Relation op1;
    408 //       is >> std::ws;
    409 //       writexpression(is, e1);
    410 //       is >> std::ws;
    411 //       writeRelation(is, op1);
    412 //       is >> std::ws;
    413 //       writexpression(is, e2);
    414 //       if (!is.get(x)) {
    415 //         if (op1 == LE) {
    416 //           c = e1 <= e2;
    417 //         } else if (op1 == GE) {
    418 //           c = e1 >= e2;
    419 //         } else {
    420 //           c = e1 == e2;
    421 //         }
    422 //       } else {
    423 //         is.putback(x);
    424 //         LpSolverBase::Expr e3;
    425 //         Relation op2;
    426 //         writeRelation(is, op2);
    427 //         is >> std::ws;
    428 //         writexpression(is, e3);
    429 //         if (!e1.empty() || !e3.empty()) {
    430 //           throw DataFormatError("Wrong range format");
    431 //         }
    432 //         if (op2 != op1 || op1 == EQ) {
    433 //           throw DataFormatError("Wrong range format");
    434 //         }
    435 //         if (op1 == LE) {
    436 //           c = e1.constComp() <= e2 <= e3.constComp();
    437 //         } else {
    438 //           c = e1.constComp() >= e2 >= e3.constComp();
    439 //         }
    440 //       }
    441 //     }
    442 
    443 //     std::ostream& writexpression(std::ostream& is, LpSolverBase::Expr& e) {
    444 //       LpSolverBase::Col c;
    445 //       double d;
    446 //       char x;
    447 //       writelement(is, c, d);
    448 //       if (c != INVALID) {
    449 //         e += d * c;
    450 //       } else {
    451 //         e += d;
    452 //       }
    453 //       is >> std::ws;
    454 //       while (is.get(x) && (x == '+' || x == '-')) {
    455 //         is >> std::ws;
    456 //         writelement(is, c, d);
    457 //         if (c != INVALID) {
    458 //           e += (x == '+' ? d : -d) * c;
    459 //         } else {
    460 //           e += (x == '+' ? d : -d);
    461 //         }
    462 //         is >> std::ws;
    463 //       }
    464 //       if (!is) {
    465 //         is.clear();
    466 //       } else {
    467 //         is.putback(x);
    468 //       }
    469 //       return is;
    470 //     }
    471 
    472 //     std::ostream& writelement(std::ostream& is,
    473 //                               LpSolverBase::Col& c, double& d) {
    474 //       d = 1.0;
    475 //       c = INVALID;
    476 //       char x, y;
    477 //       if (!is.get(x)) throw DataFormatError("Cannot find lp element");
    478 //       if (x == '+' || x == '-') {
    479 //         is >> std::ws;
    480 //         d *= x == '-' ? -1 : 1;
    481 //         while (is.get(x) && (x == '+' || x == '-')) {
    482 //           d *= x == '-' ? -1 : 1;
    483 //           is >> std::ws;
    484 //         }
    485 //         if (!is) throw DataFormatError("Cannot find lp element");
    486 //       }
    487 //       if (numFirstChar(x)) {
    488 //         is.putback(x);
    489 //         double e;
    490 //         writeNum(is, e);
    491 //         d *= e;
    492 //       } else if (varFirstChar(x)) {
    493 //         is.putback(x);
    494 //         LpSolverBase::Col f;
    495 //         writeCol(is, f);
    496 //         c = f;
    497 //       } else {
    498 //         throw DataFormatError("Invalid expression format");         
    499 //       }
    500 //       is >> std::ws;
    501 //       while (is.get(y) && (y == '*' || y == '/')) {
    502 //         is >> std::ws;
    503 //         if (!is.get(x)) throw DataFormatError("Cannot find lp element");
    504 //         if (x == '+' || x == '-') {
    505 //           is >> std::ws;
    506 //           d *= x == '-' ? -1 : 1;
    507 //           while (is.get(x) && (x == '+' || x == '-')) {
    508 //             d *= x == '-' ? -1 : 1;
    509 //             is >> std::ws;
    510 //           }
    511 //           if (!is) throw DataFormatError("Cannot find lp element");
    512 //         }
    513 //         if (numFirstChar(x)) {
    514 //           is.putback(x);
    515 //           double e;
    516 //           writeNum(is, e);
    517 //           if (y == '*') {
    518 //             d *= e;
    519 //           } else {
    520 //             d /= e;
    521 //           }
    522 //         } else if (varFirstChar(x)) {
    523 //           is.putback(x);
    524 //           LpSolverBase::Col f;
    525 //           writeCol(is, f);
    526 //           if (y == '*') {
    527 //             if (c == INVALID) {
    528 //               c = f;
    529 //             } else {
    530 //               throw DataFormatError("Quadratic element in expression");
    531 //             }
    532 //           } else {
    533 //             throw DataFormatError("Division by variable");
    534 //           }
    535 //         } else {
    536 //           throw DataFormatError("Invalid expression format");         
    537 //         }
    538 //         is >> std::ws;
    539 //       }
    540 //       if (!is) {
    541 //         is.clear();
    542 //       } else {
    543 //         is.putback(y);
    544 //       }
    545 //       return is;
    546 //     }
    547 
    548 //     std::ostream& writeCol(std::ostream& is, LpSolverBase::Col& c) {
    549 //       char x;
    550 //       std::string var;
    551 //       while (is.get(x) && varChar(x)) {
    552 //         var += x;
    553 //       }
    554 //       if (!is) {
    555 //         is.clear();
    556 //       } else {
    557 //         is.putback(x);
    558 //       }
    559 //       ColMap::const_iterator it = cols.find(var);
    560 //       if (cols.find(var) != cols.end()) {
    561 //         c = it->second;
    562 //       } else {
    563 //         c = lp.addCol();
    564 //         cols.insert(std::make_pair(var, c));
    565 //         lp.colName(c, var);
    566 //       }
    567 //       return is;
    568 //     }
    569 
    570 //     std::ostream& writeNum(std::ostream& is, double& d) {
    571 //       is >> d;
    572 //       if (!is) throw DataFormatError("Wrong number format");
    573 //       return is;
    574 //     }
    575 
    576 //     std::ostream& writeRelation(std::ostream& is, Relation& op) {
    577 //       char x, y;
    578 //       if (!is.get(x) || !(x == '<' || x == '=' || x == '>')) {
    579 //         throw DataFormatError("Wrong relation operator");
    580 //       }
    581 //       if (!is.get(y) || y != '=') {
    582 //         throw DataFormatError("Wrong relation operator");
    583 //       }
    584 //       switch (x) {
    585 //       case '<': op = LE;
    586 //         break;
    587 //       case '=': op = EQ;
    588 //         break;
    589 //       case '>': op = GE;
    590 //         break;
    591 //       }
    592 //       return is;
    593 //     }
    594 
    595 //     static bool relationFirstChar(char c) {
    596 //       return c == '<' || c == '=' || c == '>';
    597 //     }
    598 
    599 //     static bool varFirstChar(char c) {
    600 //       return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    601 //     }
    602 
    603 //     static bool numFirstChar(char c) {
    604 //       return (c >= '0' && c <= '9') || c == '.';
    605 //     }
    606 
    607 //     static bool varChar(char c) {
    608 //       return (c >= '0' && c <= '9') ||
    609 //         (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    610 //     }
    611 
    612 
    613 //     void addConstraint(const LpSolverBase::Constr& constr) {
    614 //       if (constr.expr().size() != 1) {
    615 //         lp.addRow(constr);
    616 //       } else {
    617 //         Lp::Expr e = constr.expr();
    618 //         LpSolverBase::Col col = e.begin()->first;
    619 //         double coeff = e.begin()->second;
    620 //         double lb = LpSolverBase::NaN;
    621 //         double ub = LpSolverBase::NaN;
    622 //         if (coeff > 0) {
    623 //           if (constr.upperBounded()) {
    624 //             lb = (constr.lowerBound() - e.constComp()) / coeff;
    625 //           }
    626 //           if (constr.lowerBounded()) {
    627 //             ub = (constr.upperBound() - e.constComp()) / coeff;
    628 //           }
    629 //         } else if (coeff < 0) {
    630 //           if (constr.upperBounded()) {
    631 //             lb = (constr.upperBound() - e.constComp()) / coeff;
    632 //           }
    633 //           if (constr.lowerBounded()) {
    634 //             ub = (constr.lowerBound() - e.constComp()) / coeff;
    635 //           }
    636 //         } else {
    637 //           lb = -LpSolverBase::INF;
    638 //           ub = LpSolverBase::INF;
    639 //         }
    640 //         lp.colLowerBound(col, lb);
    641 //         lp.colUpperBound(col, ub);
    642 //       }
    643 //     }
    644    
    645 //   protected:
    646 
    647 //     /// \brief Writer function of the section.
    648 //     ///
    649 //     /// It writes the content of the section.
    650 //     virtual void write(std::ostream& is) {
    651 //       std::string line;
    652 //       std::map<std::string, LpSolverBase::Col> vars;
    653 //       while (getline(is, line)) {
    654 //         std::istringstream ls(line);
    655 //         std::string sense;
    656 //         ls >> sense;
    657 //         if (sense == "min" || sense == "max") {
    658 //           LpSolverBase::Expr expr;
    659 //           ls >> std::ws;
    660 //           writeExpression(ls, expr);
    661 //           lp.setObj(expr);
    662 //           if (sense == "min") {
    663 //             lp.min();
    664 //           } else {
    665 //             lp.max();
    666 //           }
    667 //         } else {
    668 //           ls.str(line);
    669 //           LpSolverBase::Constr constr;
    670 //           ls >> std::ws;
    671 //           writeConstraint(ls, constr);
    672 //           addConstraint(constr);
    673 //         }       
    674 //       }
    675 //     }
     551      for (LpSolverBase::RowIt it(lp); it != INVALID; ++it) {
     552        double lower, upper;
     553        lp.getRowBounds(it, lower, upper);
     554        if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
     555          continue;
     556        os << "   ";
     557       
     558        if (lower != upper) {
     559          if (lower != -LpSolverBase::INF) {
     560            os << lower << " <= ";
     561          }
     562         
     563          writeExpression(os, lp.row(it));
     564         
     565          if (upper != LpSolverBase::INF) {
     566            os << "<= " << upper << " ";
     567          }
     568        } else {
     569
     570          writeExpression(os, lp.row(it));
     571          os << "== " << upper << " ";
     572         
     573        }
     574
     575        os << std::endl;
     576      }
     577
     578      os << "bounds" << std::endl;
    676579     
    677 //     virtual void missing() {
    678 //       ErrorMessage msg;
    679 //       msg << "Lp section not found in file: @lp " << name;
    680 //       throw IoParameterError(msg.message());
    681 //     }
    682 
    683 //   private:
    684 
    685 //     typedef std::map<std::string, LpSolverBase::Col> ColMap;
     580      for (LpSolverBase::ColIt it(lp); it != INVALID; ++it) {
     581        double lower = lp.colLowerBound(it);
     582        double upper = lp.colUpperBound(it);
     583        if (lower == -LpSolverBase::INF && upper == LpSolverBase::INF)
     584          continue;
     585        os << "   ";
     586
     587        if (lower != upper) {
     588          if (lower != -LpSolverBase::INF) {
     589            os << lower << " <= ";
     590          }
     591         
     592          os << cols[it] << " ";
     593         
     594          if (upper != LpSolverBase::INF) {
     595            os << "<= " << upper << " ";
     596          }
     597        } else {
     598          os << cols[it] << " == " << upper << " ";
     599        }
     600        os << std::endl;
     601      }
     602
     603      os << "objective" << std::endl;
     604      os << "   ";
     605      if (lp.is_min()) {
     606        os << "min ";
     607      } else {
     608        os << "max ";
     609      }
     610      writeExpression(os, lp.obj());
     611      os << std::endl;
     612    }
    686613     
    687 //     LpSolverBase& lp;
    688 //     std::string name;
    689 //     ColMap cols;
    690 //   };
     614
     615  private:
     616
     617    typedef std::map<LpSolverBase::Col, std::string> ColMap;
     618     
     619    LpSolverBase& lp;
     620    std::string name;
     621    ColMap cols;
     622  };
    691623
    692624}
Note: See TracChangeset for help on using the changeset viewer.