lemon/lp_base.h
changeset 922 9312d6c89d02
parent 834 207ba6c0f2e4
child 958 9a716871028e
equal deleted inserted replaced
11:a676d488eee1 12:c50cc48e74ea
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    80       /// Normal output.
    80       /// Normal output.
    81       MESSAGE_NORMAL,
    81       MESSAGE_NORMAL,
    82       /// Verbose output.
    82       /// Verbose output.
    83       MESSAGE_VERBOSE
    83       MESSAGE_VERBOSE
    84     };
    84     };
    85     
    85 
    86 
    86 
    87     ///The floating point type used by the solver
    87     ///The floating point type used by the solver
    88     typedef double Value;
    88     typedef double Value;
    89     ///The infinity constant
    89     ///The infinity constant
    90     static const Value INF;
    90     static const Value INF;
   112       explicit Col(int id) : _id(id) {}
   112       explicit Col(int id) : _id(id) {}
   113     public:
   113     public:
   114       typedef Value ExprValue;
   114       typedef Value ExprValue;
   115       typedef True LpCol;
   115       typedef True LpCol;
   116       /// Default constructor
   116       /// Default constructor
   117       
   117 
   118       /// \warning The default constructor sets the Col to an
   118       /// \warning The default constructor sets the Col to an
   119       /// undefined value.
   119       /// undefined value.
   120       Col() {}
   120       Col() {}
   121       /// Invalid constructor \& conversion.
   121       /// Invalid constructor \& conversion.
   122       
   122 
   123       /// This constructor initializes the Col to be invalid.
   123       /// This constructor initializes the Col to be invalid.
   124       /// \sa Invalid for more details.      
   124       /// \sa Invalid for more details.
   125       Col(const Invalid&) : _id(-1) {}
   125       Col(const Invalid&) : _id(-1) {}
   126       /// Equality operator
   126       /// Equality operator
   127 
   127 
   128       /// Two \ref Col "Col"s are equal if and only if they point to
   128       /// Two \ref Col "Col"s are equal if and only if they point to
   129       /// the same LP column or both are invalid.
   129       /// the same LP column or both are invalid.
   154     ///\endcode
   154     ///\endcode
   155     class ColIt : public Col {
   155     class ColIt : public Col {
   156       const LpBase *_solver;
   156       const LpBase *_solver;
   157     public:
   157     public:
   158       /// Default constructor
   158       /// Default constructor
   159       
   159 
   160       /// \warning The default constructor sets the iterator
   160       /// \warning The default constructor sets the iterator
   161       /// to an undefined value.
   161       /// to an undefined value.
   162       ColIt() {}
   162       ColIt() {}
   163       /// Sets the iterator to the first Col
   163       /// Sets the iterator to the first Col
   164       
   164 
   165       /// Sets the iterator to the first Col.
   165       /// Sets the iterator to the first Col.
   166       ///
   166       ///
   167       ColIt(const LpBase &solver) : _solver(&solver)
   167       ColIt(const LpBase &solver) : _solver(&solver)
   168       {
   168       {
   169         _solver->cols.firstItem(_id);
   169         _solver->cols.firstItem(_id);
   170       }
   170       }
   171       /// Invalid constructor \& conversion
   171       /// Invalid constructor \& conversion
   172       
   172 
   173       /// Initialize the iterator to be invalid.
   173       /// Initialize the iterator to be invalid.
   174       /// \sa Invalid for more details.
   174       /// \sa Invalid for more details.
   175       ColIt(const Invalid&) : Col(INVALID) {}
   175       ColIt(const Invalid&) : Col(INVALID) {}
   176       /// Next column
   176       /// Next column
   177       
   177 
   178       /// Assign the iterator to the next column.
   178       /// Assign the iterator to the next column.
   179       ///
   179       ///
   180       ColIt &operator++()
   180       ColIt &operator++()
   181       {
   181       {
   182         _solver->cols.nextItem(_id);
   182         _solver->cols.nextItem(_id);
   207       explicit Row(int id) : _id(id) {}
   207       explicit Row(int id) : _id(id) {}
   208     public:
   208     public:
   209       typedef Value ExprValue;
   209       typedef Value ExprValue;
   210       typedef True LpRow;
   210       typedef True LpRow;
   211       /// Default constructor
   211       /// Default constructor
   212       
   212 
   213       /// \warning The default constructor sets the Row to an
   213       /// \warning The default constructor sets the Row to an
   214       /// undefined value.
   214       /// undefined value.
   215       Row() {}
   215       Row() {}
   216       /// Invalid constructor \& conversion.
   216       /// Invalid constructor \& conversion.
   217       
   217 
   218       /// This constructor initializes the Row to be invalid.
   218       /// This constructor initializes the Row to be invalid.
   219       /// \sa Invalid for more details.      
   219       /// \sa Invalid for more details.
   220       Row(const Invalid&) : _id(-1) {}
   220       Row(const Invalid&) : _id(-1) {}
   221       /// Equality operator
   221       /// Equality operator
   222 
   222 
   223       /// Two \ref Row "Row"s are equal if and only if they point to
   223       /// Two \ref Row "Row"s are equal if and only if they point to
   224       /// the same LP row or both are invalid.
   224       /// the same LP row or both are invalid.
   225       bool operator==(Row r) const  {return _id == r._id;}
   225       bool operator==(Row r) const  {return _id == r._id;}
   226       /// Inequality operator
   226       /// Inequality operator
   227       
   227 
   228       /// \sa operator==(Row r)
   228       /// \sa operator==(Row r)
   229       ///
   229       ///
   230       bool operator!=(Row r) const  {return _id != r._id;}
   230       bool operator!=(Row r) const  {return _id != r._id;}
   231       /// Artificial ordering operator.
   231       /// Artificial ordering operator.
   232 
   232 
   249     ///\endcode
   249     ///\endcode
   250     class RowIt : public Row {
   250     class RowIt : public Row {
   251       const LpBase *_solver;
   251       const LpBase *_solver;
   252     public:
   252     public:
   253       /// Default constructor
   253       /// Default constructor
   254       
   254 
   255       /// \warning The default constructor sets the iterator
   255       /// \warning The default constructor sets the iterator
   256       /// to an undefined value.
   256       /// to an undefined value.
   257       RowIt() {}
   257       RowIt() {}
   258       /// Sets the iterator to the first Row
   258       /// Sets the iterator to the first Row
   259       
   259 
   260       /// Sets the iterator to the first Row.
   260       /// Sets the iterator to the first Row.
   261       ///
   261       ///
   262       RowIt(const LpBase &solver) : _solver(&solver)
   262       RowIt(const LpBase &solver) : _solver(&solver)
   263       {
   263       {
   264         _solver->rows.firstItem(_id);
   264         _solver->rows.firstItem(_id);
   265       }
   265       }
   266       /// Invalid constructor \& conversion
   266       /// Invalid constructor \& conversion
   267       
   267 
   268       /// Initialize the iterator to be invalid.
   268       /// Initialize the iterator to be invalid.
   269       /// \sa Invalid for more details.
   269       /// \sa Invalid for more details.
   270       RowIt(const Invalid&) : Row(INVALID) {}
   270       RowIt(const Invalid&) : Row(INVALID) {}
   271       /// Next row
   271       /// Next row
   272       
   272 
   273       /// Assign the iterator to the next row.
   273       /// Assign the iterator to the next row.
   274       ///
   274       ///
   275       RowIt &operator++()
   275       RowIt &operator++()
   276       {
   276       {
   277         _solver->rows.nextItem(_id);
   277         _solver->rows.nextItem(_id);
   345       std::map<int, Value> comps;
   345       std::map<int, Value> comps;
   346 
   346 
   347     public:
   347     public:
   348       typedef True SolverExpr;
   348       typedef True SolverExpr;
   349       /// Default constructor
   349       /// Default constructor
   350       
   350 
   351       /// Construct an empty expression, the coefficients and
   351       /// Construct an empty expression, the coefficients and
   352       /// the constant component are initialized to zero.
   352       /// the constant component are initialized to zero.
   353       Expr() : const_comp(0) {}
   353       Expr() : const_comp(0) {}
   354       /// Construct an expression from a column
   354       /// Construct an expression from a column
   355 
   355 
   446         const_comp/=c;
   446         const_comp/=c;
   447         return *this;
   447         return *this;
   448       }
   448       }
   449 
   449 
   450       ///Iterator over the expression
   450       ///Iterator over the expression
   451       
   451 
   452       ///The iterator iterates over the terms of the expression. 
   452       ///The iterator iterates over the terms of the expression.
   453       /// 
   453       ///
   454       ///\code
   454       ///\code
   455       ///double s=0;
   455       ///double s=0;
   456       ///for(LpBase::Expr::CoeffIt i(e);i!=INVALID;++i)
   456       ///for(LpBase::Expr::CoeffIt i(e);i!=INVALID;++i)
   457       ///  s+= *i * primal(i);
   457       ///  s+= *i * primal(i);
   458       ///\endcode
   458       ///\endcode
   462         std::map<int, Value>::iterator _it, _end;
   462         std::map<int, Value>::iterator _it, _end;
   463 
   463 
   464       public:
   464       public:
   465 
   465 
   466         /// Sets the iterator to the first term
   466         /// Sets the iterator to the first term
   467         
   467 
   468         /// Sets the iterator to the first term of the expression.
   468         /// Sets the iterator to the first term of the expression.
   469         ///
   469         ///
   470         CoeffIt(Expr& e)
   470         CoeffIt(Expr& e)
   471           : _it(e.comps.begin()), _end(e.comps.end()){}
   471           : _it(e.comps.begin()), _end(e.comps.end()){}
   472 
   472 
   479         Value& operator*() { return _it->second; }
   479         Value& operator*() { return _it->second; }
   480 
   480 
   481         /// Returns the coefficient of the term
   481         /// Returns the coefficient of the term
   482         const Value& operator*() const { return _it->second; }
   482         const Value& operator*() const { return _it->second; }
   483         /// Next term
   483         /// Next term
   484         
   484 
   485         /// Assign the iterator to the next term.
   485         /// Assign the iterator to the next term.
   486         ///
   486         ///
   487         CoeffIt& operator++() { ++_it; return *this; }
   487         CoeffIt& operator++() { ++_it; return *this; }
   488 
   488 
   489         /// Equality operator
   489         /// Equality operator
   491         /// Inequality operator
   491         /// Inequality operator
   492         bool operator!=(Invalid) const { return _it != _end; }
   492         bool operator!=(Invalid) const { return _it != _end; }
   493       };
   493       };
   494 
   494 
   495       /// Const iterator over the expression
   495       /// Const iterator over the expression
   496       
   496 
   497       ///The iterator iterates over the terms of the expression. 
   497       ///The iterator iterates over the terms of the expression.
   498       /// 
   498       ///
   499       ///\code
   499       ///\code
   500       ///double s=0;
   500       ///double s=0;
   501       ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i)
   501       ///for(LpBase::Expr::ConstCoeffIt i(e);i!=INVALID;++i)
   502       ///  s+=*i * primal(i);
   502       ///  s+=*i * primal(i);
   503       ///\endcode
   503       ///\endcode
   507         std::map<int, Value>::const_iterator _it, _end;
   507         std::map<int, Value>::const_iterator _it, _end;
   508 
   508 
   509       public:
   509       public:
   510 
   510 
   511         /// Sets the iterator to the first term
   511         /// Sets the iterator to the first term
   512         
   512 
   513         /// Sets the iterator to the first term of the expression.
   513         /// Sets the iterator to the first term of the expression.
   514         ///
   514         ///
   515         ConstCoeffIt(const Expr& e)
   515         ConstCoeffIt(const Expr& e)
   516           : _it(e.comps.begin()), _end(e.comps.end()){}
   516           : _it(e.comps.begin()), _end(e.comps.end()){}
   517 
   517 
   522 
   522 
   523         /// Returns the coefficient of the term
   523         /// Returns the coefficient of the term
   524         const Value& operator*() const { return _it->second; }
   524         const Value& operator*() const { return _it->second; }
   525 
   525 
   526         /// Next term
   526         /// Next term
   527         
   527 
   528         /// Assign the iterator to the next term.
   528         /// Assign the iterator to the next term.
   529         ///
   529         ///
   530         ConstCoeffIt& operator++() { ++_it; return *this; }
   530         ConstCoeffIt& operator++() { ++_it; return *this; }
   531 
   531 
   532         /// Equality operator
   532         /// Equality operator
   671       std::map<int, Value> comps;
   671       std::map<int, Value> comps;
   672 
   672 
   673     public:
   673     public:
   674       typedef True SolverExpr;
   674       typedef True SolverExpr;
   675       /// Default constructor
   675       /// Default constructor
   676       
   676 
   677       /// Construct an empty expression, the coefficients are
   677       /// Construct an empty expression, the coefficients are
   678       /// initialized to zero.
   678       /// initialized to zero.
   679       DualExpr() {}
   679       DualExpr() {}
   680       /// Construct an expression from a row
   680       /// Construct an expression from a row
   681 
   681 
   706         } else {
   706         } else {
   707           comps.erase(id(r));
   707           comps.erase(id(r));
   708         }
   708         }
   709       }
   709       }
   710       /// \brief Removes the coefficients which's absolute value does
   710       /// \brief Removes the coefficients which's absolute value does
   711       /// not exceed \c epsilon. 
   711       /// not exceed \c epsilon.
   712       void simplify(Value epsilon = 0.0) {
   712       void simplify(Value epsilon = 0.0) {
   713         std::map<int, Value>::iterator it=comps.begin();
   713         std::map<int, Value>::iterator it=comps.begin();
   714         while (it != comps.end()) {
   714         while (it != comps.end()) {
   715           std::map<int, Value>::iterator jt=it;
   715           std::map<int, Value>::iterator jt=it;
   716           ++jt;
   716           ++jt;
   755           it->second/=v;
   755           it->second/=v;
   756         return *this;
   756         return *this;
   757       }
   757       }
   758 
   758 
   759       ///Iterator over the expression
   759       ///Iterator over the expression
   760       
   760 
   761       ///The iterator iterates over the terms of the expression. 
   761       ///The iterator iterates over the terms of the expression.
   762       /// 
   762       ///
   763       ///\code
   763       ///\code
   764       ///double s=0;
   764       ///double s=0;
   765       ///for(LpBase::DualExpr::CoeffIt i(e);i!=INVALID;++i)
   765       ///for(LpBase::DualExpr::CoeffIt i(e);i!=INVALID;++i)
   766       ///  s+= *i * dual(i);
   766       ///  s+= *i * dual(i);
   767       ///\endcode
   767       ///\endcode
   771         std::map<int, Value>::iterator _it, _end;
   771         std::map<int, Value>::iterator _it, _end;
   772 
   772 
   773       public:
   773       public:
   774 
   774 
   775         /// Sets the iterator to the first term
   775         /// Sets the iterator to the first term
   776         
   776 
   777         /// Sets the iterator to the first term of the expression.
   777         /// Sets the iterator to the first term of the expression.
   778         ///
   778         ///
   779         CoeffIt(DualExpr& e)
   779         CoeffIt(DualExpr& e)
   780           : _it(e.comps.begin()), _end(e.comps.end()){}
   780           : _it(e.comps.begin()), _end(e.comps.end()){}
   781 
   781 
   789 
   789 
   790         /// Returns the coefficient of the term
   790         /// Returns the coefficient of the term
   791         const Value& operator*() const { return _it->second; }
   791         const Value& operator*() const { return _it->second; }
   792 
   792 
   793         /// Next term
   793         /// Next term
   794         
   794 
   795         /// Assign the iterator to the next term.
   795         /// Assign the iterator to the next term.
   796         ///
   796         ///
   797         CoeffIt& operator++() { ++_it; return *this; }
   797         CoeffIt& operator++() { ++_it; return *this; }
   798 
   798 
   799         /// Equality operator
   799         /// Equality operator
   801         /// Inequality operator
   801         /// Inequality operator
   802         bool operator!=(Invalid) const { return _it != _end; }
   802         bool operator!=(Invalid) const { return _it != _end; }
   803       };
   803       };
   804 
   804 
   805       ///Iterator over the expression
   805       ///Iterator over the expression
   806       
   806 
   807       ///The iterator iterates over the terms of the expression. 
   807       ///The iterator iterates over the terms of the expression.
   808       /// 
   808       ///
   809       ///\code
   809       ///\code
   810       ///double s=0;
   810       ///double s=0;
   811       ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i)
   811       ///for(LpBase::DualExpr::ConstCoeffIt i(e);i!=INVALID;++i)
   812       ///  s+= *i * dual(i);
   812       ///  s+= *i * dual(i);
   813       ///\endcode
   813       ///\endcode
   817         std::map<int, Value>::const_iterator _it, _end;
   817         std::map<int, Value>::const_iterator _it, _end;
   818 
   818 
   819       public:
   819       public:
   820 
   820 
   821         /// Sets the iterator to the first term
   821         /// Sets the iterator to the first term
   822         
   822 
   823         /// Sets the iterator to the first term of the expression.
   823         /// Sets the iterator to the first term of the expression.
   824         ///
   824         ///
   825         ConstCoeffIt(const DualExpr& e)
   825         ConstCoeffIt(const DualExpr& e)
   826           : _it(e.comps.begin()), _end(e.comps.end()){}
   826           : _it(e.comps.begin()), _end(e.comps.end()){}
   827 
   827 
   832 
   832 
   833         /// Returns the coefficient of the term
   833         /// Returns the coefficient of the term
   834         const Value& operator*() const { return _it->second; }
   834         const Value& operator*() const { return _it->second; }
   835 
   835 
   836         /// Next term
   836         /// Next term
   837         
   837 
   838         /// Assign the iterator to the next term.
   838         /// Assign the iterator to the next term.
   839         ///
   839         ///
   840         ConstCoeffIt& operator++() { ++_it; return *this; }
   840         ConstCoeffIt& operator++() { ++_it; return *this; }
   841 
   841 
   842         /// Equality operator
   842         /// Equality operator
  1227     ///\param c is a linear expression (see \ref Constr)
  1227     ///\param c is a linear expression (see \ref Constr)
  1228     ///\return The created row.
  1228     ///\return The created row.
  1229     Row addRow(const Constr &c) {
  1229     Row addRow(const Constr &c) {
  1230       Row r;
  1230       Row r;
  1231       c.expr().simplify();
  1231       c.expr().simplify();
  1232       r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF, 
  1232       r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF,
  1233                                 ExprIterator(c.expr().comps.begin(), cols),
  1233                                 ExprIterator(c.expr().comps.begin(), cols),
  1234                                 ExprIterator(c.expr().comps.end(), cols),
  1234                                 ExprIterator(c.expr().comps.end(), cols),
  1235                                 c.upperBounded()?c.upperBound()-*c.expr():INF));
  1235                                 c.upperBounded()?c.upperBound()-*c.expr():INF));
  1236       return r;
  1236       return r;
  1237     }
  1237     }
  1815     };
  1815     };
  1816 
  1816 
  1817     ///The basis status of variables
  1817     ///The basis status of variables
  1818     enum VarStatus {
  1818     enum VarStatus {
  1819       /// The variable is in the basis
  1819       /// The variable is in the basis
  1820       BASIC, 
  1820       BASIC,
  1821       /// The variable is free, but not basic
  1821       /// The variable is free, but not basic
  1822       FREE,
  1822       FREE,
  1823       /// The variable has active lower bound 
  1823       /// The variable has active lower bound
  1824       LOWER,
  1824       LOWER,
  1825       /// The variable has active upper bound
  1825       /// The variable has active upper bound
  1826       UPPER,
  1826       UPPER,
  1827       /// The variable is non-basic and fixed
  1827       /// The variable is non-basic and fixed
  1828       FIXED
  1828       FIXED
  1897         res += *c * primal(c);
  1897         res += *c * primal(c);
  1898       }
  1898       }
  1899       return res;
  1899       return res;
  1900     }
  1900     }
  1901     /// Returns a component of the primal ray
  1901     /// Returns a component of the primal ray
  1902     
  1902 
  1903     /// The primal ray is solution of the modified primal problem,
  1903     /// The primal ray is solution of the modified primal problem,
  1904     /// where we change each finite bound to 0, and we looking for a
  1904     /// where we change each finite bound to 0, and we looking for a
  1905     /// negative objective value in case of minimization, and positive
  1905     /// negative objective value in case of minimization, and positive
  1906     /// objective value for maximization. If there is such solution,
  1906     /// objective value for maximization. If there is such solution,
  1907     /// that proofs the unsolvability of the dual problem, and if a
  1907     /// that proofs the unsolvability of the dual problem, and if a
  1931       }
  1931       }
  1932       return res;
  1932       return res;
  1933     }
  1933     }
  1934 
  1934 
  1935     /// Returns a component of the dual ray
  1935     /// Returns a component of the dual ray
  1936     
  1936 
  1937     /// The dual ray is solution of the modified primal problem, where
  1937     /// The dual ray is solution of the modified primal problem, where
  1938     /// we change each finite bound to 0 (i.e. the objective function
  1938     /// we change each finite bound to 0 (i.e. the objective function
  1939     /// coefficients in the primal problem), and we looking for a
  1939     /// coefficients in the primal problem), and we looking for a
  1940     /// ositive objective value. If there is such solution, that
  1940     /// ositive objective value. If there is such solution, that
  1941     /// proofs the unsolvability of the primal problem, and if a
  1941     /// proofs the unsolvability of the primal problem, and if a
  2073         res += *c * sol(c);
  2073         res += *c * sol(c);
  2074       }
  2074       }
  2075       return res;
  2075       return res;
  2076     }
  2076     }
  2077     ///The value of the objective function
  2077     ///The value of the objective function
  2078     
  2078 
  2079     ///\return
  2079     ///\return
  2080     ///- \ref INF or -\ref INF means either infeasibility or unboundedness
  2080     ///- \ref INF or -\ref INF means either infeasibility or unboundedness
  2081     /// of the problem, depending on whether we minimize or maximize.
  2081     /// of the problem, depending on whether we minimize or maximize.
  2082     ///- \ref NaN if no primal solution is found.
  2082     ///- \ref NaN if no primal solution is found.
  2083     ///- The (finite) objective value if an optimal solution is found.
  2083     ///- The (finite) objective value if an optimal solution is found.