COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/lp_base.h @ 2431:51f4a390e3e5

Last change on this file since 2431:51f4a390e3e5 was 2431:51f4a390e3e5, checked in by Akos Ladanyi, 13 years ago

fix to compile with gcc 4.1.2

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