RhodeCode

 *

 * 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.

 *

 */

#include <lemon/clp.h>

#include <coin/ClpSimplex.hpp>

namespace lemon {

    _prob = new ClpSimplex();

    _init_temporals();

    messageLevel(MESSAGE_NO_OUTPUT);

  }

    _prob = new ClpSimplex(*other._prob);

    rows = other.rows;

    cols = other.cols;

    _init_temporals();

    messageLevel(MESSAGE_NO_OUTPUT);

  }

    delete _prob;

    _clear_temporals();

  }

    _primal_ray = 0;

    _dual_ray = 0;

  }

    if (_primal_ray) {

      delete[] _primal_ray;

      _primal_ray = 0;

    }

    if (_dual_ray) {

      delete[] _dual_ray;

      _dual_ray = 0;

    }

  }

    return newlp;

  }

    return copylp;

  }

    _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0);

    return _prob->numberColumns() - 1;

  }

    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);

    return _prob->numberRows() - 1;

  }

    _col_names_ref.erase(_prob->getColumnName(c));

    _prob->deleteColumns(1, &c);

  }

    _row_names_ref.erase(_prob->getRowName(r));

    _prob->deleteRows(1, &r);

  }

    cols.eraseIndex(i);

    cols.shiftIndices(i);

  }

    rows.eraseIndex(i);

    rows.shiftIndices(i);

  }

    name = _prob->getColumnName(c);

  }

    _prob->setColumnName(c, const_cast<std::string&>(name));

    _col_names_ref[name] = c;

  }

    std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);

    return it != _col_names_ref.end() ? it->second : -1;

  }

    name = _prob->getRowName(r);

  }

    _prob->setRowName(r, const_cast<std::string&>(name));

    _row_names_ref[name] = r;

  }

    std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);

    return it != _row_names_ref.end() ? it->second : -1;

  }

    std::map<int, Value> coeffs;

    int n = _prob->clpMatrix()->getNumCols();

    const int* indices = _prob->clpMatrix()->getIndices();

    const double* elements = _prob->clpMatrix()->getElements();

    for (int i = 0; i < n; ++i) {

      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];

      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];

      const int* it = std::lower_bound(indices + begin, indices + end, ix);

    }

    for (ExprIterator it = b; it != e; ++it) {

      coeffs[it->first] = it->second;

    }

    for (std::map<int, Value>::iterator it = coeffs.begin();

         it != coeffs.end(); ++it) {

      _prob->modifyCoefficient(ix, it->first, it->second);

    }

  }

    int n = _prob->clpMatrix()->getNumCols();

    const int* indices = _prob->clpMatrix()->getIndices();

    const double* elements = _prob->clpMatrix()->getElements();

    for (int i = 0; i < n; ++i) {

      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];

      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];

      const int* it = std::lower_bound(indices + begin, indices + end, ix);

      if (it != indices + end && *it == ix) {

        *b = std::make_pair(i, elements[it - indices]);

      }

    }

  }

    std::map<int, Value> coeffs;

    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];

    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];

    const int* indices = _prob->clpMatrix()->getIndices();

    const double* elements = _prob->clpMatrix()->getElements();

    for (CoinBigIndex i = begin; i != end; ++i) {

      if (elements[i] != 0.0) {

        coeffs[indices[i]] = 0.0;

      }

    }

    for (ExprIterator it = b; it != e; ++it) {

      coeffs[it->first] = it->second;

    }

    for (std::map<int, Value>::iterator it = coeffs.begin();

         it != coeffs.end(); ++it) {

      _prob->modifyCoefficient(it->first, ix, it->second);

    }

  }

    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];

    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];

    const int* indices = _prob->clpMatrix()->getIndices();

    const double* elements = _prob->clpMatrix()->getElements();

    for (CoinBigIndex i = begin; i != end; ++i) {

      *b = std::make_pair(indices[i], elements[i]);

      ++b;

    }

  }

    _prob->modifyCoefficient(ix, jx, value);

  }

    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];

    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];

    const int* indices = _prob->clpMatrix()->getIndices();

    const double* elements = _prob->clpMatrix()->getElements();

    const int* it = std::lower_bound(indices + begin, indices + end, jx);

    if (it != indices + end && *it == jx) {

      return elements[it - indices];

    } else {

      return 0.0;

    }

  }

    _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);

  }

    double val = _prob->getColLower()[i];

    return val == - COIN_DBL_MAX ? - INF : val;

  }

    _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);

  }

    double val = _prob->getColUpper()[i];

    return val == COIN_DBL_MAX ? INF : val;

  }

    _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);

  }

    double val = _prob->getRowLower()[i];

    return val == - COIN_DBL_MAX ? - INF : val;

  }

    _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);

  }

    double val = _prob->getRowUpper()[i];

    return val == COIN_DBL_MAX ? INF : val;

  }

    int num = _prob->clpMatrix()->getNumCols();

    for (int i = 0; i < num; ++i) {

      _prob->setObjectiveCoefficient(i, 0.0);

    }

    for (ExprIterator it = b; it != e; ++it) {

      _prob->setObjectiveCoefficient(it->first, it->second);

    }

  }

    int num = _prob->clpMatrix()->getNumCols();

    for (int i = 0; i < num; ++i) {

      Value coef = _prob->getObjCoefficients()[i];

      if (coef != 0.0) {

        *b = std::make_pair(i, coef);

        ++b;

      }

    }

  }

    _prob->setObjectiveCoefficient(i, obj_coef);

  }

    return _prob->getObjCoefficients()[i];

  }

    return _prob->primal() >= 0 ? SOLVED : UNSOLVED;

  }

    return _prob->primal() >= 0 ? SOLVED : UNSOLVED;

  }

    return _prob->dual() >= 0 ? SOLVED : UNSOLVED;

  }

    return _prob->barrier() >= 0 ? SOLVED : UNSOLVED;

  }

    return _prob->primalColumnSolution()[i];

  }

    return _prob->objectiveValue();

  }

    return _prob->dualRowSolution()[i];

  }

    if (!_primal_ray) {

      _primal_ray = _prob->unboundedRay();

      LEMON_ASSERT(_primal_ray != 0, "Primal ray is not provided");

    }

    return _primal_ray[i];

  }

    if (!_dual_ray) {

      _dual_ray = _prob->infeasibilityRay();

      LEMON_ASSERT(_dual_ray != 0, "Dual ray is not provided");

    }

    return _dual_ray[i];

  }

    switch (_prob->getColumnStatus(i)) {

    case ClpSimplex::basic:

      return BASIC;

    case ClpSimplex::isFree:

      return FREE;

    case ClpSimplex::atUpperBound:

      return UPPER;

    case ClpSimplex::atLowerBound:

      return LOWER;

    case ClpSimplex::isFixed:

      return FIXED;

    case ClpSimplex::superBasic:

      return FREE;

    default:

      LEMON_ASSERT(false, "Wrong column status");

      return VarStatus();

    }

  }

    switch (_prob->getColumnStatus(i)) {

    case ClpSimplex::basic:

      return BASIC;

    case ClpSimplex::isFree:

      return FREE;

    case ClpSimplex::atUpperBound:

      return UPPER;

    case ClpSimplex::atLowerBound:

      return LOWER;

    case ClpSimplex::isFixed:

      return FIXED;

    case ClpSimplex::superBasic:

      return FREE;

    default:

      LEMON_ASSERT(false, "Wrong row status");

      return VarStatus();

    }

  }

    if (_prob->isProvenOptimal()) {

      return OPTIMAL;

    } else if (_prob->isProvenPrimalInfeasible()) {

      return INFEASIBLE;

    } else if (_prob->isProvenDualInfeasible()) {

      return UNBOUNDED;

    } else {

      return UNDEFINED;

    }

  }

    if (_prob->isProvenOptimal()) {

      return OPTIMAL;

    } else if (_prob->isProvenDualInfeasible()) {

      return INFEASIBLE;

    } else if (_prob->isProvenPrimalInfeasible()) {

      return INFEASIBLE;

    } else {

      return UNDEFINED;

    }

  }

    switch (sense) {

    case MIN:

      _prob->setOptimizationDirection(1);

      break;

    case MAX:

      _prob->setOptimizationDirection(-1);

      break;

    }

  }

    double dir = _prob->optimizationDirection();

    if (dir > 0.0) {

      return MIN;

    } else {

      return MAX;

    }

  }

    delete _prob;

    _prob = new ClpSimplex();

    rows.clear();

    cols.clear();

    _col_names_ref.clear();

    _clear_temporals();

  }

    _prob->setLogLevel(static_cast<int>(m));

  }

} //END OF NAMESPACE LEMON

