lemon-0.x: lemon/lp_cplex.cc@8eed667ea23c

     1 /* -*- C++ -*-

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

    19 #include <iostream>

    20 #include<lemon/lp_cplex.h>

    22 ///\file

    23 ///\brief Implementation of the LEMON-CPLEX lp solver interface.

    24 namespace lemon {

    26   LpCplex::LpCplex() : LpSolverBase() {

    27     //    env = CPXopenCPLEXdevelop(&status);

    28     env = CPXopenCPLEX(&status);

    29     lp = CPXcreateprob(env, &status, "LP problem");

    30   }

    32   LpCplex::~LpCplex() {

    33     CPXfreeprob(env,&lp);

    34     CPXcloseCPLEX(&env);

    35   }

    37   LpSolverBase &LpCplex::_newLp()

    38   {

    39     //The first approach opens a new environment

    40     LpCplex* newlp=new LpCplex();

    41     return *newlp;

    42   }

    44   LpSolverBase &LpCplex::_copyLp() {

    45     ///\bug FixID data is not copied!

    46     //The first approach opens a new environment

    47     LpCplex* newlp=new LpCplex();

    48     //The routine CPXcloneprob can be used to create a new CPLEX problem

    49     //object and copy all the problem data from an existing problem

    50     //object to it. Solution and starting information is not copied.

    51     newlp->lp = CPXcloneprob(env, lp, &status);

    52     return *newlp;

    53   }

    55   int LpCplex::_addCol()

    56   {

    57     int i = CPXgetnumcols(env, lp);

    58     Value lb[1],ub[1];

    59     lb[0]=-INF;//-CPX_INFBOUND;

    60     ub[0]=INF;//CPX_INFBOUND;

    61     status = CPXnewcols(env, lp, 1, NULL, lb, ub, NULL, NULL);

    62     return i;

    63   }

    66   int LpCplex::_addRow()

    67   {

    68     //We want a row that is not constrained

    69     char sense[1];

    70     sense[0]='L';//<= constraint

    71     Value rhs[1];

    72     rhs[0]=INF;

    73     int i = CPXgetnumrows(env, lp);

    74     status = CPXnewrows(env, lp, 1, rhs, sense, NULL, NULL);

    75     return i;

    76   }

    79   void LpCplex::_eraseCol(int i) {

    80     CPXdelcols(env, lp, i, i);

    81   }

    83   void LpCplex::_eraseRow(int i) {

    84     CPXdelrows(env, lp, i, i);

    85   }

    87   void LpCplex::_getColName(int col, std::string &name) const

    88   {

    89     ///\bug Untested

    90     int storespace;

    91     CPXgetcolname(env, lp, 0, 0, 0, &storespace, col, col);

    93     storespace *= -1;

    94     std::vector<char> buf(storespace);

    95     char *names[1];

    96     int dontcare;

    97     ///\bug return code unchecked for error

    98     CPXgetcolname(env, lp, names, &*buf.begin(), storespace, &dontcare, col, col);

    99     name = names[0];

   100   }

   102   void LpCplex::_setColName(int col, const std::string &name)

   103   {

   104     ///\bug Untested

   105     char *names[1];

   106     names[0] = const_cast<char*>(name.c_str());

   107     ///\bug return code unchecked for error

   108     CPXchgcolname(env, lp, 1, &col, names);

   109   }

   111   int LpCplex::_colByName(const std::string& name) const

   112   {

   113     int index;

   114     if (CPXgetcolindex(env, lp,

   115                        const_cast<char*>(name.c_str()), &index) == 0) {

   116       return index;

   117     }

   118     return -1;

   119   }

   121   ///\warning Data at index 0 is ignored in the arrays.

   122   void LpCplex::_setRowCoeffs(int i, ConstRowIterator b, ConstRowIterator e)

   123   {

   124     std::vector<int> indices;

   125     std::vector<int> rowlist;

   126     std::vector<Value> values;

   128     for(ConstRowIterator it=b; it!=e; ++it) {

   129       indices.push_back(it->first);

   130       values.push_back(it->second);

   131       rowlist.push_back(i);

   132     }

   134     status = CPXchgcoeflist(env, lp, values.size(),

   135 			    &rowlist[0], &indices[0], &values[0]);

   136   }

   138   void LpCplex::_getRowCoeffs(int i, RowIterator b) const {

   139     /// \todo implement

   140   }

   142   void LpCplex::_setColCoeffs(int i, ConstColIterator b, ConstColIterator e)

   143   {

   144     std::vector<int> indices;

   145     std::vector<int> collist;

   146     std::vector<Value> values;

   148     for(ConstColIterator it=b; it!=e; ++it) {

   149       indices.push_back(it->first);

   150       values.push_back(it->second);

   151       collist.push_back(i);

   152     }

   154     status = CPXchgcoeflist(env, lp, values.size(),

   155 			    &indices[0], &collist[0], &values[0]);

   156   }

   158   void LpCplex::_getColCoeffs(int i, ColIterator b) const {

   159     /// \todo implement

   160   }

   162   void LpCplex::_setCoeff(int row, int col, Value value)

   163   {

   164     CPXchgcoef(env, lp, row, col, value);

   165   }

   167   LpCplex::Value LpCplex::_getCoeff(int row, int col) const

   168   {

   169     LpCplex::Value value;

   170     CPXgetcoef(env, lp, row, col, &value);

   171     return value;

   172   }

   174   void LpCplex::_setColLowerBound(int i, Value value)

   175   {

   176     int indices[1];

   177     indices[0]=i;

   178     char lu[1];

   179     lu[0]='L';

   180     Value bd[1];

   181     bd[0]=value;

   182     status = CPXchgbds(env, lp, 1, indices, lu, bd);

   184   }

   186   LpCplex::Value LpCplex::_getColLowerBound(int i) const

   187   {

   188     LpCplex::Value x;

   189     CPXgetlb (env, lp, &x, i, i);

   190     return x;

   191   }

   193   void LpCplex::_setColUpperBound(int i, Value value)

   194   {

   195     int indices[1];

   196     indices[0]=i;

   197     char lu[1];

   198     lu[0]='U';

   199     Value bd[1];

   200     bd[0]=value;

   201     status = CPXchgbds(env, lp, 1, indices, lu, bd);

   202   }

   204   LpCplex::Value LpCplex::_getColUpperBound(int i) const

   205   {

   206     LpCplex::Value x;

   207     CPXgetub (env, lp, &x, i, i);

   208     return x;

   209   }

   211   //This will be easier to implement

   212   void LpCplex::_setRowBounds(int i, Value lb, Value ub)

   213   {

   214     //Bad parameter

   215     if (lb==INF || ub==-INF) {

   216       //FIXME error

   217     }

   219     int cnt=1;

   220     int indices[1];

   221     indices[0]=i;

   222     char sense[1];

   224     if (lb==-INF){

   225       sense[0]='L';

   226       CPXchgsense(env, lp, cnt, indices, sense);

   227       CPXchgcoef(env, lp, i, -1, ub);

   229     }

   230     else{

   231       if (ub==INF){

   232 	sense[0]='G';

   233 	CPXchgsense(env, lp, cnt, indices, sense);

   234 	CPXchgcoef(env, lp, i, -1, lb);

   235       }

   236       else{

   237 	if (lb == ub){

   238 	  sense[0]='E';

   239 	  CPXchgsense(env, lp, cnt, indices, sense);

   240 	  CPXchgcoef(env, lp, i, -1, lb);

   241 	}

   242 	else{

   243 	  sense[0]='R';

   244 	  CPXchgsense(env, lp, cnt, indices, sense);

   245 	  CPXchgcoef(env, lp, i, -1, lb);

   246 	  CPXchgcoef(env, lp, i, -2, ub-lb);

   247 	}

   248       }

   249     }

   250   }

   252 //   void LpCplex::_setRowLowerBound(int i, Value value)

   253 //   {

   254 //     //Not implemented, obsolete

   255 //   }

   257 //   void LpCplex::_setRowUpperBound(int i, Value value)

   258 //   {

   259 //     //Not implemented, obsolete

   260 // //     //TODO Ezt kell meg megirni

   261 // //     //type of the problem

   262 // //     char sense[1];

   263 // //     status = CPXgetsense(env, lp, sense, i, i);

   264 // //     Value rhs[1];

   265 // //     status = CPXgetrhs(env, lp, rhs, i, i);

   267 // //     switch (sense[0]) {

   268 // //     case 'L'://<= constraint

   269 // //       break;

   270 // //     case 'E'://= constraint

   271 // //       break;

   272 // //     case 'G'://>= constraint

   273 // //       break;

   274 // //     case 'R'://ranged constraint

   275 // //       break;

   276 // //     default: ;

   277 // //       //FIXME error

   278 // //     }

   280 // //     status = CPXchgcoef(env, lp, i, -2, value_rng);

   281 //   }

   283   void LpCplex::_getRowBounds(int i, Value &lb, Value &ub) const

   284   {

   285     char sense;

   286     CPXgetsense(env, lp, &sense,i,i);

   287     lb=-INF;

   288     ub=INF;

   289     switch (sense)

   290       {

   291       case 'L':

   292 	CPXgetcoef(env, lp, i, -1, &ub);

   293 	break;

   294       case 'G':

   295 	CPXgetcoef(env, lp, i, -1, &lb);

   296 	break;

   297       case 'E':

   298 	CPXgetcoef(env, lp, i, -1, &lb);

   299 	ub=lb;

   300 	break;

   301       case 'R':

   302 	CPXgetcoef(env, lp, i, -1, &lb);

   303 	Value x;

   304 	CPXgetcoef(env, lp, i, -2, &x);

   305 	ub=lb+x;

   306 	break;

   307       }

   308   }

   310   void LpCplex::_setObjCoeff(int i, Value obj_coef)

   311   {

   312     CPXchgcoef(env, lp, -1, i, obj_coef);

   313   }

   315   LpCplex::Value LpCplex::_getObjCoeff(int i) const

   316   {

   317     Value x;

   318     CPXgetcoef(env, lp, -1, i, &x);

   319     return x;

   320   }

   322   void LpCplex::_clearObj()

   323   {

   324     for (int i=0;i< CPXgetnumcols(env, lp);++i){

   325       CPXchgcoef(env, lp, -1, i, 0);

   326     }

   328   }

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

   330   // optimization. Examples of errors include exhausting available

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

   332   // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a

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

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

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

   336   // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain

   337   // further information about the status of the optimization.

   338   LpCplex::SolveExitStatus LpCplex::_solve()

   339   {

   340     //CPX_PARAM_LPMETHOD

   341     status = CPXlpopt(env, lp);

   342     //status = CPXprimopt(env, lp);

   343 #if CPX_VERSION >= 800

   344     if (status)

   345     {

   346       return UNSOLVED;

   347     }

   348     else

   349     {

   350       switch (CPXgetstat(env, lp))

   351       {

   352         case CPX_STAT_OPTIMAL:

   353         case CPX_STAT_INFEASIBLE:

   354         case CPX_STAT_UNBOUNDED:

   355           return SOLVED;

   356         default:

   357           return UNSOLVED;

   358       }

   359     }

   360 #else

   361     if (status == 0){

   362       //We want to exclude some cases

   363       switch (CPXgetstat(env, lp)){

   364       case CPX_OBJ_LIM:

   365       case CPX_IT_LIM_FEAS:

   366       case CPX_IT_LIM_INFEAS:

   367       case CPX_TIME_LIM_FEAS:

   368       case CPX_TIME_LIM_INFEAS:

   369 	return UNSOLVED;

   370       default:

   371 	return SOLVED;

   372       }

   373     }

   374     else{

   375       return UNSOLVED;

   376     }

   377 #endif

   378   }

   380   LpCplex::Value LpCplex::_getPrimal(int i) const

   381   {

   382     Value x;

   383     CPXgetx(env, lp, &x, i, i);

   384     return x;

   385   }

   387   LpCplex::Value LpCplex::_getDual(int i) const

   388   {

   389     Value y;

   390     CPXgetpi(env, lp, &y, i, i);

   391     return y;

   392   }

   394   LpCplex::Value LpCplex::_getPrimalValue() const

   395   {

   396     Value objval;

   397     //method = CPXgetmethod (env, lp);

   398     //printf("CPXgetprobtype %d \n",CPXgetprobtype(env,lp));

   399     CPXgetobjval(env, lp, &objval);

   400     //printf("Objective value: %g \n",objval);

   401     return objval;

   402   }

   403   bool LpCplex::_isBasicCol(int i) const

   404   {

   405     std::vector<int> cstat(CPXgetnumcols(env, lp));

   406     CPXgetbase(env, lp, &*cstat.begin(), NULL);

   407     return (cstat[i]==CPX_BASIC);

   408   }

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

   411 // 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.

   413 // For Simplex, Barrier

   414 // 1  	CPX_OPTIMAL

   415 // 	 Optimal solution found

   416 // 2  	CPX_INFEASIBLE

   417 // 	 Problem infeasible

   418 // 3    CPX_UNBOUNDED

   419 // 	 Problem unbounded

   420 // 4  	CPX_OBJ_LIM

   421 // 	 Objective limit exceeded in Phase II

   422 // 5  	CPX_IT_LIM_FEAS

   423 // 	 Iteration limit exceeded in Phase II

   424 // 6  	CPX_IT_LIM_INFEAS

   425 // 	 Iteration limit exceeded in Phase I

   426 // 7  	CPX_TIME_LIM_FEAS

   427 // 	 Time limit exceeded in Phase II

   428 // 8  	CPX_TIME_LIM_INFEAS

   429 // 	 Time limit exceeded in Phase I

   430 // 9  	CPX_NUM_BEST_FEAS

   431 // 	 Problem non-optimal, singularities in Phase II

   432 // 10 	CPX_NUM_BEST_INFEAS

   433 // 	 Problem non-optimal, singularities in Phase I

   434 // 11 	CPX_OPTIMAL_INFEAS

   435 // 	 Optimal solution found, unscaled infeasibilities

   436 // 12 	CPX_ABORT_FEAS

   437 // 	 Aborted in Phase II

   438 // 13 	CPX_ABORT_INFEAS

   439 // 	 Aborted in Phase I

   440 // 14  	CPX_ABORT_DUAL_INFEAS

   441 // 	 Aborted in barrier, dual infeasible

   442 // 15  	CPX_ABORT_PRIM_INFEAS

   443 // 	 Aborted in barrier, primal infeasible

   444 // 16  	CPX_ABORT_PRIM_DUAL_INFEAS

   445 // 	 Aborted in barrier, primal and dual infeasible

   446 // 17  	CPX_ABORT_PRIM_DUAL_FEAS

   447 // 	 Aborted in barrier, primal and dual feasible

   448 // 18  	CPX_ABORT_CROSSOVER

   449 // 	 Aborted in crossover

   450 // 19  	CPX_INForUNBD

   451 // 	 Infeasible or unbounded

   452 // 20   CPX_PIVOT

   453 //       User pivot used

   454 //

   455 //     Ezeket hova tegyem:

   456 // ??case CPX_ABORT_DUAL_INFEAS

   457 // ??case CPX_ABORT_CROSSOVER

   458 // ??case CPX_INForUNBD

   459 // ??case CPX_PIVOT

   461 //Some more interesting stuff:

   463 // CPX_PARAM_LPMETHOD  1062  int  LPMETHOD

   464 // 0 Automatic

   465 // 1 Primal Simplex

   466 // 2 Dual Simplex

   467 // 3 Network Simplex

   468 // 4 Standard Barrier

   469 // Default: 0

   470 // Description: Method for linear optimization.

   471 // Determines which algorithm is used when CPXlpopt() (or "optimize" in the Interactive Optimizer) is called. Currently the behavior of the "Automatic" setting is that CPLEX simply invokes the dual simplex method, but this capability may be expanded in the future so that CPLEX chooses the method based on problem characteristics

   472   void statusSwitch(CPXENVptr env,int& stat){

   473 #if CPX_VERSION < 900

   474     int lpmethod;

   475     CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);

   476     if (lpmethod==2){

   477       if (stat==CPX_UNBOUNDED){

   478 	stat=CPX_INFEASIBLE;

   479       }

   480       else{

   481 	if (stat==CPX_INFEASIBLE)

   482 	  stat=CPX_UNBOUNDED;

   483       }

   484     }

   485 #endif

   486   }

   488   LpCplex::SolutionStatus LpCplex::_getPrimalStatus() const

   489   {

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

   491     // About Unboundedness

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

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

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

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

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

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

   499     // feasible solution exists, then the optimal objective is

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

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

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

   503     // has a feasible solution.

   505     int stat = CPXgetstat(env, lp);

   506 #if CPX_VERSION >= 800

   507     switch (stat)

   508     {

   509       case CPX_STAT_OPTIMAL:

   510         return OPTIMAL;

   511       case CPX_STAT_UNBOUNDED:

   512         return INFINITE;

   513       case CPX_STAT_INFEASIBLE:

   514         return INFEASIBLE;

   515       default:

   516         return UNDEFINED;

   517     }

   518 #else

   519     statusSwitch(env,stat);

   520     //CPXgetstat(env, lp);

   521     //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);

   522     switch (stat) {

   523     case 0:

   524       return UNDEFINED; //Undefined

   525     case CPX_OPTIMAL://Optimal

   526       return OPTIMAL;

   527     case CPX_UNBOUNDED://Unbounded

   528       return INFEASIBLE;//In case of dual simplex

   529       //return INFINITE;

   530     case CPX_INFEASIBLE://Infeasible

   531  //    case CPX_IT_LIM_INFEAS:

   532 //     case CPX_TIME_LIM_INFEAS:

   533 //     case CPX_NUM_BEST_INFEAS:

   534 //     case CPX_OPTIMAL_INFEAS:

   535 //     case CPX_ABORT_INFEAS:

   536 //     case CPX_ABORT_PRIM_INFEAS:

   537 //     case CPX_ABORT_PRIM_DUAL_INFEAS:

   538       return INFINITE;//In case of dual simplex

   539       //return INFEASIBLE;

   540 //     case CPX_OBJ_LIM:

   541 //     case CPX_IT_LIM_FEAS:

   542 //     case CPX_TIME_LIM_FEAS:

   543 //     case CPX_NUM_BEST_FEAS:

   544 //     case CPX_ABORT_FEAS:

   545 //     case CPX_ABORT_PRIM_DUAL_FEAS:

   546 //       return FEASIBLE;

   547     default:

   548       return UNDEFINED; //Everything else comes here

   549       //FIXME error

   550     }

   551 #endif

   552   }

   554 //9.0-as cplex verzio statusai

   555 // CPX_STAT_ABORT_DUAL_OBJ_LIM

   556 // CPX_STAT_ABORT_IT_LIM

   557 // CPX_STAT_ABORT_OBJ_LIM

   558 // CPX_STAT_ABORT_PRIM_OBJ_LIM

   559 // CPX_STAT_ABORT_TIME_LIM

   560 // CPX_STAT_ABORT_USER

   561 // CPX_STAT_FEASIBLE_RELAXED

   562 // CPX_STAT_INFEASIBLE

   563 // CPX_STAT_INForUNBD

   564 // CPX_STAT_NUM_BEST

   565 // CPX_STAT_OPTIMAL

   566 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED

   567 // CPX_STAT_OPTIMAL_INFEAS

   568 // CPX_STAT_OPTIMAL_RELAXED

   569 // CPX_STAT_UNBOUNDED

   571   LpCplex::SolutionStatus LpCplex::_getDualStatus() const

   572   {

   573     int stat = CPXgetstat(env, lp);

   574 #if CPX_VERSION >= 800

   575     switch (stat)

   576     {

   577       case CPX_STAT_OPTIMAL:

   578         return OPTIMAL;

   579       case CPX_STAT_UNBOUNDED:

   580         return INFEASIBLE;

   581       default:

   582         return UNDEFINED;

   583     }

   584 #else

   585     statusSwitch(env,stat);

   586     switch (stat) {

   587     case 0:

   588       return UNDEFINED; //Undefined

   589     case CPX_OPTIMAL://Optimal

   590       return OPTIMAL;

   591     case CPX_UNBOUNDED:

   592      return INFEASIBLE;

   593     default:

   594       return UNDEFINED; //Everything else comes here

   595       //FIXME error

   596     }

   597 #endif

   598   }

   600   LpCplex::ProblemTypes LpCplex::_getProblemType() const

   601   {

   602     int stat = CPXgetstat(env, lp);

   603 #if CPX_VERSION >= 800

   604     switch (stat)

   605     {

   606       case CPX_STAT_OPTIMAL:

   607 	return PRIMAL_DUAL_FEASIBLE;

   608       case CPX_STAT_UNBOUNDED:

   609  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   610       default:

   611         return UNKNOWN;

   612     }

   613 #else

   614     switch (stat) {

   615     case CPX_OPTIMAL://Optimal

   616 	return PRIMAL_DUAL_FEASIBLE;

   617     case CPX_UNBOUNDED:

   618  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   619 // 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

   620 // 	return PRIMAL_DUAL_INFEASIBLE;

   622 //Seems to be that this is all we can say for sure

   623     default:

   624 	//In all other cases

   625 	return UNKNOWN;

   626       //FIXME error

   627     }

   628 #endif

   629   }

   631   void LpCplex::_setMax()

   632   {

   633     CPXchgobjsen(env, lp, CPX_MAX);

   634    }

   635   void LpCplex::_setMin()

   636   {

   637     CPXchgobjsen(env, lp, CPX_MIN);

   638    }

   640   bool LpCplex::_isMax() const

   641   {

   642     if (CPXgetobjsen(env, lp)==CPX_MAX)

   643       return true;

   644     else

   645       return false;

   646   }

   648 } //namespace lemon

author	kpeter
	Fri, 07 Mar 2008 00:24:23 +0000
changeset 2593	8eed667ea23c
parent 2553	bfced05fa852
child 2605	852361980706
permissions	-rw-r--r--