1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/athos/lp/Makefile Thu Mar 24 11:44:25 2005 +0000
1.3 @@ -0,0 +1,3 @@
1.4 +lp_base.o: lp_base.cc lp_base.h lin_expr.h
1.5 +
1.6 + g++ -Wall -ggdb --no-inline -I../../.. -c $<
1.7 \ No newline at end of file
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/athos/lp/lin_expr.h Thu Mar 24 11:44:25 2005 +0000
2.3 @@ -0,0 +1,71 @@
2.4 +/* -*- C++ -*-
2.5 + * src/lemon/lin_expr.h - Part of LEMON, a generic C++ optimization library
2.6 + *
2.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
2.9 + *
2.10 + * Permission to use, modify and distribute this software is granted
2.11 + * provided that this copyright notice appears in all copies. For
2.12 + * precise terms see the accompanying LICENSE file.
2.13 + *
2.14 + * This software is provided "AS IS" with no warranty of any kind,
2.15 + * express or implied, and with no claim as to its suitability for any
2.16 + * purpose.
2.17 + *
2.18 + */
2.19 +
2.20 +#ifndef LEMON_LIN_EXPR_H
2.21 +#define LEMON_LIN_EXPR_H
2.22 +
2.23 +#include<vector>
2.24 +
2.25 +
2.26 +#include<map>
2.27 +
2.28 +///\file
2.29 +///\brief Classes to handle linear expressions
2.30 +namespace lemon {
2.31 +
2.32 + /// Class to handle sparse linear expressions
2.33 + template <class _V,class _C>
2.34 + class SparseLinExpr : public std::map<_V, _C>
2.35 + {
2.36 + public:
2.37 + typedef _V Var;
2.38 + typedef _C Coeff;
2.39 +
2.40 + protected:
2.41 + typedef typename std::map<_V, _C> Base;
2.42 +
2.43 + Coeff const_comp;
2.44 + public:
2.45 + SparseLinExpr() { }
2.46 + SparseLinExpr(const Var &v) : const_comp(v) {
2.47 + Base::insert(std::make_pair(v, 1));
2.48 + }
2.49 + SparseLinExpr(const Coeff &v) : const_comp(v) {}
2.50 +
2.51 + void set(const Var &v,const Coeff &c) {
2.52 + return Base::insert(std::make_pair(v, c));
2.53 + }
2.54 +// Coeff &operator[](const Var &v) { return data[v]; }
2.55 +// const Coeff &operator[](const Var &v) const { return data[v]; }
2.56 +
2.57 + Coeff &constComp() { return const_comp; }
2.58 + const Coeff &constComp() const { return const_comp; }
2.59 +
2.60 + ///Removes the components with zero coefficient.
2.61 + void simplify() {
2.62 + for (typename Base::iterator i=Base::begin(); i!=Base::end();) {
2.63 + typename Base::iterator j=i;
2.64 + ++j;
2.65 + if ((*i).second==0) Base::erase(i);
2.66 + j=i;
2.67 + }
2.68 + }
2.69 +
2.70 + };
2.71 +
2.72 +} //namespace lemon
2.73 +
2.74 +#endif //LEMON_LIN_EXPR_H
3.1 --- a/src/work/athos/lp/lp_base.cc Wed Mar 23 16:59:13 2005 +0000
3.2 +++ b/src/work/athos/lp/lp_base.cc Thu Mar 24 11:44:25 2005 +0000
3.3 @@ -1,5 +1,5 @@
3.4 /* -*- C++ -*-
3.5 - * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library
3.6 + * src/lib/lp_base.cc - Part of LEMON, a generic C++ optimization library
3.7 *
3.8 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.9 * (Egervary Combinatorial Optimization Research Group, EGRES).
3.10 @@ -14,15 +14,12 @@
3.11 *
3.12 */
3.13
3.14 -#ifndef LEMON_LP_BASE_CC
3.15 -#define LEMON_LP_BASE_CC
3.16 -
3.17 ///\file
3.18 ///\brief The implementation of the LP solver interface.
3.19
3.20 #include "lp_base.h"
3.21 namespace lemon {
3.22
3.23 +
3.24 +
3.25 } //namespace lemon
3.26 -
3.27 -#endif //LEMON_LP_BASE_CC
4.1 --- a/src/work/athos/lp/lp_base.h Wed Mar 23 16:59:13 2005 +0000
4.2 +++ b/src/work/athos/lp/lp_base.h Thu Mar 24 11:44:25 2005 +0000
4.3 @@ -1,5 +1,5 @@
4.4 /* -*- C++ -*-
4.5 - * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library
4.6 + * src/lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
4.7 *
4.8 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.9 * (Egervary Combinatorial Optimization Research Group, EGRES).
4.10 @@ -17,19 +17,100 @@
4.11 #ifndef LEMON_LP_BASE_H
4.12 #define LEMON_LP_BASE_H
4.13
4.14 +#include<vector>
4.15 +
4.16 +#include<lemon/error.h>
4.17 +
4.18 +#include"lin_expr.h"
4.19 ///\file
4.20 ///\brief The interface of the LP solver interface.
4.21 namespace lemon {
4.22 +
4.23 + ///Internal data structure to convert floating id's to fix one's
4.24 +
4.25 + ///\todo This might by implemented to be usable in other places.
4.26 + class _FixId
4.27 + {
4.28 + std::vector<int> index;
4.29 + std::vector<int> cross;
4.30 + int first_free;
4.31 + public:
4.32 + _FixId() : first_free(-1) {};
4.33 + ///Convert a floating id to a fix one
4.34 +
4.35 + ///\param n is a floating id
4.36 + ///\return the corresponding fix id
4.37 + int fixId(int n) {return cross[n];}
4.38 + ///Convert a fix id to a floating one
4.39 +
4.40 + ///\param n is a fix id
4.41 + ///\return the corresponding floating id
4.42 + int floatingId(int n) { return index[n];}
4.43 + ///Add a new floating id.
4.44 +
4.45 + ///\param n is a floating id
4.46 + ///\return the fix id of the new value
4.47 + ///\todo Multiple additions should also be handled.
4.48 + int insert(int n)
4.49 + {
4.50 + if(n>=int(cross.size())) {
4.51 + cross.resize(n+1);
4.52 + if(first_free==-1) {
4.53 + cross[n]=index.size();
4.54 + index.push_back(n);
4.55 + }
4.56 + else {
4.57 + cross[n]=first_free;
4.58 + int next=index[first_free];
4.59 + index[first_free]=n;
4.60 + first_free=next;
4.61 + }
4.62 + }
4.63 + else throw LogicError(); //floatingId-s must form a continuous range;
4.64 + }
4.65 + ///Remove a fix id.
4.66 +
4.67 + ///\param n is a fix id
4.68 + ///
4.69 + void erase(int n)
4.70 + {
4.71 + int fl=index[n];
4.72 + index[n]=first_free;
4.73 + first_free=n;
4.74 + for(int i=fl+1;i<int(cross.size());++i) {
4.75 + cross[i-1]=cross[i];
4.76 + index[cross[i]]--;
4.77 + }
4.78 + cross.pop_back();
4.79 + }
4.80 + ///An upper bound on the largest fix id.
4.81 +
4.82 + ///\todo Do we need this?
4.83 + ///
4.84 + std::size_t maxFixId() { return cross.size()-1; }
4.85 +
4.86 + };
4.87 +
4.88 + ///Common base class for LP solvers
4.89 class LpSolverBase {
4.90 +
4.91 public:
4.92
4.93 - //UNCATEGORIZED
4.94 -
4.95 /// \e
4.96 typedef double Value;
4.97 /// \e
4.98 static const Value INF;
4.99 - protected:
4.100 +
4.101 + ///\e
4.102 + class Col { protected: int id; friend class LpSolverBase; };
4.103 + ///\e
4.104 + class Row { protected: int id; friend class LpSolverBase; };
4.105 +
4.106 + typedef SparseLinExpr<Col, Value> Expr;
4.107 +
4.108 + protected:
4.109 + _FixId rows;
4.110 + _FixId cols;
4.111
4.112 //MATRIX MANIPULATING FUNCTIONS
4.113
4.114 @@ -38,34 +119,42 @@
4.115 /// \e
4.116 virtual int _addRow() = 0;
4.117 /// \e
4.118 +
4.119 /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
4.120 + ///
4.121 virtual void _setRowCoeffs(int i,
4.122 int length,
4.123 int const * indices,
4.124 Value const * values ) = 0;
4.125 /// \e
4.126 +
4.127 /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
4.128 + ///
4.129 virtual void _setColCoeffs(int i,
4.130 int length,
4.131 int const * indices,
4.132 Value const * values ) = 0;
4.133
4.134 /// \e
4.135 +
4.136 /// The lower bound of a variable (column) have to be given by an
4.137 /// extended number of type Value, i.e. a finite number of type
4.138 /// Value or -INF.
4.139 virtual void _setColLowerBound(int i, Value value) = 0;
4.140 /// \e
4.141 +
4.142 /// The upper bound of a variable (column) have to be given by an
4.143 /// extended number of type Value, i.e. a finite number of type
4.144 /// Value or INF.
4.145 virtual void _setColUpperBound(int i, Value value) = 0;
4.146 /// \e
4.147 +
4.148 /// The lower bound of a linear expression (row) have to be given by an
4.149 /// extended number of type Value, i.e. a finite number of type
4.150 /// Value or -INF.
4.151 virtual void _setRowLowerBound(int i, Value value) = 0;
4.152 /// \e
4.153 +
4.154 /// The upper bound of a linear expression (row) have to be given by an
4.155 /// extended number of type Value, i.e. a finite number of type
4.156 /// Value or INF.
4.157 @@ -73,6 +162,90 @@
4.158
4.159 /// \e
4.160 virtual void _setObjCoeff(int i, Value obj_coef) = 0;
4.161 +
4.162 + ///\e
4.163 +
4.164 + ///\bug unimplemented!!!!
4.165 + void clearObj() {}
4.166 + public:
4.167 +
4.168 +
4.169 + ///\e
4.170 + virtual ~LpSolverBase() {}
4.171 +
4.172 + ///Add a new empty column (i.e a new variable) to the LP
4.173 + Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
4.174 + ///Add a new empty row (i.e a new constaint) to the LP
4.175 + Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
4.176 +
4.177 + ///Add a new row (i.e a new constaint) to the LP
4.178 +
4.179 + ///\param l lower bound (-INF means no bound)
4.180 + ///\param e a linear expression (see \ref Expr)
4.181 + ///\param u upper bound (INF means no bound)
4.182 + ///\bug This is a temportary function. The interface will change to
4.183 + ///a better one.
4.184 + Row addRow(Value l,Expr e, Value u) {
4.185 + Row r=addRow();
4.186 + std::vector<int> indices;
4.187 + std::vector<Value> values;
4.188 + indices.push_back(0);
4.189 + values.push_back(0);
4.190 + for(Expr::iterator i=e.begin(); i!=e.end(); ++i) {
4.191 + indices.push_back(cols.floatingId((*i).first.id));
4.192 + values.push_back((*i).second);
4.193 + }
4.194 + _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
4.195 + &indices[0],&values[0]);
4.196 + _setRowLowerBound(rows.floatingId(r.id),l);
4.197 + _setRowUpperBound(rows.floatingId(r.id),l);
4.198 + return r;
4.199 + }
4.200 +
4.201 + /// Set the lower bound of a column (i.e a variable)
4.202 +
4.203 + /// The upper bound of a variable (column) have to be given by an
4.204 + /// extended number of type Value, i.e. a finite number of type
4.205 + /// Value or -INF.
4.206 + virtual void setColLowerBound(Col c, Value value) {
4.207 + _setColLowerBound(cols.floatingId(c.id),value);
4.208 + }
4.209 + /// Set the upper bound of a column (i.e a variable)
4.210 +
4.211 + /// The upper bound of a variable (column) have to be given by an
4.212 + /// extended number of type Value, i.e. a finite number of type
4.213 + /// Value or INF.
4.214 + virtual void setColUpperBound(Col c, Value value) {
4.215 + _setColUpperBound(cols.floatingId(c.id),value);
4.216 + };
4.217 + /// Set the lower bound of a row (i.e a constraint)
4.218 +
4.219 + /// The lower bound of a linear expression (row) have to be given by an
4.220 + /// extended number of type Value, i.e. a finite number of type
4.221 + /// Value or -INF.
4.222 + virtual void setRowLowerBound(Row r, Value value) {
4.223 + _setRowLowerBound(rows.floatingId(r.id),value);
4.224 + };
4.225 + /// Set the upper bound of a row (i.e a constraint)
4.226 +
4.227 + /// The upper bound of a linear expression (row) have to be given by an
4.228 + /// extended number of type Value, i.e. a finite number of type
4.229 + /// Value or INF.
4.230 + virtual void setRowUpperBound(Row r, Value value) {
4.231 + _setRowUpperBound(rows.floatingId(r.id),value);
4.232 + };
4.233 + ///Set an element of the objective function
4.234 + void setObjCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
4.235 + ///Set the objective function
4.236 +
4.237 + ///\param e is a linear expression of type \ref Expr.
4.238 + ///\todo What to do with the constant component?
4.239 + void setObj(Expr e) {
4.240 + clearObj();
4.241 + for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
4.242 + setObjCoeff((*i).first,(*i).second);
4.243 + }
4.244 +
4.245 };
4.246
4.247 } //namespace lemon