COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lin_expr.h @ 1264:92ba3e62825d

Last change on this file since 1264:92ba3e62825d was 1264:92ba3e62825d, checked in by Alpar Juttner, 15 years ago

Constraints (expressions containing <= or >=) can be passed to addRow()
and setRow()

File size: 11.2 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/lin_expr.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_LIN_EXPR_H
18#define LEMON_LIN_EXPR_H
19
20#include<vector>
21#include<map>
22#include<lemon/utility.h>
23///\file
24///\brief Classes to handle linear expressions
25namespace lemon {
26 
27  /// Class to handle sparse linear expressions
28  template <class _V>
29  class SparseLinExpr : public std::map<_V, typename _V::ExprValue>
30  {
31  public:
32    typedef _V Var;
33    typedef typename _V::ExprValue Coeff;
34   
35  protected:
36    typedef typename std::map<_V, typename _V::ExprValue> Base;
37
38    Coeff const_comp;
39  public:
40    typedef True IsLinExpression;
41    ///\e
42    SparseLinExpr() : Base(), const_comp(0) { }
43    ///\e
44    SparseLinExpr(const Var &v) : const_comp(0) {
45      Base::insert(std::make_pair(v, 1));
46    }
47    ///\e
48    SparseLinExpr(const Coeff &v) : const_comp(v) {}
49   
50    ///\e
51    void set(const Var &v,const Coeff &c) {
52      return Base::insert(std::make_pair(v, c));
53    }
54//     Coeff &operator[](const Var &v) { return data[v]; }
55//     const Coeff &operator[](const Var &v) const { return data[v]; }
56
57    ///\e
58    Coeff &constComp() { return const_comp; }
59    ///\e
60    const Coeff &constComp() const { return const_comp; }
61
62    ///Removes the components with zero coefficient.
63    void simplify() {
64      for (typename Base::iterator i=Base::begin(); i!=Base::end();) {
65        typename Base::iterator j=i;
66        ++j;
67        if ((*i).second==0) Base::erase(i);
68        j=i;
69      }
70    }
71   
72    ///\e
73    SparseLinExpr &operator+=(const SparseLinExpr &e) {
74      for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
75        (*this)[j->first]+=j->second;
76      ///\todo it might be speeded up using "hints"
77      const_comp+=e.const_comp;
78      return *this;
79    }
80    ///\e
81    SparseLinExpr &operator-=(const SparseLinExpr &e) {
82      for (typename Base::const_iterator j=e.begin(); j!=e.end(); ++j)
83        (*this)[j->first]-=j->second;
84      const_comp-=e.const_comp;
85      return *this;
86    }
87    ///\e
88    SparseLinExpr &operator*=(const Coeff &c) {
89      for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
90        j->second*=c;
91      const_comp*=c;
92      return *this;
93    }
94    ///\e
95    SparseLinExpr &operator/=(const Coeff &c) {
96      for (typename Base::iterator j=Base::begin(); j!=Base::end(); ++j)
97        j->second/=c;
98      const_comp/=c;
99      return *this;
100    }
101   
102  };
103
104  ///\e
105 
106  ///\relates SparseLinExpr
107  ///
108  template <class V>
109  SparseLinExpr<V> operator+(const SparseLinExpr<V> &a,
110                                const SparseLinExpr<V> &b) {
111    SparseLinExpr<V> tmp(a);
112    tmp+=b; ///\todo Don't STL have some special 'merge' algorithm?
113    return tmp;
114  }
115 
116  ///\e
117 
118  ///\relates SparseLinExpr
119  ///
120  template <class V>
121  SparseLinExpr<V> operator-(const SparseLinExpr<V> &a,
122                                const SparseLinExpr<V> &b) {
123    SparseLinExpr<V> tmp(a);
124    tmp-=b; ///\todo Don't STL have some special 'merge' algorithm?
125    return tmp;
126  }
127 
128  ///\e
129 
130  ///\relates SparseLinExpr
131  ///
132  template <class V>
133  SparseLinExpr<V> operator*(const typename V::ExprValue &c,
134                               const SparseLinExpr<V> &e) {
135    SparseLinExpr<V> tmp(e);
136    tmp*=c;
137    return tmp;
138  }
139 
140  ///\e
141 
142  ///\relates SparseLinExpr
143  ///
144  template <class V>
145  SparseLinExpr<V> operator*(const SparseLinExpr<V> &e,
146                               const typename V::ExprValue &c) {
147    SparseLinExpr<V> tmp(e);
148    tmp*=c;
149    return tmp;
150  }
151 
152 
153  ///\e
154 
155  ///\relates SparseLinExpr
156  ///
157  template <class V>
158  SparseLinExpr<V> operator/(const SparseLinExpr<V> &e,
159                               const typename V::ExprValue &c) {
160    SparseLinExpr<V> tmp(e);
161    tmp/=c;
162    return tmp;
163  }
164 
165  ///\e
166 
167  ///\relates SparseLinExpr
168  ///
169  template <class V>
170  SparseLinExpr<V> operator+(const typename V::ExprValue &c,
171                             const SparseLinExpr<V> &e) {
172    SparseLinExpr<V> tmp(e);
173    tmp.constComp()+=c;
174    return tmp;
175  }
176
177  ///\e
178 
179  ///\relates SparseLinExpr
180  ///
181  template <class V>
182  SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,
183                             const typename V::ExprValue &c) {
184    SparseLinExpr<V> tmp(e);
185    tmp.constComp()+=c;
186    return tmp;
187  }
188
189  ///\e
190 
191  ///\relates SparseLinExpr
192  ///
193  template <class V>
194  SparseLinExpr<V> operator+(const V &v,const SparseLinExpr<V> &e) {
195    SparseLinExpr<V> tmp(e);
196    tmp[v]+=1;
197    return tmp;
198  }
199
200  ///\e
201 
202  ///\relates SparseLinExpr
203  ///
204  template <class V>
205  SparseLinExpr<V> operator+(const SparseLinExpr<V> &e,const V &v) {
206    SparseLinExpr<V> tmp(e);
207    tmp[v]+=1;
208    return tmp;
209  }
210
211  ///\e
212 
213  ///\relates SparseLinExpr
214  ///
215  template <class V>
216  SparseLinExpr<V> operator-(const typename V::ExprValue &c,
217                             const SparseLinExpr<V> &e) {
218    SparseLinExpr<V> tmp(e);
219    tmp*=-1;
220    tmp.constComp()+=c;
221    return tmp;
222  }
223
224  ///\e
225 
226  ///\relates SparseLinExpr
227  ///
228  template <class V>
229  SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,
230                             const typename V::ExprValue &c) {
231    SparseLinExpr<V> tmp(e);
232    tmp.constComp()-=c;
233    return tmp;
234  }
235
236  ///\e
237 
238  ///\relates SparseLinExpr
239  ///
240  template <class V>
241  SparseLinExpr<V> operator-(const V &v,const SparseLinExpr<V> &e) {
242    SparseLinExpr<V> tmp(e);
243    tmp*=-1;
244    tmp[v]+=1;
245    return tmp;
246  }
247
248  ///\e
249 
250  ///\relates SparseLinExpr
251  ///
252  template <class V>
253  SparseLinExpr<V> operator-(const SparseLinExpr<V> &e,const V &v) {
254    SparseLinExpr<V> tmp(e);
255    tmp[v]-=1;
256    return tmp;
257  }
258
259  ///\e
260 
261  ///\relates SparseLinExpr
262  ///
263  template <class V>
264  SparseLinExpr<V> operator+(const V &v,const typename V::ExprValue &c) {
265    SparseLinExpr<V> tmp(v);
266    tmp.constComp()=c;
267    return tmp;
268  }
269
270  ///\e
271 
272  ///\relates SparseLinExpr
273  ///
274  template <class V>
275  SparseLinExpr<V> operator-(const V &v,const typename V::ExprValue &c) {
276    SparseLinExpr<V> tmp(v);
277    tmp.constComp()=-c;
278    return tmp;
279  }
280
281  ///\e
282 
283  ///\relates SparseLinExpr
284  ///
285  template <class V>
286  SparseLinExpr<V> operator+(const typename V::ExprValue &c,const V &v) {
287    SparseLinExpr<V> tmp(v);
288    tmp.constComp()=c;
289    return tmp;
290  }
291
292  ///\e
293 
294  ///\relates SparseLinExpr
295  ///
296  template <class V>
297  SparseLinExpr<V> operator-(const typename V::ExprValue &c,const V &v) {
298    SparseLinExpr<V> tmp(c);
299    tmp[v]=-1;
300    return tmp;
301  }
302
303  ///\e
304 
305  ///\relates SparseLinExpr
306  ///
307  template <class V>
308  SparseLinExpr<V> operator+(const V &v1,const V &v2) {
309    SparseLinExpr<V> tmp(v1);
310    tmp[v2]+=1;
311    return tmp;
312  }
313
314  ///\e
315 
316  ///\relates SparseLinExpr
317  ///
318  template <class V>
319  SparseLinExpr<V> operator*(const V &v,const typename V::ExprValue &c) {
320    SparseLinExpr<V> tmp;
321    tmp[v]=c;
322    return tmp;
323  }
324
325  ///\e
326 
327  ///\relates SparseLinExpr
328  ///
329  template <class V>
330  SparseLinExpr<V> operator*(const typename V::ExprValue &c,const V &v) {
331    SparseLinExpr<V> tmp;
332    tmp[v]=c;
333    return tmp;
334  }
335
336  ///\e
337 
338  ///\relates SparseLinExpr
339  ///
340  template <class V>
341  SparseLinExpr<V> operator/(const V &v,const typename V::ExprValue &c) {
342    SparseLinExpr<V> tmp;
343    tmp[v]=1/c;
344    return tmp;
345  }
346
347
348  //////////////////////////////////////////////////////////////////////
349  /// Constraints
350  //////////////////////////////////////////////////////////////////////
351 
352  template <class E>
353  class LinConstr
354  {
355  public:
356    typedef E Expr;
357    typedef typename E::Var Var;
358    typedef typename E::Coeff Coeff;
359   
360    static const Coeff INF;
361    static const Coeff NaN;
362//     static const Coeff INF=0;
363//     static const Coeff NaN=1;
364
365    Expr expr;
366    Coeff lb,ub;
367   
368    LinConstr() : expr(), lb(NaN), ub(NaN) {}
369    LinConstr(Coeff _lb,const Expr &e,Coeff _ub) :
370      expr(e), lb(_lb), ub(_ub) {}
371    LinConstr(const Expr &e,Coeff _ub) :
372      expr(e), lb(NaN), ub(_ub) {}
373    LinConstr(Coeff _lb,const Expr &e) :
374      expr(e), lb(_lb), ub(NaN) {}
375  };
376
377  template<class E>
378  const typename LinConstr<E>::Coeff LinConstr<E>::INF=
379    std::numeric_limits<Coeff>::infinity();
380  template<class E>
381  const typename LinConstr<E>::Coeff LinConstr<E>::NaN=
382    std::numeric_limits<Coeff>::quiet_NaN();
383
384 
385  template<class E>
386  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
387  operator<=(const E &e,const E &f)
388  {
389    return LinConstr<E>(-LinConstr<E>::INF,e-f,0);
390  }
391
392  template<class E>
393  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
394  operator>=(const E &e,const E &f)
395  {
396    return LinConstr<E>(-LinConstr<E>::INF,f-e,0);
397  }
398
399  template<class E>
400  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
401  operator==(const E &e,const E &f)
402  {
403    return LinConstr<E>(0,e-f,0);
404  }
405 
406  //////////////////////////////
407
408  template<class E>
409  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
410  operator<=(const E &e,const typename E::Coeff &n)
411  {
412    return LinConstr<E>(e,n);
413  }
414
415  template<class E>
416  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
417  operator>=(const E &e,const typename E::Coeff &n)
418  {
419    return LinConstr<E>(n,e);
420  }
421
422  template<class E>
423  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
424  operator==(const E &e,const typename E::Coeff &n)
425  {
426    return LinConstr<E>(n,e,n);
427  }
428
429  //////////////////////////////
430
431  template<class E>
432  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
433  operator<=(const typename E::Coeff &n,const E &e)
434  {
435    return LinConstr<E>(n,e);
436  }
437
438  template<class E>
439  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
440  operator>=(const typename E::Coeff &n,const E &e)
441  {
442    return LinConstr<E>(e,n);
443  }
444
445  template<class E>
446  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
447  operator==(const typename E::Coeff &n,const E &e)
448  {
449    return LinConstr<E>(n,e,n);
450  }
451
452  //////////////////////////////
453
454  template<class E>
455  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
456  operator<=(const typename E::Coeff &n,const LinConstr<E> &c)
457  {
458    LinConstr<E> tmp(c);
459    if(tmp.lb!=tmp.NaN) throw LogicError();
460    else tmp.lb=n;
461    return tmp;
462  }
463
464  template<class E>
465  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
466  operator>=(const typename E::Coeff &n,const LinConstr<E> &c)
467  {
468    LinConstr<E> tmp(c);
469    if(tmp.ub!=tmp.NaN) throw LogicError();
470    else tmp.ub=n;
471    return tmp;
472  }
473
474  template<class E>
475  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
476  operator<=(const LinConstr<E> &c,const typename E::Coeff &n)
477  {
478    LinConstr<E> tmp(c);
479    if(tmp.ub!=tmp.NaN) throw LogicError();
480    else tmp.ub=n;
481    return tmp;
482  }
483
484  template<class E>
485  typename enable_if<typename E::IsLinExpression, LinConstr<E> >::type
486  operator>=(const LinConstr<E> &c,const typename E::Coeff &n)
487  {
488    LinConstr<E> tmp(c);
489    if(tmp.lb!=tmp.NaN) throw LogicError();
490    else tmp.lb=n;
491    return tmp;
492  }
493
494 
495
496} //namespace lemon
497
498#endif //LEMON_LIN_EXPR_H
Note: See TracBrowser for help on using the repository browser.