1.1 --- a/lemon/lp_base.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/lp_base.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -52,12 +52,12 @@
1.4
1.5 ///Possible outcomes of an LP solving procedure
1.6 enum SolveExitStatus {
1.7 - ///This means that the problem has been successfully solved: either
1.8 + /// = 0. It means that the problem has been successfully solved: either
1.9 ///an optimal solution has been found or infeasibility/unboundedness
1.10 ///has been proved.
1.11 SOLVED = 0,
1.12 - ///Any other case (including the case when some user specified
1.13 - ///limit has been exceeded)
1.14 + /// = 1. Any other case (including the case when some user specified
1.15 + ///limit has been exceeded).
1.16 UNSOLVED = 1
1.17 };
1.18
1.19 @@ -69,6 +69,21 @@
1.20 MAX
1.21 };
1.22
1.23 + ///Enum for \c messageLevel() parameter
1.24 + enum MessageLevel {
1.25 + /// No output (default value).
1.26 + MESSAGE_NOTHING,
1.27 + /// Error messages only.
1.28 + MESSAGE_ERROR,
1.29 + /// Warnings.
1.30 + MESSAGE_WARNING,
1.31 + /// Normal output.
1.32 + MESSAGE_NORMAL,
1.33 + /// Verbose output.
1.34 + MESSAGE_VERBOSE
1.35 + };
1.36 +
1.37 +
1.38 ///The floating point type used by the solver
1.39 typedef double Value;
1.40 ///The infinity constant
1.41 @@ -597,11 +612,11 @@
1.42 const Value &upperBound() const { return _ub; }
1.43 ///Is the constraint lower bounded?
1.44 bool lowerBounded() const {
1.45 - return _lb != -INF && !std::isnan(_lb);
1.46 + return _lb != -INF && !isNaN(_lb);
1.47 }
1.48 ///Is the constraint upper bounded?
1.49 bool upperBounded() const {
1.50 - return _ub != INF && !std::isnan(_ub);
1.51 + return _ub != INF && !isNaN(_ub);
1.52 }
1.53
1.54 };
1.55 @@ -918,8 +933,6 @@
1.56 protected:
1.57
1.58 //Abstract virtual functions
1.59 - virtual LpBase* _newSolver() const = 0;
1.60 - virtual LpBase* _cloneSolver() const = 0;
1.61
1.62 virtual int _addColId(int col) { return cols.addIndex(col); }
1.63 virtual int _addRowId(int row) { return rows.addIndex(row); }
1.64 @@ -930,6 +943,14 @@
1.65 virtual int _addCol() = 0;
1.66 virtual int _addRow() = 0;
1.67
1.68 + virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) {
1.69 + int row = _addRow();
1.70 + _setRowCoeffs(row, b, e);
1.71 + _setRowLowerBound(row, l);
1.72 + _setRowUpperBound(row, u);
1.73 + return row;
1.74 + }
1.75 +
1.76 virtual void _eraseCol(int col) = 0;
1.77 virtual void _eraseRow(int row) = 0;
1.78
1.79 @@ -975,6 +996,8 @@
1.80
1.81 virtual const char* _solverName() const = 0;
1.82
1.83 + virtual void _messageLevel(MessageLevel level) = 0;
1.84 +
1.85 //Own protected stuff
1.86
1.87 //Constant component of the objective function
1.88 @@ -987,15 +1010,10 @@
1.89 /// Virtual destructor
1.90 virtual ~LpBase() {}
1.91
1.92 - ///Creates a new LP problem
1.93 - LpBase* newSolver() {return _newSolver();}
1.94 - ///Makes a copy of the LP problem
1.95 - LpBase* cloneSolver() {return _cloneSolver();}
1.96 -
1.97 ///Gives back the name of the solver.
1.98 const char* solverName() const {return _solverName();}
1.99
1.100 - ///\name Build up and modify the LP
1.101 + ///\name Build Up and Modify the LP
1.102
1.103 ///@{
1.104
1.105 @@ -1067,8 +1085,8 @@
1.106 ///a better one.
1.107 void col(Col c, const DualExpr &e) {
1.108 e.simplify();
1.109 - _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), cols),
1.110 - ExprIterator(e.comps.end(), cols));
1.111 + _setColCoeffs(cols(id(c)), ExprIterator(e.comps.begin(), rows),
1.112 + ExprIterator(e.comps.end(), rows));
1.113 }
1.114
1.115 ///Get a column (i.e a dual constraint) of the LP
1.116 @@ -1197,8 +1215,10 @@
1.117 ///\param u is the upper bound (\ref INF means no bound)
1.118 ///\return The created row.
1.119 Row addRow(Value l,const Expr &e, Value u) {
1.120 - Row r=addRow();
1.121 - row(r,l,e,u);
1.122 + Row r;
1.123 + e.simplify();
1.124 + r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols),
1.125 + ExprIterator(e.comps.end(), cols), u - *e));
1.126 return r;
1.127 }
1.128
1.129 @@ -1207,8 +1227,12 @@
1.130 ///\param c is a linear expression (see \ref Constr)
1.131 ///\return The created row.
1.132 Row addRow(const Constr &c) {
1.133 - Row r=addRow();
1.134 - row(r,c);
1.135 + Row r;
1.136 + c.expr().simplify();
1.137 + r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound():-INF,
1.138 + ExprIterator(c.expr().comps.begin(), cols),
1.139 + ExprIterator(c.expr().comps.end(), cols),
1.140 + c.upperBounded()?c.upperBound():INF));
1.141 return r;
1.142 }
1.143 ///Erase a column (i.e a variable) from the LP
1.144 @@ -1383,26 +1407,26 @@
1.145 template<class T>
1.146 void colUpperBound(T &t, Value value) { return 0;}
1.147 #else
1.148 - template<class T>
1.149 - typename enable_if<typename T::value_type::LpCol,void>::type
1.150 - colUpperBound(T &t, Value value,dummy<0> = 0) {
1.151 - for(typename T::iterator i=t.begin();i!=t.end();++i) {
1.152 + template<class T1>
1.153 + typename enable_if<typename T1::value_type::LpCol,void>::type
1.154 + colUpperBound(T1 &t, Value value,dummy<0> = 0) {
1.155 + for(typename T1::iterator i=t.begin();i!=t.end();++i) {
1.156 colUpperBound(*i, value);
1.157 }
1.158 }
1.159 - template<class T>
1.160 - typename enable_if<typename T::value_type::second_type::LpCol,
1.161 + template<class T1>
1.162 + typename enable_if<typename T1::value_type::second_type::LpCol,
1.163 void>::type
1.164 - colUpperBound(T &t, Value value,dummy<1> = 1) {
1.165 - for(typename T::iterator i=t.begin();i!=t.end();++i) {
1.166 + colUpperBound(T1 &t, Value value,dummy<1> = 1) {
1.167 + for(typename T1::iterator i=t.begin();i!=t.end();++i) {
1.168 colUpperBound(i->second, value);
1.169 }
1.170 }
1.171 - template<class T>
1.172 - typename enable_if<typename T::MapIt::Value::LpCol,
1.173 + template<class T1>
1.174 + typename enable_if<typename T1::MapIt::Value::LpCol,
1.175 void>::type
1.176 - colUpperBound(T &t, Value value,dummy<2> = 2) {
1.177 - for(typename T::MapIt i(t); i!=INVALID; ++i){
1.178 + colUpperBound(T1 &t, Value value,dummy<2> = 2) {
1.179 + for(typename T1::MapIt i(t); i!=INVALID; ++i){
1.180 colUpperBound(*i, value);
1.181 }
1.182 }
1.183 @@ -1432,24 +1456,24 @@
1.184 template<class T>
1.185 void colBounds(T &t, Value lower, Value upper) { return 0;}
1.186 #else
1.187 - template<class T>
1.188 - typename enable_if<typename T::value_type::LpCol,void>::type
1.189 - colBounds(T &t, Value lower, Value upper,dummy<0> = 0) {
1.190 - for(typename T::iterator i=t.begin();i!=t.end();++i) {
1.191 + template<class T2>
1.192 + typename enable_if<typename T2::value_type::LpCol,void>::type
1.193 + colBounds(T2 &t, Value lower, Value upper,dummy<0> = 0) {
1.194 + for(typename T2::iterator i=t.begin();i!=t.end();++i) {
1.195 colBounds(*i, lower, upper);
1.196 }
1.197 }
1.198 - template<class T>
1.199 - typename enable_if<typename T::value_type::second_type::LpCol, void>::type
1.200 - colBounds(T &t, Value lower, Value upper,dummy<1> = 1) {
1.201 - for(typename T::iterator i=t.begin();i!=t.end();++i) {
1.202 + template<class T2>
1.203 + typename enable_if<typename T2::value_type::second_type::LpCol, void>::type
1.204 + colBounds(T2 &t, Value lower, Value upper,dummy<1> = 1) {
1.205 + for(typename T2::iterator i=t.begin();i!=t.end();++i) {
1.206 colBounds(i->second, lower, upper);
1.207 }
1.208 }
1.209 - template<class T>
1.210 - typename enable_if<typename T::MapIt::Value::LpCol, void>::type
1.211 - colBounds(T &t, Value lower, Value upper,dummy<2> = 2) {
1.212 - for(typename T::MapIt i(t); i!=INVALID; ++i){
1.213 + template<class T2>
1.214 + typename enable_if<typename T2::MapIt::Value::LpCol, void>::type
1.215 + colBounds(T2 &t, Value lower, Value upper,dummy<2> = 2) {
1.216 + for(typename T2::MapIt i(t); i!=INVALID; ++i){
1.217 colBounds(*i, lower, upper);
1.218 }
1.219 }
1.220 @@ -1534,6 +1558,9 @@
1.221 ///Clears the problem
1.222 void clear() { _clear(); }
1.223
1.224 + /// Sets the message level of the solver
1.225 + void messageLevel(MessageLevel level) { _messageLevel(level); }
1.226 +
1.227 ///@}
1.228
1.229 };
1.230 @@ -1666,7 +1693,7 @@
1.231 inline LpBase::Constr operator<=(const LpBase::Value &n,
1.232 const LpBase::Constr &c) {
1.233 LpBase::Constr tmp(c);
1.234 - LEMON_ASSERT(std::isnan(tmp.lowerBound()), "Wrong LP constraint");
1.235 + LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
1.236 tmp.lowerBound()=n;
1.237 return tmp;
1.238 }
1.239 @@ -1678,7 +1705,7 @@
1.240 const LpBase::Value &n)
1.241 {
1.242 LpBase::Constr tmp(c);
1.243 - LEMON_ASSERT(std::isnan(tmp.upperBound()), "Wrong LP constraint");
1.244 + LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
1.245 tmp.upperBound()=n;
1.246 return tmp;
1.247 }
1.248 @@ -1690,7 +1717,7 @@
1.249 inline LpBase::Constr operator>=(const LpBase::Value &n,
1.250 const LpBase::Constr &c) {
1.251 LpBase::Constr tmp(c);
1.252 - LEMON_ASSERT(std::isnan(tmp.upperBound()), "Wrong LP constraint");
1.253 + LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
1.254 tmp.upperBound()=n;
1.255 return tmp;
1.256 }
1.257 @@ -1702,7 +1729,7 @@
1.258 const LpBase::Value &n)
1.259 {
1.260 LpBase::Constr tmp(c);
1.261 - LEMON_ASSERT(std::isnan(tmp.lowerBound()), "Wrong LP constraint");
1.262 + LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
1.263 tmp.lowerBound()=n;
1.264 return tmp;
1.265 }
1.266 @@ -1775,15 +1802,15 @@
1.267
1.268 /// The problem types for primal and dual problems
1.269 enum ProblemType {
1.270 - ///Feasible solution hasn't been found (but may exist).
1.271 + /// = 0. Feasible solution hasn't been found (but may exist).
1.272 UNDEFINED = 0,
1.273 - ///The problem has no feasible solution
1.274 + /// = 1. The problem has no feasible solution.
1.275 INFEASIBLE = 1,
1.276 - ///Feasible solution found
1.277 + /// = 2. Feasible solution found.
1.278 FEASIBLE = 2,
1.279 - ///Optimal solution exists and found
1.280 + /// = 3. Optimal solution exists and found.
1.281 OPTIMAL = 3,
1.282 - ///The cost function is unbounded
1.283 + /// = 4. The cost function is unbounded.
1.284 UNBOUNDED = 4
1.285 };
1.286
1.287 @@ -1821,6 +1848,11 @@
1.288
1.289 public:
1.290
1.291 + ///Allocate a new LP problem instance
1.292 + virtual LpSolver* newSolver() const = 0;
1.293 + ///Make a copy of the LP problem
1.294 + virtual LpSolver* cloneSolver() const = 0;
1.295 +
1.296 ///\name Solve the LP
1.297
1.298 ///@{
1.299 @@ -1834,7 +1866,7 @@
1.300
1.301 ///@}
1.302
1.303 - ///\name Obtain the solution
1.304 + ///\name Obtain the Solution
1.305
1.306 ///@{
1.307
1.308 @@ -1935,13 +1967,8 @@
1.309 Value primal() const { return _getPrimalValue()+obj_const_comp;}
1.310 ///@}
1.311
1.312 - LpSolver* newSolver() {return _newSolver();}
1.313 - LpSolver* cloneSolver() {return _cloneSolver();}
1.314 -
1.315 protected:
1.316
1.317 - virtual LpSolver* _newSolver() const = 0;
1.318 - virtual LpSolver* _cloneSolver() const = 0;
1.319 };
1.320
1.321
1.322 @@ -1961,20 +1988,24 @@
1.323
1.324 /// The problem types for MIP problems
1.325 enum ProblemType {
1.326 - ///Feasible solution hasn't been found (but may exist).
1.327 + /// = 0. Feasible solution hasn't been found (but may exist).
1.328 UNDEFINED = 0,
1.329 - ///The problem has no feasible solution
1.330 + /// = 1. The problem has no feasible solution.
1.331 INFEASIBLE = 1,
1.332 - ///Feasible solution found
1.333 + /// = 2. Feasible solution found.
1.334 FEASIBLE = 2,
1.335 - ///Optimal solution exists and found
1.336 + /// = 3. Optimal solution exists and found.
1.337 OPTIMAL = 3,
1.338 - ///The cost function is unbounded
1.339 - ///
1.340 - ///The Mip or at least the relaxed problem is unbounded
1.341 + /// = 4. The cost function is unbounded.
1.342 + ///The Mip or at least the relaxed problem is unbounded.
1.343 UNBOUNDED = 4
1.344 };
1.345
1.346 + ///Allocate a new MIP problem instance
1.347 + virtual MipSolver* newSolver() const = 0;
1.348 + ///Make a copy of the MIP problem
1.349 + virtual MipSolver* cloneSolver() const = 0;
1.350 +
1.351 ///\name Solve the MIP
1.352
1.353 ///@{
1.354 @@ -1988,14 +2019,14 @@
1.355
1.356 ///@}
1.357
1.358 - ///\name Setting column type
1.359 + ///\name Set Column Type
1.360 ///@{
1.361
1.362 ///Possible variable (column) types (e.g. real, integer, binary etc.)
1.363 enum ColTypes {
1.364 - ///Continuous variable (default)
1.365 + /// = 0. Continuous variable (default).
1.366 REAL = 0,
1.367 - ///Integer variable
1.368 + /// = 1. Integer variable.
1.369 INTEGER = 1
1.370 };
1.371
1.372 @@ -2016,7 +2047,7 @@
1.373 }
1.374 ///@}
1.375
1.376 - ///\name Obtain the solution
1.377 + ///\name Obtain the Solution
1.378
1.379 ///@{
1.380
1.381 @@ -2062,15 +2093,6 @@
1.382 virtual Value _getSol(int i) const = 0;
1.383 virtual Value _getSolValue() const = 0;
1.384
1.385 - public:
1.386 -
1.387 - MipSolver* newSolver() {return _newSolver();}
1.388 - MipSolver* cloneSolver() {return _cloneSolver();}
1.389 -
1.390 - protected:
1.391 -
1.392 - virtual MipSolver* _newSolver() const = 0;
1.393 - virtual MipSolver* _cloneSolver() const = 0;
1.394 };
1.395
1.396