lemon/cplex.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:30:45 +0100
changeset 809 22bb98ca0101
parent 576 745e182d0139
child 877 141f9c0db4a3
permissions -rw-r--r--
Entirely rework CostScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster.
- Handle GEQ supply type (LEQ is not supported).
- Handle infinite upper bounds.
- Handle negative costs (for arcs of finite upper bound).
- Traits class + named parameter for the LargeCost type used in
internal computations.
- Extend the documentation.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <iostream>
    20 #include <vector>
    21 #include <cstring>
    22 
    23 #include <lemon/cplex.h>
    24 
    25 extern "C" {
    26 #include <ilcplex/cplex.h>
    27 }
    28 
    29 
    30 ///\file
    31 ///\brief Implementation of the LEMON-CPLEX lp solver interface.
    32 namespace lemon {
    33 
    34   CplexEnv::LicenseError::LicenseError(int status) {
    35     if (!CPXgeterrorstring(0, status, _message)) {
    36       std::strcpy(_message, "Cplex unknown error");
    37     }
    38   }
    39 
    40   CplexEnv::CplexEnv() {
    41     int status;
    42     _cnt = new int;
    43     _env = CPXopenCPLEX(&status);
    44     if (_env == 0) {
    45       delete _cnt;
    46       _cnt = 0;
    47       throw LicenseError(status);
    48     }
    49   }
    50 
    51   CplexEnv::CplexEnv(const CplexEnv& other) {
    52     _env = other._env;
    53     _cnt = other._cnt;
    54     ++(*_cnt);
    55   }
    56 
    57   CplexEnv& CplexEnv::operator=(const CplexEnv& other) {
    58     _env = other._env;
    59     _cnt = other._cnt;
    60     ++(*_cnt);
    61     return *this;
    62   }
    63 
    64   CplexEnv::~CplexEnv() {
    65     --(*_cnt);
    66     if (*_cnt == 0) {
    67       delete _cnt;
    68       CPXcloseCPLEX(&_env);
    69     }
    70   }
    71 
    72   CplexBase::CplexBase() : LpBase() {
    73     int status;
    74     _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
    75     messageLevel(MESSAGE_NOTHING);
    76   }
    77 
    78   CplexBase::CplexBase(const CplexEnv& env)
    79     : LpBase(), _env(env) {
    80     int status;
    81     _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
    82     messageLevel(MESSAGE_NOTHING);
    83   }
    84 
    85   CplexBase::CplexBase(const CplexBase& cplex)
    86     : LpBase() {
    87     int status;
    88     _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status);
    89     rows = cplex.rows;
    90     cols = cplex.cols;
    91     messageLevel(MESSAGE_NOTHING);
    92   }
    93 
    94   CplexBase::~CplexBase() {
    95     CPXfreeprob(cplexEnv(),&_prob);
    96   }
    97 
    98   int CplexBase::_addCol() {
    99     int i = CPXgetnumcols(cplexEnv(), _prob);
   100     double lb = -INF, ub = INF;
   101     CPXnewcols(cplexEnv(), _prob, 1, 0, &lb, &ub, 0, 0);
   102     return i;
   103   }
   104 
   105 
   106   int CplexBase::_addRow() {
   107     int i = CPXgetnumrows(cplexEnv(), _prob);
   108     const double ub = INF;
   109     const char s = 'L';
   110     CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
   111     return i;
   112   }
   113 
   114   int CplexBase::_addRow(Value lb, ExprIterator b, 
   115                          ExprIterator e, Value ub) {
   116     int i = CPXgetnumrows(cplexEnv(), _prob);
   117     if (lb == -INF) {
   118       const char s = 'L';
   119       CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0);
   120     } else if (ub == INF) {
   121       const char s = 'G';
   122       CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
   123     } else if (lb == ub){
   124       const char s = 'E';
   125       CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0);
   126     } else {
   127       const char s = 'R';
   128       double len = ub - lb;
   129       CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0);
   130     }
   131 
   132     std::vector<int> indices;
   133     std::vector<int> rowlist;
   134     std::vector<Value> values;
   135 
   136     for(ExprIterator it=b; it!=e; ++it) {
   137       indices.push_back(it->first);
   138       values.push_back(it->second);
   139       rowlist.push_back(i);
   140     }
   141 
   142     CPXchgcoeflist(cplexEnv(), _prob, values.size(),
   143                    &rowlist.front(), &indices.front(), &values.front());
   144 
   145     return i;
   146   }
   147 
   148   void CplexBase::_eraseCol(int i) {
   149     CPXdelcols(cplexEnv(), _prob, i, i);
   150   }
   151 
   152   void CplexBase::_eraseRow(int i) {
   153     CPXdelrows(cplexEnv(), _prob, i, i);
   154   }
   155 
   156   void CplexBase::_eraseColId(int i) {
   157     cols.eraseIndex(i);
   158     cols.shiftIndices(i);
   159   }
   160   void CplexBase::_eraseRowId(int i) {
   161     rows.eraseIndex(i);
   162     rows.shiftIndices(i);
   163   }
   164 
   165   void CplexBase::_getColName(int col, std::string &name) const {
   166     int size;
   167     CPXgetcolname(cplexEnv(), _prob, 0, 0, 0, &size, col, col);
   168     if (size == 0) {
   169       name.clear();
   170       return;
   171     }
   172 
   173     size *= -1;
   174     std::vector<char> buf(size);
   175     char *cname;
   176     int tmp;
   177     CPXgetcolname(cplexEnv(), _prob, &cname, &buf.front(), size,
   178                   &tmp, col, col);
   179     name = cname;
   180   }
   181 
   182   void CplexBase::_setColName(int col, const std::string &name) {
   183     char *cname;
   184     cname = const_cast<char*>(name.c_str());
   185     CPXchgcolname(cplexEnv(), _prob, 1, &col, &cname);
   186   }
   187 
   188   int CplexBase::_colByName(const std::string& name) const {
   189     int index;
   190     if (CPXgetcolindex(cplexEnv(), _prob,
   191                        const_cast<char*>(name.c_str()), &index) == 0) {
   192       return index;
   193     }
   194     return -1;
   195   }
   196 
   197   void CplexBase::_getRowName(int row, std::string &name) const {
   198     int size;
   199     CPXgetrowname(cplexEnv(), _prob, 0, 0, 0, &size, row, row);
   200     if (size == 0) {
   201       name.clear();
   202       return;
   203     }
   204 
   205     size *= -1;
   206     std::vector<char> buf(size);
   207     char *cname;
   208     int tmp;
   209     CPXgetrowname(cplexEnv(), _prob, &cname, &buf.front(), size,
   210                   &tmp, row, row);
   211     name = cname;
   212   }
   213 
   214   void CplexBase::_setRowName(int row, const std::string &name) {
   215     char *cname;
   216     cname = const_cast<char*>(name.c_str());
   217     CPXchgrowname(cplexEnv(), _prob, 1, &row, &cname);
   218   }
   219 
   220   int CplexBase::_rowByName(const std::string& name) const {
   221     int index;
   222     if (CPXgetrowindex(cplexEnv(), _prob,
   223                        const_cast<char*>(name.c_str()), &index) == 0) {
   224       return index;
   225     }
   226     return -1;
   227   }
   228 
   229   void CplexBase::_setRowCoeffs(int i, ExprIterator b,
   230                                       ExprIterator e)
   231   {
   232     std::vector<int> indices;
   233     std::vector<int> rowlist;
   234     std::vector<Value> values;
   235 
   236     for(ExprIterator it=b; it!=e; ++it) {
   237       indices.push_back(it->first);
   238       values.push_back(it->second);
   239       rowlist.push_back(i);
   240     }
   241 
   242     CPXchgcoeflist(cplexEnv(), _prob, values.size(),
   243                    &rowlist.front(), &indices.front(), &values.front());
   244   }
   245 
   246   void CplexBase::_getRowCoeffs(int i, InsertIterator b) const {
   247     int tmp1, tmp2, tmp3, length;
   248     CPXgetrows(cplexEnv(), _prob, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
   249 
   250     length = -length;
   251     std::vector<int> indices(length);
   252     std::vector<double> values(length);
   253 
   254     CPXgetrows(cplexEnv(), _prob, &tmp1, &tmp2,
   255                &indices.front(), &values.front(),
   256                length, &tmp3, i, i);
   257 
   258     for (int i = 0; i < length; ++i) {
   259       *b = std::make_pair(indices[i], values[i]);
   260       ++b;
   261     }
   262   }
   263 
   264   void CplexBase::_setColCoeffs(int i, ExprIterator b, ExprIterator e) {
   265     std::vector<int> indices;
   266     std::vector<int> collist;
   267     std::vector<Value> values;
   268 
   269     for(ExprIterator it=b; it!=e; ++it) {
   270       indices.push_back(it->first);
   271       values.push_back(it->second);
   272       collist.push_back(i);
   273     }
   274 
   275     CPXchgcoeflist(cplexEnv(), _prob, values.size(),
   276                    &indices.front(), &collist.front(), &values.front());
   277   }
   278 
   279   void CplexBase::_getColCoeffs(int i, InsertIterator b) const {
   280 
   281     int tmp1, tmp2, tmp3, length;
   282     CPXgetcols(cplexEnv(), _prob, &tmp1, &tmp2, 0, 0, 0, &length, i, i);
   283 
   284     length = -length;
   285     std::vector<int> indices(length);
   286     std::vector<double> values(length);
   287 
   288     CPXgetcols(cplexEnv(), _prob, &tmp1, &tmp2,
   289                &indices.front(), &values.front(),
   290                length, &tmp3, i, i);
   291 
   292     for (int i = 0; i < length; ++i) {
   293       *b = std::make_pair(indices[i], values[i]);
   294       ++b;
   295     }
   296 
   297   }
   298 
   299   void CplexBase::_setCoeff(int row, int col, Value value) {
   300     CPXchgcoef(cplexEnv(), _prob, row, col, value);
   301   }
   302 
   303   CplexBase::Value CplexBase::_getCoeff(int row, int col) const {
   304     CplexBase::Value value;
   305     CPXgetcoef(cplexEnv(), _prob, row, col, &value);
   306     return value;
   307   }
   308 
   309   void CplexBase::_setColLowerBound(int i, Value value) {
   310     const char s = 'L';
   311     CPXchgbds(cplexEnv(), _prob, 1, &i, &s, &value);
   312   }
   313 
   314   CplexBase::Value CplexBase::_getColLowerBound(int i) const {
   315     CplexBase::Value res;
   316     CPXgetlb(cplexEnv(), _prob, &res, i, i);
   317     return res <= -CPX_INFBOUND ? -INF : res;
   318   }
   319 
   320   void CplexBase::_setColUpperBound(int i, Value value)
   321   {
   322     const char s = 'U';
   323     CPXchgbds(cplexEnv(), _prob, 1, &i, &s, &value);
   324   }
   325 
   326   CplexBase::Value CplexBase::_getColUpperBound(int i) const {
   327     CplexBase::Value res;
   328     CPXgetub(cplexEnv(), _prob, &res, i, i);
   329     return res >= CPX_INFBOUND ? INF : res;
   330   }
   331 
   332   CplexBase::Value CplexBase::_getRowLowerBound(int i) const {
   333     char s;
   334     CPXgetsense(cplexEnv(), _prob, &s, i, i);
   335     CplexBase::Value res;
   336 
   337     switch (s) {
   338     case 'G':
   339     case 'R':
   340     case 'E':
   341       CPXgetrhs(cplexEnv(), _prob, &res, i, i);
   342       return res <= -CPX_INFBOUND ? -INF : res;
   343     default:
   344       return -INF;
   345     }
   346   }
   347 
   348   CplexBase::Value CplexBase::_getRowUpperBound(int i) const {
   349     char s;
   350     CPXgetsense(cplexEnv(), _prob, &s, i, i);
   351     CplexBase::Value res;
   352 
   353     switch (s) {
   354     case 'L':
   355     case 'E':
   356       CPXgetrhs(cplexEnv(), _prob, &res, i, i);
   357       return res >= CPX_INFBOUND ? INF : res;
   358     case 'R':
   359       CPXgetrhs(cplexEnv(), _prob, &res, i, i);
   360       {
   361         double rng;
   362         CPXgetrngval(cplexEnv(), _prob, &rng, i, i);
   363         res += rng;
   364       }
   365       return res >= CPX_INFBOUND ? INF : res;
   366     default:
   367       return INF;
   368     }
   369   }
   370 
   371   //This is easier to implement
   372   void CplexBase::_set_row_bounds(int i, Value lb, Value ub) {
   373     if (lb == -INF) {
   374       const char s = 'L';
   375       CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
   376       CPXchgrhs(cplexEnv(), _prob, 1, &i, &ub);
   377     } else if (ub == INF) {
   378       const char s = 'G';
   379       CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
   380       CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
   381     } else if (lb == ub){
   382       const char s = 'E';
   383       CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
   384       CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
   385     } else {
   386       const char s = 'R';
   387       CPXchgsense(cplexEnv(), _prob, 1, &i, &s);
   388       CPXchgrhs(cplexEnv(), _prob, 1, &i, &lb);
   389       double len = ub - lb;
   390       CPXchgrngval(cplexEnv(), _prob, 1, &i, &len);
   391     }
   392   }
   393 
   394   void CplexBase::_setRowLowerBound(int i, Value lb)
   395   {
   396     LEMON_ASSERT(lb != INF, "Invalid bound");
   397     _set_row_bounds(i, lb, CplexBase::_getRowUpperBound(i));
   398   }
   399 
   400   void CplexBase::_setRowUpperBound(int i, Value ub)
   401   {
   402 
   403     LEMON_ASSERT(ub != -INF, "Invalid bound");
   404     _set_row_bounds(i, CplexBase::_getRowLowerBound(i), ub);
   405   }
   406 
   407   void CplexBase::_setObjCoeffs(ExprIterator b, ExprIterator e)
   408   {
   409     std::vector<int> indices;
   410     std::vector<Value> values;
   411     for(ExprIterator it=b; it!=e; ++it) {
   412       indices.push_back(it->first);
   413       values.push_back(it->second);
   414     }
   415     CPXchgobj(cplexEnv(), _prob, values.size(),
   416               &indices.front(), &values.front());
   417 
   418   }
   419 
   420   void CplexBase::_getObjCoeffs(InsertIterator b) const
   421   {
   422     int num = CPXgetnumcols(cplexEnv(), _prob);
   423     std::vector<Value> x(num);
   424 
   425     CPXgetobj(cplexEnv(), _prob, &x.front(), 0, num - 1);
   426     for (int i = 0; i < num; ++i) {
   427       if (x[i] != 0.0) {
   428         *b = std::make_pair(i, x[i]);
   429         ++b;
   430       }
   431     }
   432   }
   433 
   434   void CplexBase::_setObjCoeff(int i, Value obj_coef)
   435   {
   436     CPXchgobj(cplexEnv(), _prob, 1, &i, &obj_coef);
   437   }
   438 
   439   CplexBase::Value CplexBase::_getObjCoeff(int i) const
   440   {
   441     Value x;
   442     CPXgetobj(cplexEnv(), _prob, &x, i, i);
   443     return x;
   444   }
   445 
   446   void CplexBase::_setSense(CplexBase::Sense sense) {
   447     switch (sense) {
   448     case MIN:
   449       CPXchgobjsen(cplexEnv(), _prob, CPX_MIN);
   450       break;
   451     case MAX:
   452       CPXchgobjsen(cplexEnv(), _prob, CPX_MAX);
   453       break;
   454     }
   455   }
   456 
   457   CplexBase::Sense CplexBase::_getSense() const {
   458     switch (CPXgetobjsen(cplexEnv(), _prob)) {
   459     case CPX_MIN:
   460       return MIN;
   461     case CPX_MAX:
   462       return MAX;
   463     default:
   464       LEMON_ASSERT(false, "Invalid sense");
   465       return CplexBase::Sense();
   466     }
   467   }
   468 
   469   void CplexBase::_clear() {
   470     CPXfreeprob(cplexEnv(),&_prob);
   471     int status;
   472     _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem");
   473     rows.clear();
   474     cols.clear();
   475   }
   476 
   477   void CplexBase::_messageLevel(MessageLevel level) {
   478     switch (level) {
   479     case MESSAGE_NOTHING:
   480       _message_enabled = false;
   481       break;
   482     case MESSAGE_ERROR:
   483     case MESSAGE_WARNING:
   484     case MESSAGE_NORMAL:
   485     case MESSAGE_VERBOSE:
   486       _message_enabled = true;
   487       break;
   488     }
   489   }
   490 
   491   void CplexBase::_applyMessageLevel() {
   492     CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, 
   493                    _message_enabled ? CPX_ON : CPX_OFF);
   494   }
   495 
   496   // CplexLp members
   497 
   498   CplexLp::CplexLp()
   499     : LpBase(), LpSolver(), CplexBase() {}
   500 
   501   CplexLp::CplexLp(const CplexEnv& env)
   502     : LpBase(), LpSolver(), CplexBase(env) {}
   503 
   504   CplexLp::CplexLp(const CplexLp& other)
   505     : LpBase(), LpSolver(), CplexBase(other) {}
   506 
   507   CplexLp::~CplexLp() {}
   508 
   509   CplexLp* CplexLp::newSolver() const { return new CplexLp; }
   510   CplexLp* CplexLp::cloneSolver() const {return new CplexLp(*this); }
   511 
   512   const char* CplexLp::_solverName() const { return "CplexLp"; }
   513 
   514   void CplexLp::_clear_temporals() {
   515     _col_status.clear();
   516     _row_status.clear();
   517     _primal_ray.clear();
   518     _dual_ray.clear();
   519   }
   520 
   521   // The routine returns zero unless an error occurred during the
   522   // optimization. Examples of errors include exhausting available
   523   // memory (CPXERR_NO_MEMORY) or encountering invalid data in the
   524   // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a
   525   // user-specified CPLEX limit, or proving the model infeasible or
   526   // unbounded, are not considered errors. Note that a zero return
   527   // value does not necessarily mean that a solution exists. Use query
   528   // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain
   529   // further information about the status of the optimization.
   530   CplexLp::SolveExitStatus CplexLp::convertStatus(int status) {
   531 #if CPX_VERSION >= 800
   532     if (status == 0) {
   533       switch (CPXgetstat(cplexEnv(), _prob)) {
   534       case CPX_STAT_OPTIMAL:
   535       case CPX_STAT_INFEASIBLE:
   536       case CPX_STAT_UNBOUNDED:
   537         return SOLVED;
   538       default:
   539         return UNSOLVED;
   540       }
   541     } else {
   542       return UNSOLVED;
   543     }
   544 #else
   545     if (status == 0) {
   546       //We want to exclude some cases
   547       switch (CPXgetstat(cplexEnv(), _prob)) {
   548       case CPX_OBJ_LIM:
   549       case CPX_IT_LIM_FEAS:
   550       case CPX_IT_LIM_INFEAS:
   551       case CPX_TIME_LIM_FEAS:
   552       case CPX_TIME_LIM_INFEAS:
   553         return UNSOLVED;
   554       default:
   555         return SOLVED;
   556       }
   557     } else {
   558       return UNSOLVED;
   559     }
   560 #endif
   561   }
   562 
   563   CplexLp::SolveExitStatus CplexLp::_solve() {
   564     _clear_temporals();
   565     _applyMessageLevel();
   566     return convertStatus(CPXlpopt(cplexEnv(), _prob));
   567   }
   568 
   569   CplexLp::SolveExitStatus CplexLp::solvePrimal() {
   570     _clear_temporals();
   571     _applyMessageLevel();
   572     return convertStatus(CPXprimopt(cplexEnv(), _prob));
   573   }
   574 
   575   CplexLp::SolveExitStatus CplexLp::solveDual() {
   576     _clear_temporals();
   577     _applyMessageLevel();
   578     return convertStatus(CPXdualopt(cplexEnv(), _prob));
   579   }
   580 
   581   CplexLp::SolveExitStatus CplexLp::solveBarrier() {
   582     _clear_temporals();
   583     _applyMessageLevel();
   584     return convertStatus(CPXbaropt(cplexEnv(), _prob));
   585   }
   586 
   587   CplexLp::Value CplexLp::_getPrimal(int i) const {
   588     Value x;
   589     CPXgetx(cplexEnv(), _prob, &x, i, i);
   590     return x;
   591   }
   592 
   593   CplexLp::Value CplexLp::_getDual(int i) const {
   594     Value y;
   595     CPXgetpi(cplexEnv(), _prob, &y, i, i);
   596     return y;
   597   }
   598 
   599   CplexLp::Value CplexLp::_getPrimalValue() const {
   600     Value objval;
   601     CPXgetobjval(cplexEnv(), _prob, &objval);
   602     return objval;
   603   }
   604 
   605   CplexLp::VarStatus CplexLp::_getColStatus(int i) const {
   606     if (_col_status.empty()) {
   607       _col_status.resize(CPXgetnumcols(cplexEnv(), _prob));
   608       CPXgetbase(cplexEnv(), _prob, &_col_status.front(), 0);
   609     }
   610     switch (_col_status[i]) {
   611     case CPX_BASIC:
   612       return BASIC;
   613     case CPX_FREE_SUPER:
   614       return FREE;
   615     case CPX_AT_LOWER:
   616       return LOWER;
   617     case CPX_AT_UPPER:
   618       return UPPER;
   619     default:
   620       LEMON_ASSERT(false, "Wrong column status");
   621       return CplexLp::VarStatus();
   622     }
   623   }
   624 
   625   CplexLp::VarStatus CplexLp::_getRowStatus(int i) const {
   626     if (_row_status.empty()) {
   627       _row_status.resize(CPXgetnumrows(cplexEnv(), _prob));
   628       CPXgetbase(cplexEnv(), _prob, 0, &_row_status.front());
   629     }
   630     switch (_row_status[i]) {
   631     case CPX_BASIC:
   632       return BASIC;
   633     case CPX_AT_LOWER:
   634       {
   635         char s;
   636         CPXgetsense(cplexEnv(), _prob, &s, i, i);
   637         return s != 'L' ? LOWER : UPPER;
   638       }
   639     case CPX_AT_UPPER:
   640       return UPPER;
   641     default:
   642       LEMON_ASSERT(false, "Wrong row status");
   643       return CplexLp::VarStatus();
   644     }
   645   }
   646 
   647   CplexLp::Value CplexLp::_getPrimalRay(int i) const {
   648     if (_primal_ray.empty()) {
   649       _primal_ray.resize(CPXgetnumcols(cplexEnv(), _prob));
   650       CPXgetray(cplexEnv(), _prob, &_primal_ray.front());
   651     }
   652     return _primal_ray[i];
   653   }
   654 
   655   CplexLp::Value CplexLp::_getDualRay(int i) const {
   656     if (_dual_ray.empty()) {
   657 
   658     }
   659     return _dual_ray[i];
   660   }
   661 
   662   // Cplex 7.0 status values
   663   // This table lists the statuses, returned by the CPXgetstat()
   664   // routine, for solutions to LP problems or mixed integer problems. If
   665   // no solution exists, the return value is zero.
   666 
   667   // For Simplex, Barrier
   668   // 1          CPX_OPTIMAL
   669   //          Optimal solution found
   670   // 2          CPX_INFEASIBLE
   671   //          Problem infeasible
   672   // 3    CPX_UNBOUNDED
   673   //          Problem unbounded
   674   // 4          CPX_OBJ_LIM
   675   //          Objective limit exceeded in Phase II
   676   // 5          CPX_IT_LIM_FEAS
   677   //          Iteration limit exceeded in Phase II
   678   // 6          CPX_IT_LIM_INFEAS
   679   //          Iteration limit exceeded in Phase I
   680   // 7          CPX_TIME_LIM_FEAS
   681   //          Time limit exceeded in Phase II
   682   // 8          CPX_TIME_LIM_INFEAS
   683   //          Time limit exceeded in Phase I
   684   // 9          CPX_NUM_BEST_FEAS
   685   //          Problem non-optimal, singularities in Phase II
   686   // 10         CPX_NUM_BEST_INFEAS
   687   //          Problem non-optimal, singularities in Phase I
   688   // 11         CPX_OPTIMAL_INFEAS
   689   //          Optimal solution found, unscaled infeasibilities
   690   // 12         CPX_ABORT_FEAS
   691   //          Aborted in Phase II
   692   // 13         CPX_ABORT_INFEAS
   693   //          Aborted in Phase I
   694   // 14          CPX_ABORT_DUAL_INFEAS
   695   //          Aborted in barrier, dual infeasible
   696   // 15          CPX_ABORT_PRIM_INFEAS
   697   //          Aborted in barrier, primal infeasible
   698   // 16          CPX_ABORT_PRIM_DUAL_INFEAS
   699   //          Aborted in barrier, primal and dual infeasible
   700   // 17          CPX_ABORT_PRIM_DUAL_FEAS
   701   //          Aborted in barrier, primal and dual feasible
   702   // 18          CPX_ABORT_CROSSOVER
   703   //          Aborted in crossover
   704   // 19          CPX_INForUNBD
   705   //          Infeasible or unbounded
   706   // 20   CPX_PIVOT
   707   //       User pivot used
   708   //
   709   // Pending return values
   710   // ??case CPX_ABORT_DUAL_INFEAS
   711   // ??case CPX_ABORT_CROSSOVER
   712   // ??case CPX_INForUNBD
   713   // ??case CPX_PIVOT
   714 
   715   //Some more interesting stuff:
   716 
   717   // CPX_PARAM_PROBMETHOD  1062  int  LPMETHOD
   718   // 0 Automatic
   719   // 1 Primal Simplex
   720   // 2 Dual Simplex
   721   // 3 Network Simplex
   722   // 4 Standard Barrier
   723   // Default: 0
   724   // Description: Method for linear optimization.
   725   // Determines which algorithm is used when CPXlpopt() (or "optimize"
   726   // in the Interactive Optimizer) is called. Currently the behavior of
   727   // the "Automatic" setting is that CPLEX simply invokes the dual
   728   // simplex method, but this capability may be expanded in the future
   729   // so that CPLEX chooses the method based on problem characteristics
   730 #if CPX_VERSION < 900
   731   void statusSwitch(CPXENVptr cplexEnv(),int& stat){
   732     int lpmethod;
   733     CPXgetintparam (cplexEnv(),CPX_PARAM_PROBMETHOD,&lpmethod);
   734     if (lpmethod==2){
   735       if (stat==CPX_UNBOUNDED){
   736         stat=CPX_INFEASIBLE;
   737       }
   738       else{
   739         if (stat==CPX_INFEASIBLE)
   740           stat=CPX_UNBOUNDED;
   741       }
   742     }
   743   }
   744 #else
   745   void statusSwitch(CPXENVptr,int&){}
   746 #endif
   747 
   748   CplexLp::ProblemType CplexLp::_getPrimalType() const {
   749     // Unboundedness not treated well: the following is from cplex 9.0 doc
   750     // About Unboundedness
   751 
   752     // The treatment of models that are unbounded involves a few
   753     // subtleties. Specifically, a declaration of unboundedness means that
   754     // ILOG CPLEX has determined that the model has an unbounded
   755     // ray. Given any feasible solution x with objective z, a multiple of
   756     // the unbounded ray can be added to x to give a feasible solution
   757     // with objective z-1 (or z+1 for maximization models). Thus, if a
   758     // feasible solution exists, then the optimal objective is
   759     // unbounded. Note that ILOG CPLEX has not necessarily concluded that
   760     // a feasible solution exists. Users can call the routine CPXsolninfo
   761     // to determine whether ILOG CPLEX has also concluded that the model
   762     // has a feasible solution.
   763 
   764     int stat = CPXgetstat(cplexEnv(), _prob);
   765 #if CPX_VERSION >= 800
   766     switch (stat)
   767       {
   768       case CPX_STAT_OPTIMAL:
   769         return OPTIMAL;
   770       case CPX_STAT_UNBOUNDED:
   771         return UNBOUNDED;
   772       case CPX_STAT_INFEASIBLE:
   773         return INFEASIBLE;
   774       default:
   775         return UNDEFINED;
   776       }
   777 #else
   778     statusSwitch(cplexEnv(),stat);
   779     //CPXgetstat(cplexEnv(), _prob);
   780     switch (stat) {
   781     case 0:
   782       return UNDEFINED; //Undefined
   783     case CPX_OPTIMAL://Optimal
   784       return OPTIMAL;
   785     case CPX_UNBOUNDED://Unbounded
   786       return INFEASIBLE;//In case of dual simplex
   787       //return UNBOUNDED;
   788     case CPX_INFEASIBLE://Infeasible
   789       //    case CPX_IT_LIM_INFEAS:
   790       //     case CPX_TIME_LIM_INFEAS:
   791       //     case CPX_NUM_BEST_INFEAS:
   792       //     case CPX_OPTIMAL_INFEAS:
   793       //     case CPX_ABORT_INFEAS:
   794       //     case CPX_ABORT_PRIM_INFEAS:
   795       //     case CPX_ABORT_PRIM_DUAL_INFEAS:
   796       return UNBOUNDED;//In case of dual simplex
   797       //return INFEASIBLE;
   798       //     case CPX_OBJ_LIM:
   799       //     case CPX_IT_LIM_FEAS:
   800       //     case CPX_TIME_LIM_FEAS:
   801       //     case CPX_NUM_BEST_FEAS:
   802       //     case CPX_ABORT_FEAS:
   803       //     case CPX_ABORT_PRIM_DUAL_FEAS:
   804       //       return FEASIBLE;
   805     default:
   806       return UNDEFINED; //Everything else comes here
   807       //FIXME error
   808     }
   809 #endif
   810   }
   811 
   812   // Cplex 9.0 status values
   813   // CPX_STAT_ABORT_DUAL_OBJ_LIM
   814   // CPX_STAT_ABORT_IT_LIM
   815   // CPX_STAT_ABORT_OBJ_LIM
   816   // CPX_STAT_ABORT_PRIM_OBJ_LIM
   817   // CPX_STAT_ABORT_TIME_LIM
   818   // CPX_STAT_ABORT_USER
   819   // CPX_STAT_FEASIBLE_RELAXED
   820   // CPX_STAT_INFEASIBLE
   821   // CPX_STAT_INForUNBD
   822   // CPX_STAT_NUM_BEST
   823   // CPX_STAT_OPTIMAL
   824   // CPX_STAT_OPTIMAL_FACE_UNBOUNDED
   825   // CPX_STAT_OPTIMAL_INFEAS
   826   // CPX_STAT_OPTIMAL_RELAXED
   827   // CPX_STAT_UNBOUNDED
   828 
   829   CplexLp::ProblemType CplexLp::_getDualType() const {
   830     int stat = CPXgetstat(cplexEnv(), _prob);
   831 #if CPX_VERSION >= 800
   832     switch (stat) {
   833     case CPX_STAT_OPTIMAL:
   834       return OPTIMAL;
   835     case CPX_STAT_UNBOUNDED:
   836       return INFEASIBLE;
   837     default:
   838       return UNDEFINED;
   839     }
   840 #else
   841     statusSwitch(cplexEnv(),stat);
   842     switch (stat) {
   843     case 0:
   844       return UNDEFINED; //Undefined
   845     case CPX_OPTIMAL://Optimal
   846       return OPTIMAL;
   847     case CPX_UNBOUNDED:
   848       return INFEASIBLE;
   849     default:
   850       return UNDEFINED; //Everything else comes here
   851       //FIXME error
   852     }
   853 #endif
   854   }
   855 
   856   // CplexMip members
   857 
   858   CplexMip::CplexMip()
   859     : LpBase(), MipSolver(), CplexBase() {
   860 
   861 #if CPX_VERSION < 800
   862     CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MIP);
   863 #else
   864     CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MILP);
   865 #endif
   866   }
   867 
   868   CplexMip::CplexMip(const CplexEnv& env)
   869     : LpBase(), MipSolver(), CplexBase(env) {
   870 
   871 #if CPX_VERSION < 800
   872     CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MIP);
   873 #else
   874     CPXchgprobtype(cplexEnv(),  _prob, CPXPROB_MILP);
   875 #endif
   876 
   877   }
   878 
   879   CplexMip::CplexMip(const CplexMip& other)
   880     : LpBase(), MipSolver(), CplexBase(other) {}
   881 
   882   CplexMip::~CplexMip() {}
   883 
   884   CplexMip* CplexMip::newSolver() const { return new CplexMip; }
   885   CplexMip* CplexMip::cloneSolver() const {return new CplexMip(*this); }
   886 
   887   const char* CplexMip::_solverName() const { return "CplexMip"; }
   888 
   889   void CplexMip::_setColType(int i, CplexMip::ColTypes col_type) {
   890 
   891     // Note If a variable is to be changed to binary, a call to CPXchgbds
   892     // should also be made to change the bounds to 0 and 1.
   893 
   894     switch (col_type){
   895     case INTEGER: {
   896       const char t = 'I';
   897       CPXchgctype (cplexEnv(), _prob, 1, &i, &t);
   898     } break;
   899     case REAL: {
   900       const char t = 'C';
   901       CPXchgctype (cplexEnv(), _prob, 1, &i, &t);
   902     } break;
   903     default:
   904       break;
   905     }
   906   }
   907 
   908   CplexMip::ColTypes CplexMip::_getColType(int i) const {
   909     char t;
   910     CPXgetctype (cplexEnv(), _prob, &t, i, i);
   911     switch (t) {
   912     case 'I':
   913       return INTEGER;
   914     case 'C':
   915       return REAL;
   916     default:
   917       LEMON_ASSERT(false, "Invalid column type");
   918       return ColTypes();
   919     }
   920 
   921   }
   922 
   923   CplexMip::SolveExitStatus CplexMip::_solve() {
   924     int status;
   925     _applyMessageLevel();
   926     status = CPXmipopt (cplexEnv(), _prob);
   927     if (status==0)
   928       return SOLVED;
   929     else
   930       return UNSOLVED;
   931 
   932   }
   933 
   934 
   935   CplexMip::ProblemType CplexMip::_getType() const {
   936 
   937     int stat = CPXgetstat(cplexEnv(), _prob);
   938 
   939     //Fortunately, MIP statuses did not change for cplex 8.0
   940     switch (stat) {
   941     case CPXMIP_OPTIMAL:
   942       // Optimal integer solution has been found.
   943     case CPXMIP_OPTIMAL_TOL:
   944       // Optimal soluton with the tolerance defined by epgap or epagap has
   945       // been found.
   946       return OPTIMAL;
   947       //This also exists in later issues
   948       //    case CPXMIP_UNBOUNDED:
   949       //return UNBOUNDED;
   950       case CPXMIP_INFEASIBLE:
   951         return INFEASIBLE;
   952     default:
   953       return UNDEFINED;
   954     }
   955     //Unboundedness not treated well: the following is from cplex 9.0 doc
   956     // About Unboundedness
   957 
   958     // The treatment of models that are unbounded involves a few
   959     // subtleties. Specifically, a declaration of unboundedness means that
   960     // ILOG CPLEX has determined that the model has an unbounded
   961     // ray. Given any feasible solution x with objective z, a multiple of
   962     // the unbounded ray can be added to x to give a feasible solution
   963     // with objective z-1 (or z+1 for maximization models). Thus, if a
   964     // feasible solution exists, then the optimal objective is
   965     // unbounded. Note that ILOG CPLEX has not necessarily concluded that
   966     // a feasible solution exists. Users can call the routine CPXsolninfo
   967     // to determine whether ILOG CPLEX has also concluded that the model
   968     // has a feasible solution.
   969   }
   970 
   971   CplexMip::Value CplexMip::_getSol(int i) const {
   972     Value x;
   973     CPXgetmipx(cplexEnv(), _prob, &x, i, i);
   974     return x;
   975   }
   976 
   977   CplexMip::Value CplexMip::_getSolValue() const {
   978     Value objval;
   979     CPXgetmipobjval(cplexEnv(), _prob, &objval);
   980     return objval;
   981   }
   982 
   983 } //namespace lemon
   984