1.1 --- a/lemon/lp_base.h Thu Feb 15 14:22:08 2007 +0000
1.2 +++ b/lemon/lp_base.h Thu Feb 15 19:15:14 2007 +0000
1.3 @@ -49,7 +49,7 @@
1.4 _lp_bits::LpId cols;
1.5
1.6 public:
1.7 -
1.8 +
1.9 ///Possible outcomes of an LP solving procedure
1.10 enum SolveExitStatus {
1.11 ///This means that the problem has been successfully solved: either
1.12 @@ -122,6 +122,7 @@
1.13 int id;
1.14 friend class LpSolverBase;
1.15 friend class MipSolverBase;
1.16 + explicit Col(int _id) : id(_id) {}
1.17 public:
1.18 typedef Value ExprValue;
1.19 typedef True LpSolverCol;
1.20 @@ -165,6 +166,7 @@
1.21 protected:
1.22 int id;
1.23 friend class LpSolverBase;
1.24 + explicit Row(int _id) : id(_id) {}
1.25 public:
1.26 typedef Value ExprValue;
1.27 typedef True LpSolverRow;
1.28 @@ -177,6 +179,22 @@
1.29 bool operator!=(Row c) const {return id!=c.id;}
1.30 };
1.31
1.32 + class RowIt : public Row {
1.33 + LpSolverBase *_lp;
1.34 + public:
1.35 + RowIt() {}
1.36 + RowIt(LpSolverBase &lp) : _lp(&lp)
1.37 + {
1.38 + _lp->rows.firstFix(id);
1.39 + }
1.40 + RowIt(const Invalid&) : Row(INVALID) {}
1.41 + RowIt &operator++()
1.42 + {
1.43 + _lp->rows.nextFix(id);
1.44 + return *this;
1.45 + }
1.46 + };
1.47 +
1.48 static int id(const Row& row) { return row.id; }
1.49
1.50 protected:
1.51 @@ -189,6 +207,14 @@
1.52 return rows.floatingId(id(row));
1.53 }
1.54
1.55 + Col _item(int id, Col) const {
1.56 + return Col(cols.fixId(id));
1.57 + }
1.58 +
1.59 + Row _item(int id, Row) const {
1.60 + return Row(rows.fixId(id));
1.61 + }
1.62 +
1.63
1.64 public:
1.65
1.66 @@ -581,11 +607,60 @@
1.67
1.68 private:
1.69
1.70 - template <typename _Base>
1.71 - class MappedIterator {
1.72 + template <typename _Expr>
1.73 + class MappedOutputIterator {
1.74 public:
1.75
1.76 - typedef _Base Base;
1.77 + typedef std::insert_iterator<_Expr> Base;
1.78 +
1.79 + typedef std::output_iterator_tag iterator_category;
1.80 + typedef void difference_type;
1.81 + typedef void value_type;
1.82 + typedef void reference;
1.83 + typedef void pointer;
1.84 +
1.85 + MappedOutputIterator(const Base& _base, const LpSolverBase& _lp)
1.86 + : base(_base), lp(_lp) {}
1.87 +
1.88 + MappedOutputIterator& operator*() {
1.89 + return *this;
1.90 + }
1.91 +
1.92 + MappedOutputIterator& operator=(const std::pair<int, Value>& value) {
1.93 + *base = std::make_pair(lp._item(value.first, typename _Expr::Key()),
1.94 + value.second);
1.95 + return *this;
1.96 + }
1.97 +
1.98 + MappedOutputIterator& operator++() {
1.99 + ++base;
1.100 + return *this;
1.101 + }
1.102 +
1.103 + MappedOutputIterator operator++(int) {
1.104 + MappedOutputIterator tmp(*this);
1.105 + ++base;
1.106 + return tmp;
1.107 + }
1.108 +
1.109 + bool operator==(const MappedOutputIterator& it) const {
1.110 + return base == it.base;
1.111 + }
1.112 +
1.113 + bool operator!=(const MappedOutputIterator& it) const {
1.114 + return base != it.base;
1.115 + }
1.116 +
1.117 + private:
1.118 + Base base;
1.119 + const LpSolverBase& lp;
1.120 + };
1.121 +
1.122 + template <typename Expr>
1.123 + class MappedInputIterator {
1.124 + public:
1.125 +
1.126 + typedef typename Expr::const_iterator Base;
1.127
1.128 typedef typename Base::iterator_category iterator_category;
1.129 typedef typename Base::difference_type difference_type;
1.130 @@ -599,7 +674,7 @@
1.131 value_type value;
1.132 };
1.133
1.134 - MappedIterator(const Base& _base, const LpSolverBase& _lp)
1.135 + MappedInputIterator(const Base& _base, const LpSolverBase& _lp)
1.136 : base(_base), lp(_lp) {}
1.137
1.138 reference operator*() {
1.139 @@ -610,22 +685,22 @@
1.140 return pointer(operator*());
1.141 }
1.142
1.143 - MappedIterator& operator++() {
1.144 + MappedInputIterator& operator++() {
1.145 ++base;
1.146 return *this;
1.147 }
1.148
1.149 - MappedIterator& operator++(int) {
1.150 - MappedIterator tmp(*this);
1.151 + MappedInputIterator operator++(int) {
1.152 + MappedInputIterator tmp(*this);
1.153 ++base;
1.154 return tmp;
1.155 }
1.156
1.157 - bool operator==(const MappedIterator& it) const {
1.158 + bool operator==(const MappedInputIterator& it) const {
1.159 return base == it.base;
1.160 }
1.161
1.162 - bool operator!=(const MappedIterator& it) const {
1.163 + bool operator!=(const MappedInputIterator& it) const {
1.164 return base != it.base;
1.165 }
1.166
1.167 @@ -637,9 +712,14 @@
1.168 protected:
1.169
1.170 /// STL compatible iterator for lp col
1.171 - typedef MappedIterator<Expr::const_iterator> LpRowIterator;
1.172 + typedef MappedInputIterator<Expr> ConstRowIterator;
1.173 /// STL compatible iterator for lp row
1.174 - typedef MappedIterator<DualExpr::const_iterator> LpColIterator;
1.175 + typedef MappedInputIterator<DualExpr> ConstColIterator;
1.176 +
1.177 + /// STL compatible iterator for lp col
1.178 + typedef MappedOutputIterator<Expr> RowIterator;
1.179 + /// STL compatible iterator for lp row
1.180 + typedef MappedOutputIterator<DualExpr> ColIterator;
1.181
1.182 //Abstract virtual functions
1.183 virtual LpSolverBase &_newLp() = 0;
1.184 @@ -659,11 +739,14 @@
1.185 virtual void _eraseRow(int row) = 0;
1.186 virtual void _getColName(int col, std::string & name) = 0;
1.187 virtual void _setColName(int col, const std::string & name) = 0;
1.188 - virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) = 0;
1.189 - virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e) = 0;
1.190 + virtual void _setRowCoeffs(int i, ConstRowIterator b,
1.191 + ConstRowIterator e) = 0;
1.192 + virtual void _getRowCoeffs(int i, RowIterator b) = 0;
1.193 + virtual void _setColCoeffs(int i, ConstColIterator b,
1.194 + ConstColIterator e) = 0;
1.195 + virtual void _getColCoeffs(int i, ColIterator b) = 0;
1.196 virtual void _setCoeff(int row, int col, Value value) = 0;
1.197 virtual Value _getCoeff(int row, int col) = 0;
1.198 -
1.199 virtual void _setColLowerBound(int i, Value value) = 0;
1.200 virtual Value _getColLowerBound(int i) = 0;
1.201 virtual void _setColUpperBound(int i, Value value) = 0;
1.202 @@ -786,8 +869,18 @@
1.203 ///a better one.
1.204 void col(Col c,const DualExpr &e) {
1.205 e.simplify();
1.206 - _setColCoeffs(_lpId(c), LpColIterator(e.begin(), *this),
1.207 - LpColIterator(e.end(), *this));
1.208 + _setColCoeffs(_lpId(c), ConstColIterator(e.begin(), *this),
1.209 + ConstColIterator(e.end(), *this));
1.210 + }
1.211 +
1.212 + ///Get a column (i.e a dual constraint) of the LP
1.213 +
1.214 + ///\param r is the column to get
1.215 + ///\return the dual expression associated to the column
1.216 + DualExpr col(Col c) {
1.217 + DualExpr e;
1.218 + _getColCoeffs(_lpId(c), ColIterator(std::inserter(e, e.end()), *this));
1.219 + return e;
1.220 }
1.221
1.222 ///Add a new column to the LP
1.223 @@ -883,9 +976,9 @@
1.224 ///added or not.
1.225 void row(Row r, Value l,const Expr &e, Value u) {
1.226 e.simplify();
1.227 - _setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this),
1.228 - LpRowIterator(e.end(), *this));
1.229 - _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
1.230 + _setRowCoeffs(_lpId(r), ConstRowIterator(e.begin(), *this),
1.231 + ConstRowIterator(e.end(), *this));
1.232 + _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
1.233 }
1.234
1.235 ///Set a row (i.e a constraint) of the LP
1.236 @@ -897,6 +990,17 @@
1.237 c.expr(), c.upperBounded()?c.upperBound():INF);
1.238 }
1.239
1.240 +
1.241 + ///Get a row (i.e a constraint) of the LP
1.242 +
1.243 + ///\param r is the row to get
1.244 + ///\return the expression associated to the row
1.245 + Expr row(Row r) {
1.246 + Expr e;
1.247 + _getRowCoeffs(_lpId(r), RowIterator(std::inserter(e, e.end()), *this));
1.248 + return e;
1.249 + }
1.250 +
1.251 ///Add a new row (i.e a new constraint) to the LP
1.252
1.253 ///\param l is the lower bound (-\ref INF means no bound)
1.254 @@ -1177,6 +1281,21 @@
1.255 obj_const_comp=e.constComp();
1.256 }
1.257
1.258 + ///Get the objective function
1.259 +
1.260 + ///\return the objective function as a linear expression of type \ref Expr.
1.261 + Expr obj() {
1.262 + Expr e;
1.263 + for (ColIt it(*this); it != INVALID; ++it) {
1.264 + double c = objCoeff(it);
1.265 + if (c != 0.0) {
1.266 + e.insert(std::make_pair(it, c));
1.267 + }
1.268 + }
1.269 + return e;
1.270 + }
1.271 +
1.272 +
1.273 ///Maximize
1.274 void max() { _setMax(); }
1.275 ///Minimize