1.1 --- a/lemon/lp_base.h Tue Dec 20 17:44:38 2011 +0100
1.2 +++ b/lemon/lp_base.h Tue Dec 20 18:15:14 2011 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2008
1.8 + * Copyright (C) 2003-2010
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -82,7 +82,7 @@
1.13 /// Verbose output.
1.14 MESSAGE_VERBOSE
1.15 };
1.16 -
1.17 +
1.18
1.19 ///The floating point type used by the solver
1.20 typedef double Value;
1.21 @@ -114,14 +114,14 @@
1.22 typedef Value ExprValue;
1.23 typedef True LpCol;
1.24 /// Default constructor
1.25 -
1.26 +
1.27 /// \warning The default constructor sets the Col to an
1.28 /// undefined value.
1.29 Col() {}
1.30 /// Invalid constructor \& conversion.
1.31 -
1.32 +
1.33 /// This constructor initializes the Col to be invalid.
1.34 - /// \sa Invalid for more details.
1.35 + /// \sa Invalid for more details.
1.36 Col(const Invalid&) : _id(-1) {}
1.37 /// Equality operator
1.38
1.39 @@ -146,7 +146,7 @@
1.40
1.41 ///Iterator for iterate over the columns of an LP problem
1.42
1.43 - /// Its usage is quite simple, for example you can count the number
1.44 + /// Its usage is quite simple, for example, you can count the number
1.45 /// of columns in an LP \c lp:
1.46 ///\code
1.47 /// int count=0;
1.48 @@ -156,12 +156,12 @@
1.49 const LpBase *_solver;
1.50 public:
1.51 /// Default constructor
1.52 -
1.53 +
1.54 /// \warning The default constructor sets the iterator
1.55 /// to an undefined value.
1.56 ColIt() {}
1.57 /// Sets the iterator to the first Col
1.58 -
1.59 +
1.60 /// Sets the iterator to the first Col.
1.61 ///
1.62 ColIt(const LpBase &solver) : _solver(&solver)
1.63 @@ -169,12 +169,12 @@
1.64 _solver->cols.firstItem(_id);
1.65 }
1.66 /// Invalid constructor \& conversion
1.67 -
1.68 +
1.69 /// Initialize the iterator to be invalid.
1.70 /// \sa Invalid for more details.
1.71 ColIt(const Invalid&) : Col(INVALID) {}
1.72 /// Next column
1.73 -
1.74 +
1.75 /// Assign the iterator to the next column.
1.76 ///
1.77 ColIt &operator++()
1.78 @@ -209,14 +209,14 @@
1.79 typedef Value ExprValue;
1.80 typedef True LpRow;
1.81 /// Default constructor
1.82 -
1.83 +
1.84 /// \warning The default constructor sets the Row to an
1.85 /// undefined value.
1.86 Row() {}
1.87 /// Invalid constructor \& conversion.
1.88 -
1.89 +
1.90 /// This constructor initializes the Row to be invalid.
1.91 - /// \sa Invalid for more details.
1.92 + /// \sa Invalid for more details.
1.93 Row(const Invalid&) : _id(-1) {}
1.94 /// Equality operator
1.95
1.96 @@ -224,7 +224,7 @@
1.97 /// the same LP row or both are invalid.
1.98 bool operator==(Row r) const {return _id == r._id;}
1.99 /// Inequality operator
1.100 -
1.101 +
1.102 /// \sa operator==(Row r)
1.103 ///
1.104 bool operator!=(Row r) const {return _id != r._id;}
1.105 @@ -241,7 +241,7 @@
1.106
1.107 ///Iterator for iterate over the rows of an LP problem
1.108
1.109 - /// Its usage is quite simple, for example you can count the number
1.110 + /// Its usage is quite simple, for example, you can count the number
1.111 /// of rows in an LP \c lp:
1.112 ///\code
1.113 /// int count=0;
1.114 @@ -251,12 +251,12 @@
1.115 const LpBase *_solver;
1.116 public:
1.117 /// Default constructor
1.118 -
1.119 +
1.120 /// \warning The default constructor sets the iterator
1.121 /// to an undefined value.
1.122 RowIt() {}
1.123 /// Sets the iterator to the first Row
1.124 -
1.125 +
1.126 /// Sets the iterator to the first Row.
1.127 ///
1.128 RowIt(const LpBase &solver) : _solver(&solver)
1.129 @@ -264,12 +264,12 @@
1.130 _solver->rows.firstItem(_id);
1.131 }
1.132 /// Invalid constructor \& conversion
1.133 -
1.134 +
1.135 /// Initialize the iterator to be invalid.
1.136 /// \sa Invalid for more details.
1.137 RowIt(const Invalid&) : Row(INVALID) {}
1.138 /// Next row
1.139 -
1.140 +
1.141 /// Assign the iterator to the next row.
1.142 ///
1.143 RowIt &operator++()
1.144 @@ -347,7 +347,7 @@
1.145 public:
1.146 typedef True SolverExpr;
1.147 /// Default constructor
1.148 -
1.149 +
1.150 /// Construct an empty expression, the coefficients and
1.151 /// the constant component are initialized to zero.
1.152 Expr() : const_comp(0) {}
1.153 @@ -448,9 +448,9 @@
1.154 }
1.155
1.156 ///Iterator over the expression
1.157 -
1.158 - ///The iterator iterates over the terms of the expression.
1.159 - ///
1.160 +
1.161 + ///The iterator iterates over the terms of the expression.
1.162 + ///
1.163 ///\code
1.164 ///double s=0;
1.165 ///for(LpBase::Expr::CoeffIt i(e);i!=INVALID;++i)
1.166 @@ -464,7 +464,7 @@
1.167 public:
1.168
1.169 /// Sets the iterator to the first term
1.170 -
1.171 +
1.172 /// Sets the iterator to the first term of the expression.
1.173 ///
1.174 CoeffIt(Expr& e)
1.175 @@ -481,7 +481,7 @@
1.176 /// Returns the coefficient of the term
1.177 const Value& operator*() const { return _it->second; }
1.178 /// Next term
1.179 -
1.180 +
1.181 /// Assign the iterator to the next term.
1.182 ///
1.183 CoeffIt& operator++() { ++_it; return *this; }
1.184 @@ -493,9 +493,9 @@
1.185 };
1.186
1.187 /// Const iterator over the expression
1.188 -
1.189 - ///The iterator iterates over the terms of the expression.
1.190 - ///
1.191 +
1.192 + ///The iterator iterates over the terms of the expression.
1.193 + ///
1.194 ///\code
1.195 ///double s=0;
1.196 ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i)
1.197 @@ -509,7 +509,7 @@
1.198 public:
1.199
1.200 /// Sets the iterator to the first term
1.201 -
1.202 +
1.203 /// Sets the iterator to the first term of the expression.
1.204 ///
1.205 ConstCoeffIt(const Expr& e)
1.206 @@ -524,7 +524,7 @@
1.207 const Value& operator*() const { return _it->second; }
1.208
1.209 /// Next term
1.210 -
1.211 +
1.212 /// Assign the iterator to the next term.
1.213 ///
1.214 ConstCoeffIt& operator++() { ++_it; return *this; }
1.215 @@ -673,7 +673,7 @@
1.216 public:
1.217 typedef True SolverExpr;
1.218 /// Default constructor
1.219 -
1.220 +
1.221 /// Construct an empty expression, the coefficients are
1.222 /// initialized to zero.
1.223 DualExpr() {}
1.224 @@ -708,7 +708,7 @@
1.225 }
1.226 }
1.227 /// \brief Removes the coefficients which's absolute value does
1.228 - /// not exceed \c epsilon.
1.229 + /// not exceed \c epsilon.
1.230 void simplify(Value epsilon = 0.0) {
1.231 std::map<int, Value>::iterator it=comps.begin();
1.232 while (it != comps.end()) {
1.233 @@ -757,9 +757,9 @@
1.234 }
1.235
1.236 ///Iterator over the expression
1.237 -
1.238 - ///The iterator iterates over the terms of the expression.
1.239 - ///
1.240 +
1.241 + ///The iterator iterates over the terms of the expression.
1.242 + ///
1.243 ///\code
1.244 ///double s=0;
1.245 ///for(LpBase::DualExpr::CoeffIt i(e);i!=INVALID;++i)
1.246 @@ -773,7 +773,7 @@
1.247 public:
1.248
1.249 /// Sets the iterator to the first term
1.250 -
1.251 +
1.252 /// Sets the iterator to the first term of the expression.
1.253 ///
1.254 CoeffIt(DualExpr& e)
1.255 @@ -791,7 +791,7 @@
1.256 const Value& operator*() const { return _it->second; }
1.257
1.258 /// Next term
1.259 -
1.260 +
1.261 /// Assign the iterator to the next term.
1.262 ///
1.263 CoeffIt& operator++() { ++_it; return *this; }
1.264 @@ -803,9 +803,9 @@
1.265 };
1.266
1.267 ///Iterator over the expression
1.268 -
1.269 - ///The iterator iterates over the terms of the expression.
1.270 - ///
1.271 +
1.272 + ///The iterator iterates over the terms of the expression.
1.273 + ///
1.274 ///\code
1.275 ///double s=0;
1.276 ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i)
1.277 @@ -819,7 +819,7 @@
1.278 public:
1.279
1.280 /// Sets the iterator to the first term
1.281 -
1.282 +
1.283 /// Sets the iterator to the first term of the expression.
1.284 ///
1.285 ConstCoeffIt(const DualExpr& e)
1.286 @@ -834,7 +834,7 @@
1.287 const Value& operator*() const { return _it->second; }
1.288
1.289 /// Next term
1.290 -
1.291 +
1.292 /// Assign the iterator to the next term.
1.293 ///
1.294 ConstCoeffIt& operator++() { ++_it; return *this; }
1.295 @@ -943,6 +943,14 @@
1.296 virtual int _addCol() = 0;
1.297 virtual int _addRow() = 0;
1.298
1.299 + virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
1.300 + int row = _addRow();
1.301 + _setRowCoeffs(row, b, e);
1.302 + _setRowLowerBound(row, l);
1.303 + _setRowUpperBound(row, u);
1.304 + return row;
1.305 + }
1.306 +
1.307 virtual void _eraseCol(int col) = 0;
1.308 virtual void _eraseRow(int row) = 0;
1.309
1.310 @@ -1207,8 +1215,10 @@
1.311 ///\param u is the upper bound (\ref INF means no bound)
1.312 ///\return The created row.
1.313 Row addRow(Value l,const Expr &e, Value u) {
1.314 - Row r=addRow();
1.315 - row(r,l,e,u);
1.316 + Row r;
1.317 + e.simplify();
1.318 + r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
1.319 + ExprIterator(e.comps.end(), cols), u - *e));
1.320 return r;
1.321 }
1.322
1.323 @@ -1217,8 +1227,12 @@
1.324 ///\param c is a linear expression (see \ref Constr)
1.325 ///\return The created row.
1.326 Row addRow(const Constr &c) {
1.327 - Row r=addRow();
1.328 - row(r,c);
1.329 + Row r;
1.330 + c.expr().simplify();
1.331 + r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
1.332 + ExprIterator(c.expr().comps.begin(), cols),
1.333 + ExprIterator(c.expr().comps.end(), cols),
1.334 + c.upperBounded()?c.upperBound()-*c.expr():INF));
1.335 return r;
1.336 }
1.337 ///Erase a column (i.e a variable) from the LP
1.338 @@ -1803,10 +1817,10 @@
1.339 ///The basis status of variables
1.340 enum VarStatus {
1.341 /// The variable is in the basis
1.342 - BASIC,
1.343 + BASIC,
1.344 /// The variable is free, but not basic
1.345 FREE,
1.346 - /// The variable has active lower bound
1.347 + /// The variable has active lower bound
1.348 LOWER,
1.349 /// The variable has active upper bound
1.350 UPPER,
1.351 @@ -1885,7 +1899,7 @@
1.352 return res;
1.353 }
1.354 /// Returns a component of the primal ray
1.355 -
1.356 +
1.357 /// The primal ray is solution of the modified primal problem,
1.358 /// where we change each finite bound to 0, and we looking for a
1.359 /// negative objective value in case of minimization, and positive
1.360 @@ -1919,7 +1933,7 @@
1.361 }
1.362
1.363 /// Returns a component of the dual ray
1.364 -
1.365 +
1.366 /// The dual ray is solution of the modified primal problem, where
1.367 /// we change each finite bound to 0 (i.e. the objective function
1.368 /// coefficients in the primal problem), and we looking for a
1.369 @@ -2061,7 +2075,7 @@
1.370 return res;
1.371 }
1.372 ///The value of the objective function
1.373 -
1.374 +
1.375 ///\return
1.376 ///- \ref INF or -\ref INF means either infeasibility or unboundedness
1.377 /// of the problem, depending on whether we minimize or maximize.