lemon-0.x: comparison src/work/marci/lp/lp_solver

equal deleted inserted replaced

-:5c774b4e1fcd
+:1d36f03c5a82
 // -*- c++ -*-
-#ifndef LEMON_LP_SOLVER_WRAPPER_H
+#ifndef LEMON_LP_SOLVER_BASE_H
-#define LEMON_LP_SOLVER_WRAPPER_H
+#define LEMON_LP_SOLVER_BASE_H
 ///\ingroup misc
 ///\file
-///\brief Dijkstra algorithm.
 // #include <stdio.h>
 #include <stdlib.h>
 #include <iostream>
 #include <map>
 #include <string>
 #include <list>
 #include <memory>
 #include <utility>
-//#include <lemon/list_graph.h>
 #include <lemon/invalid.h>
 #include <expression.h>
-//#include <bfs_dfs.h>
 //#include <stp.h>
 //#include <lemon/max_flow.h>
 //#include <augmenting_flow.h>
 //#include <iter_map.h>
 std::vector<Tip> tips;
 public:
 /// The classes are indexed by integers from \c 0 to \c classNum()-1.
 int classNum() const { return tips.size(); }
 /// This lemon style iterator iterates through a class.
-class ClassIt;
+class Class;
 /// Constructor. The number of classes is to be given which is fixed
 /// over the life of the container.
 /// The partition classes are indexed from 0 to class_num-1.
 IterablePartition(int class_num) {
 for (int i=0; i<class_num; ++i) {
 	t.first=t.last=-1;
 	tips.push_back(t);
 }
 }
 protected:
