deba@481: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@481: * deba@481: * This file is a part of LEMON, a generic C++ optimization library. deba@481: * alpar@1270: * Copyright (C) 2003-2013 deba@481: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@481: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@481: * deba@481: * Permission to use, modify and distribute this software is granted deba@481: * provided that this copyright notice appears in all copies. For deba@481: * precise terms see the accompanying LICENSE file. deba@481: * deba@481: * This software is provided "AS IS" with no warranty of any kind, deba@481: * express or implied, and with no claim as to its suitability for any deba@481: * purpose. deba@481: * deba@481: */ deba@481: deba@481: #ifndef LEMON_LP_BASE_H deba@481: #define LEMON_LP_BASE_H deba@481: deba@481: #include deba@481: #include deba@481: #include deba@481: #include deba@481: #include deba@481: deba@482: #include deba@482: #include deba@482: deba@481: #include deba@482: #include deba@481: ggab90@1336: #include ggab90@1336: deba@481: ///\file deba@481: ///\brief The interface of the LP solver interface. deba@481: ///\ingroup lp_group deba@481: namespace lemon { deba@481: deba@482: ///Common base class for LP and MIP solvers deba@481: deba@482: ///Usually this class is not used directly, please use one of the concrete deba@482: ///implementations of the solver interface. deba@481: ///\ingroup lp_group deba@482: class LpBase { deba@481: deba@481: protected: deba@481: ggab90@1336: _solver_bits::VarIndex _rows; ggab90@1336: _solver_bits::VarIndex _cols; deba@481: deba@481: public: deba@481: deba@481: ///Possible outcomes of an LP solving procedure deba@481: enum SolveExitStatus { kpeter@631: /// = 0. It means that the problem has been successfully solved: either deba@481: ///an optimal solution has been found or infeasibility/unboundedness deba@481: ///has been proved. deba@481: SOLVED = 0, kpeter@631: /// = 1. Any other case (including the case when some user specified kpeter@631: ///limit has been exceeded). deba@481: UNSOLVED = 1 deba@481: }; deba@481: deba@482: ///Direction of the optimization deba@482: enum Sense { deba@482: /// Minimization deba@482: MIN, deba@482: /// Maximization deba@482: MAX deba@481: }; deba@481: deba@623: ///Enum for \c messageLevel() parameter deba@623: enum MessageLevel { kpeter@631: /// No output (default value). deba@623: MESSAGE_NOTHING, kpeter@631: /// Error messages only. deba@623: MESSAGE_ERROR, kpeter@631: /// Warnings. deba@623: MESSAGE_WARNING, kpeter@631: /// Normal output. deba@623: MESSAGE_NORMAL, kpeter@631: /// Verbose output. deba@623: MESSAGE_VERBOSE deba@623: }; alpar@956: deba@623: deba@481: ///The floating point type used by the solver deba@481: typedef double Value; deba@481: ///The infinity constant deba@481: static const Value INF; deba@481: ///The not a number constant deba@481: static const Value NaN; deba@481: deba@481: friend class Col; deba@481: friend class ColIt; deba@481: friend class Row; deba@482: friend class RowIt; deba@481: deba@481: ///Refer to a column of the LP. deba@481: deba@481: ///This type is used to refer to a column of the LP. deba@481: /// deba@481: ///Its value remains valid and correct even after the addition or erase of deba@481: ///other columns. deba@481: /// deba@482: ///\note This class is similar to other Item types in LEMON, like deba@482: ///Node and Arc types in digraph. deba@481: class Col { deba@482: friend class LpBase; deba@481: protected: deba@482: int _id; deba@482: explicit Col(int id) : _id(id) {} deba@481: public: deba@481: typedef Value ExprValue; deba@482: typedef True LpCol; deba@482: /// Default constructor alpar@956: deba@482: /// \warning The default constructor sets the Col to an deba@482: /// undefined value. deba@481: Col() {} deba@482: /// Invalid constructor \& conversion. alpar@956: deba@482: /// This constructor initializes the Col to be invalid. alpar@956: /// \sa Invalid for more details. deba@482: Col(const Invalid&) : _id(-1) {} deba@482: /// Equality operator deba@482: deba@482: /// Two \ref Col "Col"s are equal if and only if they point to deba@482: /// the same LP column or both are invalid. deba@482: bool operator==(Col c) const {return _id == c._id;} deba@482: /// Inequality operator deba@482: deba@482: /// \sa operator==(Col c) deba@482: /// deba@482: bool operator!=(Col c) const {return _id != c._id;} deba@482: /// Artificial ordering operator. deba@482: deba@482: /// To allow the use of this object in std::map or similar deba@482: /// associative container we require this. deba@482: /// deba@482: /// \note This operator only have to define some strict ordering of deba@482: /// the items; this order has nothing to do with the iteration deba@482: /// ordering of the items. deba@482: bool operator<(Col c) const {return _id < c._id;} deba@481: }; deba@481: deba@482: ///Iterator for iterate over the columns of an LP problem deba@482: kpeter@833: /// Its usage is quite simple, for example, you can count the number deba@482: /// of columns in an LP \c lp: deba@482: ///\code deba@482: /// int count=0; deba@482: /// for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count; deba@482: ///\endcode deba@481: class ColIt : public Col { deba@482: const LpBase *_solver; deba@481: public: deba@482: /// Default constructor alpar@956: deba@482: /// \warning The default constructor sets the iterator deba@482: /// to an undefined value. deba@481: ColIt() {} deba@482: /// Sets the iterator to the first Col alpar@956: deba@482: /// Sets the iterator to the first Col. deba@482: /// deba@482: ColIt(const LpBase &solver) : _solver(&solver) deba@481: { ggab90@1336: _solver->_cols.firstItem(_id); deba@481: } deba@482: /// Invalid constructor \& conversion alpar@956: deba@482: /// Initialize the iterator to be invalid. deba@482: /// \sa Invalid for more details. deba@481: ColIt(const Invalid&) : Col(INVALID) {} deba@482: /// Next column alpar@956: deba@482: /// Assign the iterator to the next column. deba@482: /// deba@481: ColIt &operator++() deba@481: { ggab90@1336: _solver->_cols.nextItem(_id); deba@481: return *this; deba@481: } deba@481: }; deba@481: ggab90@1336: /// \brief Gets the collection of the columns of the LP problem. ggab90@1336: /// ggab90@1336: /// This function can be used for iterating on ggab90@1336: /// the columns of the LP problem. It returns a wrapped ColIt, which looks ggab90@1336: /// like an STL container (by having begin() and end()) ggab90@1336: /// which you can use in range-based for loops, STL algorithms, etc. ggab90@1336: /// For example you can write: ggab90@1336: ///\code ggab90@1336: /// for(auto c: lp.cols()) ggab90@1336: /// doSomething(c); ggab90@1336: LemonRangeWrapper1 cols() { ggab90@1336: return LemonRangeWrapper1(*this); ggab90@1336: } ggab90@1336: ggab90@1336: deba@482: /// \brief Returns the ID of the column. deba@482: static int id(const Col& col) { return col._id; } deba@482: /// \brief Returns the column with the given ID. deba@482: /// deba@482: /// \pre The argument should be a valid column ID in the LP problem. deba@482: static Col colFromId(int id) { return Col(id); } deba@481: deba@481: ///Refer to a row of the LP. deba@481: deba@481: ///This type is used to refer to a row of the LP. deba@481: /// deba@481: ///Its value remains valid and correct even after the addition or erase of deba@481: ///other rows. deba@481: /// deba@482: ///\note This class is similar to other Item types in LEMON, like deba@482: ///Node and Arc types in digraph. deba@481: class Row { deba@482: friend class LpBase; deba@481: protected: deba@482: int _id; deba@482: explicit Row(int id) : _id(id) {} deba@481: public: deba@481: typedef Value ExprValue; deba@482: typedef True LpRow; deba@482: /// Default constructor alpar@956: deba@482: /// \warning The default constructor sets the Row to an deba@482: /// undefined value. deba@481: Row() {} deba@482: /// Invalid constructor \& conversion. alpar@956: deba@482: /// This constructor initializes the Row to be invalid. alpar@956: /// \sa Invalid for more details. deba@482: Row(const Invalid&) : _id(-1) {} deba@482: /// Equality operator deba@481: deba@482: /// Two \ref Row "Row"s are equal if and only if they point to deba@482: /// the same LP row or both are invalid. deba@482: bool operator==(Row r) const {return _id == r._id;} deba@482: /// Inequality operator alpar@956: deba@482: /// \sa operator==(Row r) deba@482: /// deba@482: bool operator!=(Row r) const {return _id != r._id;} deba@482: /// Artificial ordering operator. deba@482: deba@482: /// To allow the use of this object in std::map or similar deba@482: /// associative container we require this. deba@482: /// deba@482: /// \note This operator only have to define some strict ordering of deba@482: /// the items; this order has nothing to do with the iteration deba@482: /// ordering of the items. deba@482: bool operator<(Row r) const {return _id < r._id;} deba@481: }; deba@481: deba@482: ///Iterator for iterate over the rows of an LP problem deba@482: kpeter@833: /// Its usage is quite simple, for example, you can count the number deba@482: /// of rows in an LP \c lp: deba@482: ///\code deba@482: /// int count=0; deba@482: /// for (LpBase::RowIt c(lp); c!=INVALID; ++c) ++count; deba@482: ///\endcode deba@481: class RowIt : public Row { deba@482: const LpBase *_solver; deba@481: public: deba@482: /// Default constructor alpar@956: deba@482: /// \warning The default constructor sets the iterator deba@482: /// to an undefined value. deba@481: RowIt() {} deba@482: /// Sets the iterator to the first Row alpar@956: deba@482: /// Sets the iterator to the first Row. deba@482: /// deba@482: RowIt(const LpBase &solver) : _solver(&solver) deba@481: { ggab90@1336: _solver->_rows.firstItem(_id); deba@481: } deba@482: /// Invalid constructor \& conversion alpar@956: deba@482: /// Initialize the iterator to be invalid. deba@482: /// \sa Invalid for more details. deba@481: RowIt(const Invalid&) : Row(INVALID) {} deba@482: /// Next row alpar@956: deba@482: /// Assign the iterator to the next row. deba@482: /// deba@481: RowIt &operator++() deba@481: { ggab90@1336: _solver->_rows.nextItem(_id); deba@481: return *this; deba@481: } deba@481: }; ggab90@1336: ggab90@1336: /// \brief Gets the collection of the rows of the LP problem. ggab90@1336: /// ggab90@1336: /// This function can be used for iterating on ggab90@1336: /// the rows of the LP problem. It returns a wrapped RowIt, which looks ggab90@1336: /// like an STL container (by having begin() and end()) ggab90@1336: /// which you can use in range-based for loops, STL algorithms, etc. ggab90@1336: /// For example you can write: ggab90@1336: ///\code ggab90@1336: /// for(auto c: lp.rows()) ggab90@1336: /// doSomething(c); ggab90@1336: LemonRangeWrapper1 rows() { ggab90@1336: return LemonRangeWrapper1(*this); ggab90@1336: } ggab90@1336: deba@481: deba@482: /// \brief Returns the ID of the row. deba@482: static int id(const Row& row) { return row._id; } deba@482: /// \brief Returns the row with the given ID. deba@482: /// deba@482: /// \pre The argument should be a valid row ID in the LP problem. deba@482: static Row rowFromId(int id) { return Row(id); } deba@481: deba@481: public: deba@481: deba@481: ///Linear expression of variables and a constant component deba@481: deba@481: ///This data structure stores a linear expression of the variables deba@481: ///(\ref Col "Col"s) and also has a constant component. deba@481: /// deba@481: ///There are several ways to access and modify the contents of this deba@481: ///container. deba@481: ///\code deba@481: ///e[v]=5; deba@481: ///e[v]+=12; deba@481: ///e.erase(v); deba@481: ///\endcode deba@481: ///or you can also iterate through its elements. deba@481: ///\code deba@481: ///double s=0; deba@482: ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i) deba@482: /// s+=*i * primal(i); deba@481: ///\endcode deba@482: ///(This code computes the primal value of the expression). deba@481: ///- Numbers (double's) deba@481: ///and variables (\ref Col "Col"s) directly convert to an deba@481: ///\ref Expr and the usual linear operations are defined, so deba@481: ///\code deba@481: ///v+w deba@481: ///2*v-3.12*(v-w/2)+2 deba@481: ///v*2.1+(3*v+(v*12+w+6)*3)/2 deba@481: ///\endcode deba@482: ///are valid expressions. deba@481: ///The usual assignment operations are also defined. deba@481: ///\code deba@481: ///e=v+w; deba@481: ///e+=2*v-3.12*(v-w/2)+2; deba@481: ///e*=3.4; deba@481: ///e/=5; deba@481: ///\endcode deba@482: ///- The constant member can be set and read by dereference deba@482: /// operator (unary *) deba@482: /// deba@481: ///\code deba@482: ///*e=12; deba@482: ///double c=*e; deba@481: ///\endcode deba@481: /// deba@481: ///\sa Constr deba@482: class Expr { deba@482: friend class LpBase; deba@481: public: deba@482: /// The key type of the expression deba@482: typedef LpBase::Col Key; deba@482: /// The value type of the expression deba@482: typedef LpBase::Value Value; deba@481: deba@481: protected: deba@482: Value const_comp; deba@482: std::map comps; deba@481: deba@481: public: deba@482: typedef True SolverExpr; deba@482: /// Default constructor alpar@956: deba@482: /// Construct an empty expression, the coefficients and deba@482: /// the constant component are initialized to zero. deba@482: Expr() : const_comp(0) {} deba@482: /// Construct an expression from a column deba@482: deba@482: /// Construct an expression, which has a term with \c c variable deba@482: /// and 1.0 coefficient. deba@482: Expr(const Col &c) : const_comp(0) { deba@482: typedef std::map::value_type pair_type; deba@482: comps.insert(pair_type(id(c), 1)); deba@481: } deba@482: /// Construct an expression from a constant deba@482: deba@482: /// Construct an expression, which's constant component is \c v. deba@482: /// deba@481: Expr(const Value &v) : const_comp(v) {} deba@482: /// Returns the coefficient of the column deba@482: Value operator[](const Col& c) const { deba@482: std::map::const_iterator it=comps.find(id(c)); deba@482: if (it != comps.end()) { deba@482: return it->second; deba@482: } else { deba@482: return 0; deba@481: } deba@481: } deba@482: /// Returns the coefficient of the column deba@482: Value& operator[](const Col& c) { deba@482: return comps[id(c)]; deba@482: } deba@482: /// Sets the coefficient of the column deba@482: void set(const Col &c, const Value &v) { deba@482: if (v != 0.0) { deba@482: typedef std::map::value_type pair_type; deba@482: comps.insert(pair_type(id(c), v)); deba@482: } else { deba@482: comps.erase(id(c)); deba@482: } deba@482: } deba@482: /// Returns the constant component of the expression deba@482: Value& operator*() { return const_comp; } deba@482: /// Returns the constant component of the expression deba@482: const Value& operator*() const { return const_comp; } deba@482: /// \brief Removes the coefficients which's absolute value does deba@482: /// not exceed \c epsilon. It also sets to zero the constant deba@482: /// component, if it does not exceed epsilon in absolute value. deba@482: void simplify(Value epsilon = 0.0) { deba@482: std::map::iterator it=comps.begin(); deba@482: while (it != comps.end()) { deba@482: std::map::iterator jt=it; deba@482: ++jt; deba@482: if (std::fabs((*it).second) <= epsilon) comps.erase(it); deba@482: it=jt; deba@482: } deba@482: if (std::fabs(const_comp) <= epsilon) const_comp = 0; deba@481: } deba@481: deba@482: void simplify(Value epsilon = 0.0) const { deba@482: const_cast(this)->simplify(epsilon); deba@481: } deba@481: deba@481: ///Sets all coefficients and the constant component to 0. deba@481: void clear() { deba@482: comps.clear(); deba@481: const_comp=0; deba@481: } deba@481: deba@482: ///Compound assignment deba@481: Expr &operator+=(const Expr &e) { deba@482: for (std::map::const_iterator it=e.comps.begin(); deba@482: it!=e.comps.end(); ++it) deba@482: comps[it->first]+=it->second; deba@481: const_comp+=e.const_comp; deba@481: return *this; deba@481: } deba@482: ///Compound assignment deba@481: Expr &operator-=(const Expr &e) { deba@482: for (std::map::const_iterator it=e.comps.begin(); deba@482: it!=e.comps.end(); ++it) deba@482: comps[it->first]-=it->second; deba@481: const_comp-=e.const_comp; deba@481: return *this; deba@481: } deba@482: ///Multiply with a constant deba@482: Expr &operator*=(const Value &v) { deba@482: for (std::map::iterator it=comps.begin(); deba@482: it!=comps.end(); ++it) deba@482: it->second*=v; deba@482: const_comp*=v; deba@481: return *this; deba@481: } deba@482: ///Division with a constant deba@481: Expr &operator/=(const Value &c) { deba@482: for (std::map::iterator it=comps.begin(); deba@482: it!=comps.end(); ++it) deba@482: it->second/=c; deba@481: const_comp/=c; deba@481: return *this; deba@481: } deba@481: deba@482: ///Iterator over the expression alpar@956: alpar@956: ///The iterator iterates over the terms of the expression. alpar@956: /// deba@482: ///\code deba@482: ///double s=0; deba@482: ///for(LpBase::Expr::CoeffIt i(e);i!=INVALID;++i) deba@482: /// s+= *i * primal(i); deba@482: ///\endcode deba@482: class CoeffIt { deba@482: private: deba@482: deba@482: std::map::iterator _it, _end; deba@482: deba@482: public: deba@482: deba@482: /// Sets the iterator to the first term alpar@956: deba@482: /// Sets the iterator to the first term of the expression. deba@482: /// deba@482: CoeffIt(Expr& e) deba@482: : _it(e.comps.begin()), _end(e.comps.end()){} deba@482: deba@482: /// Convert the iterator to the column of the term deba@482: operator Col() const { deba@482: return colFromId(_it->first); deba@482: } deba@482: deba@482: /// Returns the coefficient of the term deba@482: Value& operator*() { return _it->second; } deba@482: deba@482: /// Returns the coefficient of the term deba@482: const Value& operator*() const { return _it->second; } deba@482: /// Next term alpar@956: deba@482: /// Assign the iterator to the next term. deba@482: /// deba@482: CoeffIt& operator++() { ++_it; return *this; } deba@482: deba@482: /// Equality operator deba@482: bool operator==(Invalid) const { return _it == _end; } deba@482: /// Inequality operator deba@482: bool operator!=(Invalid) const { return _it != _end; } deba@482: }; deba@482: deba@482: /// Const iterator over the expression alpar@956: alpar@956: ///The iterator iterates over the terms of the expression. alpar@956: /// deba@482: ///\code deba@482: ///double s=0; deba@482: ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i) deba@482: /// s+=*i * primal(i); deba@482: ///\endcode deba@482: class ConstCoeffIt { deba@482: private: deba@482: deba@482: std::map::const_iterator _it, _end; deba@482: deba@482: public: deba@482: deba@482: /// Sets the iterator to the first term alpar@956: deba@482: /// Sets the iterator to the first term of the expression. deba@482: /// deba@482: ConstCoeffIt(const Expr& e) deba@482: : _it(e.comps.begin()), _end(e.comps.end()){} deba@482: deba@482: /// Convert the iterator to the column of the term deba@482: operator Col() const { deba@482: return colFromId(_it->first); deba@482: } deba@482: deba@482: /// Returns the coefficient of the term deba@482: const Value& operator*() const { return _it->second; } deba@482: deba@482: /// Next term alpar@956: deba@482: /// Assign the iterator to the next term. deba@482: /// deba@482: ConstCoeffIt& operator++() { ++_it; return *this; } deba@482: deba@482: /// Equality operator deba@482: bool operator==(Invalid) const { return _it == _end; } deba@482: /// Inequality operator deba@482: bool operator!=(Invalid) const { return _it != _end; } deba@482: }; deba@482: deba@481: }; deba@481: deba@481: ///Linear constraint deba@481: deba@481: ///This data stucture represents a linear constraint in the LP. deba@481: ///Basically it is a linear expression with a lower or an upper bound deba@481: ///(or both). These parts of the constraint can be obtained by the member deba@481: ///functions \ref expr(), \ref lowerBound() and \ref upperBound(), deba@481: ///respectively. deba@481: ///There are two ways to construct a constraint. deba@481: ///- You can set the linear expression and the bounds directly deba@481: /// by the functions above. deba@481: ///- The operators \<=, == and \>= deba@481: /// are defined between expressions, or even between constraints whenever deba@481: /// it makes sense. Therefore if \c e and \c f are linear expressions and deba@481: /// \c s and \c t are numbers, then the followings are valid expressions deba@481: /// and thus they can be used directly e.g. in \ref addRow() whenever deba@481: /// it makes sense. deba@481: ///\code deba@481: /// e<=s deba@481: /// e<=f deba@481: /// e==f deba@481: /// s<=e<=t deba@481: /// e>=t deba@481: ///\endcode deba@482: ///\warning The validity of a constraint is checked only at run deba@482: ///time, so e.g. \ref addRow(x[1]\<=x[2]<=5) will deba@482: ///compile, but will fail an assertion. deba@481: class Constr deba@481: { deba@481: public: deba@482: typedef LpBase::Expr Expr; deba@481: typedef Expr::Key Key; deba@481: typedef Expr::Value Value; deba@481: deba@481: protected: deba@481: Expr _expr; deba@481: Value _lb,_ub; deba@481: public: deba@481: ///\e deba@481: Constr() : _expr(), _lb(NaN), _ub(NaN) {} deba@481: ///\e deba@482: Constr(Value lb, const Expr &e, Value ub) : deba@481: _expr(e), _lb(lb), _ub(ub) {} deba@481: Constr(const Expr &e) : deba@481: _expr(e), _lb(NaN), _ub(NaN) {} deba@481: ///\e deba@481: void clear() deba@481: { deba@481: _expr.clear(); deba@481: _lb=_ub=NaN; deba@481: } deba@481: deba@481: ///Reference to the linear expression deba@481: Expr &expr() { return _expr; } deba@481: ///Cont reference to the linear expression deba@481: const Expr &expr() const { return _expr; } deba@481: ///Reference to the lower bound. deba@481: deba@481: ///\return deba@481: ///- \ref INF "INF": the constraint is lower unbounded. deba@481: ///- \ref NaN "NaN": lower bound has not been set. deba@481: ///- finite number: the lower bound deba@481: Value &lowerBound() { return _lb; } deba@481: ///The const version of \ref lowerBound() deba@481: const Value &lowerBound() const { return _lb; } deba@481: ///Reference to the upper bound. deba@481: deba@481: ///\return deba@481: ///- \ref INF "INF": the constraint is upper unbounded. deba@481: ///- \ref NaN "NaN": upper bound has not been set. deba@481: ///- finite number: the upper bound deba@481: Value &upperBound() { return _ub; } deba@481: ///The const version of \ref upperBound() deba@481: const Value &upperBound() const { return _ub; } deba@481: ///Is the constraint lower bounded? deba@481: bool lowerBounded() const { alpar@558: return _lb != -INF && !isNaN(_lb); deba@481: } deba@481: ///Is the constraint upper bounded? deba@481: bool upperBounded() const { alpar@558: return _ub != INF && !isNaN(_ub); deba@481: } deba@481: deba@481: }; deba@481: deba@481: ///Linear expression of rows deba@481: deba@481: ///This data structure represents a column of the matrix, deba@481: ///thas is it strores a linear expression of the dual variables deba@481: ///(\ref Row "Row"s). deba@481: /// deba@481: ///There are several ways to access and modify the contents of this deba@481: ///container. deba@481: ///\code deba@481: ///e[v]=5; deba@481: ///e[v]+=12; deba@481: ///e.erase(v); deba@481: ///\endcode deba@481: ///or you can also iterate through its elements. deba@481: ///\code deba@481: ///double s=0; deba@482: ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i) deba@482: /// s+=*i; deba@481: ///\endcode deba@481: ///(This code computes the sum of all coefficients). deba@481: ///- Numbers (double's) deba@481: ///and variables (\ref Row "Row"s) directly convert to an deba@481: ///\ref DualExpr and the usual linear operations are defined, so deba@481: ///\code deba@481: ///v+w deba@481: ///2*v-3.12*(v-w/2) deba@481: ///v*2.1+(3*v+(v*12+w)*3)/2 deba@481: ///\endcode deba@482: ///are valid \ref DualExpr dual expressions. deba@481: ///The usual assignment operations are also defined. deba@481: ///\code deba@481: ///e=v+w; deba@481: ///e+=2*v-3.12*(v-w/2); deba@481: ///e*=3.4; deba@481: ///e/=5; deba@481: ///\endcode deba@481: /// deba@481: ///\sa Expr deba@482: class DualExpr { deba@482: friend class LpBase; deba@481: public: deba@482: /// The key type of the expression deba@482: typedef LpBase::Row Key; deba@482: /// The value type of the expression deba@482: typedef LpBase::Value Value; deba@481: deba@481: protected: deba@482: std::map comps; deba@481: deba@481: public: deba@482: typedef True SolverExpr; deba@482: /// Default constructor alpar@956: deba@482: /// Construct an empty expression, the coefficients are deba@482: /// initialized to zero. deba@482: DualExpr() {} deba@482: /// Construct an expression from a row deba@482: deba@482: /// Construct an expression, which has a term with \c r dual deba@482: /// variable and 1.0 coefficient. deba@482: DualExpr(const Row &r) { deba@482: typedef std::map::value_type pair_type; deba@482: comps.insert(pair_type(id(r), 1)); deba@481: } deba@482: /// Returns the coefficient of the row deba@482: Value operator[](const Row& r) const { deba@482: std::map::const_iterator it = comps.find(id(r)); deba@482: if (it != comps.end()) { deba@482: return it->second; deba@482: } else { deba@482: return 0; deba@482: } deba@481: } deba@482: /// Returns the coefficient of the row deba@482: Value& operator[](const Row& r) { deba@482: return comps[id(r)]; deba@482: } deba@482: /// Sets the coefficient of the row deba@482: void set(const Row &r, const Value &v) { deba@482: if (v != 0.0) { deba@482: typedef std::map::value_type pair_type; deba@482: comps.insert(pair_type(id(r), v)); deba@482: } else { deba@482: comps.erase(id(r)); deba@482: } deba@482: } deba@482: /// \brief Removes the coefficients which's absolute value does alpar@956: /// not exceed \c epsilon. deba@482: void simplify(Value epsilon = 0.0) { deba@482: std::map::iterator it=comps.begin(); deba@482: while (it != comps.end()) { deba@482: std::map::iterator jt=it; deba@482: ++jt; deba@482: if (std::fabs((*it).second) <= epsilon) comps.erase(it); deba@482: it=jt; deba@481: } deba@481: } deba@481: deba@482: void simplify(Value epsilon = 0.0) const { deba@482: const_cast(this)->simplify(epsilon); deba@481: } deba@481: deba@481: ///Sets all coefficients to 0. deba@481: void clear() { deba@482: comps.clear(); deba@482: } deba@482: ///Compound assignment deba@482: DualExpr &operator+=(const DualExpr &e) { deba@482: for (std::map::const_iterator it=e.comps.begin(); deba@482: it!=e.comps.end(); ++it) deba@482: comps[it->first]+=it->second; deba@482: return *this; deba@482: } deba@482: ///Compound assignment deba@482: DualExpr &operator-=(const DualExpr &e) { deba@482: for (std::map::const_iterator it=e.comps.begin(); deba@482: it!=e.comps.end(); ++it) deba@482: comps[it->first]-=it->second; deba@482: return *this; deba@482: } deba@482: ///Multiply with a constant deba@482: DualExpr &operator*=(const Value &v) { deba@482: for (std::map::iterator it=comps.begin(); deba@482: it!=comps.end(); ++it) deba@482: it->second*=v; deba@482: return *this; deba@482: } deba@482: ///Division with a constant deba@482: DualExpr &operator/=(const Value &v) { deba@482: for (std::map::iterator it=comps.begin(); deba@482: it!=comps.end(); ++it) deba@482: it->second/=v; deba@482: return *this; deba@481: } deba@481: deba@482: ///Iterator over the expression alpar@956: alpar@956: ///The iterator iterates over the terms of the expression. alpar@956: /// deba@482: ///\code deba@482: ///double s=0; deba@482: ///for(LpBase::DualExpr::CoeffIt i(e);i!=INVALID;++i) deba@482: /// s+= *i * dual(i); deba@482: ///\endcode deba@482: class CoeffIt { deba@482: private: deba@482: deba@482: std::map::iterator _it, _end; deba@482: deba@482: public: deba@482: deba@482: /// Sets the iterator to the first term alpar@956: deba@482: /// Sets the iterator to the first term of the expression. deba@482: /// deba@482: CoeffIt(DualExpr& e) deba@482: : _it(e.comps.begin()), _end(e.comps.end()){} deba@482: deba@482: /// Convert the iterator to the row of the term deba@482: operator Row() const { deba@482: return rowFromId(_it->first); deba@482: } deba@482: deba@482: /// Returns the coefficient of the term deba@482: Value& operator*() { return _it->second; } deba@482: deba@482: /// Returns the coefficient of the term deba@482: const Value& operator*() const { return _it->second; } deba@482: deba@482: /// Next term alpar@956: deba@482: /// Assign the iterator to the next term. deba@482: /// deba@482: CoeffIt& operator++() { ++_it; return *this; } deba@482: deba@482: /// Equality operator deba@482: bool operator==(Invalid) const { return _it == _end; } deba@482: /// Inequality operator deba@482: bool operator!=(Invalid) const { return _it != _end; } deba@482: }; deba@482: deba@482: ///Iterator over the expression alpar@956: alpar@956: ///The iterator iterates over the terms of the expression. alpar@956: /// deba@482: ///\code deba@482: ///double s=0; deba@482: ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i) deba@482: /// s+= *i * dual(i); deba@482: ///\endcode deba@482: class ConstCoeffIt { deba@482: private: deba@482: deba@482: std::map::const_iterator _it, _end; deba@482: deba@482: public: deba@482: deba@482: /// Sets the iterator to the first term alpar@956: deba@482: /// Sets the iterator to the first term of the expression. deba@482: /// deba@482: ConstCoeffIt(const DualExpr& e) deba@482: : _it(e.comps.begin()), _end(e.comps.end()){} deba@482: deba@482: /// Convert the iterator to the row of the term deba@482: operator Row() const { deba@482: return rowFromId(_it->first); deba@482: } deba@482: deba@482: /// Returns the coefficient of the term deba@482: const Value& operator*() const { return _it->second; } deba@482: deba@482: /// Next term alpar@956: deba@482: /// Assign the iterator to the next term. deba@482: /// deba@482: ConstCoeffIt& operator++() { ++_it; return *this; } deba@482: deba@482: /// Equality operator deba@482: bool operator==(Invalid) const { return _it == _end; } deba@482: /// Inequality operator deba@482: bool operator!=(Invalid) const { return _it != _end; } deba@482: }; deba@481: }; deba@481: deba@481: deba@482: protected: deba@481: deba@482: class InsertIterator { deba@482: private: deba@482: deba@482: std::map& _host; deba@482: const _solver_bits::VarIndex& _index; deba@482: deba@481: public: deba@481: deba@481: typedef std::output_iterator_tag iterator_category; deba@481: typedef void difference_type; deba@481: typedef void value_type; deba@481: typedef void reference; deba@481: typedef void pointer; deba@481: deba@482: InsertIterator(std::map& host, deba@482: const _solver_bits::VarIndex& index) deba@482: : _host(host), _index(index) {} deba@481: deba@482: InsertIterator& operator=(const std::pair& value) { deba@482: typedef std::map::value_type pair_type; deba@482: _host.insert(pair_type(_index[value.first], value.second)); deba@481: return *this; deba@481: } deba@481: deba@482: InsertIterator& operator*() { return *this; } deba@482: InsertIterator& operator++() { return *this; } deba@482: InsertIterator operator++(int) { return *this; } deba@481: deba@481: }; deba@481: deba@482: class ExprIterator { deba@482: private: deba@482: std::map::const_iterator _host_it; deba@482: const _solver_bits::VarIndex& _index; deba@481: public: deba@481: deba@482: typedef std::bidirectional_iterator_tag iterator_category; deba@482: typedef std::ptrdiff_t difference_type; deba@481: typedef const std::pair value_type; deba@481: typedef value_type reference; deba@482: deba@481: class pointer { deba@481: public: deba@481: pointer(value_type& _value) : value(_value) {} deba@481: value_type* operator->() { return &value; } deba@481: private: deba@481: value_type value; deba@481: }; deba@481: deba@482: ExprIterator(const std::map::const_iterator& host_it, deba@482: const _solver_bits::VarIndex& index) deba@482: : _host_it(host_it), _index(index) {} deba@481: deba@481: reference operator*() { deba@482: return std::make_pair(_index(_host_it->first), _host_it->second); deba@481: } deba@481: deba@481: pointer operator->() { deba@481: return pointer(operator*()); deba@481: } deba@481: deba@482: ExprIterator& operator++() { ++_host_it; return *this; } deba@482: ExprIterator operator++(int) { deba@482: ExprIterator tmp(*this); ++_host_it; return tmp; deba@481: } deba@481: deba@482: ExprIterator& operator--() { --_host_it; return *this; } deba@482: ExprIterator operator--(int) { deba@482: ExprIterator tmp(*this); --_host_it; return tmp; deba@481: } deba@481: deba@482: bool operator==(const ExprIterator& it) const { deba@482: return _host_it == it._host_it; deba@481: } deba@481: deba@482: bool operator!=(const ExprIterator& it) const { deba@482: return _host_it != it._host_it; deba@481: } deba@481: deba@481: }; deba@481: deba@481: protected: deba@481: deba@482: //Abstract virtual functions deba@481: ggab90@1336: virtual int _addColId(int col) { return _cols.addIndex(col); } ggab90@1336: virtual int _addRowId(int row) { return _rows.addIndex(row); } deba@481: ggab90@1336: virtual void _eraseColId(int col) { _cols.eraseIndex(col); } ggab90@1336: virtual void _eraseRowId(int row) { _rows.eraseIndex(row); } deba@481: deba@481: virtual int _addCol() = 0; deba@481: virtual int _addRow() = 0; deba@481: deba@793: virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) { deba@793: int row = _addRow(); deba@793: _setRowCoeffs(row, b, e); deba@793: _setRowLowerBound(row, l); deba@793: _setRowUpperBound(row, u); deba@793: return row; deba@793: } deba@793: deba@481: virtual void _eraseCol(int col) = 0; deba@481: virtual void _eraseRow(int row) = 0; deba@481: deba@482: virtual void _getColName(int col, std::string& name) const = 0; deba@482: virtual void _setColName(int col, const std::string& name) = 0; deba@481: virtual int _colByName(const std::string& name) const = 0; deba@481: deba@482: virtual void _getRowName(int row, std::string& name) const = 0; deba@482: virtual void _setRowName(int row, const std::string& name) = 0; deba@482: virtual int _rowByName(const std::string& name) const = 0; deba@482: deba@482: virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e) = 0; deba@482: virtual void _getRowCoeffs(int i, InsertIterator b) const = 0; deba@482: deba@482: virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e) = 0; deba@482: virtual void _getColCoeffs(int i, InsertIterator b) const = 0; deba@482: deba@481: virtual void _setCoeff(int row, int col, Value value) = 0; deba@481: virtual Value _getCoeff(int row, int col) const = 0; deba@482: deba@481: virtual void _setColLowerBound(int i, Value value) = 0; deba@481: virtual Value _getColLowerBound(int i) const = 0; deba@482: deba@481: virtual void _setColUpperBound(int i, Value value) = 0; deba@481: virtual Value _getColUpperBound(int i) const = 0; deba@482: deba@482: virtual void _setRowLowerBound(int i, Value value) = 0; deba@482: virtual Value _getRowLowerBound(int i) const = 0; deba@482: deba@482: virtual void _setRowUpperBound(int i, Value value) = 0; deba@482: virtual Value _getRowUpperBound(int i) const = 0; deba@482: deba@482: virtual void _setObjCoeffs(ExprIterator b, ExprIterator e) = 0; deba@482: virtual void _getObjCoeffs(InsertIterator b) const = 0; deba@481: deba@481: virtual void _setObjCoeff(int i, Value obj_coef) = 0; deba@481: virtual Value _getObjCoeff(int i) const = 0; deba@481: deba@482: virtual void _setSense(Sense) = 0; deba@482: virtual Sense _getSense() const = 0; deba@481: deba@482: virtual void _clear() = 0; deba@481: deba@482: virtual const char* _solverName() const = 0; deba@481: deba@623: virtual void _messageLevel(MessageLevel level) = 0; deba@623: deba@481: //Own protected stuff deba@481: deba@481: //Constant component of the objective function deba@481: Value obj_const_comp; deba@481: ggab90@1336: LpBase() : _rows(), _cols(), obj_const_comp(0) {} deba@482: deba@481: public: deba@481: alpar@1252: ///Unsupported file format exception alpar@1231: class UnsupportedFormatError : public Exception alpar@1231: { alpar@1231: std::string _format; alpar@1231: mutable std::string _what; alpar@1231: public: alpar@1231: explicit UnsupportedFormatError(std::string format) throw() alpar@1231: : _format(format) { } alpar@1231: virtual ~UnsupportedFormatError() throw() {} alpar@1231: virtual const char* what() const throw() { alpar@1231: try { alpar@1231: _what.clear(); alpar@1231: std::ostringstream oss; alpar@1231: oss << "lemon::UnsupportedFormatError: " << _format; alpar@1231: _what = oss.str(); alpar@1231: } alpar@1231: catch (...) {} alpar@1231: if (!_what.empty()) return _what.c_str(); alpar@1231: else return "lemon::UnsupportedFormatError"; alpar@1231: } alpar@1231: }; alpar@1270: alpar@1231: protected: alpar@1231: virtual void _write(std::string, std::string format) const alpar@1231: { alpar@1231: throw UnsupportedFormatError(format); alpar@1231: } alpar@1270: alpar@1231: public: alpar@1231: deba@482: /// Virtual destructor deba@482: virtual ~LpBase() {} deba@481: deba@482: ///Gives back the name of the solver. deba@482: const char* solverName() const {return _solverName();} deba@481: kpeter@631: ///\name Build Up and Modify the LP deba@481: deba@481: ///@{ deba@481: deba@481: ///Add a new empty column (i.e a new variable) to the LP deba@482: Col addCol() { Col c; c._id = _addColId(_addCol()); return c;} deba@481: deba@482: ///\brief Adds several new columns (i.e variables) at once deba@481: /// deba@482: ///This magic function takes a container as its argument and fills deba@482: ///its elements with new columns (i.e. variables) deba@481: ///\param t can be deba@481: ///- a standard STL compatible iterable container with deba@482: ///\ref Col as its \c values_type like deba@481: ///\code deba@482: ///std::vector deba@482: ///std::list deba@481: ///\endcode deba@481: ///- a standard STL compatible iterable container with deba@482: ///\ref Col as its \c mapped_type like deba@481: ///\code deba@482: ///std::map deba@481: ///\endcode deba@481: ///- an iterable lemon \ref concepts::WriteMap "write map" like deba@481: ///\code deba@482: ///ListGraph::NodeMap deba@482: ///ListGraph::ArcMap deba@481: ///\endcode deba@481: ///\return The number of the created column. deba@481: #ifdef DOXYGEN deba@481: template deba@481: int addColSet(T &t) { return 0;} deba@481: #else deba@481: template deba@482: typename enable_if::type deba@481: addColSet(T &t,dummy<0> = 0) { deba@481: int s=0; deba@481: for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;} deba@481: return s; deba@481: } deba@481: template deba@482: typename enable_if::type deba@481: addColSet(T &t,dummy<1> = 1) { deba@481: int s=0; deba@481: for(typename T::iterator i=t.begin();i!=t.end();++i) { deba@481: i->second=addCol(); deba@481: s++; deba@481: } deba@481: return s; deba@481: } deba@481: template deba@482: typename enable_if::type deba@481: addColSet(T &t,dummy<2> = 2) { deba@481: int s=0; deba@481: for(typename T::MapIt i(t); i!=INVALID; ++i) deba@481: { deba@481: i.set(addCol()); deba@481: s++; deba@481: } deba@481: return s; deba@481: } deba@481: #endif deba@481: deba@481: ///Set a column (i.e a dual constraint) of the LP deba@481: deba@481: ///\param c is the column to be modified deba@481: ///\param e is a dual linear expression (see \ref DualExpr) deba@481: ///a better one. deba@482: void col(Col c, const DualExpr &e) { deba@481: e.simplify(); ggab90@1336: _setColCoeffs(_cols(id(c)), ExprIterator(e.comps.begin(), _rows), ggab90@1336: ExprIterator(e.comps.end(), _rows)); deba@481: } deba@481: deba@481: ///Get a column (i.e a dual constraint) of the LP deba@481: deba@482: ///\param c is the column to get deba@481: ///\return the dual expression associated to the column deba@481: DualExpr col(Col c) const { deba@481: DualExpr e; ggab90@1336: _getColCoeffs(_cols(id(c)), InsertIterator(e.comps, _rows)); deba@481: return e; deba@481: } deba@481: deba@481: ///Add a new column to the LP deba@481: deba@481: ///\param e is a dual linear expression (see \ref DualExpr) deba@482: ///\param o is the corresponding component of the objective deba@481: ///function. It is 0 by default. deba@481: ///\return The created column. deba@481: Col addCol(const DualExpr &e, Value o = 0) { deba@481: Col c=addCol(); deba@481: col(c,e); deba@481: objCoeff(c,o); deba@481: return c; deba@481: } deba@481: deba@481: ///Add a new empty row (i.e a new constraint) to the LP deba@481: deba@481: ///This function adds a new empty row (i.e a new constraint) to the LP. deba@481: ///\return The created row deba@482: Row addRow() { Row r; r._id = _addRowId(_addRow()); return r;} deba@481: deba@482: ///\brief Add several new rows (i.e constraints) at once deba@481: /// deba@482: ///This magic function takes a container as its argument and fills deba@482: ///its elements with new row (i.e. variables) deba@481: ///\param t can be deba@481: ///- a standard STL compatible iterable container with deba@482: ///\ref Row as its \c values_type like deba@481: ///\code deba@482: ///std::vector deba@482: ///std::list deba@481: ///\endcode deba@481: ///- a standard STL compatible iterable container with deba@482: ///\ref Row as its \c mapped_type like deba@481: ///\code deba@482: ///std::map deba@481: ///\endcode deba@481: ///- an iterable lemon \ref concepts::WriteMap "write map" like deba@481: ///\code deba@482: ///ListGraph::NodeMap deba@482: ///ListGraph::ArcMap deba@481: ///\endcode deba@481: ///\return The number of rows created. deba@481: #ifdef DOXYGEN deba@481: template deba@481: int addRowSet(T &t) { return 0;} deba@481: #else deba@481: template deba@482: typename enable_if::type deba@482: addRowSet(T &t, dummy<0> = 0) { deba@481: int s=0; deba@481: for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;} deba@481: return s; deba@481: } deba@481: template deba@482: typename enable_if::type deba@482: addRowSet(T &t, dummy<1> = 1) { deba@481: int s=0; deba@481: for(typename T::iterator i=t.begin();i!=t.end();++i) { deba@481: i->second=addRow(); deba@481: s++; deba@481: } deba@481: return s; deba@481: } deba@481: template deba@482: typename enable_if::type deba@482: addRowSet(T &t, dummy<2> = 2) { deba@481: int s=0; deba@481: for(typename T::MapIt i(t); i!=INVALID; ++i) deba@481: { deba@481: i.set(addRow()); deba@481: s++; deba@481: } deba@481: return s; deba@481: } deba@481: #endif deba@481: deba@481: ///Set a row (i.e a constraint) of the LP deba@481: deba@481: ///\param r is the row to be modified deba@481: ///\param l is lower bound (-\ref INF means no bound) deba@481: ///\param e is a linear expression (see \ref Expr) deba@481: ///\param u is the upper bound (\ref INF means no bound) deba@481: void row(Row r, Value l, const Expr &e, Value u) { deba@481: e.simplify(); ggab90@1336: _setRowCoeffs(_rows(id(r)), ExprIterator(e.comps.begin(), _cols), ggab90@1336: ExprIterator(e.comps.end(), _cols)); ggab90@1336: _setRowLowerBound(_rows(id(r)),l - *e); ggab90@1336: _setRowUpperBound(_rows(id(r)),u - *e); deba@481: } deba@481: deba@481: ///Set a row (i.e a constraint) of the LP deba@481: deba@481: ///\param r is the row to be modified deba@481: ///\param c is a linear expression (see \ref Constr) deba@481: void row(Row r, const Constr &c) { deba@481: row(r, c.lowerBounded()?c.lowerBound():-INF, deba@481: c.expr(), c.upperBounded()?c.upperBound():INF); deba@481: } deba@481: deba@481: deba@481: ///Get a row (i.e a constraint) of the LP deba@481: deba@481: ///\param r is the row to get deba@481: ///\return the expression associated to the row deba@481: Expr row(Row r) const { deba@481: Expr e; ggab90@1336: _getRowCoeffs(_rows(id(r)), InsertIterator(e.comps, _cols)); deba@481: return e; deba@481: } deba@481: deba@481: ///Add a new row (i.e a new constraint) to the LP deba@481: deba@481: ///\param l is the lower bound (-\ref INF means no bound) deba@481: ///\param e is a linear expression (see \ref Expr) deba@481: ///\param u is the upper bound (\ref INF means no bound) deba@481: ///\return The created row. deba@481: Row addRow(Value l,const Expr &e, Value u) { deba@793: Row r; deba@793: e.simplify(); ggab90@1336: r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), _cols), ggab90@1336: ExprIterator(e.comps.end(), _cols), u - *e)); deba@481: return r; deba@481: } deba@481: deba@481: ///Add a new row (i.e a new constraint) to the LP deba@481: deba@481: ///\param c is a linear expression (see \ref Constr) deba@481: ///\return The created row. deba@481: Row addRow(const Constr &c) { deba@793: Row r; deba@793: c.expr().simplify(); alpar@956: r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF, ggab90@1336: ExprIterator(c.expr().comps.begin(), _cols), ggab90@1336: ExprIterator(c.expr().comps.end(), _cols), deba@903: c.upperBounded()?c.upperBound()-*c.expr():INF)); deba@481: return r; deba@481: } deba@482: ///Erase a column (i.e a variable) from the LP deba@481: deba@482: ///\param c is the column to be deleted deba@482: void erase(Col c) { ggab90@1336: _eraseCol(_cols(id(c))); ggab90@1336: _eraseColId(_cols(id(c))); deba@481: } deba@482: ///Erase a row (i.e a constraint) from the LP deba@481: deba@481: ///\param r is the row to be deleted deba@482: void erase(Row r) { ggab90@1336: _eraseRow(_rows(id(r))); ggab90@1336: _eraseRowId(_rows(id(r))); deba@481: } deba@481: deba@481: /// Get the name of a column deba@481: deba@482: ///\param c is the coresponding column deba@481: ///\return The name of the colunm deba@481: std::string colName(Col c) const { deba@481: std::string name; ggab90@1336: _getColName(_cols(id(c)), name); deba@481: return name; deba@481: } deba@481: deba@481: /// Set the name of a column deba@481: deba@482: ///\param c is the coresponding column deba@481: ///\param name The name to be given deba@481: void colName(Col c, const std::string& name) { ggab90@1336: _setColName(_cols(id(c)), name); deba@481: } deba@481: deba@481: /// Get the column by its name deba@481: deba@481: ///\param name The name of the column deba@481: ///\return the proper column or \c INVALID deba@481: Col colByName(const std::string& name) const { deba@481: int k = _colByName(name); ggab90@1336: return k != -1 ? Col(_cols[k]) : Col(INVALID); deba@482: } deba@482: deba@482: /// Get the name of a row deba@482: deba@482: ///\param r is the coresponding row deba@482: ///\return The name of the row deba@482: std::string rowName(Row r) const { deba@482: std::string name; ggab90@1336: _getRowName(_rows(id(r)), name); deba@482: return name; deba@482: } deba@482: deba@482: /// Set the name of a row deba@482: deba@482: ///\param r is the coresponding row deba@482: ///\param name The name to be given deba@482: void rowName(Row r, const std::string& name) { ggab90@1336: _setRowName(_rows(id(r)), name); deba@482: } deba@482: deba@482: /// Get the row by its name deba@482: deba@482: ///\param name The name of the row deba@482: ///\return the proper row or \c INVALID deba@482: Row rowByName(const std::string& name) const { deba@482: int k = _rowByName(name); ggab90@1336: return k != -1 ? Row(_rows[k]) : Row(INVALID); deba@481: } deba@481: deba@481: /// Set an element of the coefficient matrix of the LP deba@481: deba@481: ///\param r is the row of the element to be modified deba@482: ///\param c is the column of the element to be modified deba@481: ///\param val is the new value of the coefficient deba@481: void coeff(Row r, Col c, Value val) { ggab90@1336: _setCoeff(_rows(id(r)),_cols(id(c)), val); deba@481: } deba@481: deba@481: /// Get an element of the coefficient matrix of the LP deba@481: deba@482: ///\param r is the row of the element deba@482: ///\param c is the column of the element deba@481: ///\return the corresponding coefficient deba@481: Value coeff(Row r, Col c) const { ggab90@1336: return _getCoeff(_rows(id(r)),_cols(id(c))); deba@481: } deba@481: deba@481: /// Set the lower bound of a column (i.e a variable) deba@481: deba@481: /// The lower bound of a variable (column) has to be given by an deba@481: /// extended number of type Value, i.e. a finite number of type deba@481: /// Value or -\ref INF. deba@481: void colLowerBound(Col c, Value value) { ggab90@1336: _setColLowerBound(_cols(id(c)),value); deba@481: } deba@481: deba@481: /// Get the lower bound of a column (i.e a variable) deba@481: deba@482: /// This function returns the lower bound for column (variable) \c c deba@481: /// (this might be -\ref INF as well). deba@482: ///\return The lower bound for column \c c deba@481: Value colLowerBound(Col c) const { ggab90@1336: return _getColLowerBound(_cols(id(c))); deba@481: } deba@481: deba@481: ///\brief Set the lower bound of several columns deba@482: ///(i.e variables) at once deba@481: /// deba@481: ///This magic function takes a container as its argument deba@481: ///and applies the function on all of its elements. deba@482: ///The lower bound of a variable (column) has to be given by an deba@482: ///extended number of type Value, i.e. a finite number of type deba@482: ///Value or -\ref INF. deba@481: #ifdef DOXYGEN deba@481: template deba@481: void colLowerBound(T &t, Value value) { return 0;} deba@481: #else deba@481: template deba@482: typename enable_if::type deba@481: colLowerBound(T &t, Value value,dummy<0> = 0) { deba@481: for(typename T::iterator i=t.begin();i!=t.end();++i) { deba@481: colLowerBound(*i, value); deba@481: } deba@481: } deba@481: template deba@482: typename enable_if::type deba@481: colLowerBound(T &t, Value value,dummy<1> = 1) { deba@481: for(typename T::iterator i=t.begin();i!=t.end();++i) { deba@481: colLowerBound(i->second, value); deba@481: } deba@481: } deba@481: template deba@482: typename enable_if::type deba@481: colLowerBound(T &t, Value value,dummy<2> = 2) { deba@481: for(typename T::MapIt i(t); i!=INVALID; ++i){ deba@481: colLowerBound(*i, value); deba@481: } deba@481: } deba@481: #endif deba@481: deba@481: /// Set the upper bound of a column (i.e a variable) deba@481: deba@481: /// The upper bound of a variable (column) has to be given by an deba@481: /// extended number of type Value, i.e. a finite number of type deba@481: /// Value or \ref INF. deba@481: void colUpperBound(Col c, Value value) { ggab90@1336: _setColUpperBound(_cols(id(c)),value); deba@481: }; deba@481: deba@481: /// Get the upper bound of a column (i.e a variable) deba@481: deba@482: /// This function returns the upper bound for column (variable) \c c deba@481: /// (this might be \ref INF as well). deba@482: /// \return The upper bound for column \c c deba@481: Value colUpperBound(Col c) const { ggab90@1336: return _getColUpperBound(_cols(id(c))); deba@481: } deba@481: deba@481: ///\brief Set the upper bound of several columns deba@482: ///(i.e variables) at once deba@481: /// deba@481: ///This magic function takes a container as its argument deba@481: ///and applies the function on all of its elements. deba@482: ///The upper bound of a variable (column) has to be given by an deba@482: ///extended number of type Value, i.e. a finite number of type deba@482: ///Value or \ref INF. deba@481: #ifdef DOXYGEN deba@481: template deba@481: void colUpperBound(T &t, Value value) { return 0;} deba@481: #else tapolcai@561: template tapolcai@561: typename enable_if::type tapolcai@561: colUpperBound(T1 &t, Value value,dummy<0> = 0) { tapolcai@561: for(typename T1::iterator i=t.begin();i!=t.end();++i) { deba@481: colUpperBound(*i, value); deba@481: } deba@481: } tapolcai@561: template tapolcai@561: typename enable_if::type tapolcai@561: colUpperBound(T1 &t, Value value,dummy<1> = 1) { tapolcai@561: for(typename T1::iterator i=t.begin();i!=t.end();++i) { deba@481: colUpperBound(i->second, value); deba@481: } deba@481: } tapolcai@561: template tapolcai@561: typename enable_if::type tapolcai@561: colUpperBound(T1 &t, Value value,dummy<2> = 2) { tapolcai@561: for(typename T1::MapIt i(t); i!=INVALID; ++i){ deba@481: colUpperBound(*i, value); deba@481: } deba@481: } deba@481: #endif deba@481: deba@481: /// Set the lower and the upper bounds of a column (i.e a variable) deba@481: deba@481: /// The lower and the upper bounds of deba@481: /// a variable (column) have to be given by an deba@481: /// extended number of type Value, i.e. a finite number of type deba@481: /// Value, -\ref INF or \ref INF. deba@481: void colBounds(Col c, Value lower, Value upper) { ggab90@1336: _setColLowerBound(_cols(id(c)),lower); ggab90@1336: _setColUpperBound(_cols(id(c)),upper); deba@481: } deba@481: deba@481: ///\brief Set the lower and the upper bound of several columns deba@482: ///(i.e variables) at once deba@481: /// deba@481: ///This magic function takes a container as its argument deba@481: ///and applies the function on all of its elements. deba@481: /// The lower and the upper bounds of deba@481: /// a variable (column) have to be given by an deba@481: /// extended number of type Value, i.e. a finite number of type deba@481: /// Value, -\ref INF or \ref INF. deba@481: #ifdef DOXYGEN deba@481: template deba@481: void colBounds(T &t, Value lower, Value upper) { return 0;} deba@481: #else tapolcai@561: template tapolcai@561: typename enable_if::type tapolcai@561: colBounds(T2 &t, Value lower, Value upper,dummy<0> = 0) { tapolcai@561: for(typename T2::iterator i=t.begin();i!=t.end();++i) { deba@481: colBounds(*i, lower, upper); deba@481: } deba@481: } tapolcai@561: template tapolcai@561: typename enable_if::type tapolcai@561: colBounds(T2 &t, Value lower, Value upper,dummy<1> = 1) { tapolcai@561: for(typename T2::iterator i=t.begin();i!=t.end();++i) { deba@481: colBounds(i->second, lower, upper); deba@481: } deba@481: } tapolcai@561: template tapolcai@561: typename enable_if::type tapolcai@561: colBounds(T2 &t, Value lower, Value upper,dummy<2> = 2) { tapolcai@561: for(typename T2::MapIt i(t); i!=INVALID; ++i){ deba@481: colBounds(*i, lower, upper); deba@481: } deba@481: } deba@481: #endif deba@481: deba@482: /// Set the lower bound of a row (i.e a constraint) deba@481: deba@482: /// The lower bound of a constraint (row) has to be given by an deba@482: /// extended number of type Value, i.e. a finite number of type deba@482: /// Value or -\ref INF. deba@482: void rowLowerBound(Row r, Value value) { ggab90@1336: _setRowLowerBound(_rows(id(r)),value); deba@481: } deba@481: deba@482: /// Get the lower bound of a row (i.e a constraint) deba@481: deba@482: /// This function returns the lower bound for row (constraint) \c c deba@482: /// (this might be -\ref INF as well). deba@482: ///\return The lower bound for row \c r deba@482: Value rowLowerBound(Row r) const { ggab90@1336: return _getRowLowerBound(_rows(id(r))); deba@482: } deba@482: deba@482: /// Set the upper bound of a row (i.e a constraint) deba@482: deba@482: /// The upper bound of a constraint (row) has to be given by an deba@482: /// extended number of type Value, i.e. a finite number of type deba@482: /// Value or -\ref INF. deba@482: void rowUpperBound(Row r, Value value) { ggab90@1336: _setRowUpperBound(_rows(id(r)),value); deba@482: } deba@482: deba@482: /// Get the upper bound of a row (i.e a constraint) deba@482: deba@482: /// This function returns the upper bound for row (constraint) \c c deba@482: /// (this might be -\ref INF as well). deba@482: ///\return The upper bound for row \c r deba@482: Value rowUpperBound(Row r) const { ggab90@1336: return _getRowUpperBound(_rows(id(r))); deba@481: } deba@481: deba@481: ///Set an element of the objective function ggab90@1336: void objCoeff(Col c, Value v) {_setObjCoeff(_cols(id(c)),v); }; deba@481: deba@481: ///Get an element of the objective function ggab90@1336: Value objCoeff(Col c) const { return _getObjCoeff(_cols(id(c))); }; deba@481: deba@481: ///Set the objective function deba@481: deba@481: ///\param e is a linear expression of type \ref Expr. deba@482: /// deba@482: void obj(const Expr& e) { ggab90@1336: _setObjCoeffs(ExprIterator(e.comps.begin(), _cols), ggab90@1336: ExprIterator(e.comps.end(), _cols)); deba@482: obj_const_comp = *e; deba@481: } deba@481: deba@481: ///Get the objective function deba@481: deba@482: ///\return the objective function as a linear expression of type deba@482: ///Expr. deba@481: Expr obj() const { deba@481: Expr e; ggab90@1336: _getObjCoeffs(InsertIterator(e.comps, _cols)); deba@482: *e = obj_const_comp; deba@481: return e; deba@481: } deba@481: deba@481: deba@482: ///Set the direction of optimization deba@482: void sense(Sense sense) { _setSense(sense); } deba@481: deba@482: ///Query the direction of the optimization deba@482: Sense sense() const {return _getSense(); } deba@481: deba@482: ///Set the sense to maximization deba@482: void max() { _setSense(MAX); } deba@482: deba@482: ///Set the sense to maximization deba@482: void min() { _setSense(MIN); } deba@482: alpar@1231: ///Clear the problem ggab90@1336: void clear() { _clear(); _rows.clear(); _cols.clear(); } deba@481: alpar@1231: /// Set the message level of the solver deba@623: void messageLevel(MessageLevel level) { _messageLevel(level); } deba@623: alpar@1231: /// Write the problem to a file in the given format alpar@1231: alpar@1231: /// This function writes the problem to a file in the given format. alpar@1231: /// Different solver backends may support different formats. alpar@1231: /// Trying to write in an unsupported format will trigger alpar@1231: /// \ref UnsupportedFormatError. For the supported formats, alpar@1231: /// visit the documentation of the base class of the related backends alpar@1231: /// (\ref CplexBase, \ref GlpkBase etc.) alpar@1231: /// \param file The file path alpar@1231: /// \param format The output file format. alpar@1231: void write(std::string file, std::string format = "MPS") const alpar@1231: { alpar@1231: _write(file.c_str(),format.c_str()); alpar@1231: } alpar@1231: deba@481: ///@} deba@481: deba@482: }; deba@482: deba@482: /// Addition deba@482: deba@482: ///\relates LpBase::Expr deba@482: /// deba@482: inline LpBase::Expr operator+(const LpBase::Expr &a, const LpBase::Expr &b) { deba@482: LpBase::Expr tmp(a); deba@482: tmp+=b; deba@482: return tmp; deba@482: } deba@482: ///Substraction deba@482: deba@482: ///\relates LpBase::Expr deba@482: /// deba@482: inline LpBase::Expr operator-(const LpBase::Expr &a, const LpBase::Expr &b) { deba@482: LpBase::Expr tmp(a); deba@482: tmp-=b; deba@482: return tmp; deba@482: } deba@482: ///Multiply with constant deba@482: deba@482: ///\relates LpBase::Expr deba@482: /// deba@482: inline LpBase::Expr operator*(const LpBase::Expr &a, const LpBase::Value &b) { deba@482: LpBase::Expr tmp(a); deba@482: tmp*=b; deba@482: return tmp; deba@482: } deba@482: deba@482: ///Multiply with constant deba@482: deba@482: ///\relates LpBase::Expr deba@482: /// deba@482: inline LpBase::Expr operator*(const LpBase::Value &a, const LpBase::Expr &b) { deba@482: LpBase::Expr tmp(b); deba@482: tmp*=a; deba@482: return tmp; deba@482: } deba@482: ///Divide with constant deba@482: deba@482: ///\relates LpBase::Expr deba@482: /// deba@482: inline LpBase::Expr operator/(const LpBase::Expr &a, const LpBase::Value &b) { deba@482: LpBase::Expr tmp(a); deba@482: tmp/=b; deba@482: return tmp; deba@482: } deba@482: deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator<=(const LpBase::Expr &e, deba@482: const LpBase::Expr &f) { retvari@1092: return LpBase::Constr(0, f - e, LpBase::NaN); deba@482: } deba@482: deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator<=(const LpBase::Value &e, deba@482: const LpBase::Expr &f) { deba@482: return LpBase::Constr(e, f, LpBase::NaN); deba@482: } deba@482: deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator<=(const LpBase::Expr &e, deba@482: const LpBase::Value &f) { retvari@1092: return LpBase::Constr(LpBase::NaN, e, f); deba@482: } deba@482: deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator>=(const LpBase::Expr &e, deba@482: const LpBase::Expr &f) { retvari@1092: return LpBase::Constr(0, e - f, LpBase::NaN); deba@482: } deba@482: deba@482: deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator>=(const LpBase::Value &e, deba@482: const LpBase::Expr &f) { deba@482: return LpBase::Constr(LpBase::NaN, f, e); deba@482: } deba@482: deba@482: deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator>=(const LpBase::Expr &e, deba@482: const LpBase::Value &f) { retvari@1092: return LpBase::Constr(f, e, LpBase::NaN); deba@482: } deba@482: deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator==(const LpBase::Expr &e, deba@482: const LpBase::Value &f) { deba@482: return LpBase::Constr(f, e, f); deba@482: } deba@482: deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator==(const LpBase::Expr &e, deba@482: const LpBase::Expr &f) { deba@482: return LpBase::Constr(0, f - e, 0); deba@482: } deba@482: deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator<=(const LpBase::Value &n, deba@482: const LpBase::Constr &c) { deba@482: LpBase::Constr tmp(c); alpar@558: LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint"); deba@482: tmp.lowerBound()=n; deba@482: return tmp; deba@482: } deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator<=(const LpBase::Constr &c, deba@482: const LpBase::Value &n) deba@482: { deba@482: LpBase::Constr tmp(c); alpar@558: LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint"); deba@482: tmp.upperBound()=n; deba@482: return tmp; deba@482: } deba@482: deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator>=(const LpBase::Value &n, deba@482: const LpBase::Constr &c) { deba@482: LpBase::Constr tmp(c); alpar@558: LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint"); deba@482: tmp.upperBound()=n; deba@482: return tmp; deba@482: } deba@482: ///Create constraint deba@482: deba@482: ///\relates LpBase::Constr deba@482: /// deba@482: inline LpBase::Constr operator>=(const LpBase::Constr &c, deba@482: const LpBase::Value &n) deba@482: { deba@482: LpBase::Constr tmp(c); alpar@558: LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint"); deba@482: tmp.lowerBound()=n; deba@482: return tmp; deba@482: } deba@482: deba@482: ///Addition deba@482: deba@482: ///\relates LpBase::DualExpr deba@482: /// deba@482: inline LpBase::DualExpr operator+(const LpBase::DualExpr &a, deba@482: const LpBase::DualExpr &b) { deba@482: LpBase::DualExpr tmp(a); deba@482: tmp+=b; deba@482: return tmp; deba@482: } deba@482: ///Substraction deba@482: deba@482: ///\relates LpBase::DualExpr deba@482: /// deba@482: inline LpBase::DualExpr operator-(const LpBase::DualExpr &a, deba@482: const LpBase::DualExpr &b) { deba@482: LpBase::DualExpr tmp(a); deba@482: tmp-=b; deba@482: return tmp; deba@482: } deba@482: ///Multiply with constant deba@482: deba@482: ///\relates LpBase::DualExpr deba@482: /// deba@482: inline LpBase::DualExpr operator*(const LpBase::DualExpr &a, deba@482: const LpBase::Value &b) { deba@482: LpBase::DualExpr tmp(a); deba@482: tmp*=b; deba@482: return tmp; deba@482: } deba@482: deba@482: ///Multiply with constant deba@482: deba@482: ///\relates LpBase::DualExpr deba@482: /// deba@482: inline LpBase::DualExpr operator*(const LpBase::Value &a, deba@482: const LpBase::DualExpr &b) { deba@482: LpBase::DualExpr tmp(b); deba@482: tmp*=a; deba@482: return tmp; deba@482: } deba@482: ///Divide with constant deba@482: deba@482: ///\relates LpBase::DualExpr deba@482: /// deba@482: inline LpBase::DualExpr operator/(const LpBase::DualExpr &a, deba@482: const LpBase::Value &b) { deba@482: LpBase::DualExpr tmp(a); deba@482: tmp/=b; deba@482: return tmp; deba@482: } deba@482: deba@482: /// \ingroup lp_group deba@482: /// deba@482: /// \brief Common base class for LP solvers deba@482: /// deba@482: /// This class is an abstract base class for LP solvers. This class deba@482: /// provides a full interface for set and modify an LP problem, deba@482: /// solve it and retrieve the solution. You can use one of the deba@482: /// descendants as a concrete implementation, or the \c Lp deba@482: /// default LP solver. However, if you would like to handle LP deba@482: /// solvers as reference or pointer in a generic way, you can use deba@482: /// this class directly. deba@482: class LpSolver : virtual public LpBase { deba@482: public: deba@482: deba@482: /// The problem types for primal and dual problems deba@482: enum ProblemType { kpeter@631: /// = 0. Feasible solution hasn't been found (but may exist). deba@482: UNDEFINED = 0, kpeter@631: /// = 1. The problem has no feasible solution. deba@482: INFEASIBLE = 1, kpeter@631: /// = 2. Feasible solution found. deba@482: FEASIBLE = 2, kpeter@631: /// = 3. Optimal solution exists and found. deba@482: OPTIMAL = 3, kpeter@631: /// = 4. The cost function is unbounded. deba@482: UNBOUNDED = 4 deba@482: }; deba@482: deba@482: ///The basis status of variables deba@482: enum VarStatus { deba@482: /// The variable is in the basis alpar@956: BASIC, deba@482: /// The variable is free, but not basic deba@482: FREE, alpar@956: /// The variable has active lower bound deba@482: LOWER, deba@482: /// The variable has active upper bound deba@482: UPPER, deba@482: /// The variable is non-basic and fixed deba@482: FIXED deba@482: }; deba@482: deba@482: protected: deba@482: deba@482: virtual SolveExitStatus _solve() = 0; deba@482: deba@482: virtual Value _getPrimal(int i) const = 0; deba@482: virtual Value _getDual(int i) const = 0; deba@482: deba@482: virtual Value _getPrimalRay(int i) const = 0; deba@482: virtual Value _getDualRay(int i) const = 0; deba@482: deba@482: virtual Value _getPrimalValue() const = 0; deba@482: deba@482: virtual VarStatus _getColStatus(int i) const = 0; deba@482: virtual VarStatus _getRowStatus(int i) const = 0; deba@482: deba@482: virtual ProblemType _getPrimalType() const = 0; deba@482: virtual ProblemType _getDualType() const = 0; deba@482: deba@482: public: deba@481: alpar@587: ///Allocate a new LP problem instance alpar@587: virtual LpSolver* newSolver() const = 0; alpar@587: ///Make a copy of the LP problem alpar@587: virtual LpSolver* cloneSolver() const = 0; alpar@587: deba@481: ///\name Solve the LP deba@481: deba@481: ///@{ deba@481: deba@481: ///\e Solve the LP problem at hand deba@481: /// deba@481: ///\return The result of the optimization procedure. Possible deba@481: ///values and their meanings can be found in the documentation of deba@481: ///\ref SolveExitStatus. deba@481: SolveExitStatus solve() { return _solve(); } deba@481: deba@481: ///@} deba@481: kpeter@631: ///\name Obtain the Solution deba@481: deba@481: ///@{ deba@481: deba@482: /// The type of the primal problem deba@482: ProblemType primalType() const { deba@482: return _getPrimalType(); deba@481: } deba@481: deba@482: /// The type of the dual problem deba@482: ProblemType dualType() const { deba@482: return _getDualType(); deba@481: } deba@481: deba@482: /// Return the primal value of the column deba@482: deba@482: /// Return the primal value of the column. deba@482: /// \pre The problem is solved. ggab90@1336: Value primal(Col c) const { return _getPrimal(_cols(id(c))); } deba@482: deba@482: /// Return the primal value of the expression deba@482: deba@482: /// Return the primal value of the expression, i.e. the dot deba@482: /// product of the primal solution and the expression. deba@482: /// \pre The problem is solved. deba@482: Value primal(const Expr& e) const { deba@482: double res = *e; deba@482: for (Expr::ConstCoeffIt c(e); c != INVALID; ++c) { deba@482: res += *c * primal(c); deba@482: } deba@482: return res; deba@481: } deba@482: /// Returns a component of the primal ray alpar@956: deba@482: /// The primal ray is solution of the modified primal problem, deba@482: /// where we change each finite bound to 0, and we looking for a deba@482: /// negative objective value in case of minimization, and positive deba@482: /// objective value for maximization. If there is such solution, deba@482: /// that proofs the unsolvability of the dual problem, and if a deba@482: /// feasible primal solution exists, then the unboundness of deba@482: /// primal problem. deba@482: /// deba@482: /// \pre The problem is solved and the dual problem is infeasible. deba@482: /// \note Some solvers does not provide primal ray calculation deba@482: /// functions. ggab90@1336: Value primalRay(Col c) const { return _getPrimalRay(_cols(id(c))); } deba@481: deba@482: /// Return the dual value of the row deba@482: deba@482: /// Return the dual value of the row. deba@482: /// \pre The problem is solved. ggab90@1336: Value dual(Row r) const { return _getDual(_rows(id(r))); } deba@482: deba@482: /// Return the dual value of the dual expression deba@482: deba@482: /// Return the dual value of the dual expression, i.e. the dot deba@482: /// product of the dual solution and the dual expression. deba@482: /// \pre The problem is solved. deba@482: Value dual(const DualExpr& e) const { deba@482: double res = 0.0; deba@482: for (DualExpr::ConstCoeffIt r(e); r != INVALID; ++r) { deba@482: res += *r * dual(r); deba@481: } deba@481: return res; deba@481: } deba@481: deba@482: /// Returns a component of the dual ray alpar@956: deba@482: /// The dual ray is solution of the modified primal problem, where deba@482: /// we change each finite bound to 0 (i.e. the objective function deba@482: /// coefficients in the primal problem), and we looking for a deba@482: /// ositive objective value. If there is such solution, that deba@482: /// proofs the unsolvability of the primal problem, and if a deba@482: /// feasible dual solution exists, then the unboundness of deba@482: /// dual problem. deba@482: /// deba@482: /// \pre The problem is solved and the primal problem is infeasible. deba@482: /// \note Some solvers does not provide dual ray calculation deba@482: /// functions. ggab90@1336: Value dualRay(Row r) const { return _getDualRay(_rows(id(r))); } deba@481: deba@482: /// Return the basis status of the column deba@481: deba@482: /// \see VarStatus ggab90@1336: VarStatus colStatus(Col c) const { return _getColStatus(_cols(id(c))); } deba@482: deba@482: /// Return the basis status of the row deba@482: deba@482: /// \see VarStatus ggab90@1336: VarStatus rowStatus(Row r) const { return _getRowStatus(_rows(id(r))); } deba@482: deba@482: ///The value of the objective function deba@481: deba@481: ///\return deba@481: ///- \ref INF or -\ref INF means either infeasibility or unboundedness deba@481: /// of the primal problem, depending on whether we minimize or maximize. deba@481: ///- \ref NaN if no primal solution is found. deba@481: ///- The (finite) objective value if an optimal solution is found. deba@482: Value primal() const { return _getPrimalValue()+obj_const_comp;} deba@481: ///@} deba@481: deba@482: protected: deba@482: deba@481: }; deba@481: deba@481: deba@481: /// \ingroup lp_group deba@481: /// deba@481: /// \brief Common base class for MIP solvers deba@482: /// deba@482: /// This class is an abstract base class for MIP solvers. This class deba@482: /// provides a full interface for set and modify an MIP problem, deba@482: /// solve it and retrieve the solution. You can use one of the deba@482: /// descendants as a concrete implementation, or the \c Lp deba@482: /// default MIP solver. However, if you would like to handle MIP deba@482: /// solvers as reference or pointer in a generic way, you can use deba@482: /// this class directly. deba@482: class MipSolver : virtual public LpBase { deba@481: public: deba@481: deba@482: /// The problem types for MIP problems deba@482: enum ProblemType { kpeter@631: /// = 0. Feasible solution hasn't been found (but may exist). deba@482: UNDEFINED = 0, kpeter@631: /// = 1. The problem has no feasible solution. deba@482: INFEASIBLE = 1, kpeter@631: /// = 2. Feasible solution found. deba@482: FEASIBLE = 2, kpeter@631: /// = 3. Optimal solution exists and found. deba@482: OPTIMAL = 3, kpeter@631: /// = 4. The cost function is unbounded. kpeter@631: ///The Mip or at least the relaxed problem is unbounded. deba@482: UNBOUNDED = 4 deba@482: }; deba@482: alpar@587: ///Allocate a new MIP problem instance alpar@587: virtual MipSolver* newSolver() const = 0; alpar@587: ///Make a copy of the MIP problem alpar@587: virtual MipSolver* cloneSolver() const = 0; alpar@587: deba@482: ///\name Solve the MIP deba@482: deba@482: ///@{ deba@482: deba@482: /// Solve the MIP problem at hand deba@482: /// deba@482: ///\return The result of the optimization procedure. Possible deba@482: ///values and their meanings can be found in the documentation of deba@482: ///\ref SolveExitStatus. deba@482: SolveExitStatus solve() { return _solve(); } deba@482: deba@482: ///@} deba@482: kpeter@631: ///\name Set Column Type deba@482: ///@{ deba@482: deba@482: ///Possible variable (column) types (e.g. real, integer, binary etc.) deba@481: enum ColTypes { kpeter@631: /// = 0. Continuous variable (default). deba@481: REAL = 0, kpeter@631: /// = 1. Integer variable. deba@482: INTEGER = 1 deba@481: }; deba@481: deba@482: ///Sets the type of the given column to the given type deba@482: deba@482: ///Sets the type of the given column to the given type. deba@481: /// deba@481: void colType(Col c, ColTypes col_type) { ggab90@1336: _setColType(_cols(id(c)),col_type); deba@481: } deba@481: deba@481: ///Gives back the type of the column. deba@482: deba@482: ///Gives back the type of the column. deba@481: /// deba@481: ColTypes colType(Col c) const { ggab90@1336: return _getColType(_cols(id(c))); deba@482: } deba@482: ///@} deba@482: kpeter@631: ///\name Obtain the Solution deba@482: deba@482: ///@{ deba@482: deba@482: /// The type of the MIP problem deba@482: ProblemType type() const { deba@482: return _getType(); deba@481: } deba@481: deba@482: /// Return the value of the row in the solution deba@482: deba@482: /// Return the value of the row in the solution. deba@482: /// \pre The problem is solved. ggab90@1336: Value sol(Col c) const { return _getSol(_cols(id(c))); } deba@482: deba@482: /// Return the value of the expression in the solution deba@482: deba@482: /// Return the value of the expression in the solution, i.e. the deba@482: /// dot product of the solution and the expression. deba@482: /// \pre The problem is solved. deba@482: Value sol(const Expr& e) const { deba@482: double res = *e; deba@482: for (Expr::ConstCoeffIt c(e); c != INVALID; ++c) { deba@482: res += *c * sol(c); deba@482: } deba@482: return res; deba@481: } deba@482: ///The value of the objective function alpar@956: deba@482: ///\return deba@482: ///- \ref INF or -\ref INF means either infeasibility or unboundedness deba@482: /// of the problem, depending on whether we minimize or maximize. deba@482: ///- \ref NaN if no primal solution is found. deba@482: ///- The (finite) objective value if an optimal solution is found. deba@482: Value solValue() const { return _getSolValue()+obj_const_comp;} deba@482: ///@} deba@481: deba@481: protected: deba@481: deba@482: virtual SolveExitStatus _solve() = 0; deba@482: virtual ColTypes _getColType(int col) const = 0; deba@482: virtual void _setColType(int col, ColTypes col_type) = 0; deba@482: virtual ProblemType _getType() const = 0; deba@482: virtual Value _getSol(int i) const = 0; deba@482: virtual Value _getSolValue() const = 0; deba@481: deba@481: }; deba@481: deba@481: deba@481: deba@481: } //namespace lemon deba@481: deba@481: #endif //LEMON_LP_BASE_H