class ClpSimplex;

namespace lemon {

  /// \ingroup lp_group

  ///

  /// \brief Interface for the CLP solver

  ///

  /// This class implements an interface for the Clp LP solver.  The

  /// Clp library is an object oriented lp solver library developed at

  /// the IBM. The CLP is part of the COIN-OR package and it can be

  /// used with Common Public License.

  protected:

    ClpSimplex* _prob;

    std::map<std::string, int> _col_names_ref;

    std::map<std::string, int> _row_names_ref;

  public:

    /// \e

    /// \e

    /// \e

  protected:

    mutable double* _primal_ray;

    mutable double* _dual_ray;

    void _init_temporals();

    void _clear_temporals();

  protected:

    virtual const char* _solverName() const;

    virtual int _addCol();

    virtual int _addRow();

    virtual void _eraseCol(int i);

    virtual void _eraseRow(int i);

    virtual void _eraseColId(int i);

    virtual void _eraseRowId(int i);

      return CplexBase::Sense();

    }

  }

  void CplexBase::_clear() {

    CPXfreeprob(cplexEnv(),&_prob);

    int status;

    _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");

    rows.clear();

    cols.clear();

  }

    : LpBase(), CplexBase(), LpSolver() {}

    : LpBase(), CplexBase(env), LpSolver() {}

    : LpBase(), CplexBase(other), LpSolver() {}

    _col_status.clear();

    _row_status.clear();

    _primal_ray.clear();

    _dual_ray.clear();

  }

  // The routine returns zero unless an error occurred during the

  // optimization. Examples of errors include exhausting available

  // memory (CPXERR_NO_MEMORY) or encountering invalid data in the

  // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a

  // user-specified CPLEX limit, or proving the model infeasible or

  // unbounded, are not considered errors. Note that a zero return

  // value does not necessarily mean that a solution exists. Use query

  // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain

  // further information about the status of the optimization.

