lemon: comparison lemon/lp

equal deleted inserted replaced

-:a676d488eee1
+:c50cc48e74ea
 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
-* Copyright (C) 2003-2008
+* Copyright (C) 2003-2010
 * 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
 /// Normal output.
 MESSAGE_NORMAL,
 /// Verbose output.
 MESSAGE_VERBOSE
 };
 ///The floating point type used by the solver
 typedef double Value;
 ///The infinity constant
 static const Value INF;
 explicit Col(int id) : _id(id) {}
 public:
 typedef Value ExprValue;
 typedef True LpCol;
 /// Default constructor
 /// \warning The default constructor sets the Col to an
 /// undefined value.
 Col() {}
 /// Invalid constructor \& conversion.
 /// This constructor initializes the Col to be invalid.
 /// \sa Invalid for more details.
 Col(const Invalid&) : _id(-1) {}
 /// Equality operator
 /// Two \ref Col "Col"s are equal if and only if they point to
 /// the same LP column or both are invalid.
 ///\endcode
 class ColIt : public Col {
 const LpBase *_solver;
 public:
 /// Default constructor
 /// \warning The default constructor sets the iterator
 /// to an undefined value.
 ColIt() {}
 /// Sets the iterator to the first Col
 /// Sets the iterator to the first Col.
 ///
 ColIt(const LpBase &solver) : _solver(&solver)
 {
 _solver->cols.firstItem(_id);
 }
 /// Invalid constructor \& conversion
 /// Initialize the iterator to be invalid.
 /// \sa Invalid for more details.
 ColIt(const Invalid&) : Col(INVALID) {}
 /// Next column
 /// Assign the iterator to the next column.
 ///
 ColIt &operator++()
 {
 _solver->cols.nextItem(_id);
 explicit Row(int id) : _id(id) {}
 public:
 typedef Value ExprValue;
 typedef True LpRow;
 /// Default constructor
 /// \warning The default constructor sets the Row to an
 /// undefined value.
 Row() {}
 /// Invalid constructor \& conversion.
 /// This constructor initializes the Row to be invalid.
 /// \sa Invalid for more details.
 Row(const Invalid&) : _id(-1) {}
 /// Equality operator
 /// Two \ref Row "Row"s are equal if and only if they point to
 /// the same LP row or both are invalid.
 bool operator==(Row r) const  {return _id == r._id;}
 /// Inequality operator
 /// \sa operator==(Row r)
 ///
 bool operator!=(Row r) const  {return _id != r._id;}
 /// Artificial ordering operator.
 ///\endcode
 class RowIt : public Row {
 const LpBase *_solver;
 public:
 /// Default constructor
 /// \warning The default constructor sets the iterator
 /// to an undefined value.
 RowIt() {}
 /// Sets the iterator to the first Row
 /// Sets the iterator to the first Row.
 ///
 RowIt(const LpBase &solver) : _solver(&solver)
 {
 _solver->rows.firstItem(_id);
 }
 /// Invalid constructor \& conversion
 /// Initialize the iterator to be invalid.
 /// \sa Invalid for more details.
 RowIt(const Invalid&) : Row(INVALID) {}
 /// Next row
 /// Assign the iterator to the next row.
 ///
 RowIt &operator++()
 {
 _solver->rows.nextItem(_id);
 std::map<int, Value> comps;
 public:
 typedef True SolverExpr;
 /// Default constructor
 /// Construct an empty expression, the coefficients and
 /// the constant component are initialized to zero.
 Expr() : const_comp(0) {}
 /// Construct an expression from a column
 const_comp/=c;
 return *this;
 }
 ///Iterator over the expression
 ///The iterator iterates over the terms of the expression.
 ///
 ///\code
 ///double s=0;
 ///for(LpBase::Expr::CoeffIt i(e);i!=INVALID;++i)
 ///  s+= *i * primal(i);
 ///\endcode
 std::map<int, Value>::iterator _it, _end;
 public:
 /// Sets the iterator to the first term
 /// Sets the iterator to the first term of the expression.
 ///
 CoeffIt(Expr& e)
 : _it(e.comps.begin()), _end(e.comps.end()){}
 Value& operator*() { return _it->second; }
 /// Returns the coefficient of the term
 const Value& operator*() const { return _it->second; }
 /// Next term
 /// Assign the iterator to the next term.
 ///
 CoeffIt& operator++() { ++_it; return *this; }
 /// Equality operator
 /// Inequality operator
 bool operator!=(Invalid) const { return _it != _end; }
 };
 /// Const iterator over the expression
 ///The iterator iterates over the terms of the expression.
 ///
 ///\code
 ///double s=0;
 ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i)
 ///  s+=*i * primal(i);
 ///\endcode
 std::map<int, Value>::const_iterator _it, _end;
 public:
 /// Sets the iterator to the first term
 /// Sets the iterator to the first term of the expression.
 ///
 ConstCoeffIt(const Expr& e)
 : _it(e.comps.begin()), _end(e.comps.end()){}
 /// Returns the coefficient of the term
 const Value& operator*() const { return _it->second; }
 /// Next term
 /// Assign the iterator to the next term.
 ///
 ConstCoeffIt& operator++() { ++_it; return *this; }
 /// Equality operator
 std::map<int, Value> comps;
 public:
 typedef True SolverExpr;
 /// Default constructor
 /// Construct an empty expression, the coefficients are
 /// initialized to zero.
 DualExpr() {}
 /// Construct an expression from a row
 } else {
 comps.erase(id(r));
 }
 }
 /// \brief Removes the coefficients which's absolute value does
 /// not exceed \c epsilon.
 void simplify(Value epsilon = 0.0) {
 std::map<int, Value>::iterator it=comps.begin();
 while (it != comps.end()) {
 std::map<int, Value>::iterator jt=it;
 ++jt;
 it->second/=v;
 return *this;
 }
 ///Iterator over the expression
 ///The iterator iterates over the terms of the expression.
 ///
 ///\code
 ///double s=0;
 ///for(LpBase::DualExpr::CoeffIt i(e);i!=INVALID;++i)
 ///  s+= *i * dual(i);
 ///\endcode
 std::map<int, Value>::iterator _it, _end;
 public:
 /// Sets the iterator to the first term
 /// Sets the iterator to the first term of the expression.
 ///
 CoeffIt(DualExpr& e)
 : _it(e.comps.begin()), _end(e.comps.end()){}
 /// Returns the coefficient of the term
 const Value& operator*() const { return _it->second; }
 /// Next term
 /// Assign the iterator to the next term.
 ///
 CoeffIt& operator++() { ++_it; return *this; }
 /// Equality operator
 /// Inequality operator
 bool operator!=(Invalid) const { return _it != _end; }
 };
 ///Iterator over the expression
 ///The iterator iterates over the terms of the expression.
 ///
 ///\code
 ///double s=0;
 ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i)
 ///  s+= *i * dual(i);
 ///\endcode
 std::map<int, Value>::const_iterator _it, _end;
 public:
 /// Sets the iterator to the first term
 /// Sets the iterator to the first term of the expression.
 ///
 ConstCoeffIt(const DualExpr& e)
 : _it(e.comps.begin()), _end(e.comps.end()){}
 /// Returns the coefficient of the term
 const Value& operator*() const { return _it->second; }
 /// Next term
 /// Assign the iterator to the next term.
 ///
 ConstCoeffIt& operator++() { ++_it; return *this; }
 /// Equality operator
 ///\param c is a linear expression (see \ref Constr)
 ///\return The created row.
 Row addRow(const Constr &c) {
 Row r;
 c.expr().simplify();
 r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
 ExprIterator(c.expr().comps.begin(), cols),
 ExprIterator(c.expr().comps.end(), cols),
 c.upperBounded()?c.upperBound()-*c.expr():INF));
 return r;
 }
 };
 ///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
 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
 }
 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
 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.

changeset 1048	1226290a9b7d
parent 903	207ba6c0f2e4
child 1094	140facbd1d7c