athos@1247: /* -*- C++ -*-
alpar@1253:  * src/lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
athos@1247:  *
athos@1247:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
athos@1247:  * (Egervary Combinatorial Optimization Research Group, EGRES).
athos@1247:  *
athos@1247:  * Permission to use, modify and distribute this software is granted
athos@1247:  * provided that this copyright notice appears in all copies. For
athos@1247:  * precise terms see the accompanying LICENSE file.
athos@1247:  *
athos@1247:  * This software is provided "AS IS" with no warranty of any kind,
athos@1247:  * express or implied, and with no claim as to its suitability for any
athos@1247:  * purpose.
athos@1247:  *
athos@1247:  */
athos@1247: 
athos@1246: #ifndef LEMON_LP_BASE_H
athos@1246: #define LEMON_LP_BASE_H
athos@1246: 
alpar@1253: #include<vector>
alpar@1256: #include<limits>
alpar@1253: 
alpar@1256: #include<lemon/utility.h>
alpar@1253: #include<lemon/error.h>
alpar@1256: #include<lemon/invalid.h>
alpar@1253: 
alpar@1253: #include"lin_expr.h"
athos@1246: ///\file
athos@1246: ///\brief The interface of the LP solver interface.
athos@1246: namespace lemon {
alpar@1253:   
alpar@1253:   ///Internal data structure to convert floating id's to fix one's
alpar@1253:     
alpar@1253:   ///\todo This might by implemented to be usable in other places.
alpar@1253:   class _FixId 
alpar@1253:   {
alpar@1253:     std::vector<int> index;
alpar@1253:     std::vector<int> cross;
alpar@1253:     int first_free;
alpar@1253:   public:
alpar@1253:     _FixId() : first_free(-1) {};
alpar@1253:     ///Convert a floating id to a fix one
alpar@1253: 
alpar@1253:     ///\param n is a floating id
alpar@1253:     ///\return the corresponding fix id
alpar@1253:     int fixId(int n) {return cross[n];}
alpar@1253:     ///Convert a fix id to a floating one
alpar@1253: 
alpar@1253:     ///\param n is a fix id
alpar@1253:     ///\return the corresponding floating id
alpar@1253:     int floatingId(int n) { return index[n];}
alpar@1253:     ///Add a new floating id.
alpar@1253: 
alpar@1253:     ///\param n is a floating id
alpar@1253:     ///\return the fix id of the new value
alpar@1253:     ///\todo Multiple additions should also be handled.
alpar@1253:     int insert(int n)
alpar@1253:     {
alpar@1253:       if(n>=int(cross.size())) {
alpar@1253: 	cross.resize(n+1);
alpar@1253: 	if(first_free==-1) {
alpar@1253: 	  cross[n]=index.size();
alpar@1253: 	  index.push_back(n);
alpar@1253: 	}
alpar@1253: 	else {
alpar@1253: 	  cross[n]=first_free;
alpar@1253: 	  int next=index[first_free];
alpar@1253: 	  index[first_free]=n;
alpar@1253: 	  first_free=next;
alpar@1253: 	}
alpar@1256: 	return cross[n];
alpar@1253:       }
alpar@1253:       else throw LogicError(); //floatingId-s must form a continuous range;
alpar@1253:     }
alpar@1253:     ///Remove a fix id.
alpar@1253: 
alpar@1253:     ///\param n is a fix id
alpar@1253:     ///
alpar@1253:     void erase(int n) 
alpar@1253:     {
alpar@1253:       int fl=index[n];
alpar@1253:       index[n]=first_free;
alpar@1253:       first_free=n;
alpar@1253:       for(int i=fl+1;i<int(cross.size());++i) {
alpar@1253: 	cross[i-1]=cross[i];
alpar@1253: 	index[cross[i]]--;
alpar@1253:       }
alpar@1253:       cross.pop_back();
alpar@1253:     }
alpar@1253:     ///An upper bound on the largest fix id.
alpar@1253: 
alpar@1253:     ///\todo Do we need this?
alpar@1253:     ///
alpar@1253:     std::size_t maxFixId() { return cross.size()-1; }
alpar@1253:   
alpar@1253:   };
alpar@1253:     
alpar@1253:   ///Common base class for LP solvers
athos@1246:   class LpSolverBase {
alpar@1253:     
athos@1247:   public:
athos@1247: 
alpar@1263:     ///\e
alpar@1263:     enum SolutionType {
alpar@1263:       ///\e
alpar@1263:       INFEASIBLE = 0,
alpar@1263:       ///\e
alpar@1263:       UNBOUNDED = 1,
alpar@1263:       ///\e
alpar@1263:       OPTIMAL = 2,
alpar@1263:       ///\e
alpar@1263:       FEASIBLE = 3,
alpar@1263:     };
alpar@1263:       
alpar@1256:     ///The floating point type used by the solver
athos@1247:     typedef double Value;
alpar@1256:     ///The infinity constant
athos@1247:     static const Value INF;
alpar@1264:     ///The not a number constant
alpar@1264:     static const Value NaN;
alpar@1253:     
alpar@1256:     ///Refer to a column of the LP.
alpar@1256: 
alpar@1256:     ///This type is used to refer to a column of the LP.
alpar@1256:     ///
alpar@1256:     ///Its value remains valid and correct even after the addition or erase of
alpar@1256:     ///new column (unless the referred column itself was also deleted,
alpar@1256:     ///of course).
alpar@1256:     ///
alpar@1256:     ///\todo Document what can one do with a Col (INVALID, comparing,
alpar@1256:     ///it is similar to Node/Edge)
alpar@1256:     class Col {
alpar@1256:     protected:
alpar@1256:       int id;
alpar@1256:       friend class LpSolverBase;
alpar@1256:     public:
alpar@1259:       typedef Value ExprValue;
alpar@1256:       typedef True LpSolverCol;
alpar@1256:       Col() {}
alpar@1256:       Col(const Invalid&) : id(-1) {}
alpar@1256:       bool operator<(Col c) const  {return id<c.id;}
alpar@1256:       bool operator==(Col c) const  {return id==c.id;}
alpar@1256:       bool operator!=(Col c) const  {return id==c.id;}
alpar@1256:     };
alpar@1256: 
alpar@1256:     ///Refer to a row of the LP.
alpar@1256: 
alpar@1256:     ///This type is used to refer to a row of the LP.
alpar@1256:     ///
alpar@1256:     ///Its value remains valid and correct even after the addition or erase of
alpar@1256:     ///new rows (unless the referred row itself was also deleted, of course).
alpar@1256:     ///
alpar@1256:     ///\todo Document what can one do with a Row (INVALID, comparing,
alpar@1256:     ///it is similar to Node/Edge)
alpar@1256:     class Row {
alpar@1256:     protected:
alpar@1256:       int id;
alpar@1256:       friend class LpSolverBase;
alpar@1256:     public:
alpar@1259:       typedef Value ExprValue;
alpar@1256:       typedef True LpSolverRow;
alpar@1256:       Row() {}
alpar@1256:       Row(const Invalid&) : id(-1) {}
alpar@1256:       typedef True LpSolverRow;
alpar@1256:       bool operator<(Row c) const  {return id<c.id;}
alpar@1256:       bool operator==(Row c) const  {return id==c.id;}
alpar@1256:       bool operator!=(Row c) const  {return id==c.id;} 
alpar@1256:    };
alpar@1259:     
alpar@1259:     ///Linear expression
alpar@1259:     typedef SparseLinExpr<Col> Expr;
alpar@1264:     ///Linear constraint
alpar@1264:     typedef LinConstr<Expr> Constr;
alpar@1253: 
alpar@1253:   protected:
alpar@1253:     _FixId rows;
alpar@1253:     _FixId cols;
athos@1246: 
athos@1246:     /// \e
athos@1246:     virtual int _addCol() = 0;
athos@1246:     /// \e
athos@1246:     virtual int _addRow() = 0;
athos@1246:     /// \e
alpar@1253: 
athos@1246:     /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
alpar@1253:     ///
athos@1246:     virtual void _setRowCoeffs(int i, 
athos@1251: 			       int length,
athos@1247:                                int  const * indices, 
athos@1247:                                Value  const * values ) = 0;
athos@1246:     /// \e
alpar@1253: 
athos@1246:     /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
alpar@1253:     ///
athos@1246:     virtual void _setColCoeffs(int i, 
athos@1251: 			       int length,
athos@1247:                                int  const * indices, 
athos@1247:                                Value  const * values ) = 0;
athos@1246:     
athos@1247:     /// \e
alpar@1253: 
athos@1247:     /// The lower bound of a variable (column) have to be given by an 
athos@1247:     /// extended number of type Value, i.e. a finite number of type 
alpar@1259:     /// Value or -\ref INF.
athos@1247:     virtual void _setColLowerBound(int i, Value value) = 0;
athos@1247:     /// \e
alpar@1253: 
athos@1247:     /// The upper bound of a variable (column) have to be given by an 
athos@1247:     /// extended number of type Value, i.e. a finite number of type 
alpar@1259:     /// Value or \ref INF.
athos@1247:     virtual void _setColUpperBound(int i, Value value) = 0;
athos@1247:     /// \e
alpar@1253: 
athos@1247:     /// The lower bound of a linear expression (row) have to be given by an 
athos@1247:     /// extended number of type Value, i.e. a finite number of type 
alpar@1259:     /// Value or -\ref INF.
athos@1247:     virtual void _setRowLowerBound(int i, Value value) = 0;
athos@1247:     /// \e
alpar@1253: 
athos@1247:     /// The upper bound of a linear expression (row) have to be given by an 
athos@1247:     /// extended number of type Value, i.e. a finite number of type 
alpar@1259:     /// Value or \ref INF.
athos@1247:     virtual void _setRowUpperBound(int i, Value value) = 0;
athos@1247: 
athos@1247:     /// \e
athos@1247:     virtual void _setObjCoeff(int i, Value obj_coef) = 0;
alpar@1253: 
alpar@1253:     ///\e
alpar@1263:     
alpar@1263:     ///\bug Wrong interface
alpar@1263:     ///
alpar@1263:     virtual SolutionType _solve() = 0;
alpar@1263: 
alpar@1263:     ///\e
alpar@1263: 
alpar@1263:     ///\bug Wrong interface
alpar@1263:     ///
alpar@1263:     virtual Value _getSolution(int i) = 0;
alpar@1263:     ///\e
alpar@1253: 
alpar@1253:     ///\bug unimplemented!!!!
alpar@1253:     void clearObj() {}
alpar@1253:   public:
alpar@1253: 
alpar@1253: 
alpar@1253:     ///\e
alpar@1253:     virtual ~LpSolverBase() {}
alpar@1253: 
alpar@1263:     ///\name Building up and modification of the LP
alpar@1263: 
alpar@1263:     ///@{
alpar@1263: 
alpar@1253:     ///Add a new empty column (i.e a new variable) to the LP
alpar@1253:     Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
alpar@1263: 
alpar@1256:     ///\brief Fill the elements of a container with newly created columns
alpar@1256:     ///(i.e a new variables)
alpar@1256:     ///
alpar@1256:     ///This magic function takes container as its argument
alpar@1256:     ///and fills its elements
alpar@1256:     ///with new columns (i.e. variables)
alpar@1256:     ///\param t can be either any standard STL iterable container with
alpar@1256:     ///\ref Col \c values_type or \c mapped_type
alpar@1256:     ///like <tt>std::vector<LpSolverBase::Col></tt>,
alpar@1256:     /// <tt>std::list<LpSolverBase::Col></tt> or
alpar@1256:     /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or
alpar@1256:     ///it can be an iterable lemon map like 
alpar@1256:     /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>.
alpar@1256:     ///\return The number of the created column.
alpar@1256:     ///\bug Iterable nodemap hasn't been implemented yet.
alpar@1256: #ifdef DOXYGEN
alpar@1256:     template<class T>
alpar@1256:     int addColSet(T &t) { return 0;} 
alpar@1256: #else
alpar@1256:     template<class T>
alpar@1256:     typename enable_if<typename T::value_type::LpSolverCol,int>::type
alpar@1256:     addColSet(T &t,dummy<0> = 0) {
alpar@1256:       int s=0;
alpar@1256:       for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
alpar@1256:       return s;
alpar@1256:     }
alpar@1256:     template<class T>
alpar@1256:     typename enable_if<typename T::value_type::second_type::LpSolverCol,
alpar@1256: 		       int>::type
alpar@1256:     addColSet(T &t,dummy<1> = 1) { 
alpar@1256:       int s=0;
alpar@1256:       for(typename T::iterator i=t.begin();i!=t.end();++i) {
alpar@1256: 	i->second=addCol();
alpar@1256: 	s++;
alpar@1256:       }
alpar@1256:       return s;
alpar@1256:     }
alpar@1256: #endif
alpar@1263: 
alpar@1253:     ///Add a new empty row (i.e a new constaint) to the LP
alpar@1258: 
alpar@1258:     ///This function adds a new empty row (i.e a new constaint) to the LP.
alpar@1258:     ///\return The created row
alpar@1253:     Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
alpar@1253: 
alpar@1258:     ///Set a row (i.e a constaint) of the LP
alpar@1253: 
alpar@1258:     ///\param r is the row to be modified
alpar@1259:     ///\param l is lower bound (-\ref INF means no bound)
alpar@1258:     ///\param e is a linear expression (see \ref Expr)
alpar@1259:     ///\param u is the upper bound (\ref INF means no bound)
alpar@1253:     ///\bug This is a temportary function. The interface will change to
alpar@1253:     ///a better one.
alpar@1258:     void setRow(Row r, Value l,const Expr &e, Value u) {
alpar@1253:       std::vector<int> indices;
alpar@1253:       std::vector<Value> values;
alpar@1253:       indices.push_back(0);
alpar@1253:       values.push_back(0);
alpar@1258:       for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
alpar@1256: 	if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
alpar@1256: 	  indices.push_back(cols.floatingId((*i).first.id));
alpar@1256: 	  values.push_back((*i).second);
alpar@1256: 	}
alpar@1253:       _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
alpar@1253: 		    &indices[0],&values[0]);
alpar@1256:       _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
alpar@1256:       _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
alpar@1258:     }
alpar@1258: 
alpar@1264:     ///Set a row (i.e a constaint) of the LP
alpar@1264: 
alpar@1264:     ///\param r is the row to be modified
alpar@1264:     ///\param c is a linear expression (see \ref Constr)
alpar@1264:     ///\bug This is a temportary function. The interface will change to
alpar@1264:     ///a better one.
alpar@1264:     void setRow(Row r, const Constr &c) {
alpar@1264:       Value lb= c.lb==NaN?-INF:lb;
alpar@1264:       Value ub= c.ub==NaN?INF:lb;
alpar@1264:       setRow(r,lb,c.expr,ub);
alpar@1264:     }
alpar@1264: 
alpar@1258:     ///Add a new row (i.e a new constaint) to the LP
alpar@1258: 
alpar@1259:     ///\param l is the lower bound (-\ref INF means no bound)
alpar@1258:     ///\param e is a linear expression (see \ref Expr)
alpar@1259:     ///\param u is the upper bound (\ref INF means no bound)
alpar@1258:     ///\return The created row.
alpar@1258:     ///\bug This is a temportary function. The interface will change to
alpar@1258:     ///a better one.
alpar@1258:     Row addRow(Value l,const Expr &e, Value u) {
alpar@1258:       Row r=addRow();
alpar@1258:       setRow(r,l,e,u);
alpar@1253:       return r;
alpar@1253:     }
alpar@1253: 
alpar@1264:     ///Add a new row (i.e a new constaint) to the LP
alpar@1264: 
alpar@1264:     ///\param c is a linear expression (see \ref Constr)
alpar@1264:     ///\return The created row.
alpar@1264:     ///\bug This is a temportary function. The interface will change to
alpar@1264:     ///a better one.
alpar@1264:     Row addRow(const Constr &c) {
alpar@1264:       Row r=addRow();
alpar@1264:       setRow(r,c);
alpar@1264:       return r;
alpar@1264:     }
alpar@1264: 
alpar@1253:     /// Set the lower bound of a column (i.e a variable)
alpar@1253: 
alpar@1253:     /// The upper bound of a variable (column) have to be given by an 
alpar@1253:     /// extended number of type Value, i.e. a finite number of type 
alpar@1259:     /// Value or -\ref INF.
alpar@1253:     virtual void setColLowerBound(Col c, Value value) {
alpar@1253:       _setColLowerBound(cols.floatingId(c.id),value);
alpar@1253:     }
alpar@1253:     /// Set the upper bound of a column (i.e a variable)
alpar@1253: 
alpar@1253:     /// The upper bound of a variable (column) have to be given by an 
alpar@1253:     /// extended number of type Value, i.e. a finite number of type 
alpar@1259:     /// Value or \ref INF.
alpar@1253:     virtual void setColUpperBound(Col c, Value value) {
alpar@1253:       _setColUpperBound(cols.floatingId(c.id),value);
alpar@1253:     };
alpar@1253:     /// Set the lower bound of a row (i.e a constraint)
alpar@1253: 
alpar@1253:     /// The lower bound of a linear expression (row) have to be given by an 
alpar@1253:     /// extended number of type Value, i.e. a finite number of type 
alpar@1259:     /// Value or -\ref INF.
alpar@1253:     virtual void setRowLowerBound(Row r, Value value) {
alpar@1253:       _setRowLowerBound(rows.floatingId(r.id),value);
alpar@1253:     };
alpar@1253:     /// Set the upper bound of a row (i.e a constraint)
alpar@1253: 
alpar@1253:     /// The upper bound of a linear expression (row) have to be given by an 
alpar@1253:     /// extended number of type Value, i.e. a finite number of type 
alpar@1259:     /// Value or \ref INF.
alpar@1253:     virtual void setRowUpperBound(Row r, Value value) {
alpar@1253:       _setRowUpperBound(rows.floatingId(r.id),value);
alpar@1253:     };
alpar@1253:     ///Set an element of the objective function
alpar@1253:     void setObjCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
alpar@1253:     ///Set the objective function
alpar@1253:     
alpar@1253:     ///\param e is a linear expression of type \ref Expr.
alpar@1253:     ///\todo What to do with the constant component?
alpar@1253:     void setObj(Expr e) {
alpar@1253:       clearObj();
alpar@1253:       for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
alpar@1253: 	setObjCoeff((*i).first,(*i).second);
alpar@1253:     }
alpar@1263: 
alpar@1263:     ///@}
alpar@1263: 
alpar@1263: 
alpar@1263:     ///\name Solving the LP
alpar@1263: 
alpar@1263:     ///@{
alpar@1263: 
alpar@1263:     ///\e
alpar@1263:     SolutionType solve() { return _solve(); }
alpar@1263:     
alpar@1263:     ///@}
alpar@1263:     
alpar@1263:     ///\name Obtaining the solution LP
alpar@1263: 
alpar@1263:     ///@{
alpar@1263: 
alpar@1263:     ///\e
alpar@1263:     Value solution(Col c) { return _getSolution(cols.floatingId(c.id)); }
alpar@1263: 
alpar@1263:     ///@}
alpar@1253:     
athos@1248:   };  
athos@1246: 
athos@1246: } //namespace lemon
athos@1246: 
athos@1246: #endif //LEMON_LP_BASE_H