#if CPX_VERSION >= 800

    if (status == 0) {

      switch (CPXgetstat(cplexEnv(), _prob)) {

      case CPX_STAT_OPTIMAL:

      case CPX_STAT_INFEASIBLE:

      case CPX_STAT_UNBOUNDED:

        return SOLVED;

      default:

        return UNSOLVED;

      }

    } else {

      return UNSOLVED;

      case CPX_TIME_LIM_FEAS:

      case CPX_TIME_LIM_INFEAS:

        return UNSOLVED;

      default:

        return SOLVED;

      }

    } else {

      return UNSOLVED;

    }

#endif

  }

    _clear_temporals();

    return convertStatus(CPXlpopt(cplexEnv(), _prob));

  }

    _clear_temporals();

    return convertStatus(CPXprimopt(cplexEnv(), _prob));

  }

    _clear_temporals();

    return convertStatus(CPXdualopt(cplexEnv(), _prob));

  }

    _clear_temporals();

    return convertStatus(CPXbaropt(cplexEnv(), _prob));

  }

    Value x;

    CPXgetx(cplexEnv(), _prob, &x, i, i);

    return x;

  }

    Value y;

    CPXgetpi(cplexEnv(), _prob, &y, i, i);

    return y;

  }

    Value objval;

    CPXgetobjval(cplexEnv(), _prob, &objval);

    return objval;

  }

    if (_col_status.empty()) {

      _col_status.resize(CPXgetnumcols(cplexEnv(), _prob));

      CPXgetbase(cplexEnv(), _prob, &_col_status.front(), 0);

    }

    switch (_col_status[i]) {

    case CPX_BASIC:

      return BASIC;

    case CPX_FREE_SUPER:

      return FREE;

    case CPX_AT_LOWER:

      return LOWER;

    case CPX_AT_UPPER:

      return UPPER;

    default:

      LEMON_ASSERT(false, "Wrong column status");

    }

  }

    if (_row_status.empty()) {

      _row_status.resize(CPXgetnumrows(cplexEnv(), _prob));

      CPXgetbase(cplexEnv(), _prob, 0, &_row_status.front());

    }

    switch (_row_status[i]) {

    case CPX_BASIC:

      return BASIC;

    case CPX_AT_LOWER:

      {

        char s;

        CPXgetsense(cplexEnv(), _prob, &s, i, i);

        return s != 'L' ? LOWER : UPPER;

      }

    case CPX_AT_UPPER:

      return UPPER;

    default:

      LEMON_ASSERT(false, "Wrong row status");

    }

  }

    if (_primal_ray.empty()) {

      _primal_ray.resize(CPXgetnumcols(cplexEnv(), _prob));

      CPXgetray(cplexEnv(), _prob, &_primal_ray.front());

    }

    return _primal_ray[i];

  }

    if (_dual_ray.empty()) {

    }

    return _dual_ray[i];

  }

  //7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!)

  // This table lists the statuses, returned by the CPXgetstat()

  // routine, for solutions to LP problems or mixed integer problems. If

  // no solution exists, the return value is zero.

  // For Simplex, Barrier

        stat=CPX_INFEASIBLE;

      }

      else{

        if (stat==CPX_INFEASIBLE)

          stat=CPX_UNBOUNDED;

      }

    }

  }

