COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/lp/lp_base.h @ 1253:609fe893df8c

Last change on this file since 1253:609fe893df8c was 1253:609fe893df8c, checked in by Alpar Juttner, 18 years ago
  • simple makefile added
  • _FixId class added (more clarification needed)
  • LinExpr? class added
  • some higher level interfaces added to LpSolverBase?
  • minor corrections
File size: 7.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
22#include<lemon/error.h>
23
24#include"lin_expr.h"
25///\file
26///\brief The interface of the LP solver interface.
27namespace lemon {
28 
29  ///Internal data structure to convert floating id's to fix one's
30   
31  ///\todo This might by implemented to be usable in other places.
32  class _FixId
33  {
34    std::vector<int> index;
35    std::vector<int> cross;
36    int first_free;
37  public:
38    _FixId() : first_free(-1) {};
39    ///Convert a floating id to a fix one
40
41    ///\param n is a floating id
42    ///\return the corresponding fix id
43    int fixId(int n) {return cross[n];}
44    ///Convert a fix id to a floating one
45
46    ///\param n is a fix id
47    ///\return the corresponding floating id
48    int floatingId(int n) { return index[n];}
49    ///Add a new floating id.
50
51    ///\param n is a floating id
52    ///\return the fix id of the new value
53    ///\todo Multiple additions should also be handled.
54    int insert(int n)
55    {
56      if(n>=int(cross.size())) {
57        cross.resize(n+1);
58        if(first_free==-1) {
59          cross[n]=index.size();
60          index.push_back(n);
61        }
62        else {
63          cross[n]=first_free;
64          int next=index[first_free];
65          index[first_free]=n;
66          first_free=next;
67        }
68      }
69      else throw LogicError(); //floatingId-s must form a continuous range;
70    }
71    ///Remove a fix id.
72
73    ///\param n is a fix id
74    ///
75    void erase(int n)
76    {
77      int fl=index[n];
78      index[n]=first_free;
79      first_free=n;
80      for(int i=fl+1;i<int(cross.size());++i) {
81        cross[i-1]=cross[i];
82        index[cross[i]]--;
83      }
84      cross.pop_back();
85    }
86    ///An upper bound on the largest fix id.
87
88    ///\todo Do we need this?
89    ///
90    std::size_t maxFixId() { return cross.size()-1; }
91 
92  };
93   
94  ///Common base class for LP solvers
95  class LpSolverBase {
96   
97  public:
98
99    /// \e
100    typedef double Value;
101    /// \e
102    static const Value INF;
103   
104    ///\e
105    class Col { protected: int id; friend class LpSolverBase; };
106    ///\e
107    class Row { protected: int id; friend class LpSolverBase; };
108
109    typedef SparseLinExpr<Col, Value> Expr;
110
111  protected:
112    _FixId rows;
113    _FixId cols;
114
115    //MATRIX MANIPULATING FUNCTIONS
116
117    /// \e
118    virtual int _addCol() = 0;
119    /// \e
120    virtual int _addRow() = 0;
121    /// \e
122
123    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
124    ///
125    virtual void _setRowCoeffs(int i,
126                               int length,
127                               int  const * indices,
128                               Value  const * values ) = 0;
129    /// \e
130
131    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
132    ///
133    virtual void _setColCoeffs(int i,
134                               int length,
135                               int  const * indices,
136                               Value  const * values ) = 0;
137   
138    /// \e
139
140    /// The lower bound of a variable (column) have to be given by an
141    /// extended number of type Value, i.e. a finite number of type
142    /// Value or -INF.
143    virtual void _setColLowerBound(int i, Value value) = 0;
144    /// \e
145
146    /// The upper bound of a variable (column) have to be given by an
147    /// extended number of type Value, i.e. a finite number of type
148    /// Value or INF.
149    virtual void _setColUpperBound(int i, Value value) = 0;
150    /// \e
151
152    /// The lower bound of a linear expression (row) have to be given by an
153    /// extended number of type Value, i.e. a finite number of type
154    /// Value or -INF.
155    virtual void _setRowLowerBound(int i, Value value) = 0;
156    /// \e
157
158    /// The upper bound of a linear expression (row) have to be given by an
159    /// extended number of type Value, i.e. a finite number of type
160    /// Value or INF.
161    virtual void _setRowUpperBound(int i, Value value) = 0;
162
163    /// \e
164    virtual void _setObjCoeff(int i, Value obj_coef) = 0;
165
166    ///\e
167
168    ///\bug unimplemented!!!!
169    void clearObj() {}
170  public:
171
172
173    ///\e
174    virtual ~LpSolverBase() {}
175
176    ///Add a new empty column (i.e a new variable) to the LP
177    Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
178    ///Add a new empty row (i.e a new constaint) to the LP
179    Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
180
181    ///Add a new row (i.e a new constaint) to the LP
182
183    ///\param l lower bound (-INF means no bound)
184    ///\param e a linear expression (see \ref Expr)
185    ///\param u upper bound (INF means no bound)
186    ///\bug This is a temportary function. The interface will change to
187    ///a better one.
188    Row addRow(Value l,Expr e, Value u) {
189      Row r=addRow();
190      std::vector<int> indices;
191      std::vector<Value> values;
192      indices.push_back(0);
193      values.push_back(0);
194      for(Expr::iterator i=e.begin(); i!=e.end(); ++i) {
195        indices.push_back(cols.floatingId((*i).first.id));
196        values.push_back((*i).second);
197      }
198      _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
199                    &indices[0],&values[0]);
200      _setRowLowerBound(rows.floatingId(r.id),l);
201      _setRowUpperBound(rows.floatingId(r.id),l);
202      return r;
203    }
204
205    /// Set the lower bound of a column (i.e a variable)
206
207    /// The upper bound of a variable (column) have to be given by an
208    /// extended number of type Value, i.e. a finite number of type
209    /// Value or -INF.
210    virtual void setColLowerBound(Col c, Value value) {
211      _setColLowerBound(cols.floatingId(c.id),value);
212    }
213    /// Set the upper bound of a column (i.e a variable)
214
215    /// The upper bound of a variable (column) have to be given by an
216    /// extended number of type Value, i.e. a finite number of type
217    /// Value or INF.
218    virtual void setColUpperBound(Col c, Value value) {
219      _setColUpperBound(cols.floatingId(c.id),value);
220    };
221    /// Set the lower bound of a row (i.e a constraint)
222
223    /// The lower bound of a linear expression (row) have to be given by an
224    /// extended number of type Value, i.e. a finite number of type
225    /// Value or -INF.
226    virtual void setRowLowerBound(Row r, Value value) {
227      _setRowLowerBound(rows.floatingId(r.id),value);
228    };
229    /// Set the upper bound of a row (i.e a constraint)
230
231    /// The upper bound of a linear expression (row) have to be given by an
232    /// extended number of type Value, i.e. a finite number of type
233    /// Value or INF.
234    virtual void setRowUpperBound(Row r, Value value) {
235      _setRowUpperBound(rows.floatingId(r.id),value);
236    };
237    ///Set an element of the objective function
238    void setObjCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
239    ///Set the objective function
240   
241    ///\param e is a linear expression of type \ref Expr.
242    ///\todo What to do with the constant component?
243    void setObj(Expr e) {
244      clearObj();
245      for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
246        setObjCoeff((*i).first,(*i).second);
247    }
248   
249  }; 
250
251} //namespace lemon
252
253#endif //LEMON_LP_BASE_H
Note: See TracBrowser for help on using the repository browser.