lemon-0.x: lemon/lp_cplex.cc@3a5e67bd42d2

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

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     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)

    88   {

    89     ///\bug Untested

    90     int storespace;

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

    93     storespace *= -1;

    94     char buf[storespace];

    95     char *names[1];

    96     int dontcare;

    97     ///\bug return code unchecked for error

    98     CPXgetcolname(env, lp, names, buf, 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   ///\warning Data at index 0 is ignored in the arrays.

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

   113   {

   114     std::vector<int> indices;

   115     std::vector<int> rowlist;

   116     std::vector<Value> values;

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

   119       indices.push_back(it->first);

   120       values.push_back(it->second);

   121       rowlist.push_back(i);

   122     }

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

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

   126   }

   128   void LpSoplex::_getRowCoeffs(int i, RowIterator b) {

   129     /// \todo implement

   130   }

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

   133   {

   134     std::vector<int> indices;

   135     std::vector<int> collist;

   136     std::vector<Value> values;

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

   139       indices.push_back(it->first);

   140       values.push_back(it->second);

   141       collist.push_back(i);

   142     }

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

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

   146   }

   148   void LpSoplex::_getColCoeffs(int i, ColIterator b) {

   149     /// \todo implement

   150   }

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

   153   {

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

   155   }

   157   LpCplex::Value LpCplex::_getCoeff(int row, int col)

   158   {

   159     LpCplex::Value value;

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

   161     return value;

   162   }

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

   165   {

   166     int indices[1];

   167     indices[0]=i;

   168     char lu[1];

   169     lu[0]='L';

   170     Value bd[1];

   171     bd[0]=value;

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

   174   }

   176   LpCplex::Value LpCplex::_getColLowerBound(int i)

   177   {

   178     LpCplex::Value x;

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

   180     return x;

   181   }

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

   184   {

   185     int indices[1];

   186     indices[0]=i;

   187     char lu[1];

   188     lu[0]='U';

   189     Value bd[1];

   190     bd[0]=value;

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

   192   }

   194   LpCplex::Value LpCplex::_getColUpperBound(int i)

   195   {

   196     LpCplex::Value x;

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

   198     return x;

   199   }

   201   //This will be easier to implement

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

   203   {

   204     //Bad parameter

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

   206       //FIXME error

   207     }

   209     int cnt=1;

   210     int indices[1];

   211     indices[0]=i;

   212     char sense[1];

   214     if (lb==-INF){

   215       sense[0]='L';

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

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

   219     }

   220     else{

   221       if (ub==INF){

   222 	sense[0]='G';

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

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

   225       }

   226       else{

   227 	if (lb == ub){

   228 	  sense[0]='E';

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

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

   231 	}

   232 	else{

   233 	  sense[0]='R';

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

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

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

   237 	}

   238       }

   239     }

   240   }

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

   243 //   {

   244 //     //Not implemented, obsolete

   245 //   }

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

   248 //   {

   249 //     //Not implemented, obsolete

   250 // //     //TODO Ezt kell meg megirni

   251 // //     //type of the problem

   252 // //     char sense[1];

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

   254 // //     Value rhs[1];

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

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

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

   259 // //       break;

   260 // //     case 'E'://= constraint

   261 // //       break;

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

   263 // //       break;

   264 // //     case 'R'://ranged constraint

   265 // //       break;

   266 // //     default: ;

   267 // //       //FIXME error

   268 // //     }

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

   271 //   }

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

   274   {

   275     char sense;

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

   277     lb=-INF;

   278     ub=INF;

   279     switch (sense)

   280       {

   281       case 'L':

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

   283 	break;

   284       case 'G':

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

   286 	break;

   287       case 'E':

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

   289 	ub=lb;

   290 	break;

   291       case 'R':

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

   293 	Value x;

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

   295 	ub=lb+x;

   296 	break;

   297       }

   298   }

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

   301   {

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

   303   }

   305   LpCplex::Value LpCplex::_getObjCoeff(int i)

   306   {

   307     Value x;

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

   309     return x;

   310   }

   312   void LpCplex::_clearObj()

   313   {

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

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

   316     }

   318   }

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

   320   // optimization. Examples of errors include exhausting available

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

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

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

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

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

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

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

   328   LpCplex::SolveExitStatus LpCplex::_solve()

   329   {

   330     //CPX_PARAM_LPMETHOD

   331     status = CPXlpopt(env, lp);

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

   333 #if CPX_VERSION >= 800

   334     if (status)

   335     {

   336       return UNSOLVED;

   337     }

   338     else

   339     {

   340       switch (CPXgetstat(env, lp))

   341       {

   342         case CPX_STAT_OPTIMAL:

   343         case CPX_STAT_INFEASIBLE:

   344         case CPX_STAT_UNBOUNDED:

   345           return SOLVED;

   346         default:

   347           return UNSOLVED;

   348       }

   349     }

   350 #else

   351     if (status == 0){

   352       //We want to exclude some cases

   353       switch (CPXgetstat(env, lp)){

   354       case CPX_OBJ_LIM:

   355       case CPX_IT_LIM_FEAS:

   356       case CPX_IT_LIM_INFEAS:

   357       case CPX_TIME_LIM_FEAS:

   358       case CPX_TIME_LIM_INFEAS:

   359 	return UNSOLVED;

   360       default:

   361 	return SOLVED;

   362       }

   363     }

   364     else{

   365       return UNSOLVED;

   366     }

   367 #endif

   368   }

   370   LpCplex::Value LpCplex::_getPrimal(int i)

   371   {

   372     Value x;

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

   374     return x;

   375   }

   377   LpCplex::Value LpCplex::_getDual(int i)

   378   {

   379     Value y;

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

   381     return y;

   382   }

   384   LpCplex::Value LpCplex::_getPrimalValue()

   385   {

   386     Value objval;

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

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

   389     status = CPXgetobjval(env, lp, &objval);

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

   391     return objval;

   392   }

   393   bool LpCplex::_isBasicCol(int i) {

   394     int cstat[CPXgetnumcols(env, lp)];

   395     CPXgetbase(env, lp, cstat, NULL);

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

   397   }

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

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

   402 // For Simplex, Barrier

   403 // 1  	CPX_OPTIMAL

   404 // 	 Optimal solution found

   405 // 2  	CPX_INFEASIBLE

   406 // 	 Problem infeasible

   407 // 3    CPX_UNBOUNDED

   408 // 	 Problem unbounded

   409 // 4  	CPX_OBJ_LIM

   410 // 	 Objective limit exceeded in Phase II

   411 // 5  	CPX_IT_LIM_FEAS

   412 // 	 Iteration limit exceeded in Phase II

   413 // 6  	CPX_IT_LIM_INFEAS

   414 // 	 Iteration limit exceeded in Phase I

   415 // 7  	CPX_TIME_LIM_FEAS

   416 // 	 Time limit exceeded in Phase II

   417 // 8  	CPX_TIME_LIM_INFEAS

   418 // 	 Time limit exceeded in Phase I

   419 // 9  	CPX_NUM_BEST_FEAS

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

   421 // 10 	CPX_NUM_BEST_INFEAS

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

   423 // 11 	CPX_OPTIMAL_INFEAS

   424 // 	 Optimal solution found, unscaled infeasibilities

   425 // 12 	CPX_ABORT_FEAS

   426 // 	 Aborted in Phase II

   427 // 13 	CPX_ABORT_INFEAS

   428 // 	 Aborted in Phase I

   429 // 14  	CPX_ABORT_DUAL_INFEAS

   430 // 	 Aborted in barrier, dual infeasible

   431 // 15  	CPX_ABORT_PRIM_INFEAS

   432 // 	 Aborted in barrier, primal infeasible

   433 // 16  	CPX_ABORT_PRIM_DUAL_INFEAS

   434 // 	 Aborted in barrier, primal and dual infeasible

   435 // 17  	CPX_ABORT_PRIM_DUAL_FEAS

   436 // 	 Aborted in barrier, primal and dual feasible

   437 // 18  	CPX_ABORT_CROSSOVER

   438 // 	 Aborted in crossover

   439 // 19  	CPX_INForUNBD

   440 // 	 Infeasible or unbounded

   441 // 20   CPX_PIVOT

   442 //       User pivot used

   443 //

   444 //     Ezeket hova tegyem:

   445 // ??case CPX_ABORT_DUAL_INFEAS

   446 // ??case CPX_ABORT_CROSSOVER

   447 // ??case CPX_INForUNBD

   448 // ??case CPX_PIVOT

   450 //Some more interesting stuff:

   452 // CPX_PARAM_LPMETHOD  1062  int  LPMETHOD

   453 // 0 Automatic

   454 // 1 Primal Simplex

   455 // 2 Dual Simplex

   456 // 3 Network Simplex

   457 // 4 Standard Barrier

   458 // Default: 0

   459 // Description: Method for linear optimization.

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

   461   //Hulye cplex

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

   463 #if CPX_VERSION < 900

   464     int lpmethod;

   465     CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);

   466     if (lpmethod==2){

   467       if (stat==CPX_UNBOUNDED){

   468 	stat=CPX_INFEASIBLE;

   469       }

   470       else{

   471 	if (stat==CPX_INFEASIBLE)

   472 	  stat=CPX_UNBOUNDED;

   473       }

   474     }

   475 #endif

   476   }

   478   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()

   479   {

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

   481     // About Unboundedness

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

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

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

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

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

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

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

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

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

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

   493     // has a feasible solution.

   495     int stat = CPXgetstat(env, lp);

   496 #if CPX_VERSION >= 800

   497     switch (stat)

   498     {

   499       case CPX_STAT_OPTIMAL:

   500         return OPTIMAL;

   501       case CPX_STAT_UNBOUNDED:

   502         return INFINITE;

   503       case CPX_STAT_INFEASIBLE:

   504         return INFEASIBLE;

   505       default:

   506         return UNDEFINED;

   507     }

   508 #else

   509     statusSwitch(env,stat);

   510     //CPXgetstat(env, lp);

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

   512     switch (stat) {

   513     case 0:

   514       return UNDEFINED; //Undefined

   515     case CPX_OPTIMAL://Optimal

   516       return OPTIMAL;

   517     case CPX_UNBOUNDED://Unbounded

   518       return INFEASIBLE;//In case of dual simplex

   519       //return INFINITE;

   520     case CPX_INFEASIBLE://Infeasible

   521  //    case CPX_IT_LIM_INFEAS:

   522 //     case CPX_TIME_LIM_INFEAS:

   523 //     case CPX_NUM_BEST_INFEAS:

   524 //     case CPX_OPTIMAL_INFEAS:

   525 //     case CPX_ABORT_INFEAS:

   526 //     case CPX_ABORT_PRIM_INFEAS:

   527 //     case CPX_ABORT_PRIM_DUAL_INFEAS:

   528       return INFINITE;//In case of dual simplex

   529       //return INFEASIBLE;

   530 //     case CPX_OBJ_LIM:

   531 //     case CPX_IT_LIM_FEAS:

   532 //     case CPX_TIME_LIM_FEAS:

   533 //     case CPX_NUM_BEST_FEAS:

   534 //     case CPX_ABORT_FEAS:

   535 //     case CPX_ABORT_PRIM_DUAL_FEAS:

   536 //       return FEASIBLE;

   537     default:

   538       return UNDEFINED; //Everything else comes here

   539       //FIXME error

   540     }

   541 #endif

   542   }

   544 //9.0-as cplex verzio statusai

   545 // CPX_STAT_ABORT_DUAL_OBJ_LIM

   546 // CPX_STAT_ABORT_IT_LIM

   547 // CPX_STAT_ABORT_OBJ_LIM

   548 // CPX_STAT_ABORT_PRIM_OBJ_LIM

   549 // CPX_STAT_ABORT_TIME_LIM

   550 // CPX_STAT_ABORT_USER

   551 // CPX_STAT_FEASIBLE_RELAXED

   552 // CPX_STAT_INFEASIBLE

   553 // CPX_STAT_INForUNBD

   554 // CPX_STAT_NUM_BEST

   555 // CPX_STAT_OPTIMAL

   556 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED

   557 // CPX_STAT_OPTIMAL_INFEAS

   558 // CPX_STAT_OPTIMAL_RELAXED

   559 // CPX_STAT_UNBOUNDED

   561   LpCplex::SolutionStatus LpCplex::_getDualStatus()

   562   {

   563     int stat = CPXgetstat(env, lp);

   564 #if CPX_VERSION >= 800

   565     switch (stat)

   566     {

   567       case CPX_STAT_OPTIMAL:

   568         return OPTIMAL;

   569       case CPX_STAT_UNBOUNDED:

   570         return INFEASIBLE;

   571       default:

   572         return UNDEFINED;

   573     }

   574 #else

   575     statusSwitch(env,stat);

   576     switch (stat) {

   577     case 0:

   578       return UNDEFINED; //Undefined

   579     case CPX_OPTIMAL://Optimal

   580       return OPTIMAL;

   581     case CPX_UNBOUNDED:

   582      return INFEASIBLE;

   583     default:

   584       return UNDEFINED; //Everything else comes here

   585       //FIXME error

   586     }

   587 #endif

   588   }

   590   LpCplex::ProblemTypes LpCplex::_getProblemType()

   591   {

   592     int stat = CPXgetstat(env, lp);

   593 #if CPX_VERSION >= 800

   594     switch (stat)

   595     {

   596       case CPX_STAT_OPTIMAL:

   597 	return PRIMAL_DUAL_FEASIBLE;

   598       case CPX_STAT_UNBOUNDED:

   599  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   600       default:

   601         return UNKNOWN;

   602     }

   603 #else

   604     switch (stat) {

   605     case CPX_OPTIMAL://Optimal

   606 	return PRIMAL_DUAL_FEASIBLE;

   607     case CPX_UNBOUNDED:

   608  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;

   609 // 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;

   610 // 	return PRIMAL_DUAL_INFEASIBLE;

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

   613     default:

   614 	//In all other cases

   615 	return UNKNOWN;

   616       //FIXME error

   617     }

   618 #endif

   619   }

   621   void LpCplex::_setMax()

   622   {

   623     CPXchgobjsen(env, lp, CPX_MAX);

   624    }

   625   void LpCplex::_setMin()

   626   {

   627     CPXchgobjsen(env, lp, CPX_MIN);

   628    }

   630   bool LpCplex::_isMax()

   631   {

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

   633       return true;

   634     else

   635       return false;

   636   }

   638 } //namespace lemon

author	deba
	Thu, 15 Feb 2007 19:15:14 +0000
changeset 2364	3a5e67bd42d2
parent 2363	2aabce558574
child 2366	bfbdded3763a
permissions	-rw-r--r--