#else

  void statusSwitch(CPXENVptr,int&){}

#endif

    // Unboundedness not treated well: the following is from cplex 9.0 doc

    // About Unboundedness

    // The treatment of models that are unbounded involves a few

    // subtleties. Specifically, a declaration of unboundedness means that

    // ILOG CPLEX has determined that the model has an unbounded

    // ray. Given any feasible solution x with objective z, a multiple of

    // the unbounded ray can be added to x to give a feasible solution

    // with objective z-1 (or z+1 for maximization models). Thus, if a

    // feasible solution exists, then the optimal objective is

    // unbounded. Note that ILOG CPLEX has not necessarily concluded that

    // a feasible solution exists. Users can call the routine CPXsolninfo

  // CPX_STAT_ABORT_TIME_LIM

  // CPX_STAT_ABORT_USER

  // CPX_STAT_FEASIBLE_RELAXED

  // CPX_STAT_INFEASIBLE

  // CPX_STAT_INForUNBD

  // CPX_STAT_NUM_BEST

  // CPX_STAT_OPTIMAL

  // CPX_STAT_OPTIMAL_FACE_UNBOUNDED

  // CPX_STAT_OPTIMAL_INFEAS

  // CPX_STAT_OPTIMAL_RELAXED

  // CPX_STAT_UNBOUNDED

    int stat = CPXgetstat(cplexEnv(), _prob);

#if CPX_VERSION >= 800

    switch (stat) {

    case CPX_STAT_OPTIMAL:

      return OPTIMAL;

    case CPX_STAT_UNBOUNDED:

      return INFEASIBLE;

    default:

      return UNDEFINED;

    }

#else

    statusSwitch(cplexEnv(),stat);

      return UNDEFINED; //Undefined

    case CPX_OPTIMAL://Optimal

      return OPTIMAL;

    case CPX_UNBOUNDED:

      return INFEASIBLE;

    default:

      return UNDEFINED; //Everything else comes here

      //FIXME error

    }

#endif

  }

    : LpBase(), CplexBase(), MipSolver() {

#if CPX_VERSION < 800

    CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MIP);

#else

    CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MILP);

#endif

  }

    : LpBase(), CplexBase(env), MipSolver() {

#if CPX_VERSION < 800

    CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MIP);

#else

    CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MILP);

