source: lemon-0.x/src/work/athos/lp/lp_solver_glpk.h @ 1338:b261caf79ce7

// -*- c++ -*-
#ifndef LEMON_LP_SOLVER_GLPK_H
#define LEMON_LP_SOLVER_GLPK_H

///\ingroup misc
///\file

extern "C" {
#include "glpk.h"
}
#include <lp_solver_base.h>

namespace lemon {
  
  
  template <typename Value>
  const Value LpSolverBase<Value>::INF=std::numeric_limits<Value>::infinity();


  /// \brief Wrapper for GLPK solver
  /// 
  /// This class implements a lemon wrapper for GLPK.
  class LpGlpk : public LpSolverBase<double> {

  public:

    typedef LpSolverBase<double> Parent;
    
    /// \e
    LPX* lp;

    /// \e
    LpGlpk() : Parent(), 
                        lp(lpx_create_prob()) {
      //int_row_map.push_back(Row());
      //int_col_map.push_back(Col());
      lpx_set_int_parm(lp, LPX_K_DUAL, 1);
    }
    /// \e
    ~LpGlpk() {
      lpx_delete_prob(lp);
    }

    //MATRIX INDEPEDENT MANIPULATING FUNCTIONS

    /// \e
    void setMinimize() { 
      lpx_set_obj_dir(lp, LPX_MIN);
    }
    /// \e
    void setMaximize() { 
      lpx_set_obj_dir(lp, LPX_MAX);
    }

    /// \e
    /// Retrieve number of rows
    int rowNum() const { return lpx_get_num_rows(lp); }
    /// \e
    /// Retrieve number of coloumns
    int colNum() const { return lpx_get_num_cols(lp); }

  protected:
    /// \e
    int LpGlpk::_addCol() { 
      int i=lpx_add_cols(lp, 1);
      _setColLowerBound(i, -INF);
      _setColUpperBound(i, INF);
      return i;
    }
    /// \e
    int LpGlpk::_addRow() { 
      int i=lpx_add_rows(lp, 1);
      return i;
    }
    /// \e
    virtual void _setRowCoeffs(int i, 
                               const std::vector<std::pair<int, double> >& coeffs) {
      int mem_length=1+colNum();
      int* indices = new int[mem_length];
      double* doubles = new double[mem_length];
      int length=0;
      for (std::vector<std::pair<int, double> >::
             const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
        ++length;
        indices[length]=it->first;
        doubles[length]=it->second;
      }
      lpx_set_mat_row(lp, i, length, indices, doubles);
      delete [] indices;
      delete [] doubles;
    }
    /// \e
    virtual void _getRowCoeffs(int i, 
                               std::vector<std::pair<int, double> >& coeffs) {
      int mem_length=1+colNum();
      int* indices = new int[mem_length];
      double* doubles = new double[mem_length];
      int length=lpx_get_mat_row(lp, i, indices, doubles);
      for (int i=1; i<=length; ++i) {
        coeffs.push_back(std::make_pair(indices[i], doubles[i]));
      }
      delete [] indices;
      delete [] doubles;
    }
    /// \e
    virtual void _setColCoeffs(int i, 
                               const std::vector<std::pair<int, double> >& coeffs) {
      int mem_length=1+rowNum();
      int* indices = new int[mem_length];
      double* doubles = new double[mem_length];
      int length=0;
      for (std::vector<std::pair<int, double> >::
             const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
        ++length;
        indices[length]=it->first;
        doubles[length]=it->second;
      }
      lpx_set_mat_col(lp, i, length, indices, doubles);
      delete [] indices;
      delete [] doubles;
    }
    /// \e
    virtual void _getColCoeffs(int i, 
                               std::vector<std::pair<int, double> >& coeffs) {
      int mem_length=1+rowNum();
      int* indices = new int[mem_length];
      double* doubles = new double[mem_length];
      int length=lpx_get_mat_col(lp, i, indices, doubles);
      for (int i=1; i<=length; ++i) {
        coeffs.push_back(std::make_pair(indices[i], doubles[i]));
      }
      delete [] indices;
      delete [] doubles;
    }
    /// \e
    virtual void _eraseCol(int i) {
      int cols[2];
      cols[1]=i;
      lpx_del_cols(lp, 1, cols);
    }
    virtual void _eraseRow(int i) {
      int rows[2];
      rows[1]=i;
      lpx_del_rows(lp, 1, rows);
    }

