COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lp_base.h @ 1271:40e5d0d44a65

Last change on this file since 1271:40e5d0d44a65 was 1264:92ba3e62825d, checked in by Alpar Juttner, 19 years ago

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

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