Changeset 1253:609fe893df8c in lemon-0.x

Timestamp:

03/24/05 12:44:25 (20 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:

• Makefile (added)
• lin_expr.h (added)
• lp_base.cc (modified) (3 diffs)
• lp_base.h (modified) (10 diffs)

src/work/athos/lp/lp_base.cc

@@ -1 +1 @@
 /* -*- C++ -*-
- * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library
+ * src/lib/lp_base.cc - Part of LEMON, a generic C++ optimization library
  *
  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -15 +15 @@
  */
 
-#ifndef LEMON_LP_BASE_CC
-#define LEMON_LP_BASE_CC
-
 ///\file
 ///\brief The implementation of the LP solver interface.
@@ -24 +21 @@
 namespace lemon {
 
+
+
 } //namespace lemon
-
-#endif //LEMON_LP_BASE_CC

src/work/athos/lp/lp_base.h

@@ -1 +1 @@
 /* -*- C++ -*-
- * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library
+ * src/lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
  *
  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
@@ -18 +18 @@
 #define LEMON_LP_BASE_H
 
+#include<vector>
+
+#include<lemon/error.h>
+
+#include"lin_expr.h"
 ///\file
 ///\brief The interface of the LP solver interface.
 namespace lemon {
+  
+  ///Internal data structure to convert floating id's to fix one's
+    
+  ///\todo This might by implemented to be usable in other places.
+  class _FixId 
+  {
+    std::vector<int> index;
+    std::vector<int> cross;
+    int first_free;
+  public:
+    _FixId() : first_free(-1) {};
+    ///Convert a floating id to a fix one
+
+    ///\param n is a floating id
+    ///\return the corresponding fix id
+    int fixId(int n) {return cross[n];}
+    ///Convert a fix id to a floating one
+
+    ///\param n is a fix id
+    ///\return the corresponding floating id
+    int floatingId(int n) { return index[n];}
+    ///Add a new floating id.
+
+    ///\param n is a floating id
+    ///\return the fix id of the new value
+    ///\todo Multiple additions should also be handled.
+    int insert(int n)
+    {
+      if(n>=int(cross.size())) {
+        cross.resize(n+1);
+        if(first_free==-1) {
+          cross[n]=index.size();
+          index.push_back(n);
+        }
+        else {
+          cross[n]=first_free;
+          int next=index[first_free];
+          index[first_free]=n;
+          first_free=next;
+        }
+      }
+      else throw LogicError(); //floatingId-s must form a continuous range;
+    }
+    ///Remove a fix id.
+
+    ///\param n is a fix id
+    ///
+    void erase(int n) 
+    {
+      int fl=index[n];
+      index[n]=first_free;
+      first_free=n;
+      for(int i=fl+1;i<int(cross.size());++i) {
+        cross[i-1]=cross[i];
+        index[cross[i]]--;
+      }
+      cross.pop_back();
+    }
+    ///An upper bound on the largest fix id.
+
+    ///\todo Do we need this?
+    ///
+    std::size_t maxFixId() { return cross.size()-1; }
+  
+  };
+    
+  ///Common base class for LP solvers
   class LpSolverBase {
+    
   public:
-
-    //UNCATEGORIZED
 
     /// \e
@@ -30 +101 @@
     /// \e 
     static const Value INF;
-   protected:
+    
+    ///\e
+    class Col { protected: int id; friend class LpSolverBase; };
+    ///\e
+    class Row { protected: int id; friend class LpSolverBase; };
+
+    typedef SparseLinExpr<Col, Value> Expr;
+
+  protected:
+    _FixId rows;
+    _FixId cols;
 
     //MATRIX MANIPULATING FUNCTIONS
@@ -39 +120 @@
     virtual int _addRow() = 0;
     /// \e
+
     /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
+    ///
     virtual void _setRowCoeffs(int i, 
                                int length,
@@ -45 +128 @@
                                Value  const * values ) = 0;
     /// \e
+
     /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
+    ///
     virtual void _setColCoeffs(int i, 
                                int length,
@@ -52 +137 @@
     
     /// \e
+
     /// The lower bound of a variable (column) have to be given by an 
     /// extended number of type Value, i.e. a finite number of type 
@@ -57 +143 @@
     virtual void _setColLowerBound(int i, Value value) = 0;
     /// \e
+
     /// The upper bound of a variable (column) have to be given by an 
     /// extended number of type Value, i.e. a finite number of type 
@@ -62 +149 @@
     virtual void _setColUpperBound(int i, Value value) = 0;
     /// \e
+
     /// The lower bound of a linear expression (row) have to be given by an 
     /// extended number of type Value, i.e. a finite number of type 
@@ -67 +155 @@
     virtual void _setRowLowerBound(int i, Value value) = 0;
     /// \e
+
     /// The upper bound of a linear expression (row) have to be given by an 
     /// extended number of type Value, i.e. a finite number of type 
@@ -74 +163 @@
     /// \e
     virtual void _setObjCoeff(int i, Value obj_coef) = 0;
+
+    ///\e
+
+    ///\bug unimplemented!!!!
+    void clearObj() {}
+  public:
+
+
+    ///\e
+    virtual ~LpSolverBase() {}
+
+    ///Add a new empty column (i.e a new variable) to the LP
+    Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
+    ///Add a new empty row (i.e a new constaint) to the LP
+    Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
+
+    ///Add a new row (i.e a new constaint) to the LP
+
+    ///\param l lower bound (-INF means no bound)
+    ///\param e a linear expression (see \ref Expr)
+    ///\param u upper bound (INF means no bound)
+    ///\bug This is a temportary function. The interface will change to
+    ///a better one.
+    Row addRow(Value l,Expr e, Value u) {
+      Row r=addRow();
+      std::vector<int> indices;
+      std::vector<Value> values;
+      indices.push_back(0);
+      values.push_back(0);
+      for(Expr::iterator i=e.begin(); i!=e.end(); ++i) {
+        indices.push_back(cols.floatingId((*i).first.id));
+        values.push_back((*i).second);
+      }
+      _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
+                    &indices[0],&values[0]);
+      _setRowLowerBound(rows.floatingId(r.id),l);
+      _setRowUpperBound(rows.floatingId(r.id),l);
+      return r;
+    }
+
+    /// Set the lower bound of a column (i.e a variable)
+
+    /// The upper bound of a variable (column) have to be given by an 
+    /// extended number of type Value, i.e. a finite number of type 
+    /// Value or -INF.
+    virtual void setColLowerBound(Col c, Value value) {
+      _setColLowerBound(cols.floatingId(c.id),value);
+    }
+    /// Set the upper bound of a column (i.e a variable)
+
+    /// The upper bound of a variable (column) have to be given by an 
+    /// extended number of type Value, i.e. a finite number of type 
+    /// Value or INF.
+    virtual void setColUpperBound(Col c, Value value) {
+      _setColUpperBound(cols.floatingId(c.id),value);
+    };
+    /// Set the lower bound of a row (i.e a constraint)
+
+    /// The lower bound of a linear expression (row) have to be given by an 
+    /// extended number of type Value, i.e. a finite number of type 
+    /// Value or -INF.
+    virtual void setRowLowerBound(Row r, Value value) {
+      _setRowLowerBound(rows.floatingId(r.id),value);
+    };
+    /// Set the upper bound of a row (i.e a constraint)
+
+    /// The upper bound of a linear expression (row) have to be given by an 
+    /// extended number of type Value, i.e. a finite number of type 
+    /// Value or INF.
+    virtual void setRowUpperBound(Row r, Value value) {
+      _setRowUpperBound(rows.floatingId(r.id),value);
+    };
+    ///Set an element of the objective function
+    void setObjCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
+    ///Set the objective function
+    
+    ///\param e is a linear expression of type \ref Expr.
+    ///\todo What to do with the constant component?
+    void setObj(Expr e) {
+      clearObj();
+      for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
+        setObjCoeff((*i).first,(*i).second);
+    }
+    
   };