    void _setCoeff(int row, int col, double value) {
      ///FIXME Of course this is not efficient at all, but GLPK knows not more.
      /// First approach: get one row, apply changes and set it again

      int mem_length=1+colNum();
      int* indices = new int[mem_length];
      double* doubles = new double[mem_length];


      int length=lpx_get_mat_row(lp, i, indices, doubles);

      //The following code does not suppose that the elements of the array indices are sorted
      int i=1;
      bool found=false;
      while (i <= length && !found){
        if (indices[i]=col){
          found = true;
          doubles[i]=value;
        }
        ++i;
      }
      if (!found){
        ++length;
        indices[length]=col;
        doubles[length]=value;
      }

// This is a piece of code that assumes that the array 'indices' is sorted. 
// Not ready, I suppose. 
//       //We need another arrays to put the data back, anyway
//       int* new_indices = new int[length+1];
//       double* new_doubles = new double[length+1];
//       int offset;

//       int i=1;
//       while (i <= length && indices[i]<col){
//      new_indiced[i]=indices[i];
//      new_doubles[i]=doubles[i];
//      ++i;
//       }
//       if (i>length || indices[i]>col){
//      //Ha atugrottuk, vagy a vegen van
//      new_indices[i]=col;
//      new_doubles[i]=value;
//      offset = 1;
//       }
//       else{
//      //I.e.: indices[i]=col
//      new_doubles[i]=value;
//      offset = 0;
//      ++i;
//       }
//       while (i <= length){
//      new_indices[i+offset]=indices[i];
//      new_values[i+offset]=values[i];
//       }

      lpx_set_mat_row(lp, row, length, indices, doubles);
      delete [] indices;
      delete [] doubles;

//       lpx_set_mat_row(lp, row, length+offset, new_indices, new_doubles);
//       delete [] new_indices;
//       delete [] new_doubles;
      

    }
    double _getCoeff(int col, int row) {
      /// FIXME not yet implemented
      return 0.0;
    }
    virtual void _setColLowerBound(int i, double lo) {
      if (lo==INF) {
        //FIXME error
      }
      int b=lpx_get_col_type(lp, i);
      double up=lpx_get_col_ub(lp, i);  
      if (lo==-INF) {
        switch (b) {
        case LPX_FR:
        case LPX_LO:
          lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
          break;
        case LPX_UP:
          break;
        case LPX_DB:
        case LPX_FX:
          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
          break;
        default: ;
          //FIXME error
        }
      } else {
        switch (b) {
        case LPX_FR:
        case LPX_LO:
          lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
          break;
        case LPX_UP:      
        case LPX_DB:
        case LPX_FX:
          if (lo==up) 
            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
          else 
            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
          break;
        default: ;
          //FIXME error
        }
      }
    }
    virtual double _getColLowerBound(int i) {
      int b=lpx_get_col_type(lp, i);
      switch (b) {
      case LPX_FR:
        return -INF;
      case LPX_LO:
        return lpx_get_col_lb(lp, i);
      case LPX_UP:
        return -INF;
      case LPX_DB:
      case LPX_FX:
        return lpx_get_col_lb(lp, i);
      default: ;
        //FIXME error
        return 0.0;
      }
    }
    virtual void _setColUpperBound(int i, double up) {
      if (up==-INF) {
        //FIXME error
      }
      int b=lpx_get_col_type(lp, i);
      double lo=lpx_get_col_lb(lp, i);
      if (up==INF) {
        switch (b) {
        case LPX_FR:
        case LPX_LO:
          break;
        case LPX_UP:
          lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
          break;
        case LPX_DB:
        case LPX_FX:
          lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
          break;
        default: ;
          //FIXME error
        }
      } else {
        switch (b) {
        case LPX_FR:
          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
        case LPX_LO:
          if (lo==up) 
            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
          else
            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
          break;
        case LPX_UP:
          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
          break;
        case LPX_DB:
        case LPX_FX:
          if (lo==up) 
            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
          else 
            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
          break;
        default: ;
          //FIXME error
        }
      }
    }
    virtual double _getColUpperBound(int i) {
      int b=lpx_get_col_type(lp, i);
      switch (b) {
      case LPX_FR:
      case LPX_LO:
        return INF;
      case LPX_UP:
      case LPX_DB:
      case LPX_FX:
        return lpx_get_col_ub(lp, i);
      default: ;
        //FIXME error
        return 0.0;
      }
    }
    virtual void _setRowLowerBound(int i, double lo) {
      if (lo==INF) {
        //FIXME error
      }
      int b=lpx_get_row_type(lp, i);
      double up=lpx_get_row_ub(lp, i);  
      if (lo==-INF) {
        switch (b) {
        case LPX_FR:
        case LPX_LO:
          lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
          break;
        case LPX_UP:
          break;
        case LPX_DB:
        case LPX_FX:
          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
          break;
        default: ;
          //FIXME error
        }
      } else {
        switch (b) {
        case LPX_FR:
        case LPX_LO:
          lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
          break;
        case LPX_UP:      
        case LPX_DB:
        case LPX_FX:
          if (lo==up) 
            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
          else 
            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
          break;
        default: ;
          //FIXME error
        }
      }
    }
    virtual double _getRowLowerBound(int i) {
      int b=lpx_get_row_type(lp, i);
      switch (b) {
      case LPX_FR:
        return -INF;
      case LPX_LO:
        return lpx_get_row_lb(lp, i);
      case LPX_UP:
        return -INF;
      case LPX_DB:
      case LPX_FX:
        return lpx_get_row_lb(lp, i);
      default: ;
        //FIXME error
        return 0.0;
      }
    }
    virtual void _setRowUpperBound(int i, double up) {
      if (up==-INF) {
        //FIXME error
      }
      int b=lpx_get_row_type(lp, i);
      double lo=lpx_get_row_lb(lp, i);
      if (up==INF) {
        switch (b) {
        case LPX_FR:
        case LPX_LO:
          break;
        case LPX_UP:
          lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
          break;
        case LPX_DB:
        case LPX_FX:
          lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
          break;
        default: ;
          //FIXME error
        }
      } else {
        switch (b) {
        case LPX_FR:
          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
        case LPX_LO:
          if (lo==up) 
            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
          else
            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
          break;
        case LPX_UP:
          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
          break;
        case LPX_DB:
        case LPX_FX:
          if (lo==up) 
            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
          else 
            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
          break;
        default: ;
          //FIXME error
        }
      }
    }
    virtual double _getRowUpperBound(int i) {
      int b=lpx_get_row_type(lp, i);
      switch (b) {
      case LPX_FR:
      case LPX_LO:
        return INF;
      case LPX_UP:
      case LPX_DB:
      case LPX_FX:
        return lpx_get_row_ub(lp, i);
      default: ;
        //FIXME error
        return 0.0;
      }
    }
    /// \e
    virtual double _getObjCoeff(int i) { 
      return lpx_get_obj_coef(lp, i);
    }
    /// \e
    virtual void _setObjCoeff(int i, double obj_coef) { 
      lpx_set_obj_coef(lp, i, obj_coef);
    }

