COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lp_base.h @ 1258:88dff8bb4bf2

Last change on this file since 1258:88dff8bb4bf2 was 1258:88dff8bb4bf2, checked in by Alpar Juttner, 15 years ago
  • setRow() added
  • more docs
File size: 10.7 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
263    ///This function adds a new empty row (i.e a new constaint) to the LP.
264    ///\return The created row
265    Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
266
267    ///Set a row (i.e a constaint) of the LP
268
269    ///\param r is the row to be modified
270    ///\param l is lower bound (-INF means no bound)
271    ///\param e is a linear expression (see \ref Expr)
272    ///\param u is the upper bound (INF means no bound)
273    ///\bug This is a temportary function. The interface will change to
274    ///a better one.
275    void setRow(Row r, Value l,const Expr &e, Value u) {
276      std::vector<int> indices;
277      std::vector<Value> values;
278      indices.push_back(0);
279      values.push_back(0);
280      for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
281        if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
282          indices.push_back(cols.floatingId((*i).first.id));
283          values.push_back((*i).second);
284        }
285      _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
286                    &indices[0],&values[0]);
287      _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
288      _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
289    }
290
291    ///Add a new row (i.e a new constaint) to the LP
292
293    ///\param l is the lower bound (-INF means no bound)
294    ///\param e is a linear expression (see \ref Expr)
295    ///\param u is the upper bound (INF means no bound)
296    ///\return The created row.
297    ///\bug This is a temportary function. The interface will change to
298    ///a better one.
299    Row addRow(Value l,const Expr &e, Value u) {
300      Row r=addRow();
301      setRow(r,l,e,u);
302      return r;
303    }
304
305    /// Set the lower bound of a column (i.e a variable)
306
307    /// The upper bound of a variable (column) 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 setColLowerBound(Col c, Value value) {
311      _setColLowerBound(cols.floatingId(c.id),value);
312    }
313    /// Set the upper bound of a column (i.e a variable)
314
315    /// The upper bound of a variable (column) 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 setColUpperBound(Col c, Value value) {
319      _setColUpperBound(cols.floatingId(c.id),value);
320    };
321    /// Set the lower bound of a row (i.e a constraint)
322
323    /// The lower bound of a linear expression (row) have to be given by an
324    /// extended number of type Value, i.e. a finite number of type
325    /// Value or -INF.
326    virtual void setRowLowerBound(Row r, Value value) {
327      _setRowLowerBound(rows.floatingId(r.id),value);
328    };
329    /// Set the upper bound of a row (i.e a constraint)
330
331    /// The upper bound of a linear expression (row) have to be given by an
332    /// extended number of type Value, i.e. a finite number of type
333    /// Value or INF.
334    virtual void setRowUpperBound(Row r, Value value) {
335      _setRowUpperBound(rows.floatingId(r.id),value);
336    };
337    ///Set an element of the objective function
338    void setObjCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
339    ///Set the objective function
340   
341    ///\param e is a linear expression of type \ref Expr.
342    ///\todo What to do with the constant component?
343    void setObj(Expr e) {
344      clearObj();
345      for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
346        setObjCoeff((*i).first,(*i).second);
347    }
348   
349  }; 
350
351} //namespace lemon
352
353#endif //LEMON_LP_BASE_H
Note: See TracBrowser for help on using the repository browser.