COIN-OR::LEMON - Graph Library

Changeset 1144:1cfabf245433 in lemon-0.x


Ignore:
Timestamp:
02/10/05 19:53:30 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1545
Message:

trying to add constraints of kind 1 <= x[2]+x[3] <= 4

Location:
src/work/marci/lp
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/lp/expression.h

    r1099 r1144  
    55#include <iostream>
    66#include <map>
     7#include <limits>
    78
    89namespace lemon {
     
    120121    return os;
    121122  }
     123
     124  template <typename _Col, typename _Value>
     125  class LConstr {
     126    //  protected:
     127  public:
     128    Expr<_Col, _Value> expr;
     129    _Value lo;
     130  public:
     131    LConstr(const Expr<_Col, _Value>& _expr, _Value _lo) :
     132      expr(_expr), lo(_lo) { }
     133  };
     134 
     135  template <typename _Col, typename _Value>
     136  LConstr<_Col, _Value>
     137  operator<=(_Value lo, const Expr<_Col, _Value>& expr) {
     138    return LConstr<_Col, _Value>(expr, lo);
     139  }
     140
     141  template <typename _Col, typename _Value>
     142  class UConstr {
     143    //  protected:
     144  public:
     145    Expr<_Col, _Value> expr;
     146    _Value up;
     147  public:
     148    UConstr(const Expr<_Col, _Value>& _expr, _Value _up) :
     149      expr(_expr), up(_up) { }
     150  };
     151
     152  template <typename _Col, typename _Value>
     153  UConstr<_Col, _Value>
     154  operator<=(const Expr<_Col, _Value>& expr, _Value up) {
     155    return UConstr<_Col, _Value>(expr, up);
     156  }
     157
     158  template <typename _Col, typename _Value>
     159  class Constr {
     160    //  protected:
     161  public:
     162    Expr<_Col, _Value> expr;
     163    _Value lo, up;
     164  public:
     165    Constr(const Expr<_Col, _Value>& _expr, _Value _lo, _Value _up) :
     166      expr(_expr), lo(_lo), up(_up) { }
     167    Constr(const LConstr<_Col, _Value>& _lconstr) :
     168      expr(_lconstr.expr),
     169      lo(_lconstr.lo),
     170      up(std::numeric_limits<_Value>::infinity()) { }
     171    Constr(const UConstr<_Col, _Value>& _uconstr) :
     172      expr(_uconstr.expr),
     173      lo(-std::numeric_limits<_Value>::infinity()),
     174      up(_uconstr.up) { }
     175  };
     176
     177  template <typename _Col, typename _Value>
     178  Constr<_Col, _Value>
     179  operator<=(const LConstr<_Col, _Value>& lconstr, _Value up) {
     180    return Constr<_Col, _Value>(lconstr.expr, lconstr.lo, up);
     181  }
     182
     183  template <typename _Col, typename _Value>
     184  Constr<_Col, _Value>
     185  operator<=(_Value lo, const UConstr<_Col, _Value>& uconstr) {
     186    return Constr<_Col, _Value>(uconstr.expr, lo, uconstr.up);
     187  }
     188
     189  template <typename _Col, typename _Value>
     190  Constr<_Col, _Value>
     191  operator==(const Expr<_Col, _Value>& expr, _Value value) {
     192    return Constr<_Col, _Value>(expr, value, value);
     193  }
    122194 
    123195} //namespace lemon
  • src/work/marci/lp/lp_solver_base.h

    r1143 r1144  
    194194    typedef _Value Value;
    195195    /// \e
    196     typedef IterablePartition<int>::ClassIt RowIt;
    197     /// \e
    198     typedef IterablePartition<int>::ClassIt ColIt;
     196    typedef IterablePartition<int>::ClassIt Row;
     197    /// \e
     198    typedef IterablePartition<int>::ClassIt Col;
    199199  public:
    200200    /// \e
     
    203203    IterablePartition<int> col_iter_map;
    204204    /// \e
    205     std::vector<RowIt> int_row_map;
    206     /// \e
    207     std::vector<ColIt> int_col_map;
     205    std::vector<Row> int_row_map;
     206    /// \e
     207    std::vector<Col> int_col_map;
    208208    /// \e
    209209    const int VALID_CLASS;
     
    272272    /// \e
    273273    virtual void printDualStatus(int i) = 0;
    274     /// Returns the status of the slack variable assigned to row \c row_it.
    275     virtual int getRowStat(const RowIt& row_it) = 0;
     274    /// Returns the status of the slack variable assigned to row \c row.
     275    virtual int getRowStat(const Row& row) = 0;
    276276    /// \e
    277277    virtual void printRowStatus(int i) = 0;
    278     /// Returns the status of the variable assigned to column \c col_it.
    279     virtual int getColStat(const ColIt& col_it) = 0;
     278    /// Returns the status of the variable assigned to column \c col.
     279    virtual int getColStat(const Col& col) = 0;
    280280    /// \e
    281281    virtual void printColStatus(int i) = 0;
     
    376376
    377377    /// \e
    378     ColIt addCol() {
     378    Col addCol() {
    379379      int i=_addCol(); 
    380       ColIt col_it;
    381       col_iter_map.first(col_it, INVALID_CLASS);
    382       if (col_iter_map.valid(col_it)) { //van hasznalhato hely
    383         col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
    384         col_iter_map[col_it]=i;
     380      Col col;
     381      col_iter_map.first(col, INVALID_CLASS);
     382      if (col_iter_map.valid(col)) { //van hasznalhato hely
     383        col_iter_map.set(col, INVALID_CLASS, VALID_CLASS);
     384        col_iter_map[col]=i;
    385385      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
    386         col_it=col_iter_map.push_back(i, VALID_CLASS);
    387       }
    388       int_col_map.push_back(col_it);
    389       return col_it;
    390     }
    391     /// \e
    392     RowIt addRow() {
     386        col=col_iter_map.push_back(i, VALID_CLASS);
     387      }
     388      int_col_map.push_back(col);
     389      return col;
     390    }
     391    /// \e
     392    Row addRow() {
    393393      int i=_addRow();
    394       RowIt row_it;
    395       row_iter_map.first(row_it, INVALID_CLASS);
    396       if (row_iter_map.valid(row_it)) { //van hasznalhato hely
    397         row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
    398         row_iter_map[row_it]=i;
     394      Row row;
     395      row_iter_map.first(row, INVALID_CLASS);
     396      if (row_iter_map.valid(row)) { //van hasznalhato hely
     397        row_iter_map.set(row, INVALID_CLASS, VALID_CLASS);
     398        row_iter_map[row]=i;
    399399      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
    400         row_it=row_iter_map.push_back(i, VALID_CLASS);
    401       }
    402       int_row_map.push_back(row_it);
    403       return row_it;
    404     }
    405     /// \e
    406     void eraseCol(const ColIt& col_it) {
    407       col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
     400        row=row_iter_map.push_back(i, VALID_CLASS);
     401      }
     402      int_row_map.push_back(row);
     403      return row;
     404    }
     405    /// \e
     406    void eraseCol(const Col& col) {
     407      col_iter_map.set(col, VALID_CLASS, INVALID_CLASS);
    408408      int cols[2];
    409       cols[1]=col_iter_map[col_it];
     409      cols[1]=col_iter_map[col];
    410410      _eraseCol(cols[1]);
    411       col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
    412       ColIt it;
     411      col_iter_map[col]=0; //glpk specifikus, de kell ez??
     412      Col it;
    413413      for (col_iter_map.first(it, VALID_CLASS);
    414414           col_iter_map.valid(it); col_iter_map.next(it)) {
     
    418418    }
    419419    /// \e
    420     void eraseRow(const RowIt& row_it) {
    421       row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS);
     420    void eraseRow(const Row& row) {
     421      row_iter_map.set(row, VALID_CLASS, INVALID_CLASS);
    422422      int rows[2];
    423       rows[1]=row_iter_map[row_it];
     423      rows[1]=row_iter_map[row];
    424424      _eraseRow(rows[1]);
    425       row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
    426       RowIt it;
     425      row_iter_map[row]=0; //glpk specifikus, de kell ez??
     426      Row it;
    427427      for (row_iter_map.first(it, VALID_CLASS);
    428428           row_iter_map.valid(it); row_iter_map.next(it)) {
     
    432432    }
    433433    /// \e
    434     template <typename Begin, typename End>
    435     void setRowCoeffs(RowIt row_it, Begin begin, End end) {
    436       std::vector<std::pair<int, double> > coeffs;
    437       for ( ; begin!=end; ++begin) {
    438         coeffs.push_back(std::
    439                          make_pair(col_iter_map[begin->first], begin->second));
    440       }
    441       _setRowCoeffs(row_iter_map[row_it], coeffs);
    442     }
    443     /// \e
    444     template <typename Begin, typename End>
    445     void setColCoeffs(ColIt col_it, Begin begin, End end) {
    446       std::vector<std::pair<int, double> > coeffs;
    447       for ( ; begin!=end; ++begin) {
    448         coeffs.push_back(std::
    449                          make_pair(row_iter_map[begin->first], begin->second));
    450       }
    451       _setColCoeffs(col_iter_map[col_it], coeffs);
    452     }
    453     /// \e
    454     void setColLowerBound(ColIt col_it, _Value lo) {
    455       _setColLowerBound(col_iter_map[col_it], lo);
    456     }
    457     /// \e
    458     _Value getColLowerBound(ColIt col_it) {
    459       return _getColLowerBound(col_iter_map[col_it]);
    460     }
    461     /// \e
    462     void setColUpperBound(ColIt col_it, _Value up) {
    463       _setColUpperBound(col_iter_map[col_it], up);
    464     }
    465     /// \e
    466     _Value getColUpperBound(ColIt col_it) {     
    467       return _getColUpperBound(col_iter_map[col_it]);
    468     }
    469     /// \e
    470     void setRowLowerBound(RowIt row_it, _Value lo) {
    471       _setRowLowerBound(row_iter_map[row_it], lo);
    472     }
    473     /// \e
    474     _Value getRowLowerBound(RowIt row_it) {
    475       return _getRowLowerBound(row_iter_map[row_it]);
    476     }
    477     /// \e
    478     void setRowUpperBound(RowIt row_it, _Value up) {
    479       _setRowUpperBound(row_iter_map[row_it], up);
    480     }
    481     /// \e
    482     _Value getRowUpperBound(RowIt row_it) {     
    483       return _getRowUpperBound(row_iter_map[row_it]);
    484     }
    485     /// \e
    486     void setObjCoef(const ColIt& col_it, _Value obj_coef) {
    487       _setObjCoef(col_iter_map[col_it], obj_coef);
    488     }
    489     /// \e
    490     _Value getObjCoef(const ColIt& col_it) {
    491       return _getObjCoef(col_iter_map[col_it]);
     434    void setColLowerBound(Col col, _Value lo) {
     435      _setColLowerBound(col_iter_map[col], lo);
     436    }
     437    /// \e
     438    _Value getColLowerBound(Col col) {
     439      return _getColLowerBound(col_iter_map[col]);
     440    }
     441    /// \e
     442    void setColUpperBound(Col col, _Value up) {
     443      _setColUpperBound(col_iter_map[col], up);
     444    }
     445    /// \e
     446    _Value getColUpperBound(Col col) {     
     447      return _getColUpperBound(col_iter_map[col]);
     448    }
     449    /// \e
     450    void setRowLowerBound(Row row, _Value lo) {
     451      _setRowLowerBound(row_iter_map[row], lo);
     452    }
     453    /// \e
     454    _Value getRowLowerBound(Row row) {
     455      return _getRowLowerBound(row_iter_map[row]);
     456    }
     457    /// \e
     458    void setRowUpperBound(Row row, _Value up) {
     459      _setRowUpperBound(row_iter_map[row], up);
     460    }
     461    /// \e
     462    _Value getRowUpperBound(Row row) {     
     463      return _getRowUpperBound(row_iter_map[row]);
     464    }
     465    /// \e
     466    void setObjCoef(const Col& col, _Value obj_coef) {
     467      _setObjCoef(col_iter_map[col], obj_coef);
     468    }
     469    /// \e
     470    _Value getObjCoef(const Col& col) {
     471      return _getObjCoef(col_iter_map[col]);
    492472    }
    493473
     
    495475
    496476    /// \e
    497     _Value getPrimal(const ColIt& col_it) {
    498       return _getPrimal(col_iter_map[col_it]);
     477    _Value getPrimal(const Col& col) {
     478      return _getPrimal(col_iter_map[col]);
    499479    }   
    500480
     
    509489
    510490    /// \e
    511     typedef Expr<ColIt, _Value> Expression;
    512     /// \e
    513     typedef Expr<RowIt, _Value> DualExpression;
     491    typedef Expr<Col, _Value> Expression;
     492    /// \e
     493    typedef Expr<Row, _Value> DualExpression;
     494    /// \e
     495    typedef Constr<Col, _Value> Constraint;
    514496
    515497    //MATRIX MANIPULATING FUNCTIONS
    516498
    517499    /// \e
    518     void setRowCoeffs(RowIt row_it, const Expression& expr) {
     500    void setRowCoeffs(Row row, const Expression& expr) {
    519501      std::vector<std::pair<int, _Value> > row_coeffs;
    520502      for(typename Expression::Data::const_iterator i=expr.data.begin();
     
    523505                             (col_iter_map[(*i).first], (*i).second));
    524506      }
    525       _setRowCoeffs(row_iter_map[row_it], row_coeffs);
     507      _setRowCoeffs(row_iter_map[row], row_coeffs);
     508    }
     509    /// \e
     510    void setRow(Row row, const Constraint& constr) {
     511      setRowCoeffs(row, constr.expr);
     512      setRowLowerBound(row, constr.lo);
     513      setRowUpperBound(row, constr.up);
     514    }
     515    /// \e
     516    Row addRow(const Constraint& constr) {
     517      Row row=addRow();
     518      setRowCoeffs(row, constr.expr);
     519      setRowLowerBound(row, constr.lo);
     520      setRowUpperBound(row, constr.up);
     521      return row;
    526522    }
    527523    /// \e
    528524    /// This routine modifies \c expr by only adding to it.
    529     void getRowCoeffs(RowIt row_it, Expression& expr) {
     525    void getRowCoeffs(Row row, Expression& expr) {
    530526      std::vector<std::pair<int, _Value> > row_coeffs;
    531       _getRowCoeffs(row_iter_map[row_it], row_coeffs);
     527      _getRowCoeffs(row_iter_map[row], row_coeffs);
    532528      for(typename std::vector<std::pair<int, _Value> >::const_iterator
    533529            i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) {
     
    536532    }
    537533    /// \e
    538     void setColCoeffs(ColIt col_it, const DualExpression& expr) {
     534    void setColCoeffs(Col col, const DualExpression& expr) {
    539535      std::vector<std::pair<int, _Value> > col_coeffs;
    540536      for(typename DualExpression::Data::const_iterator i=expr.data.begin();
     
    543539                             (row_iter_map[(*i).first], (*i).second));
    544540      }
    545       _setColCoeffs(col_iter_map[col_it], col_coeffs);
     541      _setColCoeffs(col_iter_map[col], col_coeffs);
    546542    }
    547543    /// \e
    548544    /// This routine modifies \c expr by only adding to it.
    549     void getColCoeffs(ColIt col_it, DualExpression& expr) {
     545    void getColCoeffs(Col col, DualExpression& expr) {
    550546      std::vector<std::pair<int, _Value> > col_coeffs;
    551       _getColCoeffs(col_iter_map[col_it], col_coeffs);
     547      _getColCoeffs(col_iter_map[col], col_coeffs);
    552548      for(typename std::vector<std::pair<int, _Value> >::const_iterator
    553549            i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) {
     
    590586    LPGLPK() : Parent(),
    591587                        lp(lpx_create_prob()) {
    592       int_row_map.push_back(RowIt());
    593       int_col_map.push_back(ColIt());
     588      int_row_map.push_back(Row());
     589      int_col_map.push_back(Col());
    594590      lpx_set_int_parm(lp, LPX_K_DUAL, 1);
    595591    }
     
    992988      }
    993989    }
    994     /// Returns the status of the slack variable assigned to row \c row_it.
    995     int getRowStat(const RowIt& row_it) {
    996       return lpx_get_row_stat(lp, row_iter_map[row_it]);
     990    /// Returns the status of the slack variable assigned to row \c row.
     991    int getRowStat(const Row& row) {
     992      return lpx_get_row_stat(lp, row_iter_map[row]);
    997993    }
    998994    /// \e
     
    10061002      }
    10071003    }
    1008     /// Returns the status of the variable assigned to column \c col_it.
    1009     int getColStat(const ColIt& col_it) {
    1010       return lpx_get_col_stat(lp, col_iter_map[col_it]);
     1004    /// Returns the status of the variable assigned to column \c col.
     1005    int getColStat(const Col& col) {
     1006      return lpx_get_col_stat(lp, col_iter_map[col]);
    10111007    }
    10121008    /// \e
  • src/work/marci/lp/max_flow_expression.cc

    r1143 r1144  
    4747  LPSolver lp;
    4848  lp.setMaximize();
    49   typedef LPSolver::ColIt ColIt;
    50   typedef LPSolver::RowIt RowIt;
    51   typedef Graph::EdgeMap<ColIt> EdgeIndexMap;
    52   typedef Graph::NodeMap<RowIt> NodeIndexMap;
     49  typedef LPSolver::Col Col;
     50  typedef LPSolver::Row Row;
     51  typedef Graph::EdgeMap<Col> EdgeIndexMap;
     52  typedef Graph::NodeMap<Row> NodeIndexMap;
    5353  EdgeIndexMap edge_index_map(g);
    5454  NodeIndexMap node_index_map(g);
     
    5757  // nonnegativity of flow and capacity function
    5858  for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
    59     ColIt col_it=lp.addCol();
    60     edge_index_map.set(e, col_it);
     59    Col col=lp.addCol();
     60    edge_index_map.set(e, col);
    6161    // interesting property in GLPK:
    6262    // if you change the order of the following two lines, the
    6363    // two runs of GLPK are extremely different
    64       lp.setColLowerBound(col_it, 0);
    65       lp.setColUpperBound(col_it, cap[e]);
     64      lp.setColLowerBound(col, 0);
     65      lp.setColUpperBound(col, cap[e]);
    6666  }
    6767 
     
    7878    // flow conservation constraints
    7979    if ((n!=s) && (n!=t)) {
    80       RowIt row_it=lp.addRow();
    81       node_index_map.set(n, row_it);
    82       lp.setRowCoeffs(row_it, expr);
    83       lp.setRowLowerBound(row_it, 0.0);
    84       lp.setRowUpperBound(row_it, 0.0);
    85 //       cout << expr << endl;
    86 //       {
    87 //      LPSolver::Expression expr;
    88 //      lp.getRowCoeffs(node_index_map[n], expr);       
    89 //      cout << expr << endl;
    90 //       }
     80      node_index_map.set(n, lp.addRow(expr == 0.0));
    9181    }
    9282  }
    9383  lp.solveSimplex();
    94 //   cout << "num of nodes: " << countNodes(g) << endl;
    95 //   cout << "num of edges: " << countEdges(g) << endl;
    96 //   cout << "num of rows: " << lp.rowNum() << endl;
    97 //   cout << "num of rows: " << lp.int_row_map.size() << endl;
    98 //   for (int i=0; i<lp.int_row_map.size(); ++i) {
    99 //     cout << lp.int_row_map[i] << " " << endl;
    100 //   }
    101 //   cout << "num of columns: " << lp.colNum() << endl;
    102 //   cout << "num of columns: " << lp.int_col_map.size() << endl;
    103 //   for (int i=0; i<lp.int_col_map.size(); ++i) {
    104 //     cout << lp.int_col_map[i] << " " << endl;
    105 //   }
    10684  cout << "elapsed time: " << ts << endl;
    107 //   Graph::NodeIt n(g);
    108 //   ++n;
    109 //   for(Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) {
    110 //     cout << edge_index_map[e] << endl;
    111 //   }
    112 //   for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) {
    113 //     cout << edge_index_map[e] << endl;
    114 //   }
    115 //   LPSolver::DualExpression expr;
    116 //   lp.getRowCoeffs(node_index_map[n], expr);
    117 //   cout << expr << endl;
    11885}
Note: See TracChangeset for help on using the changeset viewer.