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

/* -*- C++ -*-
 * src/lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Combinatorial Optimization Research Group, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_LP_BASE_H
#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:

    /// \e
    typedef double Value;
    /// \e 
    static const Value INF;
    
    ///\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

    /// \e
    virtual int _addCol() = 0;
    /// \e
    virtual int _addRow() = 0;
    /// \e

    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
    ///
    virtual void _setRowCoeffs(int i, 
                               int length,
                               int  const * indices, 
                               Value  const * values ) = 0;
    /// \e

    /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
    ///
    virtual void _setColCoeffs(int i, 
                               int length,
                               int  const * indices, 
                               Value  const * values ) = 0;
    
    /// \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 
    /// Value or -INF.
    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 
    /// Value or INF.
    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 
    /// Value or -INF.
    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 
    /// Value or INF.
    virtual void _setRowUpperBound(int i, Value value) = 0;

    /// \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);
    }
    
  };  

} //namespace lemon

#endif //LEMON_LP_BASE_H