COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lp_base.h @ 1263:a490938ad0aa

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