COIN-OR::LEMON - Graph Library

Changeset 1111:88ade201ffc6 in lemon-0.x


Ignore:
Timestamp:
02/01/05 13:53:30 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1510
Message:

lower and upper bound handling functions for rows

Location:
src/work/marci/lp
Files:
1 deleted
1 edited
1 moved

Legend:

Unmodified
Added
Removed
  • src/work/marci/lp/lp_solver_base.h

    r1110 r1111  
    2525#include <utility>
    2626
    27 //#include <sage_graph.h>
    2827//#include <lemon/list_graph.h>
    29 //#include <lemon/graph_wrapper.h>
    3028#include <lemon/invalid.h>
    3129#include <expression.h>
     
    174172
    175173  /*! \e
    176 
    177   \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
    178   \todo LEKERDEZESEK!!!
    179   \todo DOKSI!!!! Doxygen group!!!
    180 
    181    */
     174    \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
     175    \todo LEKERDEZESEK!!!
     176    \todo DOKSI!!!! Doxygen group!!!
     177    The aim of this class is to give a general surface to different
     178    solvers, i.e. it makes possible to write algorithms using LP's,
     179    in which the solver can be changed to an other one easily.
     180  */
    182181  template <typename _Value>
    183182  class LPSolverBase {
     
    220219  protected:
    221220    /// \e
     221    virtual int _addCol() = 0;
     222    /// \e
    222223    virtual int _addRow() = 0;
    223224    /// \e
    224     virtual int _addCol() = 0;
     225    virtual void _eraseCol(int i) = 0;
     226    /// \e
     227    virtual void _eraseRow(int i) = 0;
    225228    /// \e
    226229    virtual void _setRowCoeffs(int i,
     
    229232    virtual void _setColCoeffs(int i,
    230233                               const std::vector<std::pair<int, _Value> >& coeffs) = 0;
    231     /// \e
    232     virtual void _eraseCol(int i) = 0;
    233     /// \e
    234     virtual void _eraseRow(int i) = 0;
    235234  public:
    236235    /// \e
     
    243242    virtual void _setColLowerBound(int i, _Value value) = 0;
    244243    /// \e
     244    /// The lower bound of a variable (column) is an
     245    /// extended number of type _Value, i.e. a finite number of type
     246    /// _Value or -INF.
     247    virtual _Value _getColLowerBound(int i) = 0;
     248    /// \e
    245249    /// The upper bound of a variable (column) have to be given by an
    246250    /// extended number of type _Value, i.e. a finite number of type
     
    248252    virtual void _setColUpperBound(int i, _Value value) = 0;
    249253    /// \e
    250     /// The lower bound of a variable (column) is an
    251     /// extended number of type _Value, i.e. a finite number of type
    252     /// _Value or -INF.
    253     virtual _Value _getColLowerBound(int i) = 0;
    254     /// \e
    255254    /// The upper bound of a variable (column) is an
    256255    /// extended number of type _Value, i.e. a finite number of type
     
    258257    virtual _Value _getColUpperBound(int i) = 0;
    259258    /// \e
    260     virtual void _setColBounds(int i, Bound bound,
    261                                _Value lo, _Value up) = 0;
    262     /// \e
    263     virtual void _setRowBounds(int i, Bound bound,
    264                                _Value lo, _Value up) = 0;
     259    /// The lower bound of a linear expression (row) have to be given by an
     260    /// extended number of type _Value, i.e. a finite number of type
     261    /// _Value or -INF.
     262    virtual void _setRowLowerBound(int i, _Value value) = 0;
     263    /// \e
     264    /// The lower bound of a linear expression (row) is an
     265    /// extended number of type _Value, i.e. a finite number of type
     266    /// _Value or -INF.
     267    virtual _Value _getRowLowerBound(int i) = 0;
     268    /// \e
     269    /// The upper bound of a linear expression (row) have to be given by an
     270    /// extended number of type _Value, i.e. a finite number of type
     271    /// _Value or INF.
     272    virtual void _setRowUpperBound(int i, _Value value) = 0;
     273    /// \e
     274    /// The upper bound of a linear expression (row) is an
     275    /// extended number of type _Value, i.e. a finite number of type
     276    /// _Value or INF.
     277    virtual _Value _getRowUpperBound(int i) = 0;
    265278    /// \e
    266279    virtual void _setObjCoef(int i, _Value obj_coef) = 0;
     
    271284
    272285  protected:
     286    /// \e
    273287    virtual _Value _getPrimal(int i) = 0;
    274288
     
    276290
    277291  public:
     292    /// \e
     293    ColIt addCol() {
     294      int i=_addCol(); 
     295      ColIt col_it;
     296      col_iter_map.first(col_it, INVALID_CLASS);
     297      if (col_iter_map.valid(col_it)) { //van hasznalhato hely
     298        col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
     299        col_iter_map[col_it]=i;
     300      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
     301        col_it=col_iter_map.push_back(i, VALID_CLASS);
     302      }
     303      return col_it;
     304    }
    278305    /// \e
    279306    RowIt addRow() {
     
    288315      }
    289316      return row_it;
    290     }
    291     /// \e
    292     ColIt addCol() {
    293       int i=_addCol(); 
    294       ColIt col_it;
    295       col_iter_map.first(col_it, INVALID_CLASS);
    296       if (col_iter_map.valid(col_it)) { //van hasznalhato hely
    297         col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
    298         col_iter_map[col_it]=i;
    299       } else { //a cucc vegere kell inzertalni mert nincs szabad hely
    300         col_it=col_iter_map.push_back(i, VALID_CLASS);
    301       }
    302       return col_it;
    303     }
    304     /// \e
    305     template <typename Begin, typename End>
    306     void setRowCoeffs(RowIt row_it, Begin begin, End end) {
    307       std::vector<std::pair<int, double> > coeffs;
    308       for ( ; begin!=end; ++begin) {
    309         coeffs.push_back(std::
    310                          make_pair(col_iter_map[begin->first], begin->second));
    311       }
    312       _setRowCoeffs(row_iter_map[row_it], coeffs);
    313     }
    314     /// \e
    315     template <typename Begin, typename End>
    316     void setColCoeffs(ColIt col_it, Begin begin, End end) {
    317       std::vector<std::pair<int, double> > coeffs;
    318       for ( ; begin!=end; ++begin) {
    319         coeffs.push_back(std::
    320                          make_pair(row_iter_map[begin->first], begin->second));
    321       }
    322       _setColCoeffs(col_iter_map[col_it], coeffs);
    323317    }
    324318    /// \e
     
    349343    }
    350344    /// \e
     345    template <typename Begin, typename End>
     346    void setRowCoeffs(RowIt row_it, Begin begin, End end) {
     347      std::vector<std::pair<int, double> > coeffs;
     348      for ( ; begin!=end; ++begin) {
     349        coeffs.push_back(std::
     350                         make_pair(col_iter_map[begin->first], begin->second));
     351      }
     352      _setRowCoeffs(row_iter_map[row_it], coeffs);
     353    }
     354    /// \e
     355    template <typename Begin, typename End>
     356    void setColCoeffs(ColIt col_it, Begin begin, End end) {
     357      std::vector<std::pair<int, double> > coeffs;
     358      for ( ; begin!=end; ++begin) {
     359        coeffs.push_back(std::
     360                         make_pair(row_iter_map[begin->first], begin->second));
     361      }
     362      _setColCoeffs(col_iter_map[col_it], coeffs);
     363    }
     364    /// \e
    351365    void setColLowerBound(ColIt col_it, _Value lo) {
    352366      _setColLowerBound(col_iter_map[col_it], lo);
    353367    }
    354368    /// \e
     369    _Value getColLowerBound(ColIt col_it) {
     370      return _getColLowerBound(col_iter_map[col_it]);
     371    }
     372    /// \e
    355373    void setColUpperBound(ColIt col_it, _Value up) {
    356374      _setColUpperBound(col_iter_map[col_it], up);
    357375    }
    358376    /// \e
    359     _Value getColLowerBound(ColIt col_it) {
    360       return _getColLowerBound(col_iter_map[col_it]);
    361     }
    362     /// \e
    363377    _Value getColUpperBound(ColIt col_it) {     
    364378      return _getColUpperBound(col_iter_map[col_it]);
    365379    }
    366380    /// \e
    367     void setColBounds(const ColIt& col_it, Bound bound,
    368                       _Value lo, _Value up) {
    369       _setColBounds(col_iter_map[col_it], bound, lo, up);
    370     }
    371     /// \e
    372     void setRowBounds(const RowIt& row_it, Bound bound,
    373                       _Value lo, _Value up) {
    374       _setRowBounds(row_iter_map[row_it], bound, lo, up);
     381    void setRowLowerBound(RowIt row_it, _Value lo) {
     382      _setRowLowerBound(row_iter_map[row_it], lo);
     383    }
     384    /// \e
     385    _Value getRowLowerBound(RowIt row_it) {
     386      return _getRowLowerBound(row_iter_map[row_it]);
     387    }
     388    /// \e
     389    void setRowUpperBound(RowIt row_it, _Value up) {
     390      _setRowUpperBound(row_iter_map[row_it], up);
     391    }
     392    /// \e
     393    _Value getRowUpperBound(RowIt row_it) {     
     394      return _getRowUpperBound(row_iter_map[row_it]);
    375395    }
    376396    /// \e
     
    416436      }
    417437    }
     438
    418439    //SOLVER FUNCTIONS
    419440
     
    429450
    430451  public:
     452
     453    /// \e
    431454    _Value getPrimal(const ColIt& col_it) {
    432455      return _getPrimal(col_iter_map[col_it]);
     
    467490
    468491
    469   /// \brief Wrappers for LP solvers
     492  /// \brief Wrapper for GLPK solver
    470493  ///
    471   /// This class implements a lemon wrapper for glpk.
    472   /// Later other LP-solvers will be wrapped into lemon.
    473   /// The aim of this class is to give a general surface to different
    474   /// solvers, i.e. it makes possible to write algorithms using LP's,
    475   /// in which the solver can be changed to an other one easily.
     494  /// This class implements a lemon wrapper for GLPK.
    476495  class LPGLPK : public LPSolverBase<double> {
    477496  public:
     
    595614          break;
    596615        case LPX_UP:     
    597         case LPX_DB:
    598         case LPX_FX:
    599           if (lo==up)
    600             lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
    601           else
    602             lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
    603           break;
    604         default: ;
    605           //FIXME error
    606         }
    607       }
    608     }
    609     virtual void _setColUpperBound(int i, double up) {
    610       if (up==-INF) {
    611         //FIXME error
    612       }
    613       int b=lpx_get_col_type(lp, i);
    614       double lo=lpx_get_col_lb(lp, i);
    615       if (up==INF) {
    616         switch (b) {
    617         case LPX_FR:
    618         case LPX_LO:
    619           break;
    620         case LPX_UP:
    621           lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
    622           break;
    623         case LPX_DB:
    624         case LPX_FX:
    625           lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
    626           break;
    627         default: ;
    628           //FIXME error
    629         }
    630       } else {
    631         switch (b) {
    632         case LPX_FR:
    633           lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
    634         case LPX_LO:
    635           if (lo==up)
    636             lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
    637           else
    638             lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
    639           break;
    640         case LPX_UP:
    641           lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
    642           break;
    643616        case LPX_DB:
    644617        case LPX_FX:
     
    670643      }
    671644    }
     645    virtual void _setColUpperBound(int i, double up) {
     646      if (up==-INF) {
     647        //FIXME error
     648      }
     649      int b=lpx_get_col_type(lp, i);
     650      double lo=lpx_get_col_lb(lp, i);
     651      if (up==INF) {
     652        switch (b) {
     653        case LPX_FR:
     654        case LPX_LO:
     655          break;
     656        case LPX_UP:
     657          lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
     658          break;
     659        case LPX_DB:
     660        case LPX_FX:
     661          lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
     662          break;
     663        default: ;
     664          //FIXME error
     665        }
     666      } else {
     667        switch (b) {
     668        case LPX_FR:
     669          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
     670        case LPX_LO:
     671          if (lo==up)
     672            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
     673          else
     674            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
     675          break;
     676        case LPX_UP:
     677          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
     678          break;
     679        case LPX_DB:
     680        case LPX_FX:
     681          if (lo==up)
     682            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
     683          else
     684            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
     685          break;
     686        default: ;
     687          //FIXME error
     688        }
     689      }
     690    }
    672691    virtual double _getColUpperBound(int i) {
    673692      int b=lpx_get_col_type(lp, i);
     
    685704      }
    686705    }
    687     virtual void _setColBounds(int i, Bound bound,
    688                                double lo, double up) {
    689       switch (bound) {
    690       case FREE:
    691         lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
    692         break;
    693       case LOWER:
    694         lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
    695         break;
    696       case UPPER:
    697         lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
    698         break;
    699       case DOUBLE:
    700         lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
    701         break;
    702       case FIXED:
    703         lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
    704         break;
    705       }
    706     }
    707     virtual void _setRowBounds(int i, Bound bound,
    708                                double lo, double up) {
    709       switch (bound) {
    710       case FREE:
    711         lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
    712         break;
    713       case LOWER:
    714         lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
    715         break;
    716       case UPPER:
    717         lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
    718         break;
    719       case DOUBLE:
    720         lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
    721         break;
    722       case FIXED:
    723         lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
    724         break;
    725       }
    726     }
    727   protected:
     706    virtual void _setRowLowerBound(int i, double lo) {
     707      if (lo==INF) {
     708        //FIXME error
     709      }
     710      int b=lpx_get_row_type(lp, i);
     711      double up=lpx_get_row_ub(lp, i); 
     712      if (lo==-INF) {
     713        switch (b) {
     714        case LPX_FR:
     715        case LPX_LO:
     716          lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
     717          break;
     718        case LPX_UP:
     719          break;
     720        case LPX_DB:
     721        case LPX_FX:
     722          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
     723          break;
     724        default: ;
     725          //FIXME error
     726        }
     727      } else {
     728        switch (b) {
     729        case LPX_FR:
     730        case LPX_LO:
     731          lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
     732          break;
     733        case LPX_UP:     
     734        case LPX_DB:
     735        case LPX_FX:
     736          if (lo==up)
     737            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
     738          else
     739            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
     740          break;
     741        default: ;
     742          //FIXME error
     743        }
     744      }
     745    }
     746    virtual double _getRowLowerBound(int i) {
     747      int b=lpx_get_row_type(lp, i);
     748      switch (b) {
     749      case LPX_FR:
     750        return -INF;
     751      case LPX_LO:
     752        return lpx_get_row_lb(lp, i);
     753      case LPX_UP:
     754        return -INF;
     755      case LPX_DB:
     756      case LPX_FX:
     757        return lpx_get_row_lb(lp, i);
     758      default: ;
     759        //FIXME error
     760        return 0.0;
     761      }
     762    }
     763    virtual void _setRowUpperBound(int i, double up) {
     764      if (up==-INF) {
     765        //FIXME error
     766      }
     767      int b=lpx_get_row_type(lp, i);
     768      double lo=lpx_get_row_lb(lp, i);
     769      if (up==INF) {
     770        switch (b) {
     771        case LPX_FR:
     772        case LPX_LO:
     773          break;
     774        case LPX_UP:
     775          lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
     776          break;
     777        case LPX_DB:
     778        case LPX_FX:
     779          lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
     780          break;
     781        default: ;
     782          //FIXME error
     783        }
     784      } else {
     785        switch (b) {
     786        case LPX_FR:
     787          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
     788        case LPX_LO:
     789          if (lo==up)
     790            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
     791          else
     792            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
     793          break;
     794        case LPX_UP:
     795          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
     796          break;
     797        case LPX_DB:
     798        case LPX_FX:
     799          if (lo==up)
     800            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
     801          else
     802            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
     803          break;
     804        default: ;
     805          //FIXME error
     806        }
     807      }
     808    }
     809    virtual double _getRowUpperBound(int i) {
     810      int b=lpx_get_row_type(lp, i);
     811      switch (b) {
     812      case LPX_FR:
     813      case LPX_LO:
     814        return INF;
     815      case LPX_UP:
     816      case LPX_DB:
     817      case LPX_FX:
     818        return lpx_get_row_ub(lp, i);
     819      default: ;
     820        //FIXME error
     821        return 0.0;
     822      }
     823    }
    728824    /// \e
    729825    virtual double _getObjCoef(int i) {
  • src/work/marci/lp/max_flow_expression.cc

    r1110 r1111  
    77#include <lemon/dimacs.h>
    88#include <lemon/time_measure.h>
    9 #include <lp_solver_wrapper_3.h>
     9#include <lp_solver_base.h>
    1010
    1111using std::cout;
     
    5252  PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map);
    5353
    54   // capacity function
     54  // nonnegativity of flow and capacity function
    5555  for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
    5656    ColIt col_it=lp.addCol();
     
    5959    // if you change the order of the following two lines, the
    6060    // two runs of GLPK are extremely different
     61      lp.setColLowerBound(col_it, 0);
    6162      lp.setColUpperBound(col_it, cap[e]);
    62       lp.setColLowerBound(col_it, 0);
    6363  }
    6464 
     
    7373      lp.setObjCoeffs(expr);     
    7474    }
    75     // flow conservation
     75    // flow conservation constraints
    7676    if ((n!=s) && (n!=t)) {
    7777      RowIt row_it=lp.addRow();
    7878      lp.setRowCoeffs(row_it, expr);
    79       lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0);
     79      lp.setRowLowerBound(row_it, 0.0);
     80      lp.setRowUpperBound(row_it, 0.0);
    8081    }
    8182  }
Note: See TracChangeset for help on using the changeset viewer.