COIN-OR::LEMON - Graph Library

Changeset 1142:4764031c082c in lemon


Ignore:
Timestamp:
05/06/12 16:52:11 (12 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.2
Parents:
1127:be7dd3a8d6a3 (diff), 1140:8d281761dea4 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge bugfix #441 to branch 1.2

Files:
14 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/solver_bits.h

    r956 r1142  
    4545      void clear() {
    4646        first_item = -1;
     47        last_item = -1;
    4748        first_free_item = -1;
    4849        items.clear();
  • lemon/bits/solver_bits.h

    r1140 r1142  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
  • lemon/cbc.cc

    r1122 r1142  
    436436
    437437    _prob = new CoinModel();
    438     rows.clear();
    439     cols.clear();
    440438  }
    441439
  • lemon/cbc.cc

    r1140 r1142  
    9090  }
    9191
     92  int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
     93    std::vector<int> indexes;
     94    std::vector<Value> values;
     95
     96    for(ExprIterator it = b; it != e; ++it) {
     97      indexes.push_back(it->first);
     98      values.push_back(it->second);
     99    }
     100
     101    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
     102    return _prob->numberRows() - 1;
     103  }
    92104
    93105  void CbcMip::_eraseCol(int i) {
  • lemon/clp.cc

    r956 r1142  
    438438    delete _prob;
    439439    _prob = new ClpSimplex();
    440     rows.clear();
    441     cols.clear();
    442440    _col_names_ref.clear();
    443441    _clear_temporals();
  • lemon/clp.cc

    r1140 r1142  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    7676  int ClpLp::_addRow() {
    7777    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
     78    return _prob->numberRows() - 1;
     79  }
     80
     81  int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
     82    std::vector<int> indexes;
     83    std::vector<Value> values;
     84
     85    for(ExprIterator it = b; it != e; ++it) {
     86      indexes.push_back(it->first);
     87      values.push_back(it->second);
     88    }
     89
     90    _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u);
    7891    return _prob->numberRows() - 1;
    7992  }
  • lemon/cplex.cc

    r956 r1142  
    471471    int status;
    472472    _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
    473     rows.clear();
    474     cols.clear();
    475473  }
    476474
  • lemon/cplex.cc

    r1140 r1142  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    112112  }
    113113
     114  int CplexBase::_addRow(Value lb, ExprIterator b,
     115                         ExprIterator e, Value ub) {
     116    int i = CPXgetnumrows(cplexEnv(), _prob);
     117    if (lb == -INF) {
     118      const char s = 'L';
     119      CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
     120    } else if (ub == INF) {
     121      const char s = 'G';
     122      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
     123    } else if (lb == ub){
     124      const char s = 'E';
     125      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
     126    } else {
     127      const char s = 'R';
     128      double len = ub - lb;
     129      CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
     130    }
     131
     132    std::vector<int> indices;
     133    std::vector<int> rowlist;
     134    std::vector<Value> values;
     135
     136    for(ExprIterator it=b; it!=e; ++it) {
     137      indices.push_back(it->first);
     138      values.push_back(it->second);
     139      rowlist.push_back(i);
     140    }
     141
     142    CPXchgcoeflist(cplexEnv(), _prob, values.size(),
     143                   &rowlist.front(), &indices.front(), &values.front());
     144
     145    return i;
     146  }
    114147
    115148  void CplexBase::_eraseCol(int i) {
     
    455488
    456489  void CplexBase::_applyMessageLevel() {
    457     CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 
     490    CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND,
    458491                   _message_enabled ? CPX_ON : CPX_OFF);
    459492  }
  • lemon/glpk.cc

    r956 r1142  
    557557  void GlpkBase::_clear() {
    558558    glp_erase_prob(lp);
    559     rows.clear();
    560     cols.clear();
    561559  }
    562560
  • lemon/glpk.cc

    r1140 r1142  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    5757    int i = glp_add_rows(lp, 1);
    5858    glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0);
     59    return i;
     60  }
     61
     62  int GlpkBase::_addRow(Value lo, ExprIterator b,
     63                        ExprIterator e, Value up) {
     64    int i = glp_add_rows(lp, 1);
     65
     66    if (lo == -INF) {
     67      if (up == INF) {
     68        glp_set_row_bnds(lp, i, GLP_FR, lo, up);
     69      } else {
     70        glp_set_row_bnds(lp, i, GLP_UP, lo, up);
     71      }
     72    } else {
     73      if (up == INF) {
     74        glp_set_row_bnds(lp, i, GLP_LO, lo, up);
     75      } else if (lo != up) {
     76        glp_set_row_bnds(lp, i, GLP_DB, lo, up);
     77      } else {
     78        glp_set_row_bnds(lp, i, GLP_FX, lo, up);
     79      }
     80    }
     81
     82    std::vector<int> indexes;
     83    std::vector<Value> values;
     84
     85    indexes.push_back(0);
     86    values.push_back(0);
     87
     88    for(ExprIterator it = b; it != e; ++it) {
     89      indexes.push_back(it->first);
     90      values.push_back(it->second);
     91    }
     92
     93    glp_set_mat_row(lp, i, values.size() - 1,
     94                    &indexes.front(), &values.front());
    5995    return i;
    6096  }
  • lemon/lp_base.h

    r1100 r1142  
    15571557
    15581558    ///Clears the problem
    1559     void clear() { _clear(); }
     1559    void clear() { _clear(); rows.clear(); cols.clear(); }
    15601560
    15611561    /// Sets the message level of the solver
  • lemon/lp_base.h

    r1140 r1142  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    8383      MESSAGE_VERBOSE
    8484    };
    85    
     85
    8686
    8787    ///The floating point type used by the solver
     
    115115      typedef True LpCol;
    116116      /// Default constructor
    117      
     117
    118118      /// \warning The default constructor sets the Col to an
    119119      /// undefined value.
    120120      Col() {}
    121121      /// Invalid constructor \& conversion.
    122      
     122
    123123      /// This constructor initializes the Col to be invalid.
    124       /// \sa Invalid for more details.     
     124      /// \sa Invalid for more details.
    125125      Col(const Invalid&) : _id(-1) {}
    126126      /// Equality operator
     
    147147    ///Iterator for iterate over the columns of an LP problem
    148148
    149     /// Its usage is quite simple, for example you can count the number
     149    /// Its usage is quite simple, for example, you can count the number
    150150    /// of columns in an LP \c lp:
    151151    ///\code
     
    157157    public:
    158158      /// Default constructor
    159      
     159
    160160      /// \warning The default constructor sets the iterator
    161161      /// to an undefined value.
    162162      ColIt() {}
    163163      /// Sets the iterator to the first Col
    164      
     164
    165165      /// Sets the iterator to the first Col.
    166166      ///
     
    170170      }
    171171      /// Invalid constructor \& conversion
    172      
     172
    173173      /// Initialize the iterator to be invalid.
    174174      /// \sa Invalid for more details.
    175175      ColIt(const Invalid&) : Col(INVALID) {}
    176176      /// Next column
    177      
     177
    178178      /// Assign the iterator to the next column.
    179179      ///
     
    210210      typedef True LpRow;
    211211      /// Default constructor
    212      
     212
    213213      /// \warning The default constructor sets the Row to an
    214214      /// undefined value.
    215215      Row() {}
    216216      /// Invalid constructor \& conversion.
    217      
     217
    218218      /// This constructor initializes the Row to be invalid.
    219       /// \sa Invalid for more details.     
     219      /// \sa Invalid for more details.
    220220      Row(const Invalid&) : _id(-1) {}
    221221      /// Equality operator
     
    225225      bool operator==(Row r) const  {return _id == r._id;}
    226226      /// Inequality operator
    227      
     227
    228228      /// \sa operator==(Row r)
    229229      ///
     
    242242    ///Iterator for iterate over the rows of an LP problem
    243243
    244     /// Its usage is quite simple, for example you can count the number
     244    /// Its usage is quite simple, for example, you can count the number
    245245    /// of rows in an LP \c lp:
    246246    ///\code
     
    252252    public:
    253253      /// Default constructor
    254      
     254
    255255      /// \warning The default constructor sets the iterator
    256256      /// to an undefined value.
    257257      RowIt() {}
    258258      /// Sets the iterator to the first Row
    259      
     259
    260260      /// Sets the iterator to the first Row.
    261261      ///
     
    265265      }
    266266      /// Invalid constructor \& conversion
    267      
     267
    268268      /// Initialize the iterator to be invalid.
    269269      /// \sa Invalid for more details.
    270270      RowIt(const Invalid&) : Row(INVALID) {}
    271271      /// Next row
    272      
     272
    273273      /// Assign the iterator to the next row.
    274274      ///
     
    348348      typedef True SolverExpr;
    349349      /// Default constructor
    350      
     350
    351351      /// Construct an empty expression, the coefficients and
    352352      /// the constant component are initialized to zero.
     
    449449
    450450      ///Iterator over the expression
    451      
    452       ///The iterator iterates over the terms of the expression. 
    453       /// 
     451
     452      ///The iterator iterates over the terms of the expression.
     453      ///
    454454      ///\code
    455455      ///double s=0;
     
    465465
    466466        /// Sets the iterator to the first term
    467        
     467
    468468        /// Sets the iterator to the first term of the expression.
    469469        ///
     
    482482        const Value& operator*() const { return _it->second; }
    483483        /// Next term
    484        
     484
    485485        /// Assign the iterator to the next term.
    486486        ///
     
    494494
    495495      /// Const iterator over the expression
    496      
    497       ///The iterator iterates over the terms of the expression. 
    498       /// 
     496
     497      ///The iterator iterates over the terms of the expression.
     498      ///
    499499      ///\code
    500500      ///double s=0;
     
    510510
    511511        /// Sets the iterator to the first term
    512        
     512
    513513        /// Sets the iterator to the first term of the expression.
    514514        ///
     
    525525
    526526        /// Next term
    527        
     527
    528528        /// Assign the iterator to the next term.
    529529        ///
     
    674674      typedef True SolverExpr;
    675675      /// Default constructor
    676      
     676
    677677      /// Construct an empty expression, the coefficients are
    678678      /// initialized to zero.
     
    709709      }
    710710      /// \brief Removes the coefficients which's absolute value does
    711       /// not exceed \c epsilon. 
     711      /// not exceed \c epsilon.
    712712      void simplify(Value epsilon = 0.0) {
    713713        std::map<int, Value>::iterator it=comps.begin();
     
    758758
    759759      ///Iterator over the expression
    760      
    761       ///The iterator iterates over the terms of the expression. 
    762       /// 
     760
     761      ///The iterator iterates over the terms of the expression.
     762      ///
    763763      ///\code
    764764      ///double s=0;
     
    774774
    775775        /// Sets the iterator to the first term
    776        
     776
    777777        /// Sets the iterator to the first term of the expression.
    778778        ///
     
    792792
    793793        /// Next term
    794        
     794
    795795        /// Assign the iterator to the next term.
    796796        ///
     
    804804
    805805      ///Iterator over the expression
    806      
    807       ///The iterator iterates over the terms of the expression. 
    808       /// 
     806
     807      ///The iterator iterates over the terms of the expression.
     808      ///
    809809      ///\code
    810810      ///double s=0;
     
    820820
    821821        /// Sets the iterator to the first term
    822        
     822
    823823        /// Sets the iterator to the first term of the expression.
    824824        ///
     
    835835
    836836        /// Next term
    837        
     837
    838838        /// Assign the iterator to the next term.
    839839        ///
     
    943943    virtual int _addCol() = 0;
    944944    virtual int _addRow() = 0;
     945
     946    virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
     947      int row = _addRow();
     948      _setRowCoeffs(row, b, e);
     949      _setRowLowerBound(row, l);
     950      _setRowUpperBound(row, u);
     951      return row;
     952    }
    945953
    946954    virtual void _eraseCol(int col) = 0;
     
    12081216    ///\return The created row.
    12091217    Row addRow(Value l,const Expr &e, Value u) {
    1210       Row r=addRow();
    1211       row(r,l,e,u);
     1218      Row r;
     1219      e.simplify();
     1220      r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
     1221                                ExprIterator(e.comps.end(), cols), u - *e));
    12121222      return r;
    12131223    }
     
    12181228    ///\return The created row.
    12191229    Row addRow(const Constr &c) {
    1220       Row r=addRow();
    1221       row(r,c);
     1230      Row r;
     1231      c.expr().simplify();
     1232      r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
     1233                                ExprIterator(c.expr().comps.begin(), cols),
     1234                                ExprIterator(c.expr().comps.end(), cols),
     1235                                c.upperBounded()?c.upperBound()-*c.expr():INF));
    12221236      return r;
    12231237    }
     
    18041818    enum VarStatus {
    18051819      /// The variable is in the basis
    1806       BASIC, 
     1820      BASIC,
    18071821      /// The variable is free, but not basic
    18081822      FREE,
    1809       /// The variable has active lower bound 
     1823      /// The variable has active lower bound
    18101824      LOWER,
    18111825      /// The variable has active upper bound
     
    18861900    }
    18871901    /// Returns a component of the primal ray
    1888    
     1902
    18891903    /// The primal ray is solution of the modified primal problem,
    18901904    /// where we change each finite bound to 0, and we looking for a
     
    19201934
    19211935    /// Returns a component of the dual ray
    1922    
     1936
    19231937    /// The dual ray is solution of the modified primal problem, where
    19241938    /// we change each finite bound to 0 (i.e. the objective function
     
    20622076    }
    20632077    ///The value of the objective function
    2064    
     2078
    20652079    ///\return
    20662080    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
  • test/lp_test.cc

    r1097 r1141  
    4242using namespace lemon;
    4343
     44int countCols(LpBase & lp) {
     45  int count=0;
     46  for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count;
     47  return count;
     48}
     49
     50int countRows(LpBase & lp) {
     51  int count=0;
     52  for (LpBase::RowIt r(lp); r!=INVALID; ++r) ++count;
     53  return count;
     54}
     55
     56
    4457void lpTest(LpSolver& lp)
    4558{
    4659
    4760  typedef LpSolver LP;
     61
     62  // Test LpBase::clear()
     63  check(countRows(lp)==0, "Wrong number of rows");
     64  check(countCols(lp)==0, "Wrong number of cols");
     65  lp.addCol(); lp.addRow(); lp.addRow();
     66  check(countRows(lp)==2, "Wrong number of rows");
     67  check(countCols(lp)==1, "Wrong number of cols");
     68  lp.clear();
     69  check(countRows(lp)==0, "Wrong number of rows");
     70  check(countCols(lp)==0, "Wrong number of cols");
     71  lp.addCol(); lp.addCol(); lp.addCol(); lp.addRow();
     72  check(countRows(lp)==1, "Wrong number of rows");
     73  check(countCols(lp)==3, "Wrong number of cols");
     74  lp.clear();
    4875
    4976  std::vector<LP::Col> x(10);
  • test/lp_test.cc

    r1140 r1141  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
Note: See TracChangeset for help on using the changeset viewer.