COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_base.h @ 2345:bfcaad2b84e8

Last change on this file since 2345:bfcaad2b84e8 was 2345:bfcaad2b84e8, checked in by athos, 17 years ago

One important thing only: equality-type constraint can now be added to an lp. The prettyPrint functions are not too pretty yet, I accept.

File size: 45.5 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_LP_BASE_H
20#define LEMON_LP_BASE_H
21
22#include<iostream>
23
24
25#include<vector>
26#include<map>
27#include<limits>
28#include<cmath>
29
30#include<lemon/bits/utility.h>
31#include<lemon/error.h>
32#include<lemon/bits/invalid.h>
33
34///\file
35///\brief The interface of the LP solver interface.
36///\ingroup gen_opt_group
37namespace lemon {
38
39
40  ///Internal data structure to convert floating id's to fix one's
41   
42  ///\todo This might be implemented to be also usable in other places.
43  class _FixId
44  {
45  protected:
46    int _first_index;
47    int first_free;
48  public:
49    std::vector<int> index;
50    std::vector<int> cross;
51    _FixId() : _first_index(-1), first_free(-1) {};
52    ///Convert a floating id to a fix one
53
54    ///\param n is a floating id
55    ///\return the corresponding fix id
56    int fixId(int n) const {return cross[n];}
57    ///Convert a fix id to a floating one
58
59    ///\param n is a fix id
60    ///\return the corresponding floating id
61    int floatingId(int n) const { return index[n];}
62    ///Add a new floating id.
63
64    ///\param n is a floating id
65    ///\return the fix id of the new value
66    ///\todo Multiple additions should also be handled.
67    int insert(int n)
68    {
69      if(cross.empty()) _first_index=n;
70      if(n>=int(cross.size())) {
71        cross.resize(n+1);
72        if(first_free==-1) {
73          cross[n]=index.size();
74          index.push_back(n);
75        }
76        else {
77          cross[n]=first_free;
78          int next=index[first_free];
79          index[first_free]=n;
80          first_free=next;
81        }
82        return cross[n];
83      }
84      else {
85        ///\todo Create an own exception type.
86        throw LogicError(); //floatingId-s must form a continuous range;
87      }
88    }
89    ///Remove a fix id.
90
91    ///\param n is a fix id
92    ///
93    void erase(int n)
94    {
95      int fl=index[n];
96      index[n]=first_free;
97      first_free=n;
98      for(int i=fl+1;i<int(cross.size());++i) {
99        cross[i-1]=cross[i];
100        index[cross[i]]--;
101      }
102      cross.pop_back();
103    }
104    ///An upper bound on the largest fix id.
105
106    ///\todo Do we need this?
107    ///
108    std::size_t maxFixId() { return cross.size()-1; }
109 
110    ///Returns the first (smallest) inserted index
111
112    ///Returns the first (smallest) inserted index
113    ///or -1 if no index has been inserted before.
114    int firstIndex() {return _first_index;}
115  };
116
117  ///Common base class for LP solvers
118 
119  ///\todo Much more docs
120  ///\ingroup gen_opt_group
121  class LpSolverBase {
122
123  protected:
124    _FixId rows;
125    _FixId cols;
126
127  public:
128
129    ///Possible outcomes of an LP solving procedure
130    enum SolveExitStatus {
131      ///This means that the problem has been successfully solved: either
132      ///an optimal solution has been found or infeasibility/unboundedness
133      ///has been proved.
134      SOLVED = 0,
135      ///Any other case (including the case when some user specified
136      ///limit has been exceeded)
137      UNSOLVED = 1
138    };
139     
140      ///\e
141    enum SolutionStatus {
142      ///Feasible solution hasn't been found (but may exist).
143
144      ///\todo NOTFOUND might be a better name.
145      ///
146      UNDEFINED = 0,
147      ///The problem has no feasible solution
148      INFEASIBLE = 1,
149      ///Feasible solution found
150      FEASIBLE = 2,
151      ///Optimal solution exists and found
152      OPTIMAL = 3,
153      ///The cost function is unbounded
154
155      ///\todo Give a feasible solution and an infinite ray (and the
156      ///corresponding bases)
157      INFINITE = 4
158    };
159
160    ///\e The type of the investigated LP problem
161    enum ProblemTypes {
162      ///Primal-dual feasible
163      PRIMAL_DUAL_FEASIBLE = 0,
164      ///Primal feasible dual infeasible
165      PRIMAL_FEASIBLE_DUAL_INFEASIBLE = 1,
166      ///Primal infeasible dual feasible
167      PRIMAL_INFEASIBLE_DUAL_FEASIBLE = 2,
168      ///Primal-dual infeasible
169      PRIMAL_DUAL_INFEASIBLE = 3,
170      ///Could not determine so far
171      UNKNOWN = 4
172    };
173
174    ///The floating point type used by the solver
175    typedef double Value;
176    ///The infinity constant
177    static const Value INF;
178    ///The not a number constant
179    static const Value NaN;
180
181    static inline bool isNaN(const Value& v) { return v!=v; }
182   
183    friend class Col;
184    friend class ColIt;
185    friend class Row;
186   
187    ///Refer to a column of the LP.
188
189    ///This type is used to refer to a column of the LP.
190    ///
191    ///Its value remains valid and correct even after the addition or erase of
192    ///other columns.
193    ///
194    ///\todo Document what can one do with a Col (INVALID, comparing,
195    ///it is similar to Node/Edge)
196    class Col {
197    protected:
198      int id;
199      friend class LpSolverBase;
200      friend class MipSolverBase;
201    public:
202      typedef Value ExprValue;
203      typedef True LpSolverCol;
204      Col() {}
205      Col(const Invalid&) : id(-1) {}
206      bool operator< (Col c) const  {return id< c.id;}
207      bool operator> (Col c) const  {return id> c.id;}
208      bool operator==(Col c) const  {return id==c.id;}
209      bool operator!=(Col c) const  {return id!=c.id;}
210    };
211
212    class ColIt : public Col {
213      LpSolverBase *_lp;
214    public:
215      ColIt() {}
216      ColIt(LpSolverBase &lp) : _lp(&lp)
217      {
218        id = _lp->cols.cross.empty()?-1:
219          _lp->cols.fixId(_lp->cols.firstIndex());
220      }
221      ColIt(const Invalid&) : Col(INVALID) {}
222      ColIt &operator++()
223      {
224        int fid = _lp->cols.floatingId(id)+1;
225        id = unsigned(fid)<_lp->cols.cross.size() ? _lp->cols.fixId(fid) : -1;
226        return *this;
227      }
228    };
229
230    static int id(const Col& col) { return col.id; }
231 
232     
233    ///Refer to a row of the LP.
234
235    ///This type is used to refer to a row of the LP.
236    ///
237    ///Its value remains valid and correct even after the addition or erase of
238    ///other rows.
239    ///
240    ///\todo Document what can one do with a Row (INVALID, comparing,
241    ///it is similar to Node/Edge)
242    class Row {
243    protected:
244      int id;
245      friend class LpSolverBase;
246    public:
247      typedef Value ExprValue;
248      typedef True LpSolverRow;
249      Row() {}
250      Row(const Invalid&) : id(-1) {}
251
252      bool operator< (Row c) const  {return id< c.id;}
253      bool operator> (Row c) const  {return id> c.id;}
254      bool operator==(Row c) const  {return id==c.id;}
255      bool operator!=(Row c) const  {return id!=c.id;}
256    };
257
258    static int id(const Row& row) { return row.id; }
259
260  protected:
261
262    int _lpId(const Col& col) const {
263      return cols.floatingId(id(col));
264    }
265
266    int _lpId(const Row& row) const {
267      return rows.floatingId(id(row));
268    }
269
270
271  public:
272   
273    ///Linear expression of variables and a constant component
274   
275    ///This data structure stores a linear expression of the variables
276    ///(\ref Col "Col"s) and also has a constant component.
277    ///
278    ///There are several ways to access and modify the contents of this
279    ///container.
280    ///- Its it fully compatible with \c std::map<Col,double>, so for expamle
281    ///if \c e is an Expr and \c v and \c w are of type \ref Col, then you can
282    ///read and modify the coefficients like
283    ///these.
284    ///\code
285    ///e[v]=5;
286    ///e[v]+=12;
287    ///e.erase(v);
288    ///\endcode
289    ///or you can also iterate through its elements.
290    ///\code
291    ///double s=0;
292    ///for(LpSolverBase::Expr::iterator i=e.begin();i!=e.end();++i)
293    ///  s+=i->second;
294    ///\endcode
295    ///(This code computes the sum of all coefficients).
296    ///- Numbers (<tt>double</tt>'s)
297    ///and variables (\ref Col "Col"s) directly convert to an
298    ///\ref Expr and the usual linear operations are defined, so 
299    ///\code
300    ///v+w
301    ///2*v-3.12*(v-w/2)+2
302    ///v*2.1+(3*v+(v*12+w+6)*3)/2
303    ///\endcode
304    ///are valid \ref Expr "Expr"essions.
305    ///The usual assignment operations are also defined.
306    ///\code
307    ///e=v+w;
308    ///e+=2*v-3.12*(v-w/2)+2;
309    ///e*=3.4;
310    ///e/=5;
311    ///\endcode
312    ///- The constant member can be set and read by \ref constComp()
313    ///\code
314    ///e.constComp()=12;
315    ///double c=e.constComp();
316    ///\endcode
317    ///
318    ///\note \ref clear() not only sets all coefficients to 0 but also
319    ///clears the constant components.
320    ///
321    ///\sa Constr
322    ///
323    class Expr : public std::map<Col,Value>
324    {
325    public:
326      typedef LpSolverBase::Col Key;
327      typedef LpSolverBase::Value Value;
328     
329    protected:
330      typedef std::map<Col,Value> Base;
331     
332      Value const_comp;
333    public:
334      typedef True IsLinExpression;
335      ///\e
336      Expr() : Base(), const_comp(0) { }
337      ///\e
338      Expr(const Key &v) : const_comp(0) {
339        Base::insert(std::make_pair(v, 1));
340      }
341      ///\e
342      Expr(const Value &v) : const_comp(v) {}
343      ///\e
344      void set(const Key &v,const Value &c) {
345        Base::insert(std::make_pair(v, c));
346      }
347      ///\e
348      Value &constComp() { return const_comp; }
349      ///\e
350      const Value &constComp() const { return const_comp; }
351     
352      ///Removes the components with zero coefficient.
353      void simplify() {
354        for (Base::iterator i=Base::begin(); i!=Base::end();) {
355          Base::iterator j=i;
356          ++j;
357          if ((*i).second==0) Base::erase(i);
358          i=j;
359        }
360      }
361
362      void simplify() const {
363        const_cast<Expr*>(this)->simplify();
364      }
365
366      ///Removes the coefficients closer to zero than \c tolerance.
367      void simplify(double &tolerance) {
368        for (Base::iterator i=Base::begin(); i!=Base::end();) {
369          Base::iterator j=i;
370          ++j;
371          if (std::fabs((*i).second)<tolerance) Base::erase(i);
372          i=j;
373        }
374      }
375
376      ///Sets all coefficients and the constant component to 0.
377      void clear() {
378        Base::clear();
379        const_comp=0;
380      }
381
382      ///\e
383      Expr &operator+=(const Expr &e) {
384        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
385          (*this)[j->first]+=j->second;
386        const_comp+=e.const_comp;
387        return *this;
388      }
389      ///\e
390      Expr &operator-=(const Expr &e) {
391        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
392          (*this)[j->first]-=j->second;
393        const_comp-=e.const_comp;
394        return *this;
395      }
396      ///\e
397      Expr &operator*=(const Value &c) {
398        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
399          j->second*=c;
400        const_comp*=c;
401        return *this;
402      }
403      ///\e
404      Expr &operator/=(const Value &c) {
405        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
406          j->second/=c;
407        const_comp/=c;
408        return *this;
409      }
410
411      //std::ostream &
412      void prettyPrint(std::ostream &os) {
413        //std::fmtflags os.flags();
414        //os.setf(std::ios::showpos);
415        Base::iterator j=Base::begin();
416        if (j!=Base::end())
417          os<<j->second<<"*x["<<id(j->first)<<"]";
418        ++j;
419        for (; j!=Base::end(); ++j){
420          if (j->second>=0)
421            os<<"+";
422          os<<j->second<<"*x["<<id(j->first)<<"]";
423        }
424        //Nem valami korrekt, de nem talaltam meg, hogy kell
425        //os.unsetf(std::ios::showpos);
426
427        //return os;
428      }
429
430    };
431   
432    ///Linear constraint
433
434    ///This data stucture represents a linear constraint in the LP.
435    ///Basically it is a linear expression with a lower or an upper bound
436    ///(or both). These parts of the constraint can be obtained by the member
437    ///functions \ref expr(), \ref lowerBound() and \ref upperBound(),
438    ///respectively.
439    ///There are two ways to construct a constraint.
440    ///- You can set the linear expression and the bounds directly
441    ///  by the functions above.
442    ///- The operators <tt>\<=</tt>, <tt>==</tt> and  <tt>\>=</tt>
443    ///  are defined between expressions, or even between constraints whenever
444    ///  it makes sense. Therefore if \c e and \c f are linear expressions and
445    ///  \c s and \c t are numbers, then the followings are valid expressions
446    ///  and thus they can be used directly e.g. in \ref addRow() whenever
447    ///  it makes sense.
448    ///\code
449    ///  e<=s
450    ///  e<=f
451    ///  e==f
452    ///  s<=e<=t
453    ///  e>=t
454    ///\endcode
455    ///\warning The validity of a constraint is checked only at run time, so
456    ///e.g. \ref addRow(<tt>x[1]\<=x[2]<=5</tt>) will compile, but will throw a
457    ///\ref LogicError exception.
458    class Constr
459    {
460    public:
461      typedef LpSolverBase::Expr Expr;
462      typedef Expr::Key Key;
463      typedef Expr::Value Value;
464     
465    protected:
466      Expr _expr;
467      Value _lb,_ub;
468    public:
469      ///\e
470      Constr() : _expr(), _lb(NaN), _ub(NaN) {}
471      ///\e
472      Constr(Value lb,const Expr &e,Value ub) :
473        _expr(e), _lb(lb), _ub(ub) {}
474      ///\e
475      Constr(const Expr &e,Value ub) :
476        _expr(e), _lb(NaN), _ub(ub) {}
477      ///\e
478      Constr(Value lb,const Expr &e) :
479        _expr(e), _lb(lb), _ub(NaN) {}
480      ///\e
481      Constr(const Expr &e) :
482        _expr(e), _lb(NaN), _ub(NaN) {}
483      ///\e
484      void clear()
485      {
486        _expr.clear();
487        _lb=_ub=NaN;
488      }
489
490      ///Reference to the linear expression
491      Expr &expr() { return _expr; }
492      ///Cont reference to the linear expression
493      const Expr &expr() const { return _expr; }
494      ///Reference to the lower bound.
495
496      ///\return
497      ///- \ref INF "INF": the constraint is lower unbounded.
498      ///- \ref NaN "NaN": lower bound has not been set.
499      ///- finite number: the lower bound
500      Value &lowerBound() { return _lb; }
501      ///The const version of \ref lowerBound()
502      const Value &lowerBound() const { return _lb; }
503      ///Reference to the upper bound.
504
505      ///\return
506      ///- \ref INF "INF": the constraint is upper unbounded.
507      ///- \ref NaN "NaN": upper bound has not been set.
508      ///- finite number: the upper bound
509      Value &upperBound() { return _ub; }
510      ///The const version of \ref upperBound()
511      const Value &upperBound() const { return _ub; }
512      ///Is the constraint lower bounded?
513      bool lowerBounded() const {
514        using namespace std;
515        return finite(_lb);
516      }
517      ///Is the constraint upper bounded?
518      bool upperBounded() const {
519        using namespace std;
520        return finite(_ub);
521      }
522
523      void prettyPrint(std::ostream &os) {
524        if (_lb==-LpSolverBase::INF||isNaN(_lb))
525          os<<"-infty<=";
526        else
527          os<<_lb<<"<=";
528        _expr.prettyPrint(os);
529        if (_ub==LpSolverBase::INF)
530          os<<"<=infty";
531        else
532          os<<"<="<<_ub;
533        //return os;
534      }
535
536    };
537   
538    ///Linear expression of rows
539   
540    ///This data structure represents a column of the matrix,
541    ///thas is it strores a linear expression of the dual variables
542    ///(\ref Row "Row"s).
543    ///
544    ///There are several ways to access and modify the contents of this
545    ///container.
546    ///- Its it fully compatible with \c std::map<Row,double>, so for expamle
547    ///if \c e is an DualExpr and \c v
548    ///and \c w are of type \ref Row, then you can
549    ///read and modify the coefficients like
550    ///these.
551    ///\code
552    ///e[v]=5;
553    ///e[v]+=12;
554    ///e.erase(v);
555    ///\endcode
556    ///or you can also iterate through its elements.
557    ///\code
558    ///double s=0;
559    ///for(LpSolverBase::DualExpr::iterator i=e.begin();i!=e.end();++i)
560    ///  s+=i->second;
561    ///\endcode
562    ///(This code computes the sum of all coefficients).
563    ///- Numbers (<tt>double</tt>'s)
564    ///and variables (\ref Row "Row"s) directly convert to an
565    ///\ref DualExpr and the usual linear operations are defined, so
566    ///\code
567    ///v+w
568    ///2*v-3.12*(v-w/2)
569    ///v*2.1+(3*v+(v*12+w)*3)/2
570    ///\endcode
571    ///are valid \ref DualExpr "DualExpr"essions.
572    ///The usual assignment operations are also defined.
573    ///\code
574    ///e=v+w;
575    ///e+=2*v-3.12*(v-w/2);
576    ///e*=3.4;
577    ///e/=5;
578    ///\endcode
579    ///
580    ///\sa Expr
581    ///
582    class DualExpr : public std::map<Row,Value>
583    {
584    public:
585      typedef LpSolverBase::Row Key;
586      typedef LpSolverBase::Value Value;
587     
588    protected:
589      typedef std::map<Row,Value> Base;
590     
591    public:
592      typedef True IsLinExpression;
593      ///\e
594      DualExpr() : Base() { }
595      ///\e
596      DualExpr(const Key &v) {
597        Base::insert(std::make_pair(v, 1));
598      }
599      ///\e
600      void set(const Key &v,const Value &c) {
601        Base::insert(std::make_pair(v, c));
602      }
603     
604      ///Removes the components with zero coefficient.
605      void simplify() {
606        for (Base::iterator i=Base::begin(); i!=Base::end();) {
607          Base::iterator j=i;
608          ++j;
609          if ((*i).second==0) Base::erase(i);
610          i=j;
611        }
612      }
613
614      void simplify() const {
615        const_cast<DualExpr*>(this)->simplify();
616      }
617
618      ///Removes the coefficients closer to zero than \c tolerance.
619      void simplify(double &tolerance) {
620        for (Base::iterator i=Base::begin(); i!=Base::end();) {
621          Base::iterator j=i;
622          ++j;
623          if (std::fabs((*i).second)<tolerance) Base::erase(i);
624          i=j;
625        }
626      }
627
628      ///Sets all coefficients to 0.
629      void clear() {
630        Base::clear();
631      }
632
633      ///\e
634      DualExpr &operator+=(const DualExpr &e) {
635        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
636          (*this)[j->first]+=j->second;
637        return *this;
638      }
639      ///\e
640      DualExpr &operator-=(const DualExpr &e) {
641        for (Base::const_iterator j=e.begin(); j!=e.end(); ++j)
642          (*this)[j->first]-=j->second;
643        return *this;
644      }
645      ///\e
646      DualExpr &operator*=(const Value &c) {
647        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
648          j->second*=c;
649        return *this;
650      }
651      ///\e
652      DualExpr &operator/=(const Value &c) {
653        for (Base::iterator j=Base::begin(); j!=Base::end(); ++j)
654          j->second/=c;
655        return *this;
656      }
657    };
658   
659
660  private:
661
662    template <typename _Base>
663    class MappedIterator {
664    public:
665
666      typedef _Base Base;
667
668      typedef typename Base::iterator_category iterator_category;
669      typedef typename Base::difference_type difference_type;
670      typedef const std::pair<int, Value> value_type;
671      typedef value_type reference;
672      class pointer {
673      public:
674        pointer(value_type& _value) : value(_value) {}
675        value_type* operator->() { return &value; }
676      private:
677        value_type value;
678      };
679
680      MappedIterator(const Base& _base, const LpSolverBase& _lp)
681        : base(_base), lp(_lp) {}
682
683      reference operator*() {
684        return std::make_pair(lp._lpId(base->first), base->second);
685      }
686
687      pointer operator->() {
688        return pointer(operator*());
689      }
690
691      MappedIterator& operator++() {
692        ++base;
693        return *this;
694      }
695
696      MappedIterator& operator++(int) {
697        MappedIterator tmp(*this);
698        ++base;
699        return tmp;
700      }
701
702      bool operator==(const MappedIterator& it) const {
703        return base == it.base;
704      }
705
706      bool operator!=(const MappedIterator& it) const {
707        return base != it.base;
708      }
709
710    private:
711      Base base;
712      const LpSolverBase& lp;
713    };
714
715  protected:
716
717    /// STL compatible iterator for lp col
718    typedef MappedIterator<Expr::const_iterator> LpRowIterator;
719    /// STL compatible iterator for lp row
720    typedef MappedIterator<DualExpr::const_iterator> LpColIterator;
721
722    //Abstract virtual functions
723    virtual LpSolverBase &_newLp() = 0;
724    virtual LpSolverBase &_copyLp(){
725      ///\todo This should be implemented here, too, when we have
726      ///problem retrieving routines. It can be overriden.
727
728      //Starting:
729      LpSolverBase & newlp(_newLp());
730      return newlp;
731      //return *(LpSolverBase*)0;
732    };
733
734    virtual int _addCol() = 0;
735    virtual int _addRow() = 0;
736    virtual void _eraseCol(int col) = 0;
737    virtual void _eraseRow(int row) = 0;
738    virtual void _getColName(int col, std::string & name) = 0;
739    virtual void _setColName(int col, const std::string & name) = 0;
740    virtual void _setRowCoeffs(int i, LpRowIterator b, LpRowIterator e) = 0;
741    virtual void _setColCoeffs(int i, LpColIterator b, LpColIterator e) = 0;
742    virtual void _setCoeff(int row, int col, Value value) = 0;
743    virtual Value _getCoeff(int row, int col) = 0;
744
745    virtual void _setColLowerBound(int i, Value value) = 0;
746    virtual Value _getColLowerBound(int i) = 0;
747    virtual void _setColUpperBound(int i, Value value) = 0;
748    virtual Value _getColUpperBound(int i) = 0;
749//     virtual void _setRowLowerBound(int i, Value value) = 0;
750//     virtual void _setRowUpperBound(int i, Value value) = 0;
751    virtual void _setRowBounds(int i, Value lower, Value upper) = 0;
752    virtual void _getRowBounds(int i, Value &lower, Value &upper)=0;
753
754    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
755    virtual Value _getObjCoeff(int i) = 0;
756    virtual void _clearObj()=0;
757
758    virtual SolveExitStatus _solve() = 0;
759    virtual Value _getPrimal(int i) = 0;
760    virtual Value _getDual(int i) = 0;
761    virtual Value _getPrimalValue() = 0;
762    virtual bool _isBasicCol(int i) = 0;
763    virtual SolutionStatus _getPrimalStatus() = 0;
764    virtual SolutionStatus _getDualStatus() = 0;
765    ///\todo This could be implemented here, too, using _getPrimalStatus() and
766    ///_getDualStatus()
767    virtual ProblemTypes _getProblemType() = 0;
768
769    virtual void _setMax() = 0;
770    virtual void _setMin() = 0;
771   
772
773    virtual bool _isMax() = 0;
774
775    //Own protected stuff
776   
777    //Constant component of the objective function
778    Value obj_const_comp;
779       
780  public:
781
782    ///\e
783    LpSolverBase() : obj_const_comp(0) {}
784
785    ///\e
786    virtual ~LpSolverBase() {}
787
788    ///Creates a new LP problem
789    LpSolverBase &newLp() {return _newLp();}
790    ///Makes a copy of the LP problem
791    LpSolverBase &copyLp() {return _copyLp();}
792   
793    ///\name Build up and modify the LP
794
795    ///@{
796
797    ///Add a new empty column (i.e a new variable) to the LP
798    Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
799
800    ///\brief Adds several new columns
801    ///(i.e a variables) at once
802    ///
803    ///This magic function takes a container as its argument
804    ///and fills its elements
805    ///with new columns (i.e. variables)
806    ///\param t can be
807    ///- a standard STL compatible iterable container with
808    ///\ref Col as its \c values_type
809    ///like
810    ///\code
811    ///std::vector<LpSolverBase::Col>
812    ///std::list<LpSolverBase::Col>
813    ///\endcode
814    ///- a standard STL compatible iterable container with
815    ///\ref Col as its \c mapped_type
816    ///like
817    ///\code
818    ///std::map<AnyType,LpSolverBase::Col>
819    ///\endcode
820    ///- an iterable lemon \ref concepts::WriteMap "write map" like
821    ///\code
822    ///ListGraph::NodeMap<LpSolverBase::Col>
823    ///ListGraph::EdgeMap<LpSolverBase::Col>
824    ///\endcode
825    ///\return The number of the created column.
826#ifdef DOXYGEN
827    template<class T>
828    int addColSet(T &t) { return 0;}
829#else
830    template<class T>
831    typename enable_if<typename T::value_type::LpSolverCol,int>::type
832    addColSet(T &t,dummy<0> = 0) {
833      int s=0;
834      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
835      return s;
836    }
837    template<class T>
838    typename enable_if<typename T::value_type::second_type::LpSolverCol,
839                       int>::type
840    addColSet(T &t,dummy<1> = 1) {
841      int s=0;
842      for(typename T::iterator i=t.begin();i!=t.end();++i) {
843        i->second=addCol();
844        s++;
845      }
846      return s;
847    }
848    template<class T>
849    typename enable_if<typename T::MapIt::Value::LpSolverCol,
850                       int>::type
851    addColSet(T &t,dummy<2> = 2) {
852      int s=0;
853      for(typename T::MapIt i(t); i!=INVALID; ++i)
854        {
855          i.set(addCol());
856          s++;
857        }
858      return s;
859    }
860#endif
861
862    ///Set a column (i.e a dual constraint) of the LP
863
864    ///\param c is the column to be modified
865    ///\param e is a dual linear expression (see \ref DualExpr)
866    ///a better one.
867    void col(Col c,const DualExpr &e) {
868      e.simplify();
869      _setColCoeffs(_lpId(c), LpColIterator(e.begin(), *this),
870                    LpColIterator(e.end(), *this));
871    }
872
873    ///Add a new column to the LP
874
875    ///\param e is a dual linear expression (see \ref DualExpr)
876    ///\param obj is the corresponding component of the objective
877    ///function. It is 0 by default.
878    ///\return The created column.
879    Col addCol(const DualExpr &e, Value obj=0) {
880      Col c=addCol();
881      col(c,e);
882      objCoeff(c,obj);
883      return c;
884    }
885
886    ///Add a new empty row (i.e a new constraint) to the LP
887
888    ///This function adds a new empty row (i.e a new constraint) to the LP.
889    ///\return The created row
890    Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
891
892    ///\brief Add several new rows
893    ///(i.e a constraints) at once
894    ///
895    ///This magic function takes a container as its argument
896    ///and fills its elements
897    ///with new row (i.e. variables)
898    ///\param t can be
899    ///- a standard STL compatible iterable container with
900    ///\ref Row as its \c values_type
901    ///like
902    ///\code
903    ///std::vector<LpSolverBase::Row>
904    ///std::list<LpSolverBase::Row>
905    ///\endcode
906    ///- a standard STL compatible iterable container with
907    ///\ref Row as its \c mapped_type
908    ///like
909    ///\code
910    ///std::map<AnyType,LpSolverBase::Row>
911    ///\endcode
912    ///- an iterable lemon \ref concepts::WriteMap "write map" like
913    ///\code
914    ///ListGraph::NodeMap<LpSolverBase::Row>
915    ///ListGraph::EdgeMap<LpSolverBase::Row>
916    ///\endcode
917    ///\return The number of rows created.
918#ifdef DOXYGEN
919    template<class T>
920    int addRowSet(T &t) { return 0;}
921#else
922    template<class T>
923    typename enable_if<typename T::value_type::LpSolverRow,int>::type
924    addRowSet(T &t,dummy<0> = 0) {
925      int s=0;
926      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addRow();s++;}
927      return s;
928    }
929    template<class T>
930    typename enable_if<typename T::value_type::second_type::LpSolverRow,
931                       int>::type
932    addRowSet(T &t,dummy<1> = 1) {
933      int s=0;
934      for(typename T::iterator i=t.begin();i!=t.end();++i) {
935        i->second=addRow();
936        s++;
937      }
938      return s;
939    }
940    template<class T>
941    typename enable_if<typename T::MapIt::Value::LpSolverRow,
942                       int>::type
943    addRowSet(T &t,dummy<2> = 2) {
944      int s=0;
945      for(typename T::MapIt i(t); i!=INVALID; ++i)
946        {
947          i.set(addRow());
948          s++;
949        }
950      return s;
951    }
952#endif
953
954    ///Set a row (i.e a constraint) of the LP
955
956    ///\param r is the row to be modified
957    ///\param l is lower bound (-\ref INF means no bound)
958    ///\param e is a linear expression (see \ref Expr)
959    ///\param u is the upper bound (\ref INF means no bound)
960    ///\bug This is a temportary function. The interface will change to
961    ///a better one.
962    ///\todo Option to control whether a constraint with a single variable is
963    ///added or not.
964    void row(Row r, Value l,const Expr &e, Value u) {
965      e.simplify();
966      _setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this),
967                    LpRowIterator(e.end(), *this));
968//       _setRowLowerBound(_lpId(r),l-e.constComp());
969//       _setRowUpperBound(_lpId(r),u-e.constComp());
970       _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
971    }
972
973    ///Set a row (i.e a constraint) of the LP
974
975    ///\param r is the row to be modified
976    ///\param c is a linear expression (see \ref Constr)
977    void row(Row r, const Constr &c) {
978      row(r, c.lowerBounded()?c.lowerBound():-INF,
979          c.expr(), c.upperBounded()?c.upperBound():INF);
980    }
981
982    ///Add a new row (i.e a new constraint) to the LP
983
984    ///\param l is the lower bound (-\ref INF means no bound)
985    ///\param e is a linear expression (see \ref Expr)
986    ///\param u is the upper bound (\ref INF means no bound)
987    ///\return The created row.
988    ///\bug This is a temportary function. The interface will change to
989    ///a better one.
990    Row addRow(Value l,const Expr &e, Value u) {
991      Row r=addRow();
992      row(r,l,e,u);
993      return r;
994    }
995
996    ///Add a new row (i.e a new constraint) to the LP
997
998    ///\param c is a linear expression (see \ref Constr)
999    ///\return The created row.
1000    Row addRow(const Constr &c) {
1001      Row r=addRow();
1002      row(r,c);
1003      return r;
1004    }
1005    ///Erase a coloumn (i.e a variable) from the LP
1006
1007    ///\param c is the coloumn to be deleted
1008    ///\todo Please check this
1009    void eraseCol(Col c) {
1010      _eraseCol(_lpId(c));
1011      cols.erase(c.id);
1012    }
1013    ///Erase a  row (i.e a constraint) from the LP
1014
1015    ///\param r is the row to be deleted
1016    ///\todo Please check this
1017    void eraseRow(Row r) {
1018      _eraseRow(_lpId(r));
1019      rows.erase(r.id);
1020    }
1021
1022    /// Get the name of a column
1023   
1024    ///\param c is the coresponding coloumn
1025    ///\return The name of the colunm
1026    std::string colName(Col c){
1027      std::string name;
1028      _getColName(_lpId(c), name);
1029      return name;
1030    }
1031   
1032    /// Set the name of a column
1033   
1034    ///\param c is the coresponding coloumn
1035    ///\param name The name to be given
1036    void colName(Col c, const std::string& name){
1037      _setColName(_lpId(c), name);
1038    }
1039   
1040    /// Set an element of the coefficient matrix of the LP
1041
1042    ///\param r is the row of the element to be modified
1043    ///\param c is the coloumn of the element to be modified
1044    ///\param val is the new value of the coefficient
1045
1046    void coeff(Row r, Col c, Value val){
1047      _setCoeff(_lpId(r),_lpId(c), val);
1048    }
1049
1050    /// Get an element of the coefficient matrix of the LP
1051
1052    ///\param r is the row of the element in question
1053    ///\param c is the coloumn of the element in question
1054    ///\return the corresponding coefficient
1055
1056    Value coeff(Row r, Col c){
1057      return _getCoeff(_lpId(r),_lpId(c));
1058    }
1059
1060    /// Set the lower bound of a column (i.e a variable)
1061
1062    /// The lower bound of a variable (column) has to be given by an
1063    /// extended number of type Value, i.e. a finite number of type
1064    /// Value or -\ref INF.
1065    void colLowerBound(Col c, Value value) {
1066      _setColLowerBound(_lpId(c),value);
1067    }
1068
1069    /// Get the lower bound of a column (i.e a variable)
1070
1071    /// This function returns the lower bound for column (variable) \t c
1072    /// (this might be -\ref INF as well). 
1073    ///\return The lower bound for coloumn \t c
1074    Value colLowerBound(Col c) {
1075      return _getColLowerBound(_lpId(c));
1076    }
1077   
1078    ///\brief Set the lower bound of  several columns
1079    ///(i.e a variables) at once
1080    ///
1081    ///This magic function takes a container as its argument
1082    ///and applies the function on all of its elements.
1083    /// The lower bound of a variable (column) has to be given by an
1084    /// extended number of type Value, i.e. a finite number of type
1085    /// Value or -\ref INF.
1086#ifdef DOXYGEN
1087    template<class T>
1088    void colLowerBound(T &t, Value value) { return 0;}
1089#else
1090    template<class T>
1091    typename enable_if<typename T::value_type::LpSolverCol,void>::type
1092    colLowerBound(T &t, Value value,dummy<0> = 0) {
1093      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1094        colLowerBound(*i, value);
1095      }
1096    }
1097    template<class T>
1098    typename enable_if<typename T::value_type::second_type::LpSolverCol,
1099                       void>::type
1100    colLowerBound(T &t, Value value,dummy<1> = 1) {
1101      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1102        colLowerBound(i->second, value);
1103      }
1104    }
1105    template<class T>
1106    typename enable_if<typename T::MapIt::Value::LpSolverCol,
1107                       void>::type
1108    colLowerBound(T &t, Value value,dummy<2> = 2) {
1109      for(typename T::MapIt i(t); i!=INVALID; ++i){
1110        colLowerBound(*i, value);
1111      }
1112    }
1113#endif
1114   
1115    /// Set the upper bound of a column (i.e a variable)
1116
1117    /// The upper bound of a variable (column) has to be given by an
1118    /// extended number of type Value, i.e. a finite number of type
1119    /// Value or \ref INF.
1120    void colUpperBound(Col c, Value value) {
1121      _setColUpperBound(_lpId(c),value);
1122    };
1123
1124    /// Get the upper bound of a column (i.e a variable)
1125
1126    /// This function returns the upper bound for column (variable) \t c
1127    /// (this might be \ref INF as well). 
1128    ///\return The upper bound for coloumn \t c
1129    Value colUpperBound(Col c) {
1130      return _getColUpperBound(_lpId(c));
1131    }
1132
1133    ///\brief Set the upper bound of  several columns
1134    ///(i.e a variables) at once
1135    ///
1136    ///This magic function takes a container as its argument
1137    ///and applies the function on all of its elements.
1138    /// The upper bound of a variable (column) has to be given by an
1139    /// extended number of type Value, i.e. a finite number of type
1140    /// Value or \ref INF.
1141#ifdef DOXYGEN
1142    template<class T>
1143    void colUpperBound(T &t, Value value) { return 0;}
1144#else
1145    template<class T>
1146    typename enable_if<typename T::value_type::LpSolverCol,void>::type
1147    colUpperBound(T &t, Value value,dummy<0> = 0) {
1148      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1149        colUpperBound(*i, value);
1150      }
1151    }
1152    template<class T>
1153    typename enable_if<typename T::value_type::second_type::LpSolverCol,
1154                       void>::type
1155    colUpperBound(T &t, Value value,dummy<1> = 1) {
1156      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1157        colUpperBound(i->second, value);
1158      }
1159    }
1160    template<class T>
1161    typename enable_if<typename T::MapIt::Value::LpSolverCol,
1162                       void>::type
1163    colUpperBound(T &t, Value value,dummy<2> = 2) {
1164      for(typename T::MapIt i(t); i!=INVALID; ++i){
1165        colUpperBound(*i, value);
1166      }
1167    }
1168#endif
1169
1170    /// Set the lower and the upper bounds of a column (i.e a variable)
1171
1172    /// The lower and the upper bounds of
1173    /// a variable (column) have to be given by an
1174    /// extended number of type Value, i.e. a finite number of type
1175    /// Value, -\ref INF or \ref INF.
1176    void colBounds(Col c, Value lower, Value upper) {
1177      _setColLowerBound(_lpId(c),lower);
1178      _setColUpperBound(_lpId(c),upper);
1179    }
1180   
1181    ///\brief Set the lower and the upper bound of several columns
1182    ///(i.e a variables) at once
1183    ///
1184    ///This magic function takes a container as its argument
1185    ///and applies the function on all of its elements.
1186    /// The lower and the upper bounds of
1187    /// a variable (column) have to be given by an
1188    /// extended number of type Value, i.e. a finite number of type
1189    /// Value, -\ref INF or \ref INF.
1190#ifdef DOXYGEN
1191    template<class T>
1192    void colBounds(T &t, Value lower, Value upper) { return 0;}
1193#else
1194    template<class T>
1195    typename enable_if<typename T::value_type::LpSolverCol,void>::type
1196    colBounds(T &t, Value lower, Value upper,dummy<0> = 0) {
1197      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1198        colBounds(*i, lower, upper);
1199      }
1200    }
1201    template<class T>
1202    typename enable_if<typename T::value_type::second_type::LpSolverCol,
1203                       void>::type
1204    colBounds(T &t, Value lower, Value upper,dummy<1> = 1) {
1205      for(typename T::iterator i=t.begin();i!=t.end();++i) {
1206        colBounds(i->second, lower, upper);
1207      }
1208    }
1209    template<class T>
1210    typename enable_if<typename T::MapIt::Value::LpSolverCol,
1211                       void>::type
1212    colBounds(T &t, Value lower, Value upper,dummy<2> = 2) {
1213      for(typename T::MapIt i(t); i!=INVALID; ++i){
1214        colBounds(*i, lower, upper);
1215      }
1216    }
1217#endif
1218   
1219//     /// Set the lower bound of a row (i.e a constraint)
1220
1221//     /// The lower bound of a linear expression (row) has to be given by an
1222//     /// extended number of type Value, i.e. a finite number of type
1223//     /// Value or -\ref INF.
1224//     void rowLowerBound(Row r, Value value) {
1225//       _setRowLowerBound(_lpId(r),value);
1226//     };
1227//     /// Set the upper bound of a row (i.e a constraint)
1228
1229//     /// The upper bound of a linear expression (row) has to be given by an
1230//     /// extended number of type Value, i.e. a finite number of type
1231//     /// Value or \ref INF.
1232//     void rowUpperBound(Row r, Value value) {
1233//       _setRowUpperBound(_lpId(r),value);
1234//     };
1235
1236    /// Set the lower and the upper bounds of a row (i.e a constraint)
1237
1238    /// The lower and the upper bound of
1239    /// a constraint (row) have to be given by an
1240    /// extended number of type Value, i.e. a finite number of type
1241    /// Value, -\ref INF or \ref INF. There is no separate function for the
1242    /// lower and the upper bound because that would have been hard to implement
1243    /// for CPLEX.
1244    void rowBounds(Row c, Value lower, Value upper) {
1245      _setRowBounds(_lpId(c),lower, upper);
1246    }
1247   
1248    /// Get the lower and the upper bounds of a row (i.e a constraint)
1249
1250    /// The lower and the upper bound of
1251    /// a constraint (row) are 
1252    /// extended numbers of type Value, i.e.  finite numbers of type
1253    /// Value, -\ref INF or \ref INF.
1254    /// \todo There is no separate function for the
1255    /// lower and the upper bound because we had problems with the
1256    /// implementation of the setting functions for CPLEX: 
1257    /// check out whether this can be done for these functions.
1258    void getRowBounds(Row c, Value &lower, Value &upper) {
1259      _getRowBounds(_lpId(c),lower, upper);
1260    }
1261
1262    ///Set an element of the objective function
1263    void objCoeff(Col c, Value v) {_setObjCoeff(_lpId(c),v); };
1264
1265    ///Get an element of the objective function
1266    Value objCoeff(Col c) {return _getObjCoeff(_lpId(c)); };
1267
1268    ///Set the objective function
1269
1270    ///\param e is a linear expression of type \ref Expr.
1271    ///\bug Is should be called obj()
1272    void setObj(Expr e) {
1273      _clearObj();
1274      for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
1275        objCoeff((*i).first,(*i).second);
1276      obj_const_comp=e.constComp();
1277    }
1278
1279    ///Maximize
1280    void max() { _setMax(); }
1281    ///Minimize
1282    void min() { _setMin(); }
1283
1284    ///Query function: is this a maximization problem?
1285    bool is_max() {return _isMax(); }
1286
1287    ///Query function: is this a minimization problem?
1288    bool is_min() {return !is_max(); }
1289   
1290    ///@}
1291
1292
1293    ///\name Solve the LP
1294
1295    ///@{
1296
1297    ///\e Solve the LP problem at hand
1298    ///
1299    ///\return The result of the optimization procedure. Possible
1300    ///values and their meanings can be found in the documentation of
1301    ///\ref SolveExitStatus.
1302    ///
1303    ///\todo Which method is used to solve the problem
1304    SolveExitStatus solve() { return _solve(); }
1305   
1306    ///@}
1307   
1308    ///\name Obtain the solution
1309
1310    ///@{
1311
1312    /// The status of the primal problem (the original LP problem)
1313    SolutionStatus primalStatus() {
1314      return _getPrimalStatus();
1315    }
1316
1317    /// The status of the dual (of the original LP) problem
1318    SolutionStatus dualStatus() {
1319      return _getDualStatus();
1320    }
1321
1322    ///The type of the original LP problem
1323    ProblemTypes problemType() {
1324      return _getProblemType();
1325    }
1326
1327    ///\e
1328    Value primal(Col c) { return _getPrimal(_lpId(c)); }
1329
1330    ///\e
1331    Value dual(Row r) { return _getDual(_lpId(r)); }
1332
1333    ///\e
1334    bool isBasicCol(Col c) { return _isBasicCol(_lpId(c)); }
1335
1336    ///\e
1337
1338    ///\return
1339    ///- \ref INF or -\ref INF means either infeasibility or unboundedness
1340    /// of the primal problem, depending on whether we minimize or maximize.
1341    ///- \ref NaN if no primal solution is found.
1342    ///- The (finite) objective value if an optimal solution is found.
1343    Value primalValue() { return _getPrimalValue()+obj_const_comp;}
1344    ///@}
1345   
1346  }; 
1347
1348
1349  ///Common base class for MIP solvers
1350  ///\todo Much more docs
1351  ///\ingroup gen_opt_group
1352  class MipSolverBase : virtual public LpSolverBase{
1353  public:
1354
1355    ///Possible variable (coloumn) types (e.g. real, integer, binary etc.)
1356    enum ColTypes {
1357      ///Continuous variable
1358      REAL = 0,
1359      ///Integer variable
1360
1361      ///Unfortunately, cplex 7.5 somewhere writes something like
1362      ///#define INTEGER 'I'
1363      INT = 1
1364      ///\todo No support for other types yet.
1365    };
1366
1367    ///Sets the type of the given coloumn to the given type
1368    ///
1369    ///Sets the type of the given coloumn to the given type.
1370    void colType(Col c, ColTypes col_type) {
1371      _colType(_lpId(c),col_type);
1372    }
1373
1374    ///Gives back the type of the column.
1375    ///
1376    ///Gives back the type of the column.
1377    ColTypes colType(Col c){
1378      return _colType(_lpId(c));
1379    }
1380
1381    ///Sets the type of the given Col to integer or remove that property.
1382    ///
1383    ///Sets the type of the given Col to integer or remove that property.
1384    void integer(Col c, bool enable) {
1385      if (enable)
1386        colType(c,INT);
1387      else
1388        colType(c,REAL);
1389    }
1390
1391    ///Gives back whether the type of the column is integer or not.
1392    ///
1393    ///Gives back the type of the column.
1394    ///\return true if the column has integer type and false if not.
1395    bool integer(Col c){
1396      return (colType(c)==INT);
1397    }
1398
1399    /// The status of the MIP problem
1400    SolutionStatus mipStatus() {
1401      return _getMipStatus();
1402    }
1403
1404  protected:
1405
1406    virtual ColTypes _colType(int col) = 0;
1407    virtual void _colType(int col, ColTypes col_type) = 0;
1408    virtual SolutionStatus _getMipStatus()=0;
1409
1410  };
1411 
1412  ///\relates LpSolverBase::Expr
1413  ///
1414  inline LpSolverBase::Expr operator+(const LpSolverBase::Expr &a,
1415                                      const LpSolverBase::Expr &b)
1416  {
1417    LpSolverBase::Expr tmp(a);
1418    tmp+=b;
1419    return tmp;
1420  }
1421  ///\e
1422 
1423  ///\relates LpSolverBase::Expr
1424  ///
1425  inline LpSolverBase::Expr operator-(const LpSolverBase::Expr &a,
1426                                      const LpSolverBase::Expr &b)
1427  {
1428    LpSolverBase::Expr tmp(a);
1429    tmp-=b;
1430    return tmp;
1431  }
1432  ///\e
1433 
1434  ///\relates LpSolverBase::Expr
1435  ///
1436  inline LpSolverBase::Expr operator*(const LpSolverBase::Expr &a,
1437                                      const LpSolverBase::Value &b)
1438  {
1439    LpSolverBase::Expr tmp(a);
1440    tmp*=b;
1441    return tmp;
1442  }
1443 
1444  ///\e
1445 
1446  ///\relates LpSolverBase::Expr
1447  ///
1448  inline LpSolverBase::Expr operator*(const LpSolverBase::Value &a,
1449                                      const LpSolverBase::Expr &b)
1450  {
1451    LpSolverBase::Expr tmp(b);
1452    tmp*=a;
1453    return tmp;
1454  }
1455  ///\e
1456 
1457  ///\relates LpSolverBase::Expr
1458  ///
1459  inline LpSolverBase::Expr operator/(const LpSolverBase::Expr &a,
1460                                      const LpSolverBase::Value &b)
1461  {
1462    LpSolverBase::Expr tmp(a);
1463    tmp/=b;
1464    return tmp;
1465  }
1466 
1467  ///\e
1468 
1469  ///\relates LpSolverBase::Constr
1470  ///
1471  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1472                                         const LpSolverBase::Expr &f)
1473  {
1474    return LpSolverBase::Constr(-LpSolverBase::INF,e-f,0);
1475  }
1476
1477  ///\e
1478 
1479  ///\relates LpSolverBase::Constr
1480  ///
1481  inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &e,
1482                                         const LpSolverBase::Expr &f)
1483  {
1484    return LpSolverBase::Constr(e,f);
1485  }
1486
1487  ///\e
1488 
1489  ///\relates LpSolverBase::Constr
1490  ///
1491  inline LpSolverBase::Constr operator<=(const LpSolverBase::Expr &e,
1492                                         const LpSolverBase::Value &f)
1493  {
1494    return LpSolverBase::Constr(e,f);
1495  }
1496
1497  ///\e
1498 
1499  ///\relates LpSolverBase::Constr
1500  ///
1501  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1502                                         const LpSolverBase::Expr &f)
1503  {
1504    return LpSolverBase::Constr(-LpSolverBase::INF,f-e,0);
1505  }
1506
1507
1508  ///\e
1509 
1510  ///\relates LpSolverBase::Constr
1511  ///
1512  inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &e,
1513                                         const LpSolverBase::Expr &f)
1514  {
1515    return LpSolverBase::Constr(f,e);
1516  }
1517
1518
1519  ///\e
1520 
1521  ///\relates LpSolverBase::Constr
1522  ///
1523  inline LpSolverBase::Constr operator>=(const LpSolverBase::Expr &e,
1524                                         const LpSolverBase::Value &f)
1525  {
1526    return LpSolverBase::Constr(f,e);
1527  }
1528
1529  ///\e
1530
1531  ///\relates LpSolverBase::Constr
1532  ///
1533  inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
1534                                         const LpSolverBase::Value &f)
1535  {
1536    return LpSolverBase::Constr(f,e,f);
1537  }
1538
1539  ///\e
1540 
1541  ///\relates LpSolverBase::Constr
1542  ///
1543  inline LpSolverBase::Constr operator==(const LpSolverBase::Expr &e,
1544                                         const LpSolverBase::Expr &f)
1545  {
1546    return LpSolverBase::Constr(0,e-f,0);
1547  }
1548
1549  ///\e
1550 
1551  ///\relates LpSolverBase::Constr
1552  ///
1553  inline LpSolverBase::Constr operator<=(const LpSolverBase::Value &n,
1554                                         const LpSolverBase::Constr&c)
1555  {
1556    LpSolverBase::Constr tmp(c);
1557    ///\todo Create an own exception type.
1558    if(!LpSolverBase::isNaN(tmp.lowerBound())) throw LogicError();
1559    else tmp.lowerBound()=n;
1560    return tmp;
1561  }
1562  ///\e
1563 
1564  ///\relates LpSolverBase::Constr
1565  ///
1566  inline LpSolverBase::Constr operator<=(const LpSolverBase::Constr& c,
1567                                         const LpSolverBase::Value &n)
1568  {
1569    LpSolverBase::Constr tmp(c);
1570    ///\todo Create an own exception type.
1571    if(!LpSolverBase::isNaN(tmp.upperBound())) throw LogicError();
1572    else tmp.upperBound()=n;
1573    return tmp;
1574  }
1575
1576  ///\e
1577 
1578  ///\relates LpSolverBase::Constr
1579  ///
1580  inline LpSolverBase::Constr operator>=(const LpSolverBase::Value &n,
1581                                         const LpSolverBase::Constr&c)
1582  {
1583    LpSolverBase::Constr tmp(c);
1584    ///\todo Create an own exception type.
1585    if(!LpSolverBase::isNaN(tmp.upperBound())) throw LogicError();
1586    else tmp.upperBound()=n;
1587    return tmp;
1588  }
1589  ///\e
1590 
1591  ///\relates LpSolverBase::Constr
1592  ///
1593  inline LpSolverBase::Constr operator>=(const LpSolverBase::Constr& c,
1594                                         const LpSolverBase::Value &n)
1595  {
1596    LpSolverBase::Constr tmp(c);
1597    ///\todo Create an own exception type.
1598    if(!LpSolverBase::isNaN(tmp.lowerBound())) throw LogicError();
1599    else tmp.lowerBound()=n;
1600    return tmp;
1601  }
1602
1603  ///\e
1604 
1605  ///\relates LpSolverBase::DualExpr
1606  ///
1607  inline LpSolverBase::DualExpr operator+(const LpSolverBase::DualExpr &a,
1608                                          const LpSolverBase::DualExpr &b)
1609  {
1610    LpSolverBase::DualExpr tmp(a);
1611    tmp+=b;
1612    return tmp;
1613  }
1614  ///\e
1615 
1616  ///\relates LpSolverBase::DualExpr
1617  ///
1618  inline LpSolverBase::DualExpr operator-(const LpSolverBase::DualExpr &a,
1619                                          const LpSolverBase::DualExpr &b)
1620  {
1621    LpSolverBase::DualExpr tmp(a);
1622    tmp-=b;
1623    return tmp;
1624  }
1625  ///\e
1626 
1627  ///\relates LpSolverBase::DualExpr
1628  ///
1629  inline LpSolverBase::DualExpr operator*(const LpSolverBase::DualExpr &a,
1630                                          const LpSolverBase::Value &b)
1631  {
1632    LpSolverBase::DualExpr tmp(a);
1633    tmp*=b;
1634    return tmp;
1635  }
1636 
1637  ///\e
1638 
1639  ///\relates LpSolverBase::DualExpr
1640  ///
1641  inline LpSolverBase::DualExpr operator*(const LpSolverBase::Value &a,
1642                                          const LpSolverBase::DualExpr &b)
1643  {
1644    LpSolverBase::DualExpr tmp(b);
1645    tmp*=a;
1646    return tmp;
1647  }
1648  ///\e
1649 
1650  ///\relates LpSolverBase::DualExpr
1651  ///
1652  inline LpSolverBase::DualExpr operator/(const LpSolverBase::DualExpr &a,
1653                                          const LpSolverBase::Value &b)
1654  {
1655    LpSolverBase::DualExpr tmp(a);
1656    tmp/=b;
1657    return tmp;
1658  }
1659 
1660
1661} //namespace lemon
1662
1663#endif //LEMON_LP_BASE_H
Note: See TracBrowser for help on using the repository browser.