#endif

  }

    : LpBase(), CplexBase(other), MipSolver() {}

    // Note If a variable is to be changed to binary, a call to CPXchgbds

    // should also be made to change the bounds to 0 and 1.

    switch (col_type){

    case INTEGER: {

      const char t = 'I';

      CPXchgctype (cplexEnv(), _prob, 1, &i, &t);

    } break;

    case REAL: {

      const char t = 'C';

      CPXchgctype (cplexEnv(), _prob, 1, &i, &t);

    } break;

    default:

      break;

    }

  }

    char t;

    CPXgetctype (cplexEnv(), _prob, &t, i, i);

    switch (t) {

    case 'I':

      return INTEGER;

    case 'C':

      return REAL;

    default:

      LEMON_ASSERT(false, "Invalid column type");

      return ColTypes();

    }

  }

    int status;

    status = CPXmipopt (cplexEnv(), _prob);

    if (status==0)

      return SOLVED;

    else

      return UNSOLVED;

  }

    int stat = CPXgetstat(cplexEnv(), _prob);

    //Fortunately, MIP statuses did not change for cplex 8.0

    switch (stat) {

    case CPXMIP_OPTIMAL:

      // Optimal integer solution has been found.

    case CPXMIP_OPTIMAL_TOL:

      // Optimal soluton with the tolerance defined by epgap or epagap has

      // been found.

      return OPTIMAL;

      //This also exists in later issues

    // subtleties. Specifically, a declaration of unboundedness means that

    // ILOG CPLEX has determined that the model has an unbounded

    // ray. Given any feasible solution x with objective z, a multiple of

    // the unbounded ray can be added to x to give a feasible solution

    // with objective z-1 (or z+1 for maximization models). Thus, if a

    // feasible solution exists, then the optimal objective is

    // unbounded. Note that ILOG CPLEX has not necessarily concluded that

    // a feasible solution exists. Users can call the routine CPXsolninfo

    // to determine whether ILOG CPLEX has also concluded that the model

    // has a feasible solution.

  }

    Value x;

    CPXgetmipx(cplexEnv(), _prob, &x, i, i);

    return x;

  }

    Value objval;

    CPXgetmipobjval(cplexEnv(), _prob, &objval);

    return objval;

  }

} //namespace lemon

    ///

    const cpxenv* cplexEnv() const { return _env.cplexEnv(); }

    cpxlp* cplexLp() { return _prob; }

    const cpxlp* cplexLp() const { return _prob; }

  };

  /// \brief Interface for the CPLEX LP solver

  ///

  /// This class implements an interface for the CPLEX LP solver.

  ///\ingroup lp_group

  public:

    /// \e

    /// \e

    /// \e

    /// \e

  private:

    // these values cannot retrieved element by element

    mutable std::vector<int> _col_status;

    mutable std::vector<int> _row_status;

    mutable std::vector<Value> _primal_ray;

    mutable std::vector<Value> _dual_ray;

    void _clear_temporals();

    SolveExitStatus convertStatus(int status);

  protected:

    virtual const char* _solverName() const;

    virtual SolveExitStatus _solve();

    virtual Value _getPrimal(int i) const;

    virtual Value _getDual(int i) const;

    virtual Value _getPrimalValue() const;

    virtual VarStatus _getColStatus(int i) const;

    virtual VarStatus _getRowStatus(int i) const;

    virtual Value _getPrimalRay(int i) const;

    /// Solve with dual simplex method

    SolveExitStatus solveDual();

    /// Solve with barrier method

    SolveExitStatus solveBarrier();

  };

  /// \brief Interface for the CPLEX MIP solver

  ///

  /// This class implements an interface for the CPLEX MIP solver.

  ///\ingroup lp_group

  public:

    /// \e

    /// \e

    /// \e

    /// \e

  protected:

    virtual const char* _solverName() const;

    virtual ColTypes _getColType(int col) const;

    virtual void _setColType(int col, ColTypes col_type);

    virtual SolveExitStatus _solve();

    virtual ProblemType _getType() const;

    virtual Value _getSol(int i) const;

    virtual Value _getSolValue() const;

  };

    default:

      LEMON_ASSERT(false, "Wrong sense");

      return GlpkBase::Sense();