1.1 --- a/lemon/lp_base.h Thu Feb 15 13:06:23 2007 +0000
1.2 +++ b/lemon/lp_base.h Thu Feb 15 14:22:08 2007 +0000
1.3 @@ -27,93 +27,16 @@
1.4 #include<limits>
1.5 #include<cmath>
1.6
1.7 -#include<lemon/bits/utility.h>
1.8 #include<lemon/error.h>
1.9 #include<lemon/bits/invalid.h>
1.10 +#include<lemon/bits/utility.h>
1.11 +#include<lemon/bits/lp_id.h>
1.12
1.13 ///\file
1.14 ///\brief The interface of the LP solver interface.
1.15 ///\ingroup gen_opt_group
1.16 namespace lemon {
1.17
1.18 -
1.19 - ///Internal data structure to convert floating id's to fix one's
1.20 -
1.21 - ///\todo This might be implemented to be also usable in other places.
1.22 - class _FixId
1.23 - {
1.24 - protected:
1.25 - int _first_index;
1.26 - int first_free;
1.27 - public:
1.28 - std::vector<int> index;
1.29 - std::vector<int> cross;
1.30 - _FixId() : _first_index(-1), first_free(-1) {};
1.31 - ///Convert a floating id to a fix one
1.32 -
1.33 - ///\param n is a floating id
1.34 - ///\return the corresponding fix id
1.35 - int fixId(int n) const {return cross[n];}
1.36 - ///Convert a fix id to a floating one
1.37 -
1.38 - ///\param n is a fix id
1.39 - ///\return the corresponding floating id
1.40 - int floatingId(int n) const { return index[n];}
1.41 - ///Add a new floating id.
1.42 -
1.43 - ///\param n is a floating id
1.44 - ///\return the fix id of the new value
1.45 - ///\todo Multiple additions should also be handled.
1.46 - int insert(int n)
1.47 - {
1.48 - if(cross.empty()) _first_index=n;
1.49 - if(n>=int(cross.size())) {
1.50 - cross.resize(n+1);
1.51 - if(first_free==-1) {
1.52 - cross[n]=index.size();
1.53 - index.push_back(n);
1.54 - }
1.55 - else {
1.56 - cross[n]=first_free;
1.57 - int next=index[first_free];
1.58 - index[first_free]=n;
1.59 - first_free=next;
1.60 - }
1.61 - return cross[n];
1.62 - }
1.63 - else {
1.64 - ///\todo Create an own exception type.
1.65 - throw LogicError(); //floatingId-s must form a continuous range;
1.66 - }
1.67 - }
1.68 - ///Remove a fix id.
1.69 -
1.70 - ///\param n is a fix id
1.71 - ///
1.72 - void erase(int n)
1.73 - {
1.74 - int fl=index[n];
1.75 - index[n]=first_free;
1.76 - first_free=n;
1.77 - for(int i=fl+1;i<int(cross.size());++i) {
1.78 - cross[i-1]=cross[i];
1.79 - index[cross[i]]--;
1.80 - }
1.81 - cross.pop_back();
1.82 - }
1.83 - ///An upper bound on the largest fix id.
1.84 -
1.85 - ///\todo Do we need this?
1.86 - ///
1.87 - std::size_t maxFixId() { return cross.size()-1; }
1.88 -
1.89 - ///Returns the first (smallest) inserted index
1.90 -
1.91 - ///Returns the first (smallest) inserted index
1.92 - ///or -1 if no index has been inserted before.
1.93 - int firstIndex() {return _first_index;}
1.94 - };
1.95 -
1.96 ///Common base class for LP solvers
1.97
1.98 ///\todo Much more docs
1.99 @@ -121,9 +44,10 @@
1.100 class LpSolverBase {
1.101
1.102 protected:
1.103 - _FixId rows;
1.104 - _FixId cols;
1.105
1.106 + _lp_bits::LpId rows;
1.107 + _lp_bits::LpId cols;
1.108 +
1.109 public:
1.110
1.111 ///Possible outcomes of an LP solving procedure
1.112 @@ -215,14 +139,12 @@
1.113 ColIt() {}
1.114 ColIt(LpSolverBase &lp) : _lp(&lp)
1.115 {
1.116 - id = _lp->cols.cross.empty()?-1:
1.117 - _lp->cols.fixId(_lp->cols.firstIndex());
1.118 + _lp->cols.firstFix(id);
1.119 }
1.120 ColIt(const Invalid&) : Col(INVALID) {}
1.121 ColIt &operator++()
1.122 {
1.123 - int fid = _lp->cols.floatingId(id)+1;
1.124 - id = unsigned(fid)<_lp->cols.cross.size() ? _lp->cols.fixId(fid) : -1;
1.125 + _lp->cols.nextFix(id);
1.126 return *this;
1.127 }
1.128 };
1.129 @@ -746,8 +668,6 @@
1.130 virtual Value _getColLowerBound(int i) = 0;
1.131 virtual void _setColUpperBound(int i, Value value) = 0;
1.132 virtual Value _getColUpperBound(int i) = 0;
1.133 -// virtual void _setRowLowerBound(int i, Value value) = 0;
1.134 -// virtual void _setRowUpperBound(int i, Value value) = 0;
1.135 virtual void _setRowBounds(int i, Value lower, Value upper) = 0;
1.136 virtual void _getRowBounds(int i, Value &lower, Value &upper)=0;
1.137
1.138 @@ -795,7 +715,7 @@
1.139 ///@{
1.140
1.141 ///Add a new empty column (i.e a new variable) to the LP
1.142 - Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
1.143 + Col addCol() { Col c; _addCol(); c.id = cols.addId(); return c;}
1.144
1.145 ///\brief Adds several new columns
1.146 ///(i.e a variables) at once
1.147 @@ -887,7 +807,7 @@
1.148
1.149 ///This function adds a new empty row (i.e a new constraint) to the LP.
1.150 ///\return The created row
1.151 - Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
1.152 + Row addRow() { Row r; _addRow(); r.id = rows.addId(); return r;}
1.153
1.154 ///\brief Add several new rows
1.155 ///(i.e a constraints) at once
1.156 @@ -965,8 +885,6 @@
1.157 e.simplify();
1.158 _setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this),
1.159 LpRowIterator(e.end(), *this));
1.160 -// _setRowLowerBound(_lpId(r),l-e.constComp());
1.161 -// _setRowUpperBound(_lpId(r),u-e.constComp());
1.162 _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
1.163 }
1.164
1.165 @@ -1008,7 +926,7 @@
1.166 ///\todo Please check this
1.167 void eraseCol(Col c) {
1.168 _eraseCol(_lpId(c));
1.169 - cols.erase(c.id);
1.170 + cols.eraseId(c.id);
1.171 }
1.172 ///Erase a row (i.e a constraint) from the LP
1.173
1.174 @@ -1016,7 +934,7 @@
1.175 ///\todo Please check this
1.176 void eraseRow(Row r) {
1.177 _eraseRow(_lpId(r));
1.178 - rows.erase(r.id);
1.179 + rows.eraseId(r.id);
1.180 }
1.181
1.182 /// Get the name of a column
1.183 @@ -1216,31 +1134,14 @@
1.184 }
1.185 #endif
1.186
1.187 -// /// Set the lower bound of a row (i.e a constraint)
1.188 -
1.189 -// /// The lower bound of a linear expression (row) has to be given by an
1.190 -// /// extended number of type Value, i.e. a finite number of type
1.191 -// /// Value or -\ref INF.
1.192 -// void rowLowerBound(Row r, Value value) {
1.193 -// _setRowLowerBound(_lpId(r),value);
1.194 -// };
1.195 -// /// Set the upper bound of a row (i.e a constraint)
1.196 -
1.197 -// /// The upper bound of a linear expression (row) has to be given by an
1.198 -// /// extended number of type Value, i.e. a finite number of type
1.199 -// /// Value or \ref INF.
1.200 -// void rowUpperBound(Row r, Value value) {
1.201 -// _setRowUpperBound(_lpId(r),value);
1.202 -// };
1.203
1.204 /// Set the lower and the upper bounds of a row (i.e a constraint)
1.205
1.206 - /// The lower and the upper bound of
1.207 - /// a constraint (row) have to be given by an
1.208 - /// extended number of type Value, i.e. a finite number of type
1.209 - /// Value, -\ref INF or \ref INF. There is no separate function for the
1.210 - /// lower and the upper bound because that would have been hard to implement
1.211 - /// for CPLEX.
1.212 + /// The lower and the upper bound of a constraint (row) have to be
1.213 + /// given by an extended number of type Value, i.e. a finite
1.214 + /// number of type Value, -\ref INF or \ref INF. There is no
1.215 + /// separate function for the lower and the upper bound because
1.216 + /// that would have been hard to implement for CPLEX.
1.217 void rowBounds(Row c, Value lower, Value upper) {
1.218 _setRowBounds(_lpId(c),lower, upper);
1.219 }