COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lp_base.h @ 1259:11a09f1319b3

Last change on this file since 1259:11a09f1319b3 was 1259:11a09f1319b3, checked in by Alpar Juttner, 15 years ago
  • Largely extended linear expressions
  • Better docs
File size: 10.9 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 Value ExprValue;
124      typedef True LpSolverCol;
125      Col() {}
126      Col(const Invalid&) : id(-1) {}
127      bool operator<(Col c) const  {return id<c.id;}
128      bool operator==(Col c) const  {return id==c.id;}
129      bool operator!=(Col c) const  {return id==c.id;}
130    };
131
132    ///Refer to a row of the LP.
133
134    ///This type is used to refer to a row of the LP.
135    ///
136    ///Its value remains valid and correct even after the addition or erase of
137    ///new rows (unless the referred row itself was also deleted, of course).
138    ///
139    ///\todo Document what can one do with a Row (INVALID, comparing,
140    ///it is similar to Node/Edge)
141    class Row {
142    protected:
143      int id;
144      friend class LpSolverBase;
145    public:
146      typedef Value ExprValue;
147      typedef True LpSolverRow;
148      Row() {}
149      Row(const Invalid&) : id(-1) {}
150      typedef True LpSolverRow;
151      bool operator<(Row c) const  {return id<c.id;}
152      bool operator==(Row c) const  {return id==c.id;}
153      bool operator!=(Row c) const  {return id==c.id;}
154   };
155   
156    ///Linear expression
157    typedef SparseLinExpr<Col> Expr;
158
159  protected:
160    _FixId rows;
161    _FixId cols;
162
163    //MATRIX MANIPULATING FUNCTIONS
164
165    /// \e
166    virtual int _addCol() = 0;
167    /// \e
168    virtual int _addRow() = 0;
169    /// \e
170
171    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
172    ///
173    virtual void _setRowCoeffs(int i,
174                               int length,
175                               int  const * indices,
176                               Value  const * values ) = 0;
177    /// \e
178
179    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
180    ///
181    virtual void _setColCoeffs(int i,
182                               int length,
183                               int  const * indices,
184                               Value  const * values ) = 0;
185   
186    /// \e
187
188    /// The lower bound of a variable (column) have to be given by an
189    /// extended number of type Value, i.e. a finite number of type
190    /// Value or -\ref INF.
191    virtual void _setColLowerBound(int i, Value value) = 0;
192    /// \e
193
194    /// The upper bound of a variable (column) have to be given by an
195    /// extended number of type Value, i.e. a finite number of type
196    /// Value or \ref INF.
197    virtual void _setColUpperBound(int i, Value value) = 0;
198    /// \e
199
200    /// The lower bound of a linear expression (row) have to be given by an
201    /// extended number of type Value, i.e. a finite number of type
202    /// Value or -\ref INF.
203    virtual void _setRowLowerBound(int i, Value value) = 0;
204    /// \e
205
206    /// The upper bound of a linear expression (row) have to be given by an
207    /// extended number of type Value, i.e. a finite number of type
208    /// Value or \ref INF.
209    virtual void _setRowUpperBound(int i, Value value) = 0;
210
211    /// \e
212    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
213
214    ///\e
215
216    ///\bug unimplemented!!!!
217    void clearObj() {}
218  public:
219
220
221    ///\e
222    virtual ~LpSolverBase() {}
223
224    ///Add a new empty column (i.e a new variable) to the LP
225    Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
226    ///\brief Fill the elements of a container with newly created columns
227    ///(i.e a new variables)
228    ///
229    ///This magic function takes container as its argument
230    ///and fills its elements
231    ///with new columns (i.e. variables)
232    ///\param t can be either any standard STL iterable container with
233    ///\ref Col \c values_type or \c mapped_type
234    ///like <tt>std::vector<LpSolverBase::Col></tt>,
235    /// <tt>std::list<LpSolverBase::Col></tt> or
236    /// <tt>std::map<AnyType,LpSolverBase::Col></tt> or
237    ///it can be an iterable lemon map like
238    /// <tt>ListGraph::NodeMap<LpSolverBase::Col></tt>.
239    ///\return The number of the created column.
240    ///\bug Iterable nodemap hasn't been implemented yet.
241#ifdef DOXYGEN
242    template<class T>
243    int addColSet(T &t) { return 0;}
244#else
245    template<class T>
246    typename enable_if<typename T::value_type::LpSolverCol,int>::type
247    addColSet(T &t,dummy<0> = 0) {
248      int s=0;
249      for(typename T::iterator i=t.begin();i!=t.end();++i) {*i=addCol();s++;}
250      return s;
251    }
252    template<class T>
253    typename enable_if<typename T::value_type::second_type::LpSolverCol,
254                       int>::type
255    addColSet(T &t,dummy<1> = 1) {
256      int s=0;
257      for(typename T::iterator i=t.begin();i!=t.end();++i) {
258        i->second=addCol();
259        s++;
260      }
261      return s;
262    }
263#endif
264    ///Add a new empty row (i.e a new constaint) to the LP
265
266    ///This function adds a new empty row (i.e a new constaint) to the LP.
267    ///\return The created row
268    Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
269
270    ///Set a row (i.e a constaint) of the LP
271
272    ///\param r is the row to be modified
273    ///\param l is lower bound (-\ref INF means no bound)
274    ///\param e is a linear expression (see \ref Expr)
275    ///\param u is the upper bound (\ref INF means no bound)
276    ///\bug This is a temportary function. The interface will change to
277    ///a better one.
278    void setRow(Row r, Value l,const Expr &e, Value u) {
279      std::vector<int> indices;
280      std::vector<Value> values;
281      indices.push_back(0);
282      values.push_back(0);
283      for(Expr::const_iterator i=e.begin(); i!=e.end(); ++i)
284        if((*i).second!=0) { ///\bug EPSILON would be necessary here!!!
285          indices.push_back(cols.floatingId((*i).first.id));
286          values.push_back((*i).second);
287        }
288      _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
289                    &indices[0],&values[0]);
290      _setRowLowerBound(rows.floatingId(r.id),l-e.constComp());
291      _setRowUpperBound(rows.floatingId(r.id),u-e.constComp());
292    }
293
294    ///Add a new row (i.e a new constaint) to the LP
295
296    ///\param l is the lower bound (-\ref INF means no bound)
297    ///\param e is a linear expression (see \ref Expr)
298    ///\param u is the upper bound (\ref INF means no bound)
299    ///\return The created row.
300    ///\bug This is a temportary function. The interface will change to
301    ///a better one.
302    Row addRow(Value l,const Expr &e, Value u) {
303      Row r=addRow();
304      setRow(r,l,e,u);
305      return r;
306    }
307
308    /// Set the lower bound of a column (i.e a variable)
309
310    /// The upper bound of a variable (column) have to be given by an
311    /// extended number of type Value, i.e. a finite number of type
312    /// Value or -\ref INF.
313    virtual void setColLowerBound(Col c, Value value) {
314      _setColLowerBound(cols.floatingId(c.id),value);
315    }
316    /// Set the upper bound of a column (i.e a variable)
317
318    /// The upper bound of a variable (column) have to be given by an
319    /// extended number of type Value, i.e. a finite number of type
320    /// Value or \ref INF.
321    virtual void setColUpperBound(Col c, Value value) {
322      _setColUpperBound(cols.floatingId(c.id),value);
323    };
324    /// Set the lower bound of a row (i.e a constraint)
325
326    /// The lower bound of a linear expression (row) have to be given by an
327    /// extended number of type Value, i.e. a finite number of type
328    /// Value or -\ref INF.
329    virtual void setRowLowerBound(Row r, Value value) {
330      _setRowLowerBound(rows.floatingId(r.id),value);
331    };
332    /// Set the upper bound of a row (i.e a constraint)
333
334    /// The upper bound of a linear expression (row) have to be given by an
335    /// extended number of type Value, i.e. a finite number of type
336    /// Value or \ref INF.
337    virtual void setRowUpperBound(Row r, Value value) {
338      _setRowUpperBound(rows.floatingId(r.id),value);
339    };
340    ///Set an element of the objective function
341    void setObjCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
342    ///Set the objective function
343   
344    ///\param e is a linear expression of type \ref Expr.
345    ///\todo What to do with the constant component?
346    void setObj(Expr e) {
347      clearObj();
348      for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
349        setObjCoeff((*i).first,(*i).second);
350    }
351   
352  }; 
353
354} //namespace lemon
355
356#endif //LEMON_LP_BASE_H
Note: See TracBrowser for help on using the repository browser.