lemon/cplex.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 461 08d495d48089
child 540 9db62975c32b
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

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