COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lp_base.h @ 1256:3bb4ed285c39

Last change on this file since 1256:3bb4ed285c39 was 1256:3bb4ed285c39, checked in by Alpar Juttner, 18 years ago
  • src/lemon/utility.h: dummy<> template added
  • LpSolverBase::INF is now really defined
  • AddColSet?() to add several column at once
    • using enable_if
    • with some doxygen hack
  • More doc improvements
  • Better Makefile
File size: 10.1 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/lp_base.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_LP_BASE_H
18#define LEMON_LP_BASE_H
19
20#include<vector>
21#include<limits>
22
23#include<lemon/utility.h>
24#include<lemon/error.h>
25#include<lemon/invalid.h>
26
27#include"lin_expr.h"
28///\file
29///\brief The interface of the LP solver interface.
30namespace lemon {
31 
32  ///Internal data structure to convert floating id's to fix one's
33   
34  ///\todo This might by implemented to be usable in other places.
35  class _FixId
36  {
37    std::vector<int> index;
38    std::vector<int> cross;
39    int first_free;
40  public:
41    _FixId() : first_free(-1) {};
42    ///Convert a floating id to a fix one
43
44    ///\param n is a floating id
45    ///\return the corresponding fix id
46    int fixId(int n) {return cross[n];}
47    ///Convert a fix id to a floating one
48
49    ///\param n is a fix id
50    ///\return the corresponding floating id
51    int floatingId(int n) { return index[n];}
52    ///Add a new floating id.
53
54    ///\param n is a floating id
55    ///\return the fix id of the new value
56    ///\todo Multiple additions should also be handled.
57    int insert(int n)
58    {
59      if(n>=int(cross.size())) {
60        cross.resize(n+1);
61        if(first_free==-1) {
62          cross[n]=index.size();
63          index.push_back(n);
64        }
65        else {
66          cross[n]=first_free;
67          int next=index[first_free];
68          index[first_free]=n;
69          first_free=next;
70        }
71        return cross[n];
72      }
73      else throw LogicError(); //floatingId-s must form a continuous range;
74    }
75    ///Remove a fix id.
76
77    ///\param n is a fix id
78    ///
79    void erase(int n)
80    {
81      int fl=index[n];
82      index[n]=first_free;
83      first_free=n;
84      for(int i=fl+1;i<int(cross.size());++i) {
85        cross[i-1]=cross[i];
86        index[cross[i]]--;
87      }
88      cross.pop_back();
89    }
90    ///An upper bound on the largest fix id.
91
92    ///\todo Do we need this?
93    ///
94    std::size_t maxFixId() { return cross.size()-1; }
95 
96  };
97   
98  ///Common base class for LP solvers
99  class LpSolverBase {
100   
101  public:
102
103    ///The floating point type used by the solver
104    typedef double Value;
105    ///The infinity constant
106    static const Value INF;
107   
108    ///Refer to a column of the LP.
109
110    ///This type is used to refer to a column of the LP.
111    ///
112    ///Its value remains valid and correct even after the addition or erase of
113    ///new column (unless the referred column itself was also deleted,
114    ///of course).
115    ///
116    ///\todo Document what can one do with a Col (INVALID, comparing,
117    ///it is similar to Node/Edge)
118    class Col {
119    protected:
120      int id;
121      friend class LpSolverBase;
122    public:
123      typedef True LpSolverCol;
124      Col() {}
125      Col(const Invalid&) : id(-1) {}
126      bool operator<(Col c) const  {return id<c.id;}
127      bool operator==(Col c) const  {return id==c.id;}
128      bool operator!=(Col c) const  {return id==c.id;}
129    };
130
131    ///Refer to a row of the LP.
132
133    ///This type is used to refer to a row of the LP.
134    ///
135    ///Its value remains valid and correct even after the addition or erase of
136    ///new rows (unless the referred row itself was also deleted, of course).
137    ///
138    ///\todo Document what can one do with a Row (INVALID, comparing,
139    ///it is similar to Node/Edge)
140    class Row {
141    protected:
142      int id;
143      friend class LpSolverBase;
144    public:
145      typedef True LpSolverRow;
146      Row() {}
147      Row(const Invalid&) : id(-1) {}
148      typedef True LpSolverRow;
149      bool operator<(Row c) const  {return id<c.id;}
150      bool operator==(Row c) const  {return id==c.id;}
151      bool operator!=(Row c) const  {return id==c.id;}
152   };
153
154    typedef SparseLinExpr<Col, Value> Expr;
155
156  protected:
157    _FixId rows;
158    _FixId cols;
159
160    //MATRIX MANIPULATING FUNCTIONS
161
162    /// \e
163    virtual int _addCol() = 0;
164    /// \e
165    virtual int _addRow() = 0;
166    /// \e
167
168    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
169    ///
170    virtual void _setRowCoeffs(int i,
171                               int length,
172                               int  const * indices,
173                               Value  const * values ) = 0;
174    /// \e
175
176    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
177    ///
178    virtual void _setColCoeffs(int i,
179                               int length,
180                               int  const * indices,
181                               Value  const * values ) = 0;
182   
183    /// \e
184
185    /// The lower bound of a variable (column) have to be given by an
186    /// extended number of type Value, i.e. a finite number of type
187    /// Value or -INF.
188    virtual void _setColLowerBound(int i, Value value) = 0;
189    /// \e
190
191    /// The upper bound of a variable (column) have to be given by an
192    /// extended number of type Value, i.e. a finite number of type
193    /// Value or INF.
194    virtual void _setColUpperBound(int i, Value value) = 0;
195    /// \e
196
197    /// The lower bound of a linear expression (row) have to be given by an
198    /// extended number of type Value, i.e. a finite number of type
199    /// Value or -INF.
200    virtual void _setRowLowerBound(int i, Value value) = 0;
201    /// \e
202
203    /// The upper bound of a linear expression (row) have to be given by an
204    /// extended number of type Value, i.e. a finite number of type
205    /// Value or INF.
206    virtual void _setRowUpperBound(int i, Value value) = 0;
207
208    /// \e
209    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
210
211    ///\e
212
213    ///\bug unimplemented!!!!
214    void clearObj() {}
215  public:
216
217
218    ///\e
219    virtual ~LpSolverBase() {}
220
221    ///Add a new empty column (i.e a new variable) to the LP
222    Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
223    ///\brief Fill the elements of a container with newly created columns
224    ///(i.e a new variables)
225    ///
226    ///This magic function takes container as its argument
227    ///and fills its elements
228    ///with new columns (i.e. variables)
229    ///\param t can be either any standard STL iterable container with
230    ///\ref Col \c values_type or \c mapped_type
231    ///like <tt>std::vector<LpSolverBase::Col></tt>,
232    /// <tt>std::list<LpSolverBase::Col></tt> or
233    /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or
234    ///it can be an iterable lemon map like
235    /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>.
236    ///\return The number of the created column.
237    ///\bug Iterable nodemap hasn't been implemented yet.
238#ifdef DOXYGEN
239    template<class T>
240    int addColSet(T &t) { return 0;}
241#else
242    template<class T>
243    typename enable_if<typename T::value_type::LpSolverCol,int>::type
244    addColSet(T &t,dummy<0> = 0) {
245      int s=0;
246      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
247      return s;
248    }
249    template<class T>
250    typename enable_if<typename T::value_type::second_type::LpSolverCol,
251                       int>::type
252    addColSet(T &t,dummy<1> = 1) {
253      int s=0;
254      for(typename T::iterator i=t.begin();i!=t.end();++i) {
255        i->second=addCol();
256        s++;
257      }
258      return s;
259    }
260#endif
261    ///Add a new empty row (i.e a new constaint) to the LP
262    Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
263
264    ///Add a new row (i.e a new constaint) to the LP
265
266    ///\param l lower bound (-INF means no bound)
267    ///\param e a linear expression (see \ref Expr)
268    ///\param u upper bound (INF means no bound)
269    ///\bug This is a temportary function. The interface will change to
270    ///a better one.
271    Row addRow(Value l,Expr e, Value u) {
272      Row r=addRow();
273      std::vector<int> indices;
274      std::vector<Value> values;
275      indices.push_back(0);
276      values.push_back(0);
277      for(Expr::iterator i=e.begin(); i!=e.end(); ++i)
278        if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
279          indices.push_back(cols.floatingId((*i).first.id));
280          values.push_back((*i).second);
281        }
282      _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
283                    &indices[0],&values[0]);
284      _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
285      _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
286      return r;
287    }
288
289    /// Set the lower bound of a column (i.e a variable)
290
291    /// The upper bound of a variable (column) have to be given by an
292    /// extended number of type Value, i.e. a finite number of type
293    /// Value or -INF.
294    virtual void setColLowerBound(Col c, Value value) {
295      _setColLowerBound(cols.floatingId(c.id),value);
296    }
297    /// Set the upper bound of a column (i.e a variable)
298
299    /// The upper bound of a variable (column) have to be given by an
300    /// extended number of type Value, i.e. a finite number of type
301    /// Value or INF.
302    virtual void setColUpperBound(Col c, Value value) {
303      _setColUpperBound(cols.floatingId(c.id),value);
304    };
305    /// Set the lower bound of a row (i.e a constraint)
306
307    /// The lower bound of a linear expression (row) have to be given by an
308    /// extended number of type Value, i.e. a finite number of type
309    /// Value or -INF.
310    virtual void setRowLowerBound(Row r, Value value) {
311      _setRowLowerBound(rows.floatingId(r.id),value);
312    };
313    /// Set the upper bound of a row (i.e a constraint)
314
315    /// The upper bound of a linear expression (row) have to be given by an
316    /// extended number of type Value, i.e. a finite number of type
317    /// Value or INF.
318    virtual void setRowUpperBound(Row r, Value value) {
319      _setRowUpperBound(rows.floatingId(r.id),value);
320    };
321    ///Set an element of the objective function
322    void setObjCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
323    ///Set the objective function
324   
325    ///\param e is a linear expression of type \ref Expr.
326    ///\todo What to do with the constant component?
327    void setObj(Expr e) {
328      clearObj();
329      for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
330        setObjCoeff((*i).first,(*i).second);
331    }
332   
333  }; 
334
335} //namespace lemon
336
337#endif //LEMON_LP_BASE_H
Note: See TracBrowser for help on using the repository browser.