  protected:
    virtual double _getPrimal(int i) {
      return lpx_get_col_prim(lp, i);
    }

    //MIP
  protected:
    /// \e
    void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); }
    /// \e
    void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); }
    /// \e
    double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); }


//   public:
//     /// \e
//     void solveSimplex() { lpx_simplex(lp); }
//     /// \e
//     void solvePrimalSimplex() { lpx_simplex(lp); }
//     /// \e
//     void solveDualSimplex() { lpx_simplex(lp); }
//     /// \e
//     double getObjVal() { return lpx_get_obj_val(lp); }
//     /// \e
//     int warmUp() { return lpx_warm_up(lp); }
//     /// \e
//     void printWarmUpStatus(int i) {
//       switch (i) {
//       case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
//       case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;        
//       case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
//       case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
//       }
//     }
//     /// \e
//     int getPrimalStatus() { return lpx_get_prim_stat(lp); }
//     /// \e
//     void printPrimalStatus(int i) {
//       switch (i) {
//       case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
//       case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;  
//       case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
//       case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
//       }
//     }
//     /// \e
//     int getDualStatus() { return lpx_get_dual_stat(lp); }
//     /// \e
//     void printDualStatus(int i) {
//       switch (i) {
//       case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
//       case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;  
//       case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
//       case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
//       }
//     }
//     /// Returns the status of the slack variable assigned to row \c row.
//     int getRowStat(const Row& row) { 
//       return lpx_get_row_stat(lp, row_iter_map[row]); 
//     }
//     /// \e
//     void printRowStatus(int i) {
//       switch (i) {
//       case LPX_BS: cout << "LPX_BS" << endl; break;
//       case LPX_NL: cout << "LPX_NL" << endl; break;  
//       case LPX_NU: cout << "LPX_NU" << endl; break;
//       case LPX_NF: cout << "LPX_NF" << endl; break;
//       case LPX_NS: cout << "LPX_NS" << endl; break;
//       }
//     }
//     /// Returns the status of the variable assigned to column \c col.
//     int getColStat(const Col& col) { 
//       return lpx_get_col_stat(lp, col_iter_map[col]); 
//     }
//     /// \e
//     void printColStatus(int i) {
//       switch (i) {
//       case LPX_BS: cout << "LPX_BS" << endl; break;
//       case LPX_NL: cout << "LPX_NL" << endl; break;  
//       case LPX_NU: cout << "LPX_NU" << endl; break;
//       case LPX_NF: cout << "LPX_NF" << endl; break;
//       case LPX_NS: cout << "LPX_NS" << endl; break;
//       }
//     }

//     // MIP
//     /// \e
//     void solveBandB() { lpx_integer(lp); }
//     /// \e
//     void setLP() { lpx_set_class(lp, LPX_LP); }
//     /// \e
//     void setMIP() { lpx_set_class(lp, LPX_MIP); }



  };
  
  /// @}

} //namespace lemon

#endif //LEMON_LP_SOLVER_GLPK_H