-void befuz(ClassIt it, int class_id) {
+void befuz(Class it, int class_id) {
 if (tips[class_id].first==-1) {
 	if (tips[class_id].last==-1) {
 	  nodes[it.i].prev=nodes[it.i].next=-1;
 	  tips[class_id].first=tips[class_id].last=it.i;
 	}
 	nodes[it.i].next=-1;
 	nodes[tips[class_id].last].next=it.i;
 	tips[class_id].last=it.i;
 }
 }
-void kifuz(ClassIt it, int class_id) {
+void kifuz(Class it, int class_id) {
 if (tips[class_id].first==it.i) {
 	if (tips[class_id].last==it.i) {
 	  tips[class_id].first=tips[class_id].last=-1;
 	} else {
 	  tips[class_id].first=nodes[it.i].next;
 }
 }
 public:
 /// A new element with data \c t is pushed into the vector and into class
 /// \c class_id.
-ClassIt push_back(const T& t, int class_id) {
+Class push_back(const T& t, int class_id) {
 Node n;
 n.data=t;
 nodes.push_back(n);
 int i=nodes.size()-1;
 befuz(i, class_id);
 return i;
 }
 /// A member is moved to an other class.
-void set(ClassIt it, int old_class_id, int new_class_id) {
+void set(Class it, int old_class_id, int new_class_id) {
 kifuz(it.i, old_class_id);
 befuz(it.i, new_class_id);
 }
 /// Returns the data pointed by \c it.
-T& operator[](ClassIt it) { return nodes[it.i].data; }
+T& operator[](Class it) { return nodes[it.i].data; }
 /// Returns the data pointed by \c it.
-const T& operator[](ClassIt it) const { return nodes[it.i].data; }
+const T& operator[](Class it) const { return nodes[it.i].data; }
 ///.
-class ClassIt {
+class Class {
 friend class IterablePartition;
 protected:
 int i;
 public:
 /// Default constructor.
-ClassIt() { }
+Class() { }
 /// This constructor constructs an iterator which points
 /// to the member of th container indexed by the integer _i.
-ClassIt(const int& _i) : i(_i) { }
+Class(const int& _i) : i(_i) { }
 /// Invalid constructor.
-ClassIt(const Invalid&) : i(-1) { }
+Class(const Invalid&) : i(-1) { }
-friend bool operator<(const ClassIt& x, const ClassIt& y);
+friend bool operator<(const Class& x, const Class& y);
 friend std::ostream& operator<<(std::ostream& os,
-				      const ClassIt& it);
+				      const Class& it);
+bool operator==(const Class& node) const {return i == node.i;}
+bool operator!=(const Class& node) const {return i != node.i;}
 };
-friend bool operator<(const ClassIt& x, const ClassIt& y) {
+friend bool operator<(const Class& x, const Class& y) {
 return (x.i < y.i);
 }
 friend std::ostream& operator<<(std::ostream& os,
-				    const ClassIt& it) {
+				    const Class& it) {
 os << it.i;
 return os;
 }
 /// First member of class \c class_id.
-ClassIt& first(ClassIt& it, int class_id) const {
+Class& first(Class& it, int class_id) const {
 it.i=tips[class_id].first;
 return it;
 }
 /// Next member.
-ClassIt& next(ClassIt& it) const {
+Class& next(Class& it) const {
 it.i=nodes[it.i].next;
 return it;
 }
 /// True iff the iterator is valid.
-bool valid(const ClassIt& it) const { return it.i!=-1; }
+bool valid(const Class& it) const { return it.i!=-1; }
+class ClassIt : public Class {
+const IterablePartition* iterable_partition;
+public:
+ClassIt() { }
+ClassIt(Invalid i) : Class(i) { }
+ClassIt(const IterablePartition& _iterable_partition,
+	      const int& i) : iterable_partition(&_iterable_partition) {
+_iterable_partition.first(*this, i);
+}
+ClassIt(const IterablePartition& _iterable_partition,
+	      const Class& _class) :
+	Class(_class), iterable_partition(&_iterable_partition) { }
+ClassIt& operator++() {
+iterable_partition->next(*this);
+return *this;
+}
+};
 };
 /*! \e
 \todo kellenene uj iterable structure bele, mert ez nem az igazi
 public:
 //UNCATEGORIZED
 /// \e
+typedef IterablePartition<int> Rows;
+/// \e
+typedef IterablePartition<int> Cols;
+/// \e
 typedef _Value Value;
 /// \e
-typedef IterablePartition<int>::ClassIt Row;
+typedef Rows::Class Row;
 /// \e
-typedef IterablePartition<int>::ClassIt Col;
+typedef Cols::Class Col;
 public:
 /// \e
 IterablePartition<int> row_iter_map;
 /// \e
 IterablePartition<int> col_iter_map;
 virtual void solveSimplex() = 0;
 /// \e
 virtual void solvePrimalSimplex() = 0;
 /// \e
 virtual void solveDualSimplex() = 0;
-/// \e
 //SOLUTION RETRIEVING
 /// \e
 virtual _Value getObjVal() = 0;
 			       const std::vector<std::pair<int, _Value> >& coeffs) = 0;
 /// \e
 /// This routine modifies \c coeffs only by the \c push_back method.
 virtual void _getRowCoeffs(int i,
 			       std::vector<std::pair<int, _Value> >& coeffs) = 0;
+/// \e
 virtual void _setColCoeffs(int i,
 			       const std::vector<std::pair<int, _Value> >& coeffs) = 0;
 /// \e
 /// This routine modifies \c coeffs only by the \c push_back method.
 virtual void _getColCoeffs(int i,
 			       std::vector<std::pair<int, _Value> >& coeffs) = 0;
-public:
+/// \e
-/// \e
+virtual void _setCoeff(int col, int row, _Value value) = 0;
-enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
+/// \e
+virtual _Value _getCoeff(int col, int row) = 0;
+//  public:
+//    /// \e
+//    enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
 protected:
 /// \e
 /// The lower bound of a variable (column) have to be given by an
 /// extended number of type _Value, i.e. a finite number of type
 /// _Value or -INF.
 /// The upper bound of a linear expression (row) is an
 /// extended number of type _Value, i.e. a finite number of type
 /// _Value or INF.
 virtual _Value _getRowUpperBound(int i) = 0;
 /// \e
-virtual void _setObjCoef(int i, _Value obj_coef) = 0;
+virtual void _setObjCoeff(int i, _Value obj_coef) = 0;
 /// \e
-virtual _Value _getObjCoef(int i) = 0;
+virtual _Value _getObjCoeff(int i) = 0;
 //SOLUTION RETRIEVING
 /// \e
 virtual _Value _getPrimal(int i) = 0;
 	if (row_iter_map[it]>rows[1]) --row_iter_map[it];
 }
 int_row_map.erase(int_row_map.begin()+rows[1]);
 }
 /// \e
+void setCoeff(Col col, Row row, _Value value) {
+_setCoeff(col_iter_map[col], row_iter_map[row], value);
+}
+/// \e
+_Value getCoeff(Col col, Row row) {
+return _getCoeff(col_iter_map[col], row_iter_map[row], value);
+}
+/// \e
 void setColLowerBound(Col col, _Value lo) {
 _setColLowerBound(col_iter_map[col], lo);
 }
 /// \e
 _Value getColLowerBound(Col col) {
 /// \e
 _Value getRowUpperBound(Row row) {
 return _getRowUpperBound(row_iter_map[row]);
 }
 /// \e
-void setObjCoef(const Col& col, _Value obj_coef) {
+void setObjCoeff(const Col& col, _Value obj_coef) {
-_setObjCoef(col_iter_map[col], obj_coef);
+_setObjCoeff(col_iter_map[col], obj_coef);
 }
 /// \e
-_Value getObjCoef(const Col& col) {
+_Value getObjCoeff(const Col& col) {
-return _getObjCoef(col_iter_map[col]);
+return _getObjCoeff(col_iter_map[col]);
 }
 //SOLUTION RETRIEVING FUNCTIONS
 /// \e
 	    i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) {
 	expr+= (*i).second*int_row_map[(*i).first];
 }
 }
 /// \e
-/// \bug ez igy nem jo
 void setObjCoeffs(const Expression& expr) {
+// writing zero everywhere
+for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
+	setObjCoeff(it, 0.0);
+// writing the data needed
 for(typename Expression::Data::const_iterator i=expr.data.begin();
 	  i!=expr.data.end(); ++i) {
-	setObjCoef((*i).first, (*i).second);
+	setObjCoeff((*i).first, (*i).second);
 }
 }
 /// \e
 /// This routine modifies \c expr by only adding to it.
 void getObjCoeffs(Expression& expr) {
-/// FIXME not yet implemented
+for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
+	expr+=getObjCoeff(it)*it;
+}
+//@}
+/*! @name MIP functions and types (public members)
+*/
+//@{
+public:
+/// \e
+virtual void solveBandB() = 0;
+/// \e
+virtual void setLP() = 0;
+/// \e
+virtual void setMIP() = 0;
+protected:
+/// \e
+virtual void _setColCont(int i) = 0;
+/// \e
+virtual void _setColInt(int i) = 0;
+public:
+/// \e
+void setColCont(Col col) {
+_setColCont(col_iter_map[col]);
+}
+/// \e
+void setColInt(Col col) {
+_setColInt(col_iter_map[col]);
 }
 //@}
 };
 template <typename _Value>
 }
 virtual void _eraseRow(int i) {
 int rows[2];
 rows[1]=i;
 lpx_del_rows(lp, 1, rows);
+}
+void _setCoeff(int col, int row, double value) {
+/// FIXME not yet implemented
+}
+double _getCoeff(int col, int row) {
+/// FIXME not yet implemented
+return 0.0;
 }
 virtual void _setColLowerBound(int i, double lo) {
 if (lo==INF) {
 	//FIXME error
 }
 	//FIXME error
 	return 0.0;
 }
 }
 /// \e
-virtual double _getObjCoef(int i) {
+virtual double _getObjCoeff(int i) {
 return lpx_get_obj_coef(lp, i);
 }
 /// \e
-virtual void _setObjCoef(int i, double obj_coef) {
+virtual void _setObjCoeff(int i, double obj_coef) {
 lpx_set_obj_coef(lp, i, obj_coef);
 }
 public:
 /// \e
 void solveSimplex() { lpx_simplex(lp); }
 /// \e
 void solvePrimalSimplex() { lpx_simplex(lp); }
 /// \e
 void solveDualSimplex() { lpx_simplex(lp); }
-/// \e
 protected:
 virtual double _getPrimal(int i) {
 return lpx_get_col_prim(lp, i);
 }
 public:
 case LPX_NU: cout << "LPX_NU" << endl; break;
 case LPX_NF: cout << "LPX_NF" << endl; break;
 case LPX_NS: cout << "LPX_NS" << endl; break;
 }
 }
+// MIP
+/// \e
+void solveBandB() { lpx_integer(lp); }
+/// \e
+void setLP() { lpx_set_class(lp, LPX_LP); }
+/// \e
+void setMIP() { lpx_set_class(lp, LPX_MIP); }
+protected:
+/// \e
+void _setColCont(int i) {lpx_set_col_kind(lp, i, LPX_CV); }
+/// \e
+void _setColInt(int i) {lpx_set_col_kind(lp, i, LPX_IV); }
 };
 /// @}
 } //namespace lemon
-#endif //LEMON_LP_SOLVER_WRAPPER_H
+#endif //LEMON_LP_SOLVER_BASE_H

changeset 1152	1765ff9fefa1
parent 1144	1cfabf245433
child 1153	4b0468de3a31