LEMON/LEMON-main Changeset - r957:2eebc8f7dca5

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r957:2eebc8f7dca5

« 947:0dba9b

959:17e36e »
958:9a7168 »

r957:2eebc8f7dca5

Tue, 01 Nov 2011 08:24:30

[Not Reviewed]

0 comments (0 inline)

retvari@tmit.bme.hu
retvari@tmit.bme.hu

Fix LpBase::Constr two-side limit bug (#430)

0 2 0

default

2 files changed with 12 insertions and 4 deletions:

lemon/lp_base.h

test/lp_test.cc

↑ Collapse diff ↑

lemon/lp_base.h

Show inline comments

@@ -1095,994 +1095,994 @@
 		    ///\param e is a dual linear expression (see \ref DualExpr)
 		    ///\param o is the corresponding component of the objective
 		    ///function. It is 0 by default.
 		    ///\return The created column.
 		    Col addCol(const DualExpr &e, Value o = 0) {
 		      Col c=addCol();
 		      col(c,e);
 		      objCoeff(c,o);
 		      return c;
+		    }
 		    ///Add a new empty row (i.e a new constraint) to the LP
 		    ///This function adds a new empty row (i.e a new constraint) to the LP.
 		    ///\return The created row
 		    Row addRow() { Row r; r._id = _addRowId(_addRow()); return r;}
 		    ///\brief Add several new rows (i.e constraints) at once
 		    ///
 		    ///This magic function takes a container as its argument and fills
 		    ///its elements with new row (i.e. variables)
 		    ///\param t can be
 		    ///- a standard STL compatible iterable container with
 		    ///\ref Row as its \c values_type like
 		    ///\code
 		    ///std::vector<LpBase::Row>
 		    ///std::list<LpBase::Row>
 		    ///\endcode
 		    ///- a standard STL compatible iterable container with
 		    ///\ref Row as its \c mapped_type like
 		    ///\code
 		    ///std::map<AnyType,LpBase::Row>
 		    ///\endcode
 		    ///- an iterable lemon \ref concepts::WriteMap "write map" like
 		    ///\code
 		    ///ListGraph::NodeMap<LpBase::Row>
 		    ///ListGraph::ArcMap<LpBase::Row>
 		    ///\endcode
 		    ///\return The number of rows created.
 		#ifdef DOXYGEN
 		    template<class T>
 		    int addRowSet(T &t) { return 0;}
 		#else
 		    template<class T>
 		    typename enable_if<typename T::value_type::LpRow,int>::type
 		    addRowSet(T &t, dummy<0> = 0) {
 		      int s=0;
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
 		      return s;
+		    }
 		    template<class T>
 		    typename enable_if<typename T::value_type::second_type::LpRow, int>::type
 		    addRowSet(T &t, dummy<1> = 1) {
 		      int s=0;
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {
 		        i->second=addRow();
 		        s++;
+		      }
 		      return s;
+		    }
 		    template<class T>
 		    typename enable_if<typename T::MapIt::Value::LpRow, int>::type
 		    addRowSet(T &t, dummy<2> = 2) {
 		      int s=0;
 		      for(typename T::MapIt i(t); i!=INVALID; ++i)
+		        {
 		          i.set(addRow());
 		          s++;
+		        }
 		      return s;
+		    }
 		#endif
 		    ///Set a row (i.e a constraint) of the LP
 		    ///\param r is the row to be modified
 		    ///\param l is lower bound (-\ref INF means no bound)
 		    ///\param e is a linear expression (see \ref Expr)
 		    ///\param u is the upper bound (\ref INF means no bound)
 		    void row(Row r, Value l, const Expr &e, Value u) {
 		      e.simplify();
 		      _setRowCoeffs(rows(id(r)), ExprIterator(e.comps.begin(), cols),
 		                    ExprIterator(e.comps.end(), cols));
 		      _setRowLowerBound(rows(id(r)),l - *e);
 		      _setRowUpperBound(rows(id(r)),u - *e);
+		    }
 		    ///Set a row (i.e a constraint) of the LP
 		    ///\param r is the row to be modified
 		    ///\param c is a linear expression (see \ref Constr)
 		    void row(Row r, const Constr &c) {
 		      row(r, c.lowerBounded()?c.lowerBound():-INF,
 		          c.expr(), c.upperBounded()?c.upperBound():INF);
+		    }
 		    ///Get a row (i.e a constraint) of the LP
 		    ///\param r is the row to get
 		    ///\return the expression associated to the row
 		    Expr row(Row r) const {
 		      Expr e;
 		      _getRowCoeffs(rows(id(r)), InsertIterator(e.comps, cols));
 		      return e;
+		    }
 		    ///Add a new row (i.e a new constraint) to the LP
 		    ///\param l is the lower bound (-\ref INF means no bound)
 		    ///\param e is a linear expression (see \ref Expr)
 		    ///\param u is the upper bound (\ref INF means no bound)
 		    ///\return The created row.
 		    Row addRow(Value l,const Expr &e, Value u) {
 		      Row r=addRow();
 		      row(r,l,e,u);
 		      return r;
+		    }
 		    ///Add a new row (i.e a new constraint) to the LP
 		    ///\param c is a linear expression (see \ref Constr)
 		    ///\return The created row.
 		    Row addRow(const Constr &c) {
 		      Row r=addRow();
 		      row(r,c);
 		      return r;
+		    }
 		    ///Erase a column (i.e a variable) from the LP
 		    ///\param c is the column to be deleted
 		    void erase(Col c) {
 		      _eraseCol(cols(id(c)));
 		      _eraseColId(cols(id(c)));
+		    }
 		    ///Erase a row (i.e a constraint) from the LP
 		    ///\param r is the row to be deleted
 		    void erase(Row r) {
 		      _eraseRow(rows(id(r)));
 		      _eraseRowId(rows(id(r)));
+		    }
 		    /// Get the name of a column
 		    ///\param c is the coresponding column
 		    ///\return The name of the colunm
 		    std::string colName(Col c) const {
 		      std::string name;
 		      _getColName(cols(id(c)), name);
 		      return name;
+		    }
 		    /// Set the name of a column
 		    ///\param c is the coresponding column
 		    ///\param name The name to be given
 		    void colName(Col c, const std::string& name) {
 		      _setColName(cols(id(c)), name);
+		    }
 		    /// Get the column by its name
 		    ///\param name The name of the column
 		    ///\return the proper column or \c INVALID
 		    Col colByName(const std::string& name) const {
 		      int k = _colByName(name);
 		      return k != -1 ? Col(cols[k]) : Col(INVALID);
+		    }
 		    /// Get the name of a row
 		    ///\param r is the coresponding row
 		    ///\return The name of the row
 		    std::string rowName(Row r) const {
 		      std::string name;
 		      _getRowName(rows(id(r)), name);
 		      return name;
+		    }
 		    /// Set the name of a row
 		    ///\param r is the coresponding row
 		    ///\param name The name to be given
 		    void rowName(Row r, const std::string& name) {
 		      _setRowName(rows(id(r)), name);
+		    }
 		    /// Get the row by its name
 		    ///\param name The name of the row
 		    ///\return the proper row or \c INVALID
 		    Row rowByName(const std::string& name) const {
 		      int k = _rowByName(name);
 		      return k != -1 ? Row(rows[k]) : Row(INVALID);
+		    }
 		    /// Set an element of the coefficient matrix of the LP
 		    ///\param r is the row of the element to be modified
 		    ///\param c is the column of the element to be modified
 		    ///\param val is the new value of the coefficient
 		    void coeff(Row r, Col c, Value val) {
 		      _setCoeff(rows(id(r)),cols(id(c)), val);
+		    }
 		    /// Get an element of the coefficient matrix of the LP
 		    ///\param r is the row of the element
 		    ///\param c is the column of the element
 		    ///\return the corresponding coefficient
 		    Value coeff(Row r, Col c) const {
 		      return _getCoeff(rows(id(r)),cols(id(c)));
+		    }
 		    /// Set the lower bound of a column (i.e a variable)
 		    /// The lower bound of a variable (column) has to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or -\ref INF.
 		    void colLowerBound(Col c, Value value) {
 		      _setColLowerBound(cols(id(c)),value);
+		    }
 		    /// Get the lower bound of a column (i.e a variable)
 		    /// This function returns the lower bound for column (variable) \c c
 		    /// (this might be -\ref INF as well).
 		    ///\return The lower bound for column \c c
 		    Value colLowerBound(Col c) const {
 		      return _getColLowerBound(cols(id(c)));
+		    }
 		    ///\brief Set the lower bound of  several columns
 		    ///(i.e variables) at once
 		    ///
 		    ///This magic function takes a container as its argument
 		    ///and applies the function on all of its elements.
 		    ///The lower bound of a variable (column) has to be given by an
 		    ///extended number of type Value, i.e. a finite number of type
 		    ///Value or -\ref INF.
 		#ifdef DOXYGEN
 		    template<class T>
 		    void colLowerBound(T &t, Value value) { return 0;}
 		#else
 		    template<class T>
 		    typename enable_if<typename T::value_type::LpCol,void>::type
 		    colLowerBound(T &t, Value value,dummy<0> = 0) {
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {
 		        colLowerBound(*i, value);
+		      }
+		    }
 		    template<class T>
 		    typename enable_if<typename T::value_type::second_type::LpCol,
 		                       void>::type
 		    colLowerBound(T &t, Value value,dummy<1> = 1) {
 		      for(typename T::iterator i=t.begin();i!=t.end();++i) {
 		        colLowerBound(i->second, value);
+		      }
+		    }
 		    template<class T>
 		    typename enable_if<typename T::MapIt::Value::LpCol,
 		                       void>::type
 		    colLowerBound(T &t, Value value,dummy<2> = 2) {
 		      for(typename T::MapIt i(t); i!=INVALID; ++i){
 		        colLowerBound(*i, value);
+		      }
+		    }
 		#endif
 		    /// Set the upper bound of a column (i.e a variable)
 		    /// The upper bound of a variable (column) has to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or \ref INF.
 		    void colUpperBound(Col c, Value value) {
 		      _setColUpperBound(cols(id(c)),value);
 		    };
 		    /// Get the upper bound of a column (i.e a variable)
 		    /// This function returns the upper bound for column (variable) \c c
 		    /// (this might be \ref INF as well).
 		    /// \return The upper bound for column \c c
 		    Value colUpperBound(Col c) const {
 		      return _getColUpperBound(cols(id(c)));
+		    }
 		    ///\brief Set the upper bound of  several columns
 		    ///(i.e variables) at once
 		    ///
 		    ///This magic function takes a container as its argument
 		    ///and applies the function on all of its elements.
 		    ///The upper bound of a variable (column) has to be given by an
 		    ///extended number of type Value, i.e. a finite number of type
 		    ///Value or \ref INF.
 		#ifdef DOXYGEN
 		    template<class T>
 		    void colUpperBound(T &t, Value value) { return 0;}
 		#else
 		    template<class T1>
 		    typename enable_if<typename T1::value_type::LpCol,void>::type
 		    colUpperBound(T1 &t, Value value,dummy<0> = 0) {
 		      for(typename T1::iterator i=t.begin();i!=t.end();++i) {
 		        colUpperBound(*i, value);
+		      }
+		    }
 		    template<class T1>
 		    typename enable_if<typename T1::value_type::second_type::LpCol,
 		                       void>::type
 		    colUpperBound(T1 &t, Value value,dummy<1> = 1) {
 		      for(typename T1::iterator i=t.begin();i!=t.end();++i) {
 		        colUpperBound(i->second, value);
+		      }
+		    }
 		    template<class T1>
 		    typename enable_if<typename T1::MapIt::Value::LpCol,
 		                       void>::type
 		    colUpperBound(T1 &t, Value value,dummy<2> = 2) {
 		      for(typename T1::MapIt i(t); i!=INVALID; ++i){
 		        colUpperBound(*i, value);
+		      }
+		    }
 		#endif
 		    /// Set the lower and the upper bounds of a column (i.e a variable)
 		    /// The lower and the upper bounds of
 		    /// a variable (column) have to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value, -\ref INF or \ref INF.
 		    void colBounds(Col c, Value lower, Value upper) {
 		      _setColLowerBound(cols(id(c)),lower);
 		      _setColUpperBound(cols(id(c)),upper);
+		    }
 		    ///\brief Set the lower and the upper bound of several columns
 		    ///(i.e variables) at once
 		    ///
 		    ///This magic function takes a container as its argument
 		    ///and applies the function on all of its elements.
 		    /// The lower and the upper bounds of
 		    /// a variable (column) have to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value, -\ref INF or \ref INF.
 		#ifdef DOXYGEN
 		    template<class T>
 		    void colBounds(T &t, Value lower, Value upper) { return 0;}
 		#else
 		    template<class T2>
 		    typename enable_if<typename T2::value_type::LpCol,void>::type
 		    colBounds(T2 &t, Value lower, Value upper,dummy<0> = 0) {
 		      for(typename T2::iterator i=t.begin();i!=t.end();++i) {
 		        colBounds(*i, lower, upper);
+		      }
+		    }
 		    template<class T2>
 		    typename enable_if<typename T2::value_type::second_type::LpCol, void>::type
 		    colBounds(T2 &t, Value lower, Value upper,dummy<1> = 1) {
 		      for(typename T2::iterator i=t.begin();i!=t.end();++i) {
 		        colBounds(i->second, lower, upper);
+		      }
+		    }
 		    template<class T2>
 		    typename enable_if<typename T2::MapIt::Value::LpCol, void>::type
 		    colBounds(T2 &t, Value lower, Value upper,dummy<2> = 2) {
 		      for(typename T2::MapIt i(t); i!=INVALID; ++i){
 		        colBounds(*i, lower, upper);
+		      }
+		    }
 		#endif
 		    /// Set the lower bound of a row (i.e a constraint)
 		    /// The lower bound of a constraint (row) has to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or -\ref INF.
 		    void rowLowerBound(Row r, Value value) {
 		      _setRowLowerBound(rows(id(r)),value);
+		    }
 		    /// Get the lower bound of a row (i.e a constraint)
 		    /// This function returns the lower bound for row (constraint) \c c
 		    /// (this might be -\ref INF as well).
 		    ///\return The lower bound for row \c r
 		    Value rowLowerBound(Row r) const {
 		      return _getRowLowerBound(rows(id(r)));
+		    }
 		    /// Set the upper bound of a row (i.e a constraint)
 		    /// The upper bound of a constraint (row) has to be given by an
 		    /// extended number of type Value, i.e. a finite number of type
 		    /// Value or -\ref INF.
 		    void rowUpperBound(Row r, Value value) {
 		      _setRowUpperBound(rows(id(r)),value);
+		    }
 		    /// Get the upper bound of a row (i.e a constraint)
 		    /// This function returns the upper bound for row (constraint) \c c
 		    /// (this might be -\ref INF as well).
 		    ///\return The upper bound for row \c r
 		    Value rowUpperBound(Row r) const {
 		      return _getRowUpperBound(rows(id(r)));
+		    }
 		    ///Set an element of the objective function
 		    void objCoeff(Col c, Value v) {_setObjCoeff(cols(id(c)),v); };
 		    ///Get an element of the objective function
 		    Value objCoeff(Col c) const { return _getObjCoeff(cols(id(c))); };
 		    ///Set the objective function
 		    ///\param e is a linear expression of type \ref Expr.
 		    ///
 		    void obj(const Expr& e) {
 		      _setObjCoeffs(ExprIterator(e.comps.begin(), cols),
 		                    ExprIterator(e.comps.end(), cols));
 		      obj_const_comp = *e;
+		    }
 		    ///Get the objective function
 		    ///\return the objective function as a linear expression of type
 		    ///Expr.
 		    Expr obj() const {
 		      Expr e;
 		      _getObjCoeffs(InsertIterator(e.comps, cols));
 		      *e = obj_const_comp;
 		      return e;
+		    }
 		    ///Set the direction of optimization
 		    void sense(Sense sense) { _setSense(sense); }
 		    ///Query the direction of the optimization
 		    Sense sense() const {return _getSense(); }
 		    ///Set the sense to maximization
 		    void max() { _setSense(MAX); }
 		    ///Set the sense to maximization
 		    void min() { _setSense(MIN); }
 		    ///Clears the problem
 		    void clear() { _clear(); }
 		    /// Sets the message level of the solver
 		    void messageLevel(MessageLevel level) { _messageLevel(level); }
 		    ///@}
 		  };
 		  /// Addition
 		  ///\relates LpBase::Expr
 		  ///
 		  inline LpBase::Expr operator+(const LpBase::Expr &a, const LpBase::Expr &b) {
 		    LpBase::Expr tmp(a);
 		    tmp+=b;
 		    return tmp;
+		  }
 		  ///Substraction
 		  ///\relates LpBase::Expr
 		  ///
 		  inline LpBase::Expr operator-(const LpBase::Expr &a, const LpBase::Expr &b) {
 		    LpBase::Expr tmp(a);
 		    tmp-=b;
 		    return tmp;
+		  }
 		  ///Multiply with constant
 		  ///\relates LpBase::Expr
 		  ///
 		  inline LpBase::Expr operator*(const LpBase::Expr &a, const LpBase::Value &b) {
 		    LpBase::Expr tmp(a);
 		    tmp*=b;
 		    return tmp;
+		  }
 		  ///Multiply with constant
 		  ///\relates LpBase::Expr
 		  ///
 		  inline LpBase::Expr operator*(const LpBase::Value &a, const LpBase::Expr &b) {
 		    LpBase::Expr tmp(b);
 		    tmp*=a;
 		    return tmp;
+		  }
 		  ///Divide with constant
 		  ///\relates LpBase::Expr
 		  ///
 		  inline LpBase::Expr operator/(const LpBase::Expr &a, const LpBase::Value &b) {
 		    LpBase::Expr tmp(a);
 		    tmp/=b;
 		    return tmp;
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator<=(const LpBase::Expr &e,
 		                                   const LpBase::Expr &f) {
-		    return LpBase::Constr(0, f - e, LpBase::INF);
+		    return LpBase::Constr(0, f - e, LpBase::NaN);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator<=(const LpBase::Value &e,
 		                                   const LpBase::Expr &f) {
 		    return LpBase::Constr(e, f, LpBase::NaN);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator<=(const LpBase::Expr &e,
 		                                   const LpBase::Value &f) {
-		    return LpBase::Constr(- LpBase::INF, e, f);
+		    return LpBase::Constr(LpBase::NaN, e, f);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Expr &e,
 		                                   const LpBase::Expr &f) {
-		    return LpBase::Constr(0, e - f, LpBase::INF);
+		    return LpBase::Constr(0, e - f, LpBase::NaN);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Value &e,
 		                                   const LpBase::Expr &f) {
 		    return LpBase::Constr(LpBase::NaN, f, e);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Expr &e,
 		                                   const LpBase::Value &f) {
-		    return LpBase::Constr(f, e, LpBase::INF);
+		    return LpBase::Constr(f, e, LpBase::NaN);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator==(const LpBase::Expr &e,
 		                                   const LpBase::Value &f) {
 		    return LpBase::Constr(f, e, f);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator==(const LpBase::Expr &e,
 		                                   const LpBase::Expr &f) {
 		    return LpBase::Constr(0, f - e, 0);
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator<=(const LpBase::Value &n,
 		                                   const LpBase::Constr &c) {
 		    LpBase::Constr tmp(c);
 		    LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
 		    tmp.lowerBound()=n;
 		    return tmp;
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator<=(const LpBase::Constr &c,
 		                                   const LpBase::Value &n)
+		  {
 		    LpBase::Constr tmp(c);
 		    LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
 		    tmp.upperBound()=n;
 		    return tmp;
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Value &n,
 		                                   const LpBase::Constr &c) {
 		    LpBase::Constr tmp(c);
 		    LEMON_ASSERT(isNaN(tmp.upperBound()), "Wrong LP constraint");
 		    tmp.upperBound()=n;
 		    return tmp;
+		  }
 		  ///Create constraint
 		  ///\relates LpBase::Constr
 		  ///
 		  inline LpBase::Constr operator>=(const LpBase::Constr &c,
 		                                   const LpBase::Value &n)
+		  {
 		    LpBase::Constr tmp(c);
 		    LEMON_ASSERT(isNaN(tmp.lowerBound()), "Wrong LP constraint");
 		    tmp.lowerBound()=n;
 		    return tmp;
+		  }
 		  ///Addition
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator+(const LpBase::DualExpr &a,
 		                                    const LpBase::DualExpr &b) {
 		    LpBase::DualExpr tmp(a);
 		    tmp+=b;
 		    return tmp;
+		  }
 		  ///Substraction
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator-(const LpBase::DualExpr &a,
 		                                    const LpBase::DualExpr &b) {
 		    LpBase::DualExpr tmp(a);
 		    tmp-=b;
 		    return tmp;
+		  }
 		  ///Multiply with constant
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator*(const LpBase::DualExpr &a,
 		                                    const LpBase::Value &b) {
 		    LpBase::DualExpr tmp(a);
 		    tmp*=b;
 		    return tmp;
+		  }
 		  ///Multiply with constant
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator*(const LpBase::Value &a,
 		                                    const LpBase::DualExpr &b) {
 		    LpBase::DualExpr tmp(b);
 		    tmp*=a;
 		    return tmp;
+		  }
 		  ///Divide with constant
 		  ///\relates LpBase::DualExpr
 		  ///
 		  inline LpBase::DualExpr operator/(const LpBase::DualExpr &a,
 		                                    const LpBase::Value &b) {
 		    LpBase::DualExpr tmp(a);
 		    tmp/=b;
 		    return tmp;
+		  }
 		  /// \ingroup lp_group
 		  ///
 		  /// \brief Common base class for LP solvers
 		  ///
 		  /// This class is an abstract base class for LP solvers. This class
 		  /// provides a full interface for set and modify an LP problem,
 		  /// solve it and retrieve the solution. You can use one of the
 		  /// descendants as a concrete implementation, or the \c Lp
 		  /// default LP solver. However, if you would like to handle LP
 		  /// solvers as reference or pointer in a generic way, you can use
 		  /// this class directly.
 		  class LpSolver : virtual public LpBase {
 		  public:
 		    /// The problem types for primal and dual problems
 		    enum ProblemType {
 		      /// = 0. Feasible solution hasn't been found (but may exist).
 		      UNDEFINED = 0,
 		      /// = 1. The problem has no feasible solution.
 		      INFEASIBLE = 1,
 		      /// = 2. Feasible solution found.
 		      FEASIBLE = 2,
 		      /// = 3. Optimal solution exists and found.
 		      OPTIMAL = 3,
 		      /// = 4. The cost function is unbounded.
 		      UNBOUNDED = 4
 		    };
 		    ///The basis status of variables
 		    enum VarStatus {
 		      /// The variable is in the basis
 		      BASIC,
 		      /// The variable is free, but not basic
 		      FREE,
 		      /// The variable has active lower bound
 		      LOWER,
 		      /// The variable has active upper bound
 		      UPPER,
 		      /// The variable is non-basic and fixed
 		      FIXED
 		    };
 		  protected:
 		    virtual SolveExitStatus _solve() = 0;
 		    virtual Value _getPrimal(int i) const = 0;
 		    virtual Value _getDual(int i) const = 0;
 		    virtual Value _getPrimalRay(int i) const = 0;
 		    virtual Value _getDualRay(int i) const = 0;
 		    virtual Value _getPrimalValue() const = 0;
 		    virtual VarStatus _getColStatus(int i) const = 0;
 		    virtual VarStatus _getRowStatus(int i) const = 0;
 		    virtual ProblemType _getPrimalType() const = 0;
 		    virtual ProblemType _getDualType() const = 0;
 		  public:
 		    ///Allocate a new LP problem instance
 		    virtual LpSolver* newSolver() const = 0;
 		    ///Make a copy of the LP problem
 		    virtual LpSolver* cloneSolver() const = 0;
 		    ///\name Solve the LP
 		    ///@{
 		    ///\e Solve the LP problem at hand
 		    ///
 		    ///\return The result of the optimization procedure. Possible
 		    ///values and their meanings can be found in the documentation of
 		    ///\ref SolveExitStatus.
 		    SolveExitStatus solve() { return _solve(); }
 		    ///@}
 		    ///\name Obtain the Solution
 		    ///@{
 		    /// The type of the primal problem
 		    ProblemType primalType() const {
 		      return _getPrimalType();
+		    }
 		    /// The type of the dual problem
 		    ProblemType dualType() const {
 		      return _getDualType();
+		    }
 		    /// Return the primal value of the column
 		    /// Return the primal value of the column.
 		    /// \pre The problem is solved.
 		    Value primal(Col c) const { return _getPrimal(cols(id(c))); }
 		    /// Return the primal value of the expression
 		    /// Return the primal value of the expression, i.e. the dot
 		    /// product of the primal solution and the expression.
 		    /// \pre The problem is solved.
 		    Value primal(const Expr& e) const {
 		      double res = *e;
 		      for (Expr::ConstCoeffIt c(e); c != INVALID; ++c) {
 		        res += *c * primal(c);
+		      }
 		      return res;
+		    }
 		    /// Returns a component of the primal ray
 		    /// The primal ray is solution of the modified primal problem,
 		    /// where we change each finite bound to 0, and we looking for a
 		    /// negative objective value in case of minimization, and positive
 		    /// objective value for maximization. If there is such solution,
 		    /// that proofs the unsolvability of the dual problem, and if a
 		    /// feasible primal solution exists, then the unboundness of
 		    /// primal problem.
 		    ///
 		    /// \pre The problem is solved and the dual problem is infeasible.
 		    /// \note Some solvers does not provide primal ray calculation
 		    /// functions.
 		    Value primalRay(Col c) const { return _getPrimalRay(cols(id(c))); }
 		    /// Return the dual value of the row
 		    /// Return the dual value of the row.
 		    /// \pre The problem is solved.
 		    Value dual(Row r) const { return _getDual(rows(id(r))); }
 		    /// Return the dual value of the dual expression
 		    /// Return the dual value of the dual expression, i.e. the dot
 		    /// product of the dual solution and the dual expression.
 		    /// \pre The problem is solved.
 		    Value dual(const DualExpr& e) const {
 		      double res = 0.0;
 		      for (DualExpr::ConstCoeffIt r(e); r != INVALID; ++r) {
 		        res += *r * dual(r);
+		      }
 		      return res;
+		    }
 		    /// Returns a component of the dual ray
 		    /// The dual ray is solution of the modified primal problem, where
 		    /// we change each finite bound to 0 (i.e. the objective function
 		    /// coefficients in the primal problem), and we looking for a
 		    /// ositive objective value. If there is such solution, that
 		    /// proofs the unsolvability of the primal problem, and if a
 		    /// feasible dual solution exists, then the unboundness of
 		    /// dual problem.
 		    ///
 		    /// \pre The problem is solved and the primal problem is infeasible.
 		    /// \note Some solvers does not provide dual ray calculation
 		    /// functions.
 		    Value dualRay(Row r) const { return _getDualRay(rows(id(r))); }
 		    /// Return the basis status of the column
 		    /// \see VarStatus
 		    VarStatus colStatus(Col c) const { return _getColStatus(cols(id(c))); }
 		    /// Return the basis status of the row
 		    /// \see VarStatus
 		    VarStatus rowStatus(Row r) const { return _getRowStatus(rows(id(r))); }
 		    ///The value of the objective function
 		    ///\return
 		    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
 		    /// of the primal problem, depending on whether we minimize or maximize.
 		    ///- \ref NaN if no primal solution is found.
 		    ///- The (finite) objective value if an optimal solution is found.
 		    Value primal() const { return _getPrimalValue()+obj_const_comp;}
 		    ///@}
 		  protected:
 		  };
 		  /// \ingroup lp_group
 		  ///
 		  /// \brief Common base class for MIP solvers
 		  ///
 		  /// This class is an abstract base class for MIP solvers. This class
 		  /// provides a full interface for set and modify an MIP problem,
 		  /// solve it and retrieve the solution. You can use one of the
 		  /// descendants as a concrete implementation, or the \c Lp
 		  /// default MIP solver. However, if you would like to handle MIP
 		  /// solvers as reference or pointer in a generic way, you can use
 		  /// this class directly.
 		  class MipSolver : virtual public LpBase {
 		  public:
 		    /// The problem types for MIP problems
 		    enum ProblemType {
 		      /// = 0. Feasible solution hasn't been found (but may exist).
 		      UNDEFINED = 0,
 		      /// = 1. The problem has no feasible solution.
 		      INFEASIBLE = 1,
 		      /// = 2. Feasible solution found.
 		      FEASIBLE = 2,
 		      /// = 3. Optimal solution exists and found.
 		      OPTIMAL = 3,
 		      /// = 4. The cost function is unbounded.
 		      ///The Mip or at least the relaxed problem is unbounded.
 		      UNBOUNDED = 4
 		    };
 		    ///Allocate a new MIP problem instance
 		    virtual MipSolver* newSolver() const = 0;
 		    ///Make a copy of the MIP problem
 		    virtual MipSolver* cloneSolver() const = 0;
 		    ///\name Solve the MIP
 		    ///@{
 		    /// Solve the MIP problem at hand
 		    ///
 		    ///\return The result of the optimization procedure. Possible
 		    ///values and their meanings can be found in the documentation of
 		    ///\ref SolveExitStatus.
 		    SolveExitStatus solve() { return _solve(); }
 		    ///@}
 		    ///\name Set Column Type
 		    ///@{
 		    ///Possible variable (column) types (e.g. real, integer, binary etc.)
 		    enum ColTypes {
 		      /// = 0. Continuous variable (default).
 		      REAL = 0,
 		      /// = 1. Integer variable.
 		      INTEGER = 1
 		    };
 		    ///Sets the type of the given column to the given type
 		    ///Sets the type of the given column to the given type.
 		    ///
 		    void colType(Col c, ColTypes col_type) {
 		      _setColType(cols(id(c)),col_type);
+		    }
 		    ///Gives back the type of the column.
 		    ///Gives back the type of the column.
 		    ///
 		    ColTypes colType(Col c) const {
 		      return _getColType(cols(id(c)));
+		    }
 		    ///@}
 		    ///\name Obtain the Solution
 		    ///@{
 		    /// The type of the MIP problem
 		    ProblemType type() const {
 		      return _getType();
+		    }
 		    /// Return the value of the row in the solution
 		    ///  Return the value of the row in the solution.
 		    /// \pre The problem is solved.
 		    Value sol(Col c) const { return _getSol(cols(id(c))); }
 		    /// Return the value of the expression in the solution
 		    /// Return the value of the expression in the solution, i.e. the
 		    /// dot product of the solution and the expression.
 		    /// \pre The problem is solved.
 		    Value sol(const Expr& e) const {
 		      double res = *e;
 		      for (Expr::ConstCoeffIt c(e); c != INVALID; ++c) {
 		        res += *c * sol(c);
+		      }
 		      return res;
+		    }
 		    ///The value of the objective function
 		    ///\return
 		    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
 		    /// of the problem, depending on whether we minimize or maximize.
 		    ///- \ref NaN if no primal solution is found.
 		    ///- The (finite) objective value if an optimal solution is found.
 		    Value solValue() const { return _getSolValue()+obj_const_comp;}
 		    ///@}
 		  protected:
 		    virtual SolveExitStatus _solve() = 0;
 		    virtual ColTypes _getColType(int col) const = 0;
 		    virtual void _setColType(int col, ColTypes col_type) = 0;
 		    virtual ProblemType _getType() const = 0;
 		    virtual Value _getSol(int i) const = 0;
 		    virtual Value _getSolValue() const = 0;
 		  };
 		} //namespace lemon
 		#endif //LEMON_LP_BASE_H

test/lp_test.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <sstream>
 		#include <lemon/lp_skeleton.h>
 		#include "test_tools.h"
 		#include <lemon/tolerance.h>
 		#include <lemon/config.h>
 		#ifdef LEMON_HAVE_GLPK
 		#include <lemon/glpk.h>
 		#endif
 		#ifdef LEMON_HAVE_CPLEX
 		#include <lemon/cplex.h>
 		#endif
 		#ifdef LEMON_HAVE_SOPLEX
 		#include <lemon/soplex.h>
 		#endif
 		#ifdef LEMON_HAVE_CLP
 		#include <lemon/clp.h>
 		#endif
 		using namespace lemon;
 		void lpTest(LpSolver& lp)
+		{
 		  typedef LpSolver LP;
 		  std::vector<LP::Col> x(10);
 		  //  for(int i=0;i<10;i++) x.push_back(lp.addCol());
 		  lp.addColSet(x);
 		  lp.colLowerBound(x,1);
 		  lp.colUpperBound(x,1);
 		  lp.colBounds(x,1,2);
 		  std::vector<LP::Col> y(10);
 		  lp.addColSet(y);
 		  lp.colLowerBound(y,1);
 		  lp.colUpperBound(y,1);
 		  lp.colBounds(y,1,2);
 		  std::map<int,LP::Col> z;
 		  z.insert(std::make_pair(12,INVALID));
 		  z.insert(std::make_pair(2,INVALID));
 		  z.insert(std::make_pair(7,INVALID));
 		  z.insert(std::make_pair(5,INVALID));
 		  lp.addColSet(z);
 		  lp.colLowerBound(z,1);
 		  lp.colUpperBound(z,1);
 		  lp.colBounds(z,1,2);
+		  {
 		    LP::Expr e,f,g;
 		    LP::Col p1,p2,p3,p4,p5;
 		    LP::Constr c;
 		    p1=lp.addCol();
 		    p2=lp.addCol();
 		    p3=lp.addCol();
 		    p4=lp.addCol();
 		    p5=lp.addCol();
 		    e[p1]=2;
 		    *e=12;
 		    e[p1]+=2;
 		    *e+=12;
 		    e[p1]-=2;
 		    *e-=12;
 		    e=2;
 		    e=2.2;
 		    e=p1;
 		    e=f;
 		    e+=2;
 		    e+=2.2;
 		    e+=p1;
 		    e+=f;
 		    e-=2;
 		    e-=2.2;
 		    e-=p1;
 		    e-=f;
 		    e*=2;
 		    e*=2.2;
 		    e/=2;
 		    e/=2.2;
 		    e=((p1+p2)+(p1-p2)+(p1+12)+(12+p1)+(p1-12)+(12-p1)+
 		       (f+12)+(12+f)+(p1+f)+(f+p1)+(f+g)+
 		       (f-12)+(12-f)+(p1-f)+(f-p1)+(f-g)+
 .2*f+f*2.2+f/2.2+
 *f+f*2+f/2+
 .2*p1+p1*2.2+p1/2.2+
 *p1+p1*2+p1/2
 		       );
 		    c = (e  <= f  );
 		    c = (e  <= 2.2);
 		    c = (e  <= 2  );
 		    c = (e  <= p1 );
 		    c = (2.2<= f  );
 		    c = (2  <= f  );
 		    c = (p1 <= f  );
 		    c = (p1 <= p2 );
 		    c = (p1 <= 2.2);
 		    c = (p1 <= 2  );
 		    c = (2.2<= p2 );
 		    c = (2  <= p2 );
 		    c = (e  >= f  );
 		    c = (e  >= 2.2);
 		    c = (e  >= 2  );
 		    c = (e  >= p1 );
 		    c = (2.2>= f  );
 		    c = (2  >= f  );
 		    c = (p1 >= f  );
 		    c = (p1 >= p2 );
 		    c = (p1 >= 2.2);
 		    c = (p1 >= 2  );
 		    c = (2.2>= p2 );
 		    c = (2  >= p2 );
 		    c = (e  == f  );
 		    c = (e  == 2.2);
 		    c = (e  == 2  );
 		    c = (e  == p1 );
 		    c = (2.2== f  );
 		    c = (2  == f  );
 		    c = (p1 == f  );
 		    //c = (p1 == p2 );
 		    c = (p1 == 2.2);
 		    c = (p1 == 2  );
 		    c = (2.2== p2 );
 		    c = (2  == p2 );
 		    c = ((2 <= e) <= 3);
 		    c = ((2 <= p1) <= 3);
 		    c = ((2 >= e) >= 3);
 		    c = ((2 >= p1) >= 3);
 		    { //Tests for #430
 		      LP::Col v=lp.addCol();
 		      LP::Constr c = v >= -3;
 		      c = c <= 4;
 		      LP::Constr c2;
 		      c2 = -3 <= v <= 4;
+		    }
 		    e[x[3]]=2;
 		    e[x[3]]=4;
 		    e[x[3]]=1;
 		    *e=12;
 		    lp.addRow(-LP::INF,e,23);
 		    lp.addRow(-LP::INF,3.0*(x[1]+x[2]/2)-x[3],23);
 		    lp.addRow(-LP::INF,3.0*(x[1]+x[2]*2-5*x[3]+12-x[4]/3)+2*x[4]-4,23);
 		    lp.addRow(x[1]+x[3]<=x[5]-3);
 		    lp.addRow((-7<=x[1]+x[3]-12)<=3);
 		    lp.addRow(x[1]<=x[5]);
 		    std::ostringstream buf;
 		    e=((p1+p2)+(p1-0.99*p2));
 		    //e.prettyPrint(std::cout);
 		    //(e<=2).prettyPrint(std::cout);
 		    double tolerance=0.001;
 		    e.simplify(tolerance);
 		    buf << "Coeff. of p2 should be 0.01";
 		    check(e[p2]>0, buf.str());
 		    tolerance=0.02;
 		    e.simplify(tolerance);
 		    buf << "Coeff. of p2 should be 0";
 		    check(const_cast<const LpSolver::Expr&>(e)[p2]==0, buf.str());
 		    //Test for clone/new
 		    LP* lpnew = lp.newSolver();
 		    LP* lpclone = lp.cloneSolver();
 		    delete lpnew;
 		    delete lpclone;
+		  }
+		  {
 		    LP::DualExpr e,f,g;
 		    LP::Row p1 = INVALID, p2 = INVALID, p3 = INVALID,
 		      p4 = INVALID, p5 = INVALID;
 		    e[p1]=2;
 		    e[p1]+=2;
 		    e[p1]-=2;
 		    e=p1;
 		    e=f;
 		    e+=p1;
 		    e+=f;
 		    e-=p1;
 		    e-=f;
 		    e*=2;
 		    e*=2.2;
 		    e/=2;
 		    e/=2.2;
 		    e=((p1+p2)+(p1-p2)+
 		       (p1+f)+(f+p1)+(f+g)+
 		       (p1-f)+(f-p1)+(f-g)+
 .2*f+f*2.2+f/2.2+
 *f+f*2+f/2+
 .2*p1+p1*2.2+p1/2.2+
 *p1+p1*2+p1/2
 		       );
+		  }
+		}
 		void solveAndCheck(LpSolver& lp, LpSolver::ProblemType stat,
 		                   double exp_opt) {
 		  using std::string;
 		  lp.solve();
 		  std::ostringstream buf;
 		  buf << "PrimalType should be: " << int(stat) << int(lp.primalType());
 		  check(lp.primalType()==stat, buf.str());
 		  if (stat ==  LpSolver::OPTIMAL) {
 		    std::ostringstream sbuf;
 		    sbuf << "Wrong optimal value (" << lp.primal() <<") with "
 		         << lp.solverName() <<"\n     the right optimum is " << exp_opt;
 		    check(std::abs(lp.primal()-exp_opt) < 1e-3, sbuf.str());
+		  }
+		}
 		void aTest(LpSolver & lp)
+		{
 		  typedef LpSolver LP;
 		 //The following example is very simple
 		  typedef LpSolver::Row Row;
 		  typedef LpSolver::Col Col;
 		  Col x1 = lp.addCol();
 		  Col x2 = lp.addCol();
 		  //Constraints
 		  Row upright=lp.addRow(x1+2*x2 <=1);
 		  lp.addRow(x1+x2 >=-1);
 		  lp.addRow(x1-x2 <=1);
 		  lp.addRow(x1-x2 >=-1);
 		  //Nonnegativity of the variables
 		  lp.colLowerBound(x1, 0);
 		  lp.colLowerBound(x2, 0);
 		  //Objective function
 		  lp.obj(x1+x2);
 		  lp.sense(lp.MAX);
 		  //Testing the problem retrieving routines
 		  check(lp.objCoeff(x1)==1,"First term should be 1 in the obj function!");
 		  check(lp.sense() == lp.MAX,"This is a maximization!");
 		  check(lp.coeff(upright,x1)==1,"The coefficient in question is 1!");
 		  check(lp.colLowerBound(x1)==0,
 		        "The lower bound for variable x1 should be 0.");
 		  check(lp.colUpperBound(x1)==LpSolver::INF,
 		        "The upper bound for variable x1 should be infty.");
 		  check(lp.rowLowerBound(upright) == -LpSolver::INF,
 		        "The lower bound for the first row should be -infty.");
 		  check(lp.rowUpperBound(upright)==1,
 		        "The upper bound for the first row should be 1.");
 		  LpSolver::Expr e = lp.row(upright);
 		  check(e[x1] == 1, "The first coefficient should 1.");
 		  check(e[x2] == 2, "The second coefficient should 1.");
 		  lp.row(upright, x1+x2 <=1);
 		  e = lp.row(upright);
 		  check(e[x1] == 1, "The first coefficient should 1.");
 		  check(e[x2] == 1, "The second coefficient should 1.");
 		  LpSolver::DualExpr de = lp.col(x1);
 		  check(  de[upright] == 1, "The first coefficient should 1.");
 		  LpSolver* clp = lp.cloneSolver();
 		  //Testing the problem retrieving routines
 		  check(clp->objCoeff(x1)==1,"First term should be 1 in the obj function!");
 		  check(clp->sense() == clp->MAX,"This is a maximization!");
 		  check(clp->coeff(upright,x1)==1,"The coefficient in question is 1!");
 		  //  std::cout<<lp.colLowerBound(x1)<<std::endl;
 		  check(clp->colLowerBound(x1)==0,
 		        "The lower bound for variable x1 should be 0.");
 		  check(clp->colUpperBound(x1)==LpSolver::INF,
 		        "The upper bound for variable x1 should be infty.");
 		  check(lp.rowLowerBound(upright)==-LpSolver::INF,
 		        "The lower bound for the first row should be -infty.");
 		  check(lp.rowUpperBound(upright)==1,
 		        "The upper bound for the first row should be 1.");
 		  e = clp->row(upright);
 		  check(e[x1] == 1, "The first coefficient should 1.");
 		  check(e[x2] == 1, "The second coefficient should 1.");
 		  de = clp->col(x1);
 		  check(de[upright] == 1, "The first coefficient should 1.");
 		  delete clp;
 		  //Maximization of x1+x2
 		  //over the triangle with vertices (0,0) (0,1) (1,0)
 		  double expected_opt=1;
 		  solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
 		  //Minimization
 		  lp.sense(lp.MIN);
 		  expected_opt=0;
 		  solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
 		  //Vertex (-1,0) instead of (0,0)
 		  lp.colLowerBound(x1, -LpSolver::INF);
 		  expected_opt=-1;
 		  solveAndCheck(lp, LpSolver::OPTIMAL, expected_opt);
 		  //Erase one constraint and return to maximization
 		  lp.erase(upright);
 		  lp.sense(lp.MAX);
 		  expected_opt=LpSolver::INF;
 		  solveAndCheck(lp, LpSolver::UNBOUNDED, expected_opt);
 		  //Infeasibilty
 		  lp.addRow(x1+x2 <=-2);
 		  solveAndCheck(lp, LpSolver::INFEASIBLE, expected_opt);
+		}
 		template<class LP>
 		void cloneTest()
+		{
 		  //Test for clone/new
 		  LP* lp = new LP();
 		  LP* lpnew = lp->newSolver();
 		  LP* lpclone = lp->cloneSolver();
 		  delete lp;
 		  delete lpnew;
 		  delete lpclone;
+		}
 		int main()
+		{
 		  LpSkeleton lp_skel;
 		  lpTest(lp_skel);
 		#ifdef LEMON_HAVE_GLPK
+		  {
 		    GlpkLp lp_glpk1,lp_glpk2;
 		    lpTest(lp_glpk1);
 		    aTest(lp_glpk2);
 		    cloneTest<GlpkLp>();
+		  }
 		#endif
 		#ifdef LEMON_HAVE_CPLEX
 		  try {
 		    CplexLp lp_cplex1,lp_cplex2;
 		    lpTest(lp_cplex1);
 		    aTest(lp_cplex2);
 		    cloneTest<CplexLp>();
 		  } catch (CplexEnv::LicenseError& error) {
 		    check(false, error.what());
+		  }
 		#endif
 		#ifdef LEMON_HAVE_SOPLEX
+		  {
 		    SoplexLp lp_soplex1,lp_soplex2;
 		    lpTest(lp_soplex1);
 		    aTest(lp_soplex2);
 		    cloneTest<SoplexLp>();
+		  }
 		#endif
 		#ifdef LEMON_HAVE_CLP
+		  {
 		    ClpLp lp_clp1,lp_clp2;
 		    lpTest(lp_clp1);
 		    aTest(lp_clp2);
 		    cloneTest<ClpLp>();
+		  }
 		#endif
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account