COIN-OR::LEMON - Graph Library

Changeset 1253:609fe893df8c in lemon-0.x


Ignore:
Timestamp:
03/24/05 12:44:25 (19 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1680
Message:
  • simple makefile added
  • _FixId class added (more clarification needed)
  • LinExpr? class added
  • some higher level interfaces added to LpSolverBase?
  • minor corrections
Location:
src/work/athos/lp
Files:
2 added
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/lp/lp_base.cc

    r1247 r1253  
    11/* -*- C++ -*-
    2  * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library
     2 * src/lib/lp_base.cc - Part of LEMON, a generic C++ optimization library
    33 *
    44 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     
    1515 */
    1616
    17 #ifndef LEMON_LP_BASE_CC
    18 #define LEMON_LP_BASE_CC
    19 
    2017///\file
    2118///\brief The implementation of the LP solver interface.
     
    2421namespace lemon {
    2522
     23
     24
    2625} //namespace lemon
    27 
    28 #endif //LEMON_LP_BASE_CC
  • src/work/athos/lp/lp_base.h

    r1251 r1253  
    11/* -*- C++ -*-
    2  * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library
     2 * src/lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
    33 *
    44 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     
    1818#define LEMON_LP_BASE_H
    1919
     20#include<vector>
     21
     22#include<lemon/error.h>
     23
     24#include"lin_expr.h"
    2025///\file
    2126///\brief The interface of the LP solver interface.
    2227namespace 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
    2395  class LpSolverBase {
     96   
    2497  public:
    25 
    26     //UNCATEGORIZED
    2798
    2899    /// \e
     
    30101    /// \e
    31102    static const Value INF;
    32    protected:
     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;
    33114
    34115    //MATRIX MANIPULATING FUNCTIONS
     
    39120    virtual int _addRow() = 0;
    40121    /// \e
     122
    41123    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
     124    ///
    42125    virtual void _setRowCoeffs(int i,
    43126                               int length,
     
    45128                               Value  const * values ) = 0;
    46129    /// \e
     130
    47131    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
     132    ///
    48133    virtual void _setColCoeffs(int i,
    49134                               int length,
     
    52137   
    53138    /// \e
     139
    54140    /// The lower bound of a variable (column) have to be given by an
    55141    /// extended number of type Value, i.e. a finite number of type
     
    57143    virtual void _setColLowerBound(int i, Value value) = 0;
    58144    /// \e
     145
    59146    /// The upper bound of a variable (column) have to be given by an
    60147    /// extended number of type Value, i.e. a finite number of type
     
    62149    virtual void _setColUpperBound(int i, Value value) = 0;
    63150    /// \e
     151
    64152    /// The lower bound of a linear expression (row) have to be given by an
    65153    /// extended number of type Value, i.e. a finite number of type
     
    67155    virtual void _setRowLowerBound(int i, Value value) = 0;
    68156    /// \e
     157
    69158    /// The upper bound of a linear expression (row) have to be given by an
    70159    /// extended number of type Value, i.e. a finite number of type
     
    74163    /// \e
    75164    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   
    76249  }; 
    77250
Note: See TracChangeset for help on using the changeset viewer.