COIN-OR::LEMON - Graph Library

Changeset 2363:2aabce558574 in lemon-0.x for lemon/lp_base.h


Ignore:
Timestamp:
02/15/07 15:22:08 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3174
Message:

Changes on the LP interface

_FixId => LpId?

  • handling of not common ids soplex

LpGlpk? row and col erase bug fix

  • calling lpx_std_basis before simplex

LpSoplex?

  • added getter functions
  • better m4 file
  • integration to the tests
  • better handling of unsolved lps
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/lp_base.h

    r2345 r2363  
    2828#include<cmath>
    2929
    30 #include<lemon/bits/utility.h>
    3130#include<lemon/error.h>
    3231#include<lemon/bits/invalid.h>
     32#include<lemon/bits/utility.h>
     33#include<lemon/bits/lp_id.h>
    3334
    3435///\file
     
    3738namespace lemon {
    3839
    39 
    40   ///Internal data structure to convert floating id's to fix one's
    41    
    42   ///\todo This might be implemented to be also usable in other places.
    43   class _FixId
    44   {
    45   protected:
    46     int _first_index;
    47     int first_free;
    48   public:
    49     std::vector<int> index;
    50     std::vector<int> cross;
    51     _FixId() : _first_index(-1), first_free(-1) {};
    52     ///Convert a floating id to a fix one
    53 
    54     ///\param n is a floating id
    55     ///\return the corresponding fix id
    56     int fixId(int n) const {return cross[n];}
    57     ///Convert a fix id to a floating one
    58 
    59     ///\param n is a fix id
    60     ///\return the corresponding floating id
    61     int floatingId(int n) const { return index[n];}
    62     ///Add a new floating id.
    63 
    64     ///\param n is a floating id
    65     ///\return the fix id of the new value
    66     ///\todo Multiple additions should also be handled.
    67     int insert(int n)
    68     {
    69       if(cross.empty()) _first_index=n;
    70       if(n>=int(cross.size())) {
    71         cross.resize(n+1);
    72         if(first_free==-1) {
    73           cross[n]=index.size();
    74           index.push_back(n);
    75         }
    76         else {
    77           cross[n]=first_free;
    78           int next=index[first_free];
    79           index[first_free]=n;
    80           first_free=next;
    81         }
    82         return cross[n];
    83       }
    84       else {
    85         ///\todo Create an own exception type.
    86         throw LogicError(); //floatingId-s must form a continuous range;
    87       }
    88     }
    89     ///Remove a fix id.
    90 
    91     ///\param n is a fix id
    92     ///
    93     void erase(int n)
    94     {
    95       int fl=index[n];
    96       index[n]=first_free;
    97       first_free=n;
    98       for(int i=fl+1;i<int(cross.size());++i) {
    99         cross[i-1]=cross[i];
    100         index[cross[i]]--;
    101       }
    102       cross.pop_back();
    103     }
    104     ///An upper bound on the largest fix id.
    105 
    106     ///\todo Do we need this?
    107     ///
    108     std::size_t maxFixId() { return cross.size()-1; }
    109  
    110     ///Returns the first (smallest) inserted index
    111 
    112     ///Returns the first (smallest) inserted index
    113     ///or -1 if no index has been inserted before.
    114     int firstIndex() {return _first_index;}
    115   };
    116 
    11740  ///Common base class for LP solvers
    11841 
     
    12245
    12346  protected:
    124     _FixId rows;
    125     _FixId cols;
    126 
     47
     48    _lp_bits::LpId rows;
     49    _lp_bits::LpId cols;
     50   
    12751  public:
    12852
     
    216140      ColIt(LpSolverBase &lp) : _lp(&lp)
    217141      {
    218         id = _lp->cols.cross.empty()?-1:
    219           _lp->cols.fixId(_lp->cols.firstIndex());
     142        _lp->cols.firstFix(id);
    220143      }
    221144      ColIt(const Invalid&) : Col(INVALID) {}
    222145      ColIt &operator++()
    223146      {
    224         int fid = _lp->cols.floatingId(id)+1;
    225         id = unsigned(fid)<_lp->cols.cross.size() ? _lp->cols.fixId(fid) : -1;
     147        _lp->cols.nextFix(id);
    226148        return *this;
    227149      }
     
    747669    virtual void _setColUpperBound(int i, Value value) = 0;
    748670    virtual Value _getColUpperBound(int i) = 0;
    749 //     virtual void _setRowLowerBound(int i, Value value) = 0;
    750 //     virtual void _setRowUpperBound(int i, Value value) = 0;
    751671    virtual void _setRowBounds(int i, Value lower, Value upper) = 0;
    752672    virtual void _getRowBounds(int i, Value &lower, Value &upper)=0;
     
    796716
    797717    ///Add a new empty column (i.e a new variable) to the LP
    798     Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
     718    Col addCol() { Col c; _addCol(); c.id = cols.addId(); return c;}
    799719
    800720    ///\brief Adds several new columns
     
    888808    ///This function adds a new empty row (i.e a new constraint) to the LP.
    889809    ///\return The created row
    890     Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
     810    Row addRow() { Row r; _addRow(); r.id = rows.addId(); return r;}
    891811
    892812    ///\brief Add several new rows
     
    966886      _setRowCoeffs(_lpId(r), LpRowIterator(e.begin(), *this),
    967887                    LpRowIterator(e.end(), *this));
    968 //       _setRowLowerBound(_lpId(r),l-e.constComp());
    969 //       _setRowUpperBound(_lpId(r),u-e.constComp());
    970888       _setRowBounds(_lpId(r),l-e.constComp(),u-e.constComp());
    971889    }
     
    1009927    void eraseCol(Col c) {
    1010928      _eraseCol(_lpId(c));
    1011       cols.erase(c.id);
     929      cols.eraseId(c.id);
    1012930    }
    1013931    ///Erase a  row (i.e a constraint) from the LP
     
    1017935    void eraseRow(Row r) {
    1018936      _eraseRow(_lpId(r));
    1019       rows.erase(r.id);
     937      rows.eraseId(r.id);
    1020938    }
    1021939
     
    12171135#endif
    12181136   
    1219 //     /// Set the lower bound of a row (i.e a constraint)
    1220 
    1221 //     /// The lower bound of a linear expression (row) has to be given by an
    1222 //     /// extended number of type Value, i.e. a finite number of type
    1223 //     /// Value or -\ref INF.
    1224 //     void rowLowerBound(Row r, Value value) {
    1225 //       _setRowLowerBound(_lpId(r),value);
    1226 //     };
    1227 //     /// Set the upper bound of a row (i.e a constraint)
    1228 
    1229 //     /// The upper bound of a linear expression (row) has to be given by an
    1230 //     /// extended number of type Value, i.e. a finite number of type
    1231 //     /// Value or \ref INF.
    1232 //     void rowUpperBound(Row r, Value value) {
    1233 //       _setRowUpperBound(_lpId(r),value);
    1234 //     };
    12351137
    12361138    /// Set the lower and the upper bounds of a row (i.e a constraint)
    12371139
    1238     /// The lower and the upper bound of
    1239     /// a constraint (row) have to be given by an
    1240     /// extended number of type Value, i.e. a finite number of type
    1241     /// Value, -\ref INF or \ref INF. There is no separate function for the
    1242     /// lower and the upper bound because that would have been hard to implement
    1243     /// for CPLEX.
     1140    /// The lower and the upper bound of a constraint (row) have to be
     1141    /// given by an extended number of type Value, i.e. a finite
     1142    /// number of type Value, -\ref INF or \ref INF. There is no
     1143    /// separate function for the lower and the upper bound because
     1144    /// that would have been hard to implement for CPLEX.
    12441145    void rowBounds(Row c, Value lower, Value upper) {
    12451146      _setRowBounds(_lpId(c),lower, upper);
Note: See TracChangeset for help on using the changeset viewer.