1.1 --- a/src/lemon/Makefile.am Tue Apr 05 08:43:51 2005 +0000
1.2 +++ b/src/lemon/Makefile.am Tue Apr 05 09:08:23 2005 +0000
1.3 @@ -4,7 +4,10 @@
1.4 pkgconfig_DATA = lemon.pc
1.5
1.6 lib_LTLIBRARIES = libemon.la
1.7 -libemon_la_SOURCES =
1.8 +libemon_la_SOURCES = \
1.9 + lp_base.cc \
1.10 + lp_glpk.cc \
1.11 + lp_solver_skeleton.cc
1.12
1.13 pkginclude_HEADERS = \
1.14 array_map.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/lemon/lp_base.cc Tue Apr 05 09:08:23 2005 +0000
2.3 @@ -0,0 +1,33 @@
2.4 +/* -*- C++ -*-
2.5 + * src/lib/lp_base.cc - 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 +///\file
2.21 +///\brief The implementation of the LP solver interface.
2.22 +
2.23 +#include <lemon/lp_base.h>
2.24 +namespace lemon {
2.25 +
2.26 + const LpSolverBase::Value
2.27 + LpSolverBase::INF = std::numeric_limits<Value>::infinity();
2.28 + const LpSolverBase::Value
2.29 + LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN();
2.30 +
2.31 + const LpSolverBase::Constr::Value
2.32 + LpSolverBase::Constr::INF = std::numeric_limits<Value>::infinity();
2.33 + const LpSolverBase::Constr::Value
2.34 + LpSolverBase::Constr::NaN = std::numeric_limits<Value>::quiet_NaN();
2.35 +
2.36 +} //namespace lemon
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/lemon/lp_base.h Tue Apr 05 09:08:23 2005 +0000
3.3 @@ -0,0 +1,823 @@
3.4 +/* -*- C++ -*-
3.5 + * src/lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
3.6 + *
3.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
3.9 + *
3.10 + * Permission to use, modify and distribute this software is granted
3.11 + * provided that this copyright notice appears in all copies. For
3.12 + * precise terms see the accompanying LICENSE file.
3.13 + *
3.14 + * This software is provided "AS IS" with no warranty of any kind,
3.15 + * express or implied, and with no claim as to its suitability for any
3.16 + * purpose.
3.17 + *
3.18 + */
3.19 +
3.20 +#ifndef LEMON_LP_BASE_H
3.21 +#define LEMON_LP_BASE_H
3.22 +
3.23 +#include<vector>
3.24 +#include<map>
3.25 +#include<limits>
3.26 +#include<math.h>
3.27 +
3.28 +#include<lemon/utility.h>
3.29 +#include<lemon/error.h>
3.30 +#include<lemon/invalid.h>
3.31 +
3.32 +//#include"lin_expr.h"
3.33 +
3.34 +///\file
3.35 +///\brief The interface of the LP solver interface.
3.36 +namespace lemon {
3.37 +
3.38 + ///Internal data structure to convert floating id's to fix one's
3.39 +
3.40 + ///\todo This might be implemented to be also usable in other places.
3.41 + class _FixId
3.42 + {
3.43 + std::vector<int> index;
3.44 + std::vector<int> cross;
3.45 + int first_free;
3.46 + public:
3.47 + _FixId() : first_free(-1) {};
3.48 + ///Convert a floating id to a fix one
3.49 +
3.50 + ///\param n is a floating id
3.51 + ///\return the corresponding fix id
3.52 + int fixId(int n) {return cross[n];}
3.53 + ///Convert a fix id to a floating one
3.54 +
3.55 + ///\param n is a fix id
3.56 + ///\return the corresponding floating id
3.57 + int floatingId(int n) { return index[n];}
3.58 + ///Add a new floating id.
3.59 +
3.60 + ///\param n is a floating id
3.61 + ///\return the fix id of the new value
3.62 + ///\todo Multiple additions should also be handled.
3.63 + int insert(int n)
3.64 + {
3.65 + if(n>=int(cross.size())) {
3.66 + cross.resize(n+1);
3.67 + if(first_free==-1) {
3.68 + cross[n]=index.size();
3.69 + index.push_back(n);
3.70 + }
3.71 + else {
3.72 + cross[n]=first_free;
3.73 + int next=index[first_free];
3.74 + index[first_free]=n;
3.75 + first_free=next;
3.76 + }
3.77 + return cross[n];
3.78 + }
3.79 + ///\todo Create an own exception type.
3.80 + else throw LogicError(); //floatingId-s must form a continuous range;
3.81 + }
3.82 + ///Remove a fix id.
3.83 +
3.84 + ///\param n is a fix id
3.85 + ///
3.86 + void erase(int n)
3.87 + {
3.88 + int fl=index[n];
3.89 + index[n]=first_free;
3.90 + first_free=n;
3.91 + for(int i=fl+1;i<int(cross.size());++i) {
3.92 + cross[i-1]=cross[i];
3.93 + index[cross[i]]--;
3.94 + }
3.95 + cross.pop_back();
3.96 + }
3.97 + ///An upper bound on the largest fix id.
3.98 +
3.99 + ///\todo Do we need this?
3.100 + ///
3.101 + std::size_t maxFixId() { return cross.size()-1; }
3.102 +
3.103 + };
3.104 +
3.105 + ///Common base class for LP solvers
3.106 + class LpSolverBase {
3.107 +
3.108 + public:
3.109 +
3.110 + ///\e
3.111 + enum SolveExitStatus {
3.112 + ///\e
3.113 + SOLVED = 0,
3.114 + ///\e
3.115 + UNSOLVED = 1
3.116 + };
3.117 +
3.118 + ///\e
3.119 + enum SolutionStatus {
3.120 + ///Feasible solution has'n been found (but may exist).
3.121 +
3.122 + ///\todo NOTFOUND might be a better name.
3.123 + ///
3.124 + UNDEFINED = 0,
3.125 + ///The problem has no feasible solution
3.126 + INFEASIBLE = 1,
3.127 + ///Feasible solution found
3.128 + FEASIBLE = 2,
3.129 + ///Optimal solution exists and found
3.130 + OPTIMAL = 3,
3.131 + ///The cost function is unbounded
3.132 +
3.133 + ///\todo Give a feasible solution and an infinite ray (and the
3.134 + ///corresponding bases)
3.135 + INFINITE = 4
3.136 + };
3.137 +
3.138 + ///The floating point type used by the solver
3.139 + typedef double Value;
3.140 + ///The infinity constant
3.141 + static const Value INF;
3.142 + ///The not a number constant
3.143 + static const Value NaN;
3.144 +
3.145 + ///Refer to a column of the LP.
3.146 +
3.147 + ///This type is used to refer to a column of the LP.
3.148 + ///
3.149 + ///Its value remains valid and correct even after the addition or erase of
3.150 + ///other columns.
3.151 + ///
3.152 + ///\todo Document what can one do with a Col (INVALID, comparing,
3.153 + ///it is similar to Node/Edge)
3.154 + class Col {
3.155 + protected:
3.156 + int id;
3.157 + friend class LpSolverBase;
3.158 + public:
3.159 + typedef Value ExprValue;
3.160 + typedef True LpSolverCol;
3.161 + Col() {}
3.162 + Col(const Invalid&) : id(-1) {}
3.163 + bool operator<(Col c) const {return id<c.id;}
3.164 + bool operator==(Col c) const {return id==c.id;}
3.165 + bool operator!=(Col c) const {return id==c.id;}
3.166 + };
3.167 +
3.168 + ///Refer to a row of the LP.
3.169 +
3.170 + ///This type is used to refer to a row of the LP.
3.171 + ///
3.172 + ///Its value remains valid and correct even after the addition or erase of
3.173 + ///other rows.
3.174 + ///
3.175 + ///\todo Document what can one do with a Row (INVALID, comparing,
3.176 + ///it is similar to Node/Edge)
3.177 + class Row {
3.178 + protected:
3.179 + int id;
3.180 + friend class LpSolverBase;
3.181 + public:
3.182 + typedef Value ExprValue;
3.183 + typedef True LpSolverRow;
3.184 + Row() {}
3.185 + Row(const Invalid&) : id(-1) {}
3.186 + typedef True LpSolverRow;
3.187 + bool operator<(Row c) const {return id<c.id;}
3.188 + bool operator==(Row c) const {return id==c.id;}
3.189 + bool operator!=(Row c) const {return id==c.id;}
3.190 + };
3.191 +
3.192 + ///Linear expression of variables and a constant component
3.193 +
3.194 + ///This data structure strores a linear expression of the variables
3.195 + ///(\ref Col "Col"s) and also has a constant component.
3.196 + ///
3.197 + ///There are several ways to access and modify the contents of this
3.198 + ///container.
3.199 + ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
3.200 + ///if \c e is an Expr and \c v and \c w are of type \ref Col then you can
3.201 + ///read and modify the coefficients like
3.202 + ///these.
3.203 + ///\code
3.204 + ///e[v]=5;
3.205 + ///e[v]+=12;
3.206 + ///e.erase(v);
3.207 + ///\endcode
3.208 + ///or you can also iterate through its elements.
3.209 + ///\code
3.210 + ///double s=0;
3.211 + ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
3.212 + /// s+=i->second;
3.213 + ///\endcode
3.214 + ///(This code computes the sum of all coefficients).
3.215 + ///- Numbers (<tt>double</tt>'s)
3.216 + ///and variables (\ref Col "Col"s) directly convert to an
3.217 + ///\ref Expr and the usual linear operations are defined so
3.218 + ///\code
3.219 + ///v+w
3.220 + ///2*v-3.12*(v-w/2)+2
3.221 + ///v*2.1+(3*v+(v*12+w+6)*3)/2
3.222 + ///\endcode
3.223 + ///are valid expressions. The usual assignment operations are also defined.
3.224 + ///\code
3.225 + ///e=v+w;
3.226 + ///e+=2*v-3.12*(v-w/2)+2;
3.227 + ///e*=3.4;
3.228 + ///e/=5;
3.229 + ///\endcode
3.230 + ///- The constant member can be set and read by \ref constComp()
3.231 + ///\code
3.232 + ///e.constComp()=12;
3.233 + ///double c=e.constComp();
3.234 + ///\endcode
3.235 + ///
3.236 + ///\note that \ref clear() not only sets all coefficients to 0 but also
3.237 + ///clears the constant components.
3.238 + class Expr : public std::map<Col,Value>
3.239 + {
3.240 + public:
3.241 + typedef LpSolverBase::Col Key;
3.242 + typedef LpSolverBase::Value Value;
3.243 +
3.244 + protected:
3.245 + typedef std::map<Col,Value> Base;
3.246 +
3.247 + Value const_comp;
3.248 + public:
3.249 + typedef True IsLinExpression;
3.250 + ///\e
3.251 + Expr() : Base(), const_comp(0) { }
3.252 + ///\e
3.253 + Expr(const Key &v) : const_comp(0) {
3.254 + Base::insert(std::make_pair(v, 1));
3.255 + }
3.256 + ///\e
3.257 + Expr(const Value &v) : const_comp(v) {}
3.258 + ///\e
3.259 + void set(const Key &v,const Value &c) {
3.260 + Base::insert(std::make_pair(v, c));
3.261 + }
3.262 + ///\e
3.263 + Value &constComp() { return const_comp; }
3.264 + ///\e
3.265 + const Value &constComp() const { return const_comp; }
3.266 +
3.267 + ///Removes the components with zero coefficient.
3.268 + void simplify() {
3.269 + for (Base::iterator i=Base::begin(); i!=Base::end();) {
3.270 + Base::iterator j=i;
3.271 + ++j;
3.272 + if ((*i).second==0) Base::erase(i);
3.273 + j=i;
3.274 + }
3.275 + }
3.276 +
3.277 + ///Sets all coefficients and the constant component to 0.
3.278 + void clear() {
3.279 + Base::clear();
3.280 + const_comp=0;
3.281 + }
3.282 +
3.283 + ///\e
3.284 + Expr &operator+=(const Expr &e) {
3.285 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
3.286 + (*this)[j->first]+=j->second;
3.287 + ///\todo it might be speeded up using "hints"
3.288 + const_comp+=e.const_comp;
3.289 + return *this;
3.290 + }
3.291 + ///\e
3.292 + Expr &operator-=(const Expr &e) {
3.293 + for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
3.294 + (*this)[j->first]-=j->second;
3.295 + const_comp-=e.const_comp;
3.296 + return *this;
3.297 + }
3.298 + ///\e
3.299 + Expr &operator*=(const Value &c) {
3.300 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
3.301 + j->second*=c;
3.302 + const_comp*=c;
3.303 + return *this;
3.304 + }
3.305 + ///\e
3.306 + Expr &operator/=(const Value &c) {
3.307 + for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
3.308 + j->second/=c;
3.309 + const_comp/=c;
3.310 + return *this;
3.311 + }
3.312 + };
3.313 +
3.314 + ///Linear constraint
3.315 + //typedef LinConstr<Expr> Constr;
3.316 + class Constr
3.317 + {
3.318 + public:
3.319 + typedef LpSolverBase::Expr Expr;
3.320 + typedef Expr::Key Key;
3.321 + typedef Expr::Value Value;
3.322 +
3.323 + static const Value INF;
3.324 + static const Value NaN;
3.325 + // static const Value INF=0;
3.326 + // static const Value NaN=1;
3.327 +
3.328 + protected:
3.329 + Expr _expr;
3.330 + Value _lb,_ub;
3.331 + public:
3.332 + ///\e
3.333 + Constr() : _expr(), _lb(NaN), _ub(NaN) {}
3.334 + ///\e
3.335 + Constr(Value lb,const Expr &e,Value ub) :
3.336 + _expr(e), _lb(lb), _ub(ub) {}
3.337 + ///\e
3.338 + Constr(const Expr &e,Value ub) :
3.339 + _expr(e), _lb(NaN), _ub(ub) {}
3.340 + ///\e
3.341 + Constr(Value lb,const Expr &e) :
3.342 + _expr(e), _lb(lb), _ub(NaN) {}
3.343 + ///\e
3.344 + Constr(const Expr &e) :
3.345 + _expr(e), _lb(NaN), _ub(NaN) {}
3.346 + ///\e
3.347 + void clear()
3.348 + {
3.349 + _expr.clear();
3.350 + _lb=_ub=NaN;
3.351 + }
3.352 + ///\e
3.353 + Expr &expr() { return _expr; }
3.354 + ///\e
3.355 + const Expr &expr() const { return _expr; }
3.356 + ///\e
3.357 + Value &lowerBound() { return _lb; }
3.358 + ///\e
3.359 + const Value &lowerBound() const { return _lb; }
3.360 + ///\e
3.361 + Value &upperBound() { return _ub; }
3.362 + ///\e
3.363 + const Value &upperBound() const { return _ub; }
3.364 + ///\e
3.365 + bool lowerBounded() const {
3.366 + using namespace std;
3.367 + return isfinite(_lb);
3.368 + }
3.369 + ///\e
3.370 + bool upperBounded() const {
3.371 + using namespace std;
3.372 + return isfinite(_ub);
3.373 + }
3.374 + };
3.375 +
3.376 +
3.377 + protected:
3.378 + _FixId rows;
3.379 + _FixId cols;
3.380 +
3.381 + virtual int _addCol() = 0;
3.382 + virtual int _addRow() = 0;
3.383 + virtual void _setRowCoeffs(int i,
3.384 + int length,
3.385 + int const * indices,
3.386 + Value const * values ) = 0;
3.387 + virtual void _setColCoeffs(int i,
3.388 + int length,
3.389 + int const * indices,
3.390 + Value const * values ) = 0;
3.391 + virtual void _setColLowerBound(int i, Value value) = 0;
3.392 + virtual void _setColUpperBound(int i, Value value) = 0;
3.393 + virtual void _setRowLowerBound(int i, Value value) = 0;
3.394 + virtual void _setRowUpperBound(int i, Value value) = 0;
3.395 + virtual void _setObjCoeff(int i, Value obj_coef) = 0;
3.396 + virtual SolveExitStatus _solve() = 0;
3.397 + virtual Value _getPrimal(int i) = 0;
3.398 + virtual SolutionStatus _getPrimalType() = 0;
3.399 +
3.400 +
3.401 + void clearObj() {}
3.402 + public:
3.403 +
3.404 +
3.405 + ///\e
3.406 + virtual ~LpSolverBase() {}
3.407 +
3.408 + ///\name Build up and modify of the LP
3.409 +
3.410 + ///@{
3.411 +
3.412 + ///Add a new empty column (i.e a new variable) to the LP
3.413 + Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
3.414 +
3.415 + ///\brief Adds several new columns
3.416 + ///(i.e a variables) at once
3.417 + ///
3.418 + ///This magic function takes a container as its argument
3.419 + ///and fills its elements
3.420 + ///with new columns (i.e. variables)
3.421 + ///\param t can be
3.422 + ///- a standard STL compatible iterable container with
3.423 + ///\ref Col as its \c values_type
3.424 + ///like
3.425 + ///\code
3.426 + ///std::vector<LpSolverBase::Col>
3.427 + ///std::list<LpSolverBase::Col>
3.428 + ///\endcode
3.429 + ///- a standard STL compatible iterable container with
3.430 + ///\ref Col as its \c mapped_type
3.431 + ///like
3.432 + ///\code
3.433 + ///std::map<AnyType,LpSolverBase::Col>
3.434 + ///\endcode
3.435 + ///- an iterable lemon \ref concept::WriteMap "write map" like
3.436 + ///\code
3.437 + ///ListGraph::NodeMap<LpSolverBase::Col>
3.438 + ///ListGraph::EdgeMap<LpSolverBase::Col>
3.439 + ///\endcode
3.440 + ///\return The number of the created column.
3.441 + ///\bug Iterable nodemap hasn't been implemented yet.
3.442 +#ifdef DOXYGEN
3.443 + template<class T>
3.444 + int addColSet(T &t) { return 0;}
3.445 +#else
3.446 + template<class T>
3.447 + typename enable_if<typename T::value_type::LpSolverCol,int>::type
3.448 + addColSet(T &t,dummy<0> = 0) {
3.449 + int s=0;
3.450 + for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
3.451 + return s;
3.452 + }
3.453 + template<class T>
3.454 + typename enable_if<typename T::value_type::second_type::LpSolverCol,
3.455 + int>::type
3.456 + addColSet(T &t,dummy<1> = 1) {
3.457 + int s=0;
3.458 + for(typename T::iterator i=t.begin();i!=t.end();++i) {
3.459 + i->second=addCol();
3.460 + s++;
3.461 + }
3.462 + return s;
3.463 + }
3.464 + template<class T>
3.465 + typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
3.466 + int>::type
3.467 + addColSet(T &t,dummy<2> = 2) {
3.468 + ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
3.469 + int s=0;
3.470 + for(typename T::ValueSet::iterator i=t.valueSet().begin();
3.471 + i!=t.valueSet().end();
3.472 + ++i)
3.473 + {
3.474 + *i=addCol();
3.475 + s++;
3.476 + }
3.477 + return s;
3.478 + }
3.479 +#endif
3.480 +
3.481 + ///Add a new empty row (i.e a new constaint) to the LP
3.482 +
3.483 + ///This function adds a new empty row (i.e a new constaint) to the LP.
3.484 + ///\return The created row
3.485 + Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
3.486 +
3.487 + ///Set a row (i.e a constaint) of the LP
3.488 +
3.489 + ///\param r is the row to be modified
3.490 + ///\param l is lower bound (-\ref INF means no bound)
3.491 + ///\param e is a linear expression (see \ref Expr)
3.492 + ///\param u is the upper bound (\ref INF means no bound)
3.493 + ///\bug This is a temportary function. The interface will change to
3.494 + ///a better one.
3.495 + void setRow(Row r, Value l,const Expr &e, Value u) {
3.496 + std::vector<int> indices;
3.497 + std::vector<Value> values;
3.498 + indices.push_back(0);
3.499 + values.push_back(0);
3.500 + for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
3.501 + if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
3.502 + indices.push_back(cols.floatingId((*i).first.id));
3.503 + values.push_back((*i).second);
3.504 + }
3.505 + _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
3.506 + &indices[0],&values[0]);
3.507 + _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
3.508 + _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
3.509 + }
3.510 +
3.511 + ///Set a row (i.e a constaint) of the LP
3.512 +
3.513 + ///\param r is the row to be modified
3.514 + ///\param c is a linear expression (see \ref Constr)
3.515 + void setRow(Row r, const Constr &c) {
3.516 + setRow(r,
3.517 + c.lowerBounded()?c.lowerBound():-INF,
3.518 + c.expr(),
3.519 + c.upperBounded()?c.upperBound():INF);
3.520 + }
3.521 +
3.522 + ///Add a new row (i.e a new constaint) to the LP
3.523 +
3.524 + ///\param l is the lower bound (-\ref INF means no bound)
3.525 + ///\param e is a linear expression (see \ref Expr)
3.526 + ///\param u is the upper bound (\ref INF means no bound)
3.527 + ///\return The created row.
3.528 + ///\bug This is a temportary function. The interface will change to
3.529 + ///a better one.
3.530 + Row addRow(Value l,const Expr &e, Value u) {
3.531 + Row r=addRow();
3.532 + setRow(r,l,e,u);
3.533 + return r;
3.534 + }
3.535 +
3.536 + ///Add a new row (i.e a new constaint) to the LP
3.537 +
3.538 + ///\param c is a linear expression (see \ref Constr)
3.539 + ///\return The created row.
3.540 + Row addRow(const Constr &c) {
3.541 + Row r=addRow();
3.542 + setRow(r,c);
3.543 + return r;
3.544 + }
3.545 +
3.546 + /// Set the lower bound of a column (i.e a variable)
3.547 +
3.548 + /// The upper bound of a variable (column) has to be given by an
3.549 + /// extended number of type Value, i.e. a finite number of type
3.550 + /// Value or -\ref INF.
3.551 + void colLowerBound(Col c, Value value) {
3.552 + _setColLowerBound(cols.floatingId(c.id),value);
3.553 + }
3.554 + /// Set the upper bound of a column (i.e a variable)
3.555 +
3.556 + /// The upper bound of a variable (column) has to be given by an
3.557 + /// extended number of type Value, i.e. a finite number of type
3.558 + /// Value or \ref INF.
3.559 + void colUpperBound(Col c, Value value) {
3.560 + _setColUpperBound(cols.floatingId(c.id),value);
3.561 + };
3.562 + /// Set the lower and the upper bounds of a column (i.e a variable)
3.563 +
3.564 + /// The lower and the upper bounds of
3.565 + /// a variable (column) have to be given by an
3.566 + /// extended number of type Value, i.e. a finite number of type
3.567 + /// Value, -\ref INF or \ref INF.
3.568 + void colBounds(Col c, Value lower, Value upper) {
3.569 + _setColLowerBound(cols.floatingId(c.id),lower);
3.570 + _setColUpperBound(cols.floatingId(c.id),upper);
3.571 + }
3.572 +
3.573 + /// Set the lower bound of a row (i.e a constraint)
3.574 +
3.575 + /// The lower bound of a linear expression (row) has to be given by an
3.576 + /// extended number of type Value, i.e. a finite number of type
3.577 + /// Value or -\ref INF.
3.578 + void rowLowerBound(Row r, Value value) {
3.579 + _setRowLowerBound(rows.floatingId(r.id),value);
3.580 + };
3.581 + /// Set the upper bound of a row (i.e a constraint)
3.582 +
3.583 + /// The upper bound of a linear expression (row) has to be given by an
3.584 + /// extended number of type Value, i.e. a finite number of type
3.585 + /// Value or \ref INF.
3.586 + void rowUpperBound(Row r, Value value) {
3.587 + _setRowUpperBound(rows.floatingId(r.id),value);
3.588 + };
3.589 + /// Set the lower and the upper bounds of a row (i.e a variable)
3.590 +
3.591 + /// The lower and the upper bounds of
3.592 + /// a constraint (row) have to be given by an
3.593 + /// extended number of type Value, i.e. a finite number of type
3.594 + /// Value, -\ref INF or \ref INF.
3.595 + void rowBounds(Row c, Value lower, Value upper) {
3.596 + _setRowLowerBound(rows.floatingId(c.id),lower);
3.597 + _setRowUpperBound(rows.floatingId(c.id),upper);
3.598 + }
3.599 +
3.600 + ///Set an element of the objective function
3.601 + void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
3.602 + ///Set the objective function
3.603 +
3.604 + ///\param e is a linear expression of type \ref Expr.
3.605 + ///\todo What to do with the constant component?
3.606 + void setObj(Expr e) {
3.607 + clearObj();
3.608 + for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
3.609 + objCoeff((*i).first,(*i).second);
3.610 + }
3.611 +
3.612 + ///@}
3.613 +
3.614 +
3.615 + ///\name Solve the LP
3.616 +
3.617 + ///@{
3.618 +
3.619 + ///\e
3.620 + SolveExitStatus solve() { return _solve(); }
3.621 +
3.622 + ///@}
3.623 +
3.624 + ///\name Obtain the solution
3.625 +
3.626 + ///@{
3.627 +
3.628 + ///\e
3.629 + SolutionStatus primalType() {
3.630 + return _getPrimalType();
3.631 + }
3.632 +
3.633 + ///\e
3.634 + Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
3.635 +
3.636 + ///@}
3.637 +
3.638 + };
3.639 +
3.640 + ///\e
3.641 +
3.642 + ///\relates LpSolverBase::Expr
3.643 + ///
3.644 + inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
3.645 + const LpSolverBase::Expr &b)
3.646 + {
3.647 + LpSolverBase::Expr tmp(a);
3.648 + tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
3.649 + return tmp;
3.650 + }
3.651 + ///\e
3.652 +
3.653 + ///\relates LpSolverBase::Expr
3.654 + ///
3.655 + inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
3.656 + const LpSolverBase::Expr &b)
3.657 + {
3.658 + LpSolverBase::Expr tmp(a);
3.659 + tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
3.660 + return tmp;
3.661 + }
3.662 + ///\e
3.663 +
3.664 + ///\relates LpSolverBase::Expr
3.665 + ///
3.666 + inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
3.667 + const LpSolverBase::Value &b)
3.668 + {
3.669 + LpSolverBase::Expr tmp(a);
3.670 + tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
3.671 + return tmp;
3.672 + }
3.673 +
3.674 + ///\e
3.675 +
3.676 + ///\relates LpSolverBase::Expr
3.677 + ///
3.678 + inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
3.679 + const LpSolverBase::Expr &b)
3.680 + {
3.681 + LpSolverBase::Expr tmp(b);
3.682 + tmp*=a; ///\todo Don't STL have some special 'merge' algorithm?
3.683 + return tmp;
3.684 + }
3.685 + ///\e
3.686 +
3.687 + ///\relates LpSolverBase::Expr
3.688 + ///
3.689 + inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
3.690 + const LpSolverBase::Value &b)
3.691 + {
3.692 + LpSolverBase::Expr tmp(a);
3.693 + tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
3.694 + return tmp;
3.695 + }
3.696 +
3.697 + ///\e
3.698 +
3.699 + ///\relates LpSolverBase::Constr
3.700 + ///
3.701 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
3.702 + const LpSolverBase::Expr &f)
3.703 + {
3.704 + return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
3.705 + }
3.706 +
3.707 + ///\e
3.708 +
3.709 + ///\relates LpSolverBase::Constr
3.710 + ///
3.711 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
3.712 + const LpSolverBase::Expr &f)
3.713 + {
3.714 + return LpSolverBase::Constr(e,f);
3.715 + }
3.716 +
3.717 + ///\e
3.718 +
3.719 + ///\relates LpSolverBase::Constr
3.720 + ///
3.721 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
3.722 + const LpSolverBase::Value &f)
3.723 + {
3.724 + return LpSolverBase::Constr(e,f);
3.725 + }
3.726 +
3.727 + ///\e
3.728 +
3.729 + ///\relates LpSolverBase::Constr
3.730 + ///
3.731 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
3.732 + const LpSolverBase::Expr &f)
3.733 + {
3.734 + return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
3.735 + }
3.736 +
3.737 +
3.738 + ///\e
3.739 +
3.740 + ///\relates LpSolverBase::Constr
3.741 + ///
3.742 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
3.743 + const LpSolverBase::Expr &f)
3.744 + {
3.745 + return LpSolverBase::Constr(f,e);
3.746 + }
3.747 +
3.748 +
3.749 + ///\e
3.750 +
3.751 + ///\relates LpSolverBase::Constr
3.752 + ///
3.753 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
3.754 + const LpSolverBase::Value &f)
3.755 + {
3.756 + return LpSolverBase::Constr(f,e);
3.757 + }
3.758 +
3.759 + ///\e
3.760 +
3.761 + ///\relates LpSolverBase::Constr
3.762 + ///
3.763 + inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
3.764 + const LpSolverBase::Expr &f)
3.765 + {
3.766 + return LpSolverBase::Constr(0,e-f,0);
3.767 + }
3.768 +
3.769 + ///\e
3.770 +
3.771 + ///\relates LpSolverBase::Constr
3.772 + ///
3.773 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
3.774 + const LpSolverBase::Constr&c)
3.775 + {
3.776 + LpSolverBase::Constr tmp(c);
3.777 + ///\todo Create an own exception type.
3.778 + if(!isnan(tmp.lowerBound())) throw LogicError();
3.779 + else tmp.lowerBound()=n;
3.780 + return tmp;
3.781 + }
3.782 + ///\e
3.783 +
3.784 + ///\relates LpSolverBase::Constr
3.785 + ///
3.786 + inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
3.787 + const LpSolverBase::Value &n)
3.788 + {
3.789 + LpSolverBase::Constr tmp(c);
3.790 + ///\todo Create an own exception type.
3.791 + if(!isnan(tmp.upperBound())) throw LogicError();
3.792 + else tmp.upperBound()=n;
3.793 + return tmp;
3.794 + }
3.795 +
3.796 + ///\e
3.797 +
3.798 + ///\relates LpSolverBase::Constr
3.799 + ///
3.800 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
3.801 + const LpSolverBase::Constr&c)
3.802 + {
3.803 + LpSolverBase::Constr tmp(c);
3.804 + ///\todo Create an own exception type.
3.805 + if(!isnan(tmp.upperBound())) throw LogicError();
3.806 + else tmp.upperBound()=n;
3.807 + return tmp;
3.808 + }
3.809 + ///\e
3.810 +
3.811 + ///\relates LpSolverBase::Constr
3.812 + ///
3.813 + inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
3.814 + const LpSolverBase::Value &n)
3.815 + {
3.816 + LpSolverBase::Constr tmp(c);
3.817 + ///\todo Create an own exception type.
3.818 + if(!isnan(tmp.lowerBound())) throw LogicError();
3.819 + else tmp.lowerBound()=n;
3.820 + return tmp;
3.821 + }
3.822 +
3.823 +
3.824 +} //namespace lemon
3.825 +
3.826 +#endif //LEMON_LP_BASE_H
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/lemon/lp_glpk.cc Tue Apr 05 09:08:23 2005 +0000
4.3 @@ -0,0 +1,288 @@
4.4 +/* -*- C++ -*-
4.5 + * src/lemon/lp_glpk.cc - Part of LEMON, a generic C++ optimization library
4.6 + *
4.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
4.9 + *
4.10 + * Permission to use, modify and distribute this software is granted
4.11 + * provided that this copyright notice appears in all copies. For
4.12 + * precise terms see the accompanying LICENSE file.
4.13 + *
4.14 + * This software is provided "AS IS" with no warranty of any kind,
4.15 + * express or implied, and with no claim as to its suitability for any
4.16 + * purpose.
4.17 + *
4.18 + */
4.19 +
4.20 +#ifndef LEMON_LP_GLPK_CC
4.21 +#define LEMON_LP_GLPK_CC
4.22 +
4.23 +///\file
4.24 +///\brief Implementation of the LEMON-GLPK lp solver interface.
4.25 +
4.26 +#include <lemon/lp_glpk.h>
4.27 +
4.28 +namespace lemon {
4.29 +
4.30 + /// \e
4.31 + int LpGlpk::_addCol() {
4.32 + int i=lpx_add_cols(lp, 1);
4.33 + _setColLowerBound(i, -INF);
4.34 + _setColUpperBound(i, INF);
4.35 + return i;
4.36 + }
4.37 +
4.38 + /// \e
4.39 + int LpGlpk::_addRow() {
4.40 + int i=lpx_add_rows(lp, 1);
4.41 + return i;
4.42 + }
4.43 +
4.44 +
4.45 + void LpGlpk::_setRowCoeffs(int i,
4.46 + int length,
4.47 + const int * indices,
4.48 + const Value * values )
4.49 + {
4.50 + lpx_set_mat_row(lp, i, length,
4.51 + const_cast<int * >(indices) ,
4.52 + const_cast<Value * >(values));
4.53 + }
4.54 +
4.55 + void LpGlpk::_setColCoeffs(int i,
4.56 + int length,
4.57 + const int * indices,
4.58 + const Value * values)
4.59 + {
4.60 + lpx_set_mat_col(lp, i, length,
4.61 + const_cast<int * >(indices),
4.62 + const_cast<Value * >(values));
4.63 + }
4.64 +
4.65 + void LpGlpk::_setColLowerBound(int i, Value lo)
4.66 + {
4.67 + if (lo==INF) {
4.68 + //FIXME error
4.69 + }
4.70 + int b=lpx_get_col_type(lp, i);
4.71 + double up=lpx_get_col_ub(lp, i);
4.72 + if (lo==-INF) {
4.73 + switch (b) {
4.74 + case LPX_FR:
4.75 + case LPX_LO:
4.76 + lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
4.77 + break;
4.78 + case LPX_UP:
4.79 + break;
4.80 + case LPX_DB:
4.81 + case LPX_FX:
4.82 + lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
4.83 + break;
4.84 + default: ;
4.85 + //FIXME error
4.86 + }
4.87 + } else {
4.88 + switch (b) {
4.89 + case LPX_FR:
4.90 + case LPX_LO:
4.91 + lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
4.92 + break;
4.93 + case LPX_UP:
4.94 + case LPX_DB:
4.95 + case LPX_FX:
4.96 + if (lo==up)
4.97 + lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
4.98 + else
4.99 + lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
4.100 + break;
4.101 + default: ;
4.102 + //FIXME error
4.103 + }
4.104 + }
4.105 +
4.106 + }
4.107 +
4.108 + void LpGlpk::_setColUpperBound(int i, Value up)
4.109 + {
4.110 + if (up==-INF) {
4.111 + //FIXME error
4.112 + }
4.113 + int b=lpx_get_col_type(lp, i);
4.114 + double lo=lpx_get_col_lb(lp, i);
4.115 + if (up==INF) {
4.116 + switch (b) {
4.117 + case LPX_FR:
4.118 + case LPX_LO:
4.119 + break;
4.120 + case LPX_UP:
4.121 + lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
4.122 + break;
4.123 + case LPX_DB:
4.124 + case LPX_FX:
4.125 + lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
4.126 + break;
4.127 + default: ;
4.128 + //FIXME error
4.129 + }
4.130 + } else {
4.131 + switch (b) {
4.132 + case LPX_FR:
4.133 + lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
4.134 + break;
4.135 + case LPX_UP:
4.136 + lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
4.137 + break;
4.138 + case LPX_LO:
4.139 + case LPX_DB:
4.140 + case LPX_FX:
4.141 + if (lo==up)
4.142 + lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
4.143 + else
4.144 + lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
4.145 + break;
4.146 + default: ;
4.147 + //FIXME error
4.148 + }
4.149 + }
4.150 + }
4.151 +
4.152 + void LpGlpk::_setRowLowerBound(int i, Value lo)
4.153 + {
4.154 + if (lo==INF) {
4.155 + //FIXME error
4.156 + }
4.157 + int b=lpx_get_row_type(lp, i);
4.158 + double up=lpx_get_row_ub(lp, i);
4.159 + if (lo==-INF) {
4.160 + switch (b) {
4.161 + case LPX_FR:
4.162 + case LPX_LO:
4.163 + lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
4.164 + break;
4.165 + case LPX_UP:
4.166 + break;
4.167 + case LPX_DB:
4.168 + case LPX_FX:
4.169 + lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
4.170 + break;
4.171 + default: ;
4.172 + //FIXME error
4.173 + }
4.174 + } else {
4.175 + switch (b) {
4.176 + case LPX_FR:
4.177 + case LPX_LO:
4.178 + lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
4.179 + break;
4.180 + case LPX_UP:
4.181 + case LPX_DB:
4.182 + case LPX_FX:
4.183 + if (lo==up)
4.184 + lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
4.185 + else
4.186 + lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
4.187 + break;
4.188 + default: ;
4.189 + //FIXME error
4.190 + }
4.191 + }
4.192 + }
4.193 +
4.194 + void LpGlpk::_setRowUpperBound(int i, Value up)
4.195 + {
4.196 + if (up==-INF) {
4.197 + //FIXME error
4.198 + }
4.199 + int b=lpx_get_row_type(lp, i);
4.200 + double lo=lpx_get_row_lb(lp, i);
4.201 + if (up==INF) {
4.202 + switch (b) {
4.203 + case LPX_FR:
4.204 + case LPX_LO:
4.205 + break;
4.206 + case LPX_UP:
4.207 + lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
4.208 + break;
4.209 + case LPX_DB:
4.210 + case LPX_FX:
4.211 + lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
4.212 + break;
4.213 + default: ;
4.214 + //FIXME error
4.215 + }
4.216 + } else {
4.217 + switch (b) {
4.218 + case LPX_FR:
4.219 + lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
4.220 + break;
4.221 + case LPX_UP:
4.222 + lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
4.223 + break;
4.224 + case LPX_LO:
4.225 + case LPX_DB:
4.226 + case LPX_FX:
4.227 + if (lo==up)
4.228 + lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
4.229 + else
4.230 + lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
4.231 + break;
4.232 + default: ;
4.233 + //FIXME error
4.234 + }
4.235 + }
4.236 + }
4.237 +
4.238 + void LpGlpk::_setObjCoeff(int i, Value obj_coef)
4.239 + {
4.240 + lpx_set_obj_coef(lp, i, obj_coef);
4.241 + }
4.242 +
4.243 +
4.244 + LpGlpk::SolveExitStatus LpGlpk::_solve()
4.245 + {
4.246 + int i= lpx_simplex(lp);
4.247 + switch (i) {
4.248 + case LPX_E_OK:
4.249 + return SOLVED;
4.250 + break;
4.251 + default:
4.252 + return UNSOLVED;
4.253 + }
4.254 + }
4.255 +
4.256 + LpGlpk::Value LpGlpk::_getPrimal(int i)
4.257 + {
4.258 + return lpx_get_col_prim(lp,i);
4.259 + }
4.260 +
4.261 +
4.262 + LpGlpk::SolutionStatus LpGlpk::_getPrimalType()
4.263 + {
4.264 + int stat= lpx_get_status(lp);
4.265 + switch (stat) {
4.266 + case LPX_UNDEF://Undefined (no solve has been run yet)
4.267 + return UNDEFINED;
4.268 + break;
4.269 + case LPX_NOFEAS://There is no feasible solution (primal, I guess)
4.270 + case LPX_INFEAS://Infeasible
4.271 + return INFEASIBLE;
4.272 + break;
4.273 + case LPX_UNBND://Unbounded
4.274 + return INFINITE;
4.275 + break;
4.276 + case LPX_FEAS://Feasible
4.277 + return FEASIBLE;
4.278 + break;
4.279 + case LPX_OPT://Feasible
4.280 + return OPTIMAL;
4.281 + break;
4.282 + default:
4.283 + return UNDEFINED; //to avoid gcc warning
4.284 + //FIXME error
4.285 + }
4.286 + }
4.287 +
4.288 +
4.289 +} //END OF NAMESPACE LEMON
4.290 +
4.291 +#endif //LEMON_LP_GLPK_CC
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/lemon/lp_glpk.h Tue Apr 05 09:08:23 2005 +0000
5.3 @@ -0,0 +1,89 @@
5.4 +/* -*- C++ -*-
5.5 + * src/lemon/lp_glpk.h - Part of LEMON, a generic C++ optimization library
5.6 + *
5.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
5.9 + *
5.10 + * Permission to use, modify and distribute this software is granted
5.11 + * provided that this copyright notice appears in all copies. For
5.12 + * precise terms see the accompanying LICENSE file.
5.13 + *
5.14 + * This software is provided "AS IS" with no warranty of any kind,
5.15 + * express or implied, and with no claim as to its suitability for any
5.16 + * purpose.
5.17 + *
5.18 + */
5.19 +
5.20 +#ifndef LEMON_LP_GLPK_H
5.21 +#define LEMON_LP_GLPK_H
5.22 +
5.23 +///\file
5.24 +///\brief Header of the LEMON-GLPK lp solver interface.
5.25 +
5.26 +#include "lp_base.h"
5.27 +extern "C" {
5.28 +#include "glpk.h"
5.29 +}
5.30 +
5.31 +namespace lemon {
5.32 +
5.33 +
5.34 + /// \brief Wrapper for GLPK solver
5.35 + ///
5.36 + /// This class implements a lemon wrapper for GLPK.
5.37 + class LpGlpk : public LpSolverBase {
5.38 +
5.39 + public:
5.40 +
5.41 + typedef LpSolverBase Parent;
5.42 +
5.43 + /// \e
5.44 + LPX* lp;
5.45 +
5.46 + /// \e
5.47 + LpGlpk() : Parent(),
5.48 + lp(lpx_create_prob()) {
5.49 + lpx_set_int_parm(lp, LPX_K_DUAL, 1);
5.50 + }
5.51 + /// \e
5.52 + ~LpGlpk() {
5.53 + lpx_delete_prob(lp);
5.54 + }
5.55 +
5.56 + protected:
5.57 + virtual int _addCol();
5.58 + virtual int _addRow();
5.59 + virtual void _setRowCoeffs(int i,
5.60 + int length,
5.61 + const int * indices,
5.62 + const Value * values );
5.63 + virtual void _setColCoeffs(int i,
5.64 + int length,
5.65 + const int * indices,
5.66 + const Value * values);
5.67 + virtual void _setColLowerBound(int i, Value value);
5.68 + virtual void _setColUpperBound(int i, Value value);
5.69 + virtual void _setRowLowerBound(int i, Value value);
5.70 + virtual void _setRowUpperBound(int i, Value value);
5.71 + virtual void _setObjCoeff(int i, Value obj_coef);
5.72 + ///\e
5.73 +
5.74 + ///\bug Unimplemented
5.75 + ///
5.76 + virtual SolveExitStatus _solve();
5.77 + ///\e
5.78 +
5.79 + ///\bug Unimplemented
5.80 + ///
5.81 + virtual Value _getPrimal(int i);
5.82 + ///\e
5.83 +
5.84 + ///\bug Unimplemented
5.85 + ///
5.86 + virtual SolutionStatus _getPrimalType();
5.87 +
5.88 + };
5.89 +} //END OF NAMESPACE LEMON
5.90 +
5.91 +#endif //LEMON_LP_GLPK_H
5.92 +
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/lemon/lp_solver_skeleton.cc Tue Apr 05 09:08:23 2005 +0000
6.3 @@ -0,0 +1,84 @@
6.4 +/* -*- C++ -*-
6.5 + * src/lemon/lp_solver_skeleton.cc
6.6 + * - Part of LEMON, a generic C++ optimization library
6.7 + *
6.8 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6.9 + * (Egervary Combinatorial Optimization Research Group, EGRES).
6.10 + *
6.11 + * Permission to use, modify and distribute this software is granted
6.12 + * provided that this copyright notice appears in all copies. For
6.13 + * precise terms see the accompanying LICENSE file.
6.14 + *
6.15 + * This software is provided "AS IS" with no warranty of any kind,
6.16 + * express or implied, and with no claim as to its suitability for any
6.17 + * purpose.
6.18 + *
6.19 + */
6.20 +
6.21 +#include <lemon/lp_solver_skeleton.h>
6.22 +
6.23 +///\file
6.24 +///\brief A skeleton file to implement LP solver interfaces
6.25 +namespace lemon {
6.26 +
6.27 + int LpSolverSkeleton::_addCol()
6.28 + {
6.29 + return ++col_num;
6.30 + }
6.31 +
6.32 + int LpSolverSkeleton::_addRow()
6.33 + {
6.34 + return ++row_num;
6.35 + }
6.36 +
6.37 + void LpSolverSkeleton::_setRowCoeffs(int i,
6.38 + int length,
6.39 + int const * indices,
6.40 + Value const * values )
6.41 + {
6.42 + }
6.43 +
6.44 + void LpSolverSkeleton::_setColCoeffs(int i,
6.45 + int length,
6.46 + int const * indices,
6.47 + Value const * values)
6.48 + {
6.49 + }
6.50 +
6.51 + void LpSolverSkeleton::_setColLowerBound(int i, Value value)
6.52 + {
6.53 + }
6.54 +
6.55 + void LpSolverSkeleton::_setColUpperBound(int i, Value value)
6.56 + {
6.57 + }
6.58 +
6.59 + void LpSolverSkeleton::_setRowLowerBound(int i, Value value)
6.60 + {
6.61 + }
6.62 +
6.63 + void LpSolverSkeleton::_setRowUpperBound(int i, Value value)
6.64 + {
6.65 + }
6.66 +
6.67 + void LpSolverSkeleton::_setObjCoeff(int i, Value obj_coef)
6.68 + {
6.69 + }
6.70 +
6.71 + LpSolverSkeleton::SolveExitStatus LpSolverSkeleton::_solve()
6.72 + {
6.73 + return SOLVED;
6.74 + }
6.75 +
6.76 + LpSolverSkeleton::Value LpSolverSkeleton::_getPrimal(int i)
6.77 + {
6.78 + return 0;
6.79 + }
6.80 +
6.81 + LpSolverSkeleton::SolutionStatus LpSolverSkeleton::_getPrimalType()
6.82 + {
6.83 + return OPTIMAL;
6.84 + }
6.85 +
6.86 +} //namespace lemon
6.87 +
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/src/lemon/lp_solver_skeleton.h Tue Apr 05 09:08:23 2005 +0000
7.3 @@ -0,0 +1,104 @@
7.4 +/* -*- C++ -*-
7.5 + * src/lemon/lp_solver_skeleton.h
7.6 + * - Part of LEMON, a generic C++ optimization library
7.7 + *
7.8 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.9 + * (Egervary Combinatorial Optimization Research Group, EGRES).
7.10 + *
7.11 + * Permission to use, modify and distribute this software is granted
7.12 + * provided that this copyright notice appears in all copies. For
7.13 + * precise terms see the accompanying LICENSE file.
7.14 + *
7.15 + * This software is provided "AS IS" with no warranty of any kind,
7.16 + * express or implied, and with no claim as to its suitability for any
7.17 + * purpose.
7.18 + *
7.19 + */
7.20 +
7.21 +#ifndef LEMON_LP_SOLVER_SKELETON
7.22 +#define LEMON_LP_SOLVER_SKELETON
7.23 +
7.24 +#include"lp_base.h"
7.25 +
7.26 +///\file
7.27 +///\brief A skeleton file to implement LP solver interfaces
7.28 +namespace lemon {
7.29 +
7.30 + ///A skeleton class to implement LP solver interfaces
7.31 + class LpSolverSkeleton :public LpSolverBase {
7.32 + int col_num,row_num;
7.33 +
7.34 + protected:
7.35 + /// \e
7.36 + virtual int _addCol();
7.37 + /// \e
7.38 + virtual int _addRow();
7.39 + /// \e
7.40 +
7.41 + /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
7.42 + ///
7.43 + virtual void _setRowCoeffs(int i,
7.44 + int length,
7.45 + int const * indices,
7.46 + Value const * values );
7.47 + /// \e
7.48 +
7.49 + /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
7.50 + ///
7.51 + virtual void _setColCoeffs(int i,
7.52 + int length,
7.53 + int const * indices,
7.54 + Value const * values );
7.55 +
7.56 + /// \e
7.57 +
7.58 + /// The lower bound of a variable (column) have to be given by an
7.59 + /// extended number of type Value, i.e. a finite number of type
7.60 + /// Value or -\ref INF.
7.61 + virtual void _setColLowerBound(int i, Value value);
7.62 + /// \e
7.63 +
7.64 + /// The upper bound of a variable (column) have to be given by an
7.65 + /// extended number of type Value, i.e. a finite number of type
7.66 + /// Value or \ref INF.
7.67 + virtual void _setColUpperBound(int i, Value value);
7.68 + /// \e
7.69 +
7.70 + /// The lower bound of a linear expression (row) have to be given by an
7.71 + /// extended number of type Value, i.e. a finite number of type
7.72 + /// Value or -\ref INF.
7.73 + virtual void _setRowLowerBound(int i, Value value);
7.74 + /// \e
7.75 +
7.76 + /// The upper bound of a linear expression (row) have to be given by an
7.77 + /// extended number of type Value, i.e. a finite number of type
7.78 + /// Value or \ref INF.
7.79 + virtual void _setRowUpperBound(int i, Value value);
7.80 +
7.81 + /// \e
7.82 + virtual void _setObjCoeff(int i, Value obj_coef);
7.83 +
7.84 + ///\e
7.85 +
7.86 + ///\bug Wrong interface
7.87 + ///
7.88 + virtual SolveExitStatus _solve();
7.89 +
7.90 + ///\e
7.91 +
7.92 + ///\bug Wrong interface
7.93 + ///
7.94 + virtual Value _getPrimal(int i);
7.95 + ///\e
7.96 +
7.97 + ///\bug Wrong interface
7.98 + ///
7.99 + virtual SolutionStatus _getPrimalType();
7.100 +
7.101 + public:
7.102 + LpSolverSkeleton() : LpSolverBase(), col_num(0), row_num(0) {}
7.103 + };
7.104 +
7.105 +} //namespace lemon
7.106 +
7.107 +#endif // LEMON_LP_SOLVER_SKELETON
8.1 --- a/src/work/athos/lp/lp_base.cc Tue Apr 05 08:43:51 2005 +0000
8.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
8.3 @@ -1,33 +0,0 @@
8.4 -/* -*- C++ -*-
8.5 - * src/lib/lp_base.cc - Part of LEMON, a generic C++ optimization library
8.6 - *
8.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
8.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
8.9 - *
8.10 - * Permission to use, modify and distribute this software is granted
8.11 - * provided that this copyright notice appears in all copies. For
8.12 - * precise terms see the accompanying LICENSE file.
8.13 - *
8.14 - * This software is provided "AS IS" with no warranty of any kind,
8.15 - * express or implied, and with no claim as to its suitability for any
8.16 - * purpose.
8.17 - *
8.18 - */
8.19 -
8.20 -///\file
8.21 -///\brief The implementation of the LP solver interface.
8.22 -
8.23 -#include "lp_base.h"
8.24 -namespace lemon {
8.25 -
8.26 - const LpSolverBase::Value
8.27 - LpSolverBase::INF = std::numeric_limits<Value>::infinity();
8.28 - const LpSolverBase::Value
8.29 - LpSolverBase::NaN = std::numeric_limits<Value>::quiet_NaN();
8.30 -
8.31 - const LpSolverBase::Constr::Value
8.32 - LpSolverBase::Constr::INF = std::numeric_limits<Value>::infinity();
8.33 - const LpSolverBase::Constr::Value
8.34 - LpSolverBase::Constr::NaN = std::numeric_limits<Value>::quiet_NaN();
8.35 -
8.36 -} //namespace lemon
9.1 --- a/src/work/athos/lp/lp_base.h Tue Apr 05 08:43:51 2005 +0000
9.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
9.3 @@ -1,823 +0,0 @@
9.4 -/* -*- C++ -*-
9.5 - * src/lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
9.6 - *
9.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
9.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
9.9 - *
9.10 - * Permission to use, modify and distribute this software is granted
9.11 - * provided that this copyright notice appears in all copies. For
9.12 - * precise terms see the accompanying LICENSE file.
9.13 - *
9.14 - * This software is provided "AS IS" with no warranty of any kind,
9.15 - * express or implied, and with no claim as to its suitability for any
9.16 - * purpose.
9.17 - *
9.18 - */
9.19 -
9.20 -#ifndef LEMON_LP_BASE_H
9.21 -#define LEMON_LP_BASE_H
9.22 -
9.23 -#include<vector>
9.24 -#include<map>
9.25 -#include<limits>
9.26 -#include<math.h>
9.27 -
9.28 -#include<lemon/utility.h>
9.29 -#include<lemon/error.h>
9.30 -#include<lemon/invalid.h>
9.31 -
9.32 -//#include"lin_expr.h"
9.33 -
9.34 -///\file
9.35 -///\brief The interface of the LP solver interface.
9.36 -namespace lemon {
9.37 -
9.38 - ///Internal data structure to convert floating id's to fix one's
9.39 -
9.40 - ///\todo This might be implemented to be also usable in other places.
9.41 - class _FixId
9.42 - {
9.43 - std::vector<int> index;
9.44 - std::vector<int> cross;
9.45 - int first_free;
9.46 - public:
9.47 - _FixId() : first_free(-1) {};
9.48 - ///Convert a floating id to a fix one
9.49 -
9.50 - ///\param n is a floating id
9.51 - ///\return the corresponding fix id
9.52 - int fixId(int n) {return cross[n];}
9.53 - ///Convert a fix id to a floating one
9.54 -
9.55 - ///\param n is a fix id
9.56 - ///\return the corresponding floating id
9.57 - int floatingId(int n) { return index[n];}
9.58 - ///Add a new floating id.
9.59 -
9.60 - ///\param n is a floating id
9.61 - ///\return the fix id of the new value
9.62 - ///\todo Multiple additions should also be handled.
9.63 - int insert(int n)
9.64 - {
9.65 - if(n>=int(cross.size())) {
9.66 - cross.resize(n+1);
9.67 - if(first_free==-1) {
9.68 - cross[n]=index.size();
9.69 - index.push_back(n);
9.70 - }
9.71 - else {
9.72 - cross[n]=first_free;
9.73 - int next=index[first_free];
9.74 - index[first_free]=n;
9.75 - first_free=next;
9.76 - }
9.77 - return cross[n];
9.78 - }
9.79 - ///\todo Create an own exception type.
9.80 - else throw LogicError(); //floatingId-s must form a continuous range;
9.81 - }
9.82 - ///Remove a fix id.
9.83 -
9.84 - ///\param n is a fix id
9.85 - ///
9.86 - void erase(int n)
9.87 - {
9.88 - int fl=index[n];
9.89 - index[n]=first_free;
9.90 - first_free=n;
9.91 - for(int i=fl+1;i<int(cross.size());++i) {
9.92 - cross[i-1]=cross[i];
9.93 - index[cross[i]]--;
9.94 - }
9.95 - cross.pop_back();
9.96 - }
9.97 - ///An upper bound on the largest fix id.
9.98 -
9.99 - ///\todo Do we need this?
9.100 - ///
9.101 - std::size_t maxFixId() { return cross.size()-1; }
9.102 -
9.103 - };
9.104 -
9.105 - ///Common base class for LP solvers
9.106 - class LpSolverBase {
9.107 -
9.108 - public:
9.109 -
9.110 - ///\e
9.111 - enum SolveExitStatus {
9.112 - ///\e
9.113 - SOLVED = 0,
9.114 - ///\e
9.115 - UNSOLVED = 1
9.116 - };
9.117 -
9.118 - ///\e
9.119 - enum SolutionStatus {
9.120 - ///Feasible solution has'n been found (but may exist).
9.121 -
9.122 - ///\todo NOTFOUND might be a better name.
9.123 - ///
9.124 - UNDEFINED = 0,
9.125 - ///The problem has no feasible solution
9.126 - INFEASIBLE = 1,
9.127 - ///Feasible solution found
9.128 - FEASIBLE = 2,
9.129 - ///Optimal solution exists and found
9.130 - OPTIMAL = 3,
9.131 - ///The cost function is unbounded
9.132 -
9.133 - ///\todo Give a feasible solution and an infinite ray (and the
9.134 - ///corresponding bases)
9.135 - INFINITE = 4
9.136 - };
9.137 -
9.138 - ///The floating point type used by the solver
9.139 - typedef double Value;
9.140 - ///The infinity constant
9.141 - static const Value INF;
9.142 - ///The not a number constant
9.143 - static const Value NaN;
9.144 -
9.145 - ///Refer to a column of the LP.
9.146 -
9.147 - ///This type is used to refer to a column of the LP.
9.148 - ///
9.149 - ///Its value remains valid and correct even after the addition or erase of
9.150 - ///other columns.
9.151 - ///
9.152 - ///\todo Document what can one do with a Col (INVALID, comparing,
9.153 - ///it is similar to Node/Edge)
9.154 - class Col {
9.155 - protected:
9.156 - int id;
9.157 - friend class LpSolverBase;
9.158 - public:
9.159 - typedef Value ExprValue;
9.160 - typedef True LpSolverCol;
9.161 - Col() {}
9.162 - Col(const Invalid&) : id(-1) {}
9.163 - bool operator<(Col c) const {return id<c.id;}
9.164 - bool operator==(Col c) const {return id==c.id;}
9.165 - bool operator!=(Col c) const {return id==c.id;}
9.166 - };
9.167 -
9.168 - ///Refer to a row of the LP.
9.169 -
9.170 - ///This type is used to refer to a row of the LP.
9.171 - ///
9.172 - ///Its value remains valid and correct even after the addition or erase of
9.173 - ///other rows.
9.174 - ///
9.175 - ///\todo Document what can one do with a Row (INVALID, comparing,
9.176 - ///it is similar to Node/Edge)
9.177 - class Row {
9.178 - protected:
9.179 - int id;
9.180 - friend class LpSolverBase;
9.181 - public:
9.182 - typedef Value ExprValue;
9.183 - typedef True LpSolverRow;
9.184 - Row() {}
9.185 - Row(const Invalid&) : id(-1) {}
9.186 - typedef True LpSolverRow;
9.187 - bool operator<(Row c) const {return id<c.id;}
9.188 - bool operator==(Row c) const {return id==c.id;}
9.189 - bool operator!=(Row c) const {return id==c.id;}
9.190 - };
9.191 -
9.192 - ///Linear expression of variables and a constant component
9.193 -
9.194 - ///This data structure strores a linear expression of the variables
9.195 - ///(\ref Col "Col"s) and also has a constant component.
9.196 - ///
9.197 - ///There are several ways to access and modify the contents of this
9.198 - ///container.
9.199 - ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
9.200 - ///if \c e is an Expr and \c v and \c w are of type \ref Col then you can
9.201 - ///read and modify the coefficients like
9.202 - ///these.
9.203 - ///\code
9.204 - ///e[v]=5;
9.205 - ///e[v]+=12;
9.206 - ///e.erase(v);
9.207 - ///\endcode
9.208 - ///or you can also iterate through its elements.
9.209 - ///\code
9.210 - ///double s=0;
9.211 - ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
9.212 - /// s+=i->second;
9.213 - ///\endcode
9.214 - ///(This code computes the sum of all coefficients).
9.215 - ///- Numbers (<tt>double</tt>'s)
9.216 - ///and variables (\ref Col "Col"s) directly convert to an
9.217 - ///\ref Expr and the usual linear operations are defined so
9.218 - ///\code
9.219 - ///v+w
9.220 - ///2*v-3.12*(v-w/2)+2
9.221 - ///v*2.1+(3*v+(v*12+w+6)*3)/2
9.222 - ///\endcode
9.223 - ///are valid expressions. The usual assignment operations are also defined.
9.224 - ///\code
9.225 - ///e=v+w;
9.226 - ///e+=2*v-3.12*(v-w/2)+2;
9.227 - ///e*=3.4;
9.228 - ///e/=5;
9.229 - ///\endcode
9.230 - ///- The constant member can be set and read by \ref constComp()
9.231 - ///\code
9.232 - ///e.constComp()=12;
9.233 - ///double c=e.constComp();
9.234 - ///\endcode
9.235 - ///
9.236 - ///\note that \ref clear() not only sets all coefficients to 0 but also
9.237 - ///clears the constant components.
9.238 - class Expr : public std::map<Col,Value>
9.239 - {
9.240 - public:
9.241 - typedef LpSolverBase::Col Key;
9.242 - typedef LpSolverBase::Value Value;
9.243 -
9.244 - protected:
9.245 - typedef std::map<Col,Value> Base;
9.246 -
9.247 - Value const_comp;
9.248 - public:
9.249 - typedef True IsLinExpression;
9.250 - ///\e
9.251 - Expr() : Base(), const_comp(0) { }
9.252 - ///\e
9.253 - Expr(const Key &v) : const_comp(0) {
9.254 - Base::insert(std::make_pair(v, 1));
9.255 - }
9.256 - ///\e
9.257 - Expr(const Value &v) : const_comp(v) {}
9.258 - ///\e
9.259 - void set(const Key &v,const Value &c) {
9.260 - Base::insert(std::make_pair(v, c));
9.261 - }
9.262 - ///\e
9.263 - Value &constComp() { return const_comp; }
9.264 - ///\e
9.265 - const Value &constComp() const { return const_comp; }
9.266 -
9.267 - ///Removes the components with zero coefficient.
9.268 - void simplify() {
9.269 - for (Base::iterator i=Base::begin(); i!=Base::end();) {
9.270 - Base::iterator j=i;
9.271 - ++j;
9.272 - if ((*i).second==0) Base::erase(i);
9.273 - j=i;
9.274 - }
9.275 - }
9.276 -
9.277 - ///Sets all coefficients and the constant component to 0.
9.278 - void clear() {
9.279 - Base::clear();
9.280 - const_comp=0;
9.281 - }
9.282 -
9.283 - ///\e
9.284 - Expr &operator+=(const Expr &e) {
9.285 - for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
9.286 - (*this)[j->first]+=j->second;
9.287 - ///\todo it might be speeded up using "hints"
9.288 - const_comp+=e.const_comp;
9.289 - return *this;
9.290 - }
9.291 - ///\e
9.292 - Expr &operator-=(const Expr &e) {
9.293 - for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
9.294 - (*this)[j->first]-=j->second;
9.295 - const_comp-=e.const_comp;
9.296 - return *this;
9.297 - }
9.298 - ///\e
9.299 - Expr &operator*=(const Value &c) {
9.300 - for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
9.301 - j->second*=c;
9.302 - const_comp*=c;
9.303 - return *this;
9.304 - }
9.305 - ///\e
9.306 - Expr &operator/=(const Value &c) {
9.307 - for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
9.308 - j->second/=c;
9.309 - const_comp/=c;
9.310 - return *this;
9.311 - }
9.312 - };
9.313 -
9.314 - ///Linear constraint
9.315 - //typedef LinConstr<Expr> Constr;
9.316 - class Constr
9.317 - {
9.318 - public:
9.319 - typedef LpSolverBase::Expr Expr;
9.320 - typedef Expr::Key Key;
9.321 - typedef Expr::Value Value;
9.322 -
9.323 - static const Value INF;
9.324 - static const Value NaN;
9.325 - // static const Value INF=0;
9.326 - // static const Value NaN=1;
9.327 -
9.328 - protected:
9.329 - Expr _expr;
9.330 - Value _lb,_ub;
9.331 - public:
9.332 - ///\e
9.333 - Constr() : _expr(), _lb(NaN), _ub(NaN) {}
9.334 - ///\e
9.335 - Constr(Value lb,const Expr &e,Value ub) :
9.336 - _expr(e), _lb(lb), _ub(ub) {}
9.337 - ///\e
9.338 - Constr(const Expr &e,Value ub) :
9.339 - _expr(e), _lb(NaN), _ub(ub) {}
9.340 - ///\e
9.341 - Constr(Value lb,const Expr &e) :
9.342 - _expr(e), _lb(lb), _ub(NaN) {}
9.343 - ///\e
9.344 - Constr(const Expr &e) :
9.345 - _expr(e), _lb(NaN), _ub(NaN) {}
9.346 - ///\e
9.347 - void clear()
9.348 - {
9.349 - _expr.clear();
9.350 - _lb=_ub=NaN;
9.351 - }
9.352 - ///\e
9.353 - Expr &expr() { return _expr; }
9.354 - ///\e
9.355 - const Expr &expr() const { return _expr; }
9.356 - ///\e
9.357 - Value &lowerBound() { return _lb; }
9.358 - ///\e
9.359 - const Value &lowerBound() const { return _lb; }
9.360 - ///\e
9.361 - Value &upperBound() { return _ub; }
9.362 - ///\e
9.363 - const Value &upperBound() const { return _ub; }
9.364 - ///\e
9.365 - bool lowerBounded() const {
9.366 - using namespace std;
9.367 - return isfinite(_lb);
9.368 - }
9.369 - ///\e
9.370 - bool upperBounded() const {
9.371 - using namespace std;
9.372 - return isfinite(_ub);
9.373 - }
9.374 - };
9.375 -
9.376 -
9.377 - protected:
9.378 - _FixId rows;
9.379 - _FixId cols;
9.380 -
9.381 - virtual int _addCol() = 0;
9.382 - virtual int _addRow() = 0;
9.383 - virtual void _setRowCoeffs(int i,
9.384 - int length,
9.385 - int const * indices,
9.386 - Value const * values ) = 0;
9.387 - virtual void _setColCoeffs(int i,
9.388 - int length,
9.389 - int const * indices,
9.390 - Value const * values ) = 0;
9.391 - virtual void _setColLowerBound(int i, Value value) = 0;
9.392 - virtual void _setColUpperBound(int i, Value value) = 0;
9.393 - virtual void _setRowLowerBound(int i, Value value) = 0;
9.394 - virtual void _setRowUpperBound(int i, Value value) = 0;
9.395 - virtual void _setObjCoeff(int i, Value obj_coef) = 0;
9.396 - virtual SolveExitStatus _solve() = 0;
9.397 - virtual Value _getPrimal(int i) = 0;
9.398 - virtual SolutionStatus _getPrimalType() = 0;
9.399 -
9.400 -
9.401 - void clearObj() {}
9.402 - public:
9.403 -
9.404 -
9.405 - ///\e
9.406 - virtual ~LpSolverBase() {}
9.407 -
9.408 - ///\name Build up and modify of the LP
9.409 -
9.410 - ///@{
9.411 -
9.412 - ///Add a new empty column (i.e a new variable) to the LP
9.413 - Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
9.414 -
9.415 - ///\brief Adds several new columns
9.416 - ///(i.e a variables) at once
9.417 - ///
9.418 - ///This magic function takes a container as its argument
9.419 - ///and fills its elements
9.420 - ///with new columns (i.e. variables)
9.421 - ///\param t can be
9.422 - ///- a standard STL compatible iterable container with
9.423 - ///\ref Col as its \c values_type
9.424 - ///like
9.425 - ///\code
9.426 - ///std::vector<LpSolverBase::Col>
9.427 - ///std::list<LpSolverBase::Col>
9.428 - ///\endcode
9.429 - ///- a standard STL compatible iterable container with
9.430 - ///\ref Col as its \c mapped_type
9.431 - ///like
9.432 - ///\code
9.433 - ///std::map<AnyType,LpSolverBase::Col>
9.434 - ///\endcode
9.435 - ///- an iterable lemon \ref concept::WriteMap "write map" like
9.436 - ///\code
9.437 - ///ListGraph::NodeMap<LpSolverBase::Col>
9.438 - ///ListGraph::EdgeMap<LpSolverBase::Col>
9.439 - ///\endcode
9.440 - ///\return The number of the created column.
9.441 - ///\bug Iterable nodemap hasn't been implemented yet.
9.442 -#ifdef DOXYGEN
9.443 - template<class T>
9.444 - int addColSet(T &t) { return 0;}
9.445 -#else
9.446 - template<class T>
9.447 - typename enable_if<typename T::value_type::LpSolverCol,int>::type
9.448 - addColSet(T &t,dummy<0> = 0) {
9.449 - int s=0;
9.450 - for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
9.451 - return s;
9.452 - }
9.453 - template<class T>
9.454 - typename enable_if<typename T::value_type::second_type::LpSolverCol,
9.455 - int>::type
9.456 - addColSet(T &t,dummy<1> = 1) {
9.457 - int s=0;
9.458 - for(typename T::iterator i=t.begin();i!=t.end();++i) {
9.459 - i->second=addCol();
9.460 - s++;
9.461 - }
9.462 - return s;
9.463 - }
9.464 - template<class T>
9.465 - typename enable_if<typename T::ValueSet::value_type::LpSolverCol,
9.466 - int>::type
9.467 - addColSet(T &t,dummy<2> = 2) {
9.468 - ///\bug <tt>return addColSet(t.valueSet());</tt> should also work.
9.469 - int s=0;
9.470 - for(typename T::ValueSet::iterator i=t.valueSet().begin();
9.471 - i!=t.valueSet().end();
9.472 - ++i)
9.473 - {
9.474 - *i=addCol();
9.475 - s++;
9.476 - }
9.477 - return s;
9.478 - }
9.479 -#endif
9.480 -
9.481 - ///Add a new empty row (i.e a new constaint) to the LP
9.482 -
9.483 - ///This function adds a new empty row (i.e a new constaint) to the LP.
9.484 - ///\return The created row
9.485 - Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
9.486 -
9.487 - ///Set a row (i.e a constaint) of the LP
9.488 -
9.489 - ///\param r is the row to be modified
9.490 - ///\param l is lower bound (-\ref INF means no bound)
9.491 - ///\param e is a linear expression (see \ref Expr)
9.492 - ///\param u is the upper bound (\ref INF means no bound)
9.493 - ///\bug This is a temportary function. The interface will change to
9.494 - ///a better one.
9.495 - void setRow(Row r, Value l,const Expr &e, Value u) {
9.496 - std::vector<int> indices;
9.497 - std::vector<Value> values;
9.498 - indices.push_back(0);
9.499 - values.push_back(0);
9.500 - for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
9.501 - if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
9.502 - indices.push_back(cols.floatingId((*i).first.id));
9.503 - values.push_back((*i).second);
9.504 - }
9.505 - _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
9.506 - &indices[0],&values[0]);
9.507 - _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
9.508 - _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
9.509 - }
9.510 -
9.511 - ///Set a row (i.e a constaint) of the LP
9.512 -
9.513 - ///\param r is the row to be modified
9.514 - ///\param c is a linear expression (see \ref Constr)
9.515 - void setRow(Row r, const Constr &c) {
9.516 - setRow(r,
9.517 - c.lowerBounded()?c.lowerBound():-INF,
9.518 - c.expr(),
9.519 - c.upperBounded()?c.upperBound():INF);
9.520 - }
9.521 -
9.522 - ///Add a new row (i.e a new constaint) to the LP
9.523 -
9.524 - ///\param l is the lower bound (-\ref INF means no bound)
9.525 - ///\param e is a linear expression (see \ref Expr)
9.526 - ///\param u is the upper bound (\ref INF means no bound)
9.527 - ///\return The created row.
9.528 - ///\bug This is a temportary function. The interface will change to
9.529 - ///a better one.
9.530 - Row addRow(Value l,const Expr &e, Value u) {
9.531 - Row r=addRow();
9.532 - setRow(r,l,e,u);
9.533 - return r;
9.534 - }
9.535 -
9.536 - ///Add a new row (i.e a new constaint) to the LP
9.537 -
9.538 - ///\param c is a linear expression (see \ref Constr)
9.539 - ///\return The created row.
9.540 - Row addRow(const Constr &c) {
9.541 - Row r=addRow();
9.542 - setRow(r,c);
9.543 - return r;
9.544 - }
9.545 -
9.546 - /// Set the lower bound of a column (i.e a variable)
9.547 -
9.548 - /// The upper bound of a variable (column) has to be given by an
9.549 - /// extended number of type Value, i.e. a finite number of type
9.550 - /// Value or -\ref INF.
9.551 - void colLowerBound(Col c, Value value) {
9.552 - _setColLowerBound(cols.floatingId(c.id),value);
9.553 - }
9.554 - /// Set the upper bound of a column (i.e a variable)
9.555 -
9.556 - /// The upper bound of a variable (column) has to be given by an
9.557 - /// extended number of type Value, i.e. a finite number of type
9.558 - /// Value or \ref INF.
9.559 - void colUpperBound(Col c, Value value) {
9.560 - _setColUpperBound(cols.floatingId(c.id),value);
9.561 - };
9.562 - /// Set the lower and the upper bounds of a column (i.e a variable)
9.563 -
9.564 - /// The lower and the upper bounds of
9.565 - /// a variable (column) have to be given by an
9.566 - /// extended number of type Value, i.e. a finite number of type
9.567 - /// Value, -\ref INF or \ref INF.
9.568 - void colBounds(Col c, Value lower, Value upper) {
9.569 - _setColLowerBound(cols.floatingId(c.id),lower);
9.570 - _setColUpperBound(cols.floatingId(c.id),upper);
9.571 - }
9.572 -
9.573 - /// Set the lower bound of a row (i.e a constraint)
9.574 -
9.575 - /// The lower bound of a linear expression (row) has to be given by an
9.576 - /// extended number of type Value, i.e. a finite number of type
9.577 - /// Value or -\ref INF.
9.578 - void rowLowerBound(Row r, Value value) {
9.579 - _setRowLowerBound(rows.floatingId(r.id),value);
9.580 - };
9.581 - /// Set the upper bound of a row (i.e a constraint)
9.582 -
9.583 - /// The upper bound of a linear expression (row) has to be given by an
9.584 - /// extended number of type Value, i.e. a finite number of type
9.585 - /// Value or \ref INF.
9.586 - void rowUpperBound(Row r, Value value) {
9.587 - _setRowUpperBound(rows.floatingId(r.id),value);
9.588 - };
9.589 - /// Set the lower and the upper bounds of a row (i.e a variable)
9.590 -
9.591 - /// The lower and the upper bounds of
9.592 - /// a constraint (row) have to be given by an
9.593 - /// extended number of type Value, i.e. a finite number of type
9.594 - /// Value, -\ref INF or \ref INF.
9.595 - void rowBounds(Row c, Value lower, Value upper) {
9.596 - _setRowLowerBound(rows.floatingId(c.id),lower);
9.597 - _setRowUpperBound(rows.floatingId(c.id),upper);
9.598 - }
9.599 -
9.600 - ///Set an element of the objective function
9.601 - void objCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
9.602 - ///Set the objective function
9.603 -
9.604 - ///\param e is a linear expression of type \ref Expr.
9.605 - ///\todo What to do with the constant component?
9.606 - void setObj(Expr e) {
9.607 - clearObj();
9.608 - for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
9.609 - objCoeff((*i).first,(*i).second);
9.610 - }
9.611 -
9.612 - ///@}
9.613 -
9.614 -
9.615 - ///\name Solve the LP
9.616 -
9.617 - ///@{
9.618 -
9.619 - ///\e
9.620 - SolveExitStatus solve() { return _solve(); }
9.621 -
9.622 - ///@}
9.623 -
9.624 - ///\name Obtain the solution
9.625 -
9.626 - ///@{
9.627 -
9.628 - ///\e
9.629 - SolutionStatus primalType() {
9.630 - return _getPrimalType();
9.631 - }
9.632 -
9.633 - ///\e
9.634 - Value primal(Col c) { return _getPrimal(cols.floatingId(c.id)); }
9.635 -
9.636 - ///@}
9.637 -
9.638 - };
9.639 -
9.640 - ///\e
9.641 -
9.642 - ///\relates LpSolverBase::Expr
9.643 - ///
9.644 - inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
9.645 - const LpSolverBase::Expr &b)
9.646 - {
9.647 - LpSolverBase::Expr tmp(a);
9.648 - tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
9.649 - return tmp;
9.650 - }
9.651 - ///\e
9.652 -
9.653 - ///\relates LpSolverBase::Expr
9.654 - ///
9.655 - inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
9.656 - const LpSolverBase::Expr &b)
9.657 - {
9.658 - LpSolverBase::Expr tmp(a);
9.659 - tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
9.660 - return tmp;
9.661 - }
9.662 - ///\e
9.663 -
9.664 - ///\relates LpSolverBase::Expr
9.665 - ///
9.666 - inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
9.667 - const LpSolverBase::Value &b)
9.668 - {
9.669 - LpSolverBase::Expr tmp(a);
9.670 - tmp*=b; ///\todo Don't STL have some special 'merge' algorithm?
9.671 - return tmp;
9.672 - }
9.673 -
9.674 - ///\e
9.675 -
9.676 - ///\relates LpSolverBase::Expr
9.677 - ///
9.678 - inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
9.679 - const LpSolverBase::Expr &b)
9.680 - {
9.681 - LpSolverBase::Expr tmp(b);
9.682 - tmp*=a; ///\todo Don't STL have some special 'merge' algorithm?
9.683 - return tmp;
9.684 - }
9.685 - ///\e
9.686 -
9.687 - ///\relates LpSolverBase::Expr
9.688 - ///
9.689 - inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
9.690 - const LpSolverBase::Value &b)
9.691 - {
9.692 - LpSolverBase::Expr tmp(a);
9.693 - tmp/=b; ///\todo Don't STL have some special 'merge' algorithm?
9.694 - return tmp;
9.695 - }
9.696 -
9.697 - ///\e
9.698 -
9.699 - ///\relates LpSolverBase::Constr
9.700 - ///
9.701 - inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
9.702 - const LpSolverBase::Expr &f)
9.703 - {
9.704 - return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
9.705 - }
9.706 -
9.707 - ///\e
9.708 -
9.709 - ///\relates LpSolverBase::Constr
9.710 - ///
9.711 - inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
9.712 - const LpSolverBase::Expr &f)
9.713 - {
9.714 - return LpSolverBase::Constr(e,f);
9.715 - }
9.716 -
9.717 - ///\e
9.718 -
9.719 - ///\relates LpSolverBase::Constr
9.720 - ///
9.721 - inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
9.722 - const LpSolverBase::Value &f)
9.723 - {
9.724 - return LpSolverBase::Constr(e,f);
9.725 - }
9.726 -
9.727 - ///\e
9.728 -
9.729 - ///\relates LpSolverBase::Constr
9.730 - ///
9.731 - inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
9.732 - const LpSolverBase::Expr &f)
9.733 - {
9.734 - return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
9.735 - }
9.736 -
9.737 -
9.738 - ///\e
9.739 -
9.740 - ///\relates LpSolverBase::Constr
9.741 - ///
9.742 - inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
9.743 - const LpSolverBase::Expr &f)
9.744 - {
9.745 - return LpSolverBase::Constr(f,e);
9.746 - }
9.747 -
9.748 -
9.749 - ///\e
9.750 -
9.751 - ///\relates LpSolverBase::Constr
9.752 - ///
9.753 - inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
9.754 - const LpSolverBase::Value &f)
9.755 - {
9.756 - return LpSolverBase::Constr(f,e);
9.757 - }
9.758 -
9.759 - ///\e
9.760 -
9.761 - ///\relates LpSolverBase::Constr
9.762 - ///
9.763 - inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
9.764 - const LpSolverBase::Expr &f)
9.765 - {
9.766 - return LpSolverBase::Constr(0,e-f,0);
9.767 - }
9.768 -
9.769 - ///\e
9.770 -
9.771 - ///\relates LpSolverBase::Constr
9.772 - ///
9.773 - inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
9.774 - const LpSolverBase::Constr&c)
9.775 - {
9.776 - LpSolverBase::Constr tmp(c);
9.777 - ///\todo Create an own exception type.
9.778 - if(!isnan(tmp.lowerBound())) throw LogicError();
9.779 - else tmp.lowerBound()=n;
9.780 - return tmp;
9.781 - }
9.782 - ///\e
9.783 -
9.784 - ///\relates LpSolverBase::Constr
9.785 - ///
9.786 - inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
9.787 - const LpSolverBase::Value &n)
9.788 - {
9.789 - LpSolverBase::Constr tmp(c);
9.790 - ///\todo Create an own exception type.
9.791 - if(!isnan(tmp.upperBound())) throw LogicError();
9.792 - else tmp.upperBound()=n;
9.793 - return tmp;
9.794 - }
9.795 -
9.796 - ///\e
9.797 -
9.798 - ///\relates LpSolverBase::Constr
9.799 - ///
9.800 - inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
9.801 - const LpSolverBase::Constr&c)
9.802 - {
9.803 - LpSolverBase::Constr tmp(c);
9.804 - ///\todo Create an own exception type.
9.805 - if(!isnan(tmp.upperBound())) throw LogicError();
9.806 - else tmp.upperBound()=n;
9.807 - return tmp;
9.808 - }
9.809 - ///\e
9.810 -
9.811 - ///\relates LpSolverBase::Constr
9.812 - ///
9.813 - inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
9.814 - const LpSolverBase::Value &n)
9.815 - {
9.816 - LpSolverBase::Constr tmp(c);
9.817 - ///\todo Create an own exception type.
9.818 - if(!isnan(tmp.lowerBound())) throw LogicError();
9.819 - else tmp.lowerBound()=n;
9.820 - return tmp;
9.821 - }
9.822 -
9.823 -
9.824 -} //namespace lemon
9.825 -
9.826 -#endif //LEMON_LP_BASE_H
10.1 --- a/src/work/athos/lp/lp_glpk.cc Tue Apr 05 08:43:51 2005 +0000
10.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
10.3 @@ -1,288 +0,0 @@
10.4 -/* -*- C++ -*-
10.5 - * src/lemon/lp_glpk.cc - Part of LEMON, a generic C++ optimization library
10.6 - *
10.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
10.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
10.9 - *
10.10 - * Permission to use, modify and distribute this software is granted
10.11 - * provided that this copyright notice appears in all copies. For
10.12 - * precise terms see the accompanying LICENSE file.
10.13 - *
10.14 - * This software is provided "AS IS" with no warranty of any kind,
10.15 - * express or implied, and with no claim as to its suitability for any
10.16 - * purpose.
10.17 - *
10.18 - */
10.19 -
10.20 -#ifndef LEMON_LP_GLPK_CC
10.21 -#define LEMON_LP_GLPK_CC
10.22 -
10.23 -///\file
10.24 -///\brief Implementation of the LEMON-GLPK lp solver interface.
10.25 -
10.26 -#include "lp_glpk.h"
10.27 -
10.28 -namespace lemon {
10.29 -
10.30 - /// \e
10.31 - int LpGlpk::_addCol() {
10.32 - int i=lpx_add_cols(lp, 1);
10.33 - _setColLowerBound(i, -INF);
10.34 - _setColUpperBound(i, INF);
10.35 - return i;
10.36 - }
10.37 -
10.38 - /// \e
10.39 - int LpGlpk::_addRow() {
10.40 - int i=lpx_add_rows(lp, 1);
10.41 - return i;
10.42 - }
10.43 -
10.44 -
10.45 - void LpGlpk::_setRowCoeffs(int i,
10.46 - int length,
10.47 - const int * indices,
10.48 - const Value * values )
10.49 - {
10.50 - lpx_set_mat_row(lp, i, length,
10.51 - const_cast<int * >(indices) ,
10.52 - const_cast<Value * >(values));
10.53 - }
10.54 -
10.55 - void LpGlpk::_setColCoeffs(int i,
10.56 - int length,
10.57 - const int * indices,
10.58 - const Value * values)
10.59 - {
10.60 - lpx_set_mat_col(lp, i, length,
10.61 - const_cast<int * >(indices),
10.62 - const_cast<Value * >(values));
10.63 - }
10.64 -
10.65 - void LpGlpk::_setColLowerBound(int i, Value lo)
10.66 - {
10.67 - if (lo==INF) {
10.68 - //FIXME error
10.69 - }
10.70 - int b=lpx_get_col_type(lp, i);
10.71 - double up=lpx_get_col_ub(lp, i);
10.72 - if (lo==-INF) {
10.73 - switch (b) {
10.74 - case LPX_FR:
10.75 - case LPX_LO:
10.76 - lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
10.77 - break;
10.78 - case LPX_UP:
10.79 - break;
10.80 - case LPX_DB:
10.81 - case LPX_FX:
10.82 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
10.83 - break;
10.84 - default: ;
10.85 - //FIXME error
10.86 - }
10.87 - } else {
10.88 - switch (b) {
10.89 - case LPX_FR:
10.90 - case LPX_LO:
10.91 - lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
10.92 - break;
10.93 - case LPX_UP:
10.94 - case LPX_DB:
10.95 - case LPX_FX:
10.96 - if (lo==up)
10.97 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
10.98 - else
10.99 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
10.100 - break;
10.101 - default: ;
10.102 - //FIXME error
10.103 - }
10.104 - }
10.105 -
10.106 - }
10.107 -
10.108 - void LpGlpk::_setColUpperBound(int i, Value up)
10.109 - {
10.110 - if (up==-INF) {
10.111 - //FIXME error
10.112 - }
10.113 - int b=lpx_get_col_type(lp, i);
10.114 - double lo=lpx_get_col_lb(lp, i);
10.115 - if (up==INF) {
10.116 - switch (b) {
10.117 - case LPX_FR:
10.118 - case LPX_LO:
10.119 - break;
10.120 - case LPX_UP:
10.121 - lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
10.122 - break;
10.123 - case LPX_DB:
10.124 - case LPX_FX:
10.125 - lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
10.126 - break;
10.127 - default: ;
10.128 - //FIXME error
10.129 - }
10.130 - } else {
10.131 - switch (b) {
10.132 - case LPX_FR:
10.133 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
10.134 - break;
10.135 - case LPX_UP:
10.136 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
10.137 - break;
10.138 - case LPX_LO:
10.139 - case LPX_DB:
10.140 - case LPX_FX:
10.141 - if (lo==up)
10.142 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
10.143 - else
10.144 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
10.145 - break;
10.146 - default: ;
10.147 - //FIXME error
10.148 - }
10.149 - }
10.150 - }
10.151 -
10.152 - void LpGlpk::_setRowLowerBound(int i, Value lo)
10.153 - {
10.154 - if (lo==INF) {
10.155 - //FIXME error
10.156 - }
10.157 - int b=lpx_get_row_type(lp, i);
10.158 - double up=lpx_get_row_ub(lp, i);
10.159 - if (lo==-INF) {
10.160 - switch (b) {
10.161 - case LPX_FR:
10.162 - case LPX_LO:
10.163 - lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
10.164 - break;
10.165 - case LPX_UP:
10.166 - break;
10.167 - case LPX_DB:
10.168 - case LPX_FX:
10.169 - lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
10.170 - break;
10.171 - default: ;
10.172 - //FIXME error
10.173 - }
10.174 - } else {
10.175 - switch (b) {
10.176 - case LPX_FR:
10.177 - case LPX_LO:
10.178 - lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
10.179 - break;
10.180 - case LPX_UP:
10.181 - case LPX_DB:
10.182 - case LPX_FX:
10.183 - if (lo==up)
10.184 - lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
10.185 - else
10.186 - lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
10.187 - break;
10.188 - default: ;
10.189 - //FIXME error
10.190 - }
10.191 - }
10.192 - }
10.193 -
10.194 - void LpGlpk::_setRowUpperBound(int i, Value up)
10.195 - {
10.196 - if (up==-INF) {
10.197 - //FIXME error
10.198 - }
10.199 - int b=lpx_get_row_type(lp, i);
10.200 - double lo=lpx_get_row_lb(lp, i);
10.201 - if (up==INF) {
10.202 - switch (b) {
10.203 - case LPX_FR:
10.204 - case LPX_LO:
10.205 - break;
10.206 - case LPX_UP:
10.207 - lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
10.208 - break;
10.209 - case LPX_DB:
10.210 - case LPX_FX:
10.211 - lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
10.212 - break;
10.213 - default: ;
10.214 - //FIXME error
10.215 - }
10.216 - } else {
10.217 - switch (b) {
10.218 - case LPX_FR:
10.219 - lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
10.220 - break;
10.221 - case LPX_UP:
10.222 - lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
10.223 - break;
10.224 - case LPX_LO:
10.225 - case LPX_DB:
10.226 - case LPX_FX:
10.227 - if (lo==up)
10.228 - lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
10.229 - else
10.230 - lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
10.231 - break;
10.232 - default: ;
10.233 - //FIXME error
10.234 - }
10.235 - }
10.236 - }
10.237 -
10.238 - void LpGlpk::_setObjCoeff(int i, Value obj_coef)
10.239 - {
10.240 - lpx_set_obj_coef(lp, i, obj_coef);
10.241 - }
10.242 -
10.243 -
10.244 - LpGlpk::SolveExitStatus LpGlpk::_solve()
10.245 - {
10.246 - int i= lpx_simplex(lp);
10.247 - switch (i) {
10.248 - case LPX_E_OK:
10.249 - return SOLVED;
10.250 - break;
10.251 - default:
10.252 - return UNSOLVED;
10.253 - }
10.254 - }
10.255 -
10.256 - LpGlpk::Value LpGlpk::_getPrimal(int i)
10.257 - {
10.258 - return lpx_get_col_prim(lp,i);
10.259 - }
10.260 -
10.261 -
10.262 - LpGlpk::SolutionStatus LpGlpk::_getPrimalType()
10.263 - {
10.264 - int stat= lpx_get_status(lp);
10.265 - switch (stat) {
10.266 - case LPX_UNDEF://Undefined (no solve has been run yet)
10.267 - return UNDEFINED;
10.268 - break;
10.269 - case LPX_NOFEAS://There is no feasible solution (primal, I guess)
10.270 - case LPX_INFEAS://Infeasible
10.271 - return INFEASIBLE;
10.272 - break;
10.273 - case LPX_UNBND://Unbounded
10.274 - return INFINITE;
10.275 - break;
10.276 - case LPX_FEAS://Feasible
10.277 - return FEASIBLE;
10.278 - break;
10.279 - case LPX_OPT://Feasible
10.280 - return OPTIMAL;
10.281 - break;
10.282 - default:
10.283 - return UNDEFINED; //to avoid gcc warning
10.284 - //FIXME error
10.285 - }
10.286 - }
10.287 -
10.288 -
10.289 -} //END OF NAMESPACE LEMON
10.290 -
10.291 -#endif //LEMON_LP_GLPK_CC
11.1 --- a/src/work/athos/lp/lp_glpk.h Tue Apr 05 08:43:51 2005 +0000
11.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
11.3 @@ -1,89 +0,0 @@
11.4 -/* -*- C++ -*-
11.5 - * src/lemon/lp_glpk.h - Part of LEMON, a generic C++ optimization library
11.6 - *
11.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
11.8 - * (Egervary Combinatorial Optimization Research Group, EGRES).
11.9 - *
11.10 - * Permission to use, modify and distribute this software is granted
11.11 - * provided that this copyright notice appears in all copies. For
11.12 - * precise terms see the accompanying LICENSE file.
11.13 - *
11.14 - * This software is provided "AS IS" with no warranty of any kind,
11.15 - * express or implied, and with no claim as to its suitability for any
11.16 - * purpose.
11.17 - *
11.18 - */
11.19 -
11.20 -#ifndef LEMON_LP_GLPK_H
11.21 -#define LEMON_LP_GLPK_H
11.22 -
11.23 -///\file
11.24 -///\brief Header of the LEMON-GLPK lp solver interface.
11.25 -
11.26 -#include "lp_base.h"
11.27 -extern "C" {
11.28 -#include "glpk.h"
11.29 -}
11.30 -
11.31 -namespace lemon {
11.32 -
11.33 -
11.34 - /// \brief Wrapper for GLPK solver
11.35 - ///
11.36 - /// This class implements a lemon wrapper for GLPK.
11.37 - class LpGlpk : public LpSolverBase {
11.38 -
11.39 - public:
11.40 -
11.41 - typedef LpSolverBase Parent;
11.42 -
11.43 - /// \e
11.44 - LPX* lp;
11.45 -
11.46 - /// \e
11.47 - LpGlpk() : Parent(),
11.48 - lp(lpx_create_prob()) {
11.49 - lpx_set_int_parm(lp, LPX_K_DUAL, 1);
11.50 - }
11.51 - /// \e
11.52 - ~LpGlpk() {
11.53 - lpx_delete_prob(lp);
11.54 - }
11.55 -
11.56 - protected:
11.57 - virtual int _addCol();
11.58 - virtual int _addRow();
11.59 - virtual void _setRowCoeffs(int i,
11.60 - int length,
11.61 - const int * indices,
11.62 - const Value * values );
11.63 - virtual void _setColCoeffs(int i,
11.64 - int length,
11.65 - const int * indices,
11.66 - const Value * values);
11.67 - virtual void _setColLowerBound(int i, Value value);
11.68 - virtual void _setColUpperBound(int i, Value value);
11.69 - virtual void _setRowLowerBound(int i, Value value);
11.70 - virtual void _setRowUpperBound(int i, Value value);
11.71 - virtual void _setObjCoeff(int i, Value obj_coef);
11.72 - ///\e
11.73 -
11.74 - ///\bug Unimplemented
11.75 - ///
11.76 - virtual SolveExitStatus _solve();
11.77 - ///\e
11.78 -
11.79 - ///\bug Unimplemented
11.80 - ///
11.81 - virtual Value _getPrimal(int i);
11.82 - ///\e
11.83 -
11.84 - ///\bug Unimplemented
11.85 - ///
11.86 - virtual SolutionStatus _getPrimalType();
11.87 -
11.88 - };
11.89 -} //END OF NAMESPACE LEMON
11.90 -
11.91 -#endif //LEMON_LP_GLPK_H
11.92 -
12.1 --- a/src/work/athos/lp/lp_solver_skeleton.cc Tue Apr 05 08:43:51 2005 +0000
12.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
12.3 @@ -1,84 +0,0 @@
12.4 -/* -*- C++ -*-
12.5 - * src/lemon/lp_solver_skeleton.cc
12.6 - * - Part of LEMON, a generic C++ optimization library
12.7 - *
12.8 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
12.9 - * (Egervary Combinatorial Optimization Research Group, EGRES).
12.10 - *
12.11 - * Permission to use, modify and distribute this software is granted
12.12 - * provided that this copyright notice appears in all copies. For
12.13 - * precise terms see the accompanying LICENSE file.
12.14 - *
12.15 - * This software is provided "AS IS" with no warranty of any kind,
12.16 - * express or implied, and with no claim as to its suitability for any
12.17 - * purpose.
12.18 - *
12.19 - */
12.20 -
12.21 -#include"lp_solver_skeleton.h"
12.22 -
12.23 -///\file
12.24 -///\brief A skeleton file to implement LP solver interfaces
12.25 -namespace lemon {
12.26 -
12.27 - int LpSolverSkeleton::_addCol()
12.28 - {
12.29 - return ++col_num;
12.30 - }
12.31 -
12.32 - int LpSolverSkeleton::_addRow()
12.33 - {
12.34 - return ++row_num;
12.35 - }
12.36 -
12.37 - void LpSolverSkeleton::_setRowCoeffs(int i,
12.38 - int length,
12.39 - int const * indices,
12.40 - Value const * values )
12.41 - {
12.42 - }
12.43 -
12.44 - void LpSolverSkeleton::_setColCoeffs(int i,
12.45 - int length,
12.46 - int const * indices,
12.47 - Value const * values)
12.48 - {
12.49 - }
12.50 -
12.51 - void LpSolverSkeleton::_setColLowerBound(int i, Value value)
12.52 - {
12.53 - }
12.54 -
12.55 - void LpSolverSkeleton::_setColUpperBound(int i, Value value)
12.56 - {
12.57 - }
12.58 -
12.59 - void LpSolverSkeleton::_setRowLowerBound(int i, Value value)
12.60 - {
12.61 - }
12.62 -
12.63 - void LpSolverSkeleton::_setRowUpperBound(int i, Value value)
12.64 - {
12.65 - }
12.66 -
12.67 - void LpSolverSkeleton::_setObjCoeff(int i, Value obj_coef)
12.68 - {
12.69 - }
12.70 -
12.71 - LpSolverSkeleton::SolveExitStatus LpSolverSkeleton::_solve()
12.72 - {
12.73 - return SOLVED;
12.74 - }
12.75 -
12.76 - LpSolverSkeleton::Value LpSolverSkeleton::_getPrimal(int i)
12.77 - {
12.78 - return 0;
12.79 - }
12.80 -
12.81 - LpSolverSkeleton::SolutionStatus LpSolverSkeleton::_getPrimalType()
12.82 - {
12.83 - return OPTIMAL;
12.84 - }
12.85 -
12.86 -} //namespace lemon
12.87 -
13.1 --- a/src/work/athos/lp/lp_solver_skeleton.h Tue Apr 05 08:43:51 2005 +0000
13.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
13.3 @@ -1,104 +0,0 @@
13.4 -/* -*- C++ -*-
13.5 - * src/lemon/lp_solver_skeleton.h
13.6 - * - Part of LEMON, a generic C++ optimization library
13.7 - *
13.8 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
13.9 - * (Egervary Combinatorial Optimization Research Group, EGRES).
13.10 - *
13.11 - * Permission to use, modify and distribute this software is granted
13.12 - * provided that this copyright notice appears in all copies. For
13.13 - * precise terms see the accompanying LICENSE file.
13.14 - *
13.15 - * This software is provided "AS IS" with no warranty of any kind,
13.16 - * express or implied, and with no claim as to its suitability for any
13.17 - * purpose.
13.18 - *
13.19 - */
13.20 -
13.21 -#ifndef LEMON_LP_SOLVER_SKELETON
13.22 -#define LEMON_LP_SOLVER_SKELETON
13.23 -
13.24 -#include"lp_base.h"
13.25 -
13.26 -///\file
13.27 -///\brief A skeleton file to implement LP solver interfaces
13.28 -namespace lemon {
13.29 -
13.30 - ///A skeleton class to implement LP solver interfaces
13.31 - class LpSolverSkeleton :public LpSolverBase {
13.32 - int col_num,row_num;
13.33 -
13.34 - protected:
13.35 - /// \e
13.36 - virtual int _addCol();
13.37 - /// \e
13.38 - virtual int _addRow();
13.39 - /// \e
13.40 -
13.41 - /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
13.42 - ///
13.43 - virtual void _setRowCoeffs(int i,
13.44 - int length,
13.45 - int const * indices,
13.46 - Value const * values );
13.47 - /// \e
13.48 -
13.49 - /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
13.50 - ///
13.51 - virtual void _setColCoeffs(int i,
13.52 - int length,
13.53 - int const * indices,
13.54 - Value const * values );
13.55 -
13.56 - /// \e
13.57 -
13.58 - /// The lower bound of a variable (column) have to be given by an
13.59 - /// extended number of type Value, i.e. a finite number of type
13.60 - /// Value or -\ref INF.
13.61 - virtual void _setColLowerBound(int i, Value value);
13.62 - /// \e
13.63 -
13.64 - /// The upper bound of a variable (column) have to be given by an
13.65 - /// extended number of type Value, i.e. a finite number of type
13.66 - /// Value or \ref INF.
13.67 - virtual void _setColUpperBound(int i, Value value);
13.68 - /// \e
13.69 -
13.70 - /// The lower bound of a linear expression (row) have to be given by an
13.71 - /// extended number of type Value, i.e. a finite number of type
13.72 - /// Value or -\ref INF.
13.73 - virtual void _setRowLowerBound(int i, Value value);
13.74 - /// \e
13.75 -
13.76 - /// The upper bound of a linear expression (row) have to be given by an
13.77 - /// extended number of type Value, i.e. a finite number of type
13.78 - /// Value or \ref INF.
13.79 - virtual void _setRowUpperBound(int i, Value value);
13.80 -
13.81 - /// \e
13.82 - virtual void _setObjCoeff(int i, Value obj_coef);
13.83 -
13.84 - ///\e
13.85 -
13.86 - ///\bug Wrong interface
13.87 - ///
13.88 - virtual SolveExitStatus _solve();
13.89 -
13.90 - ///\e
13.91 -
13.92 - ///\bug Wrong interface
13.93 - ///
13.94 - virtual Value _getPrimal(int i);
13.95 - ///\e
13.96 -
13.97 - ///\bug Wrong interface
13.98 - ///
13.99 - virtual SolutionStatus _getPrimalType();
13.100 -
13.101 - public:
13.102 - LpSolverSkeleton() : LpSolverBase(), col_num(0), row_num(0) {}
13.103 - };
13.104 -
13.105 -} //namespace lemon
13.106 -
13.107 -#endif // LEMON_LP_SOLVER_SKELETON