lemon/lp_cplex.cc
author deba
Thu, 15 Feb 2007 13:06:23 +0000
changeset 2362 eb37b9774ef6
parent 2328 b4931ae52069
child 2363 2aabce558574
permissions -rw-r--r--
Small changes
     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  */
    18 
    19 #include <iostream>
    20 #include<lemon/lp_cplex.h>
    21 
    22 ///\file
    23 ///\brief Implementation of the LEMON-CPLEX lp solver interface.
    24 namespace lemon {
    25   
    26   LpCplex::LpCplex() : LpSolverBase() {
    27 
    28     //    env = CPXopenCPLEXdevelop(&status);     
    29     env = CPXopenCPLEX(&status);     
    30     lp = CPXcreateprob(env, &status, "LP problem");
    31   }
    32   
    33   LpCplex::~LpCplex() {
    34     CPXfreeprob(env,&lp); 
    35     CPXcloseCPLEX(&env); 
    36   }
    37   
    38   LpSolverBase &LpCplex::_newLp() 
    39   {
    40     //The first approach opens a new environment
    41     LpCplex* newlp=new LpCplex();
    42     return *newlp;
    43   }
    44 
    45   LpSolverBase &LpCplex::_copyLp() {
    46     ///\bug FixID data is not copied!
    47     //The first approach opens a new environment
    48     LpCplex* newlp=new LpCplex();
    49     //The routine CPXcloneprob can be used to create a new CPLEX problem 
    50     //object and copy all the problem data from an existing problem 
    51     //object to it. Solution and starting information is not copied.
    52     newlp->lp = CPXcloneprob(env, lp, &status);
    53     return *newlp;
    54   }
    55 
    56   int LpCplex::_addCol()
    57   {
    58     int i = CPXgetnumcols(env, lp);
    59     Value lb[1],ub[1];
    60     lb[0]=-INF;//-CPX_INFBOUND;
    61     ub[0]=INF;//CPX_INFBOUND;
    62     status = CPXnewcols(env, lp, 1, NULL, lb, ub, NULL, NULL);
    63     return i;
    64   }
    65 
    66   
    67   int LpCplex::_addRow() 
    68   {
    69     //We want a row that is not constrained
    70     char sense[1];
    71     sense[0]='L';//<= constraint
    72     Value rhs[1];
    73     rhs[0]=INF;
    74     int i = CPXgetnumrows(env, lp);
    75     status = CPXnewrows(env, lp, 1, rhs, sense, NULL, NULL);
    76     return i;
    77   }
    78 
    79 
    80   void LpCplex::_eraseCol(int i) {
    81     CPXdelcols(env, lp, i, i);
    82   }
    83   
    84   void LpCplex::_eraseRow(int i) {
    85     CPXdelrows(env, lp, i, i);
    86   }
    87   
    88   void LpCplex::_getColName(int col, std::string &name)
    89   {
    90     ///\bug Untested
    91     int storespace;
    92     CPXgetcolname(env, lp, 0, 0, 0, &storespace, col, col);
    93 
    94     storespace *= -1;
    95     char buf[storespace];
    96     char *names[1];
    97     int dontcare;
    98     ///\bug return code unchecked for error
    99     CPXgetcolname(env, lp, names, buf, storespace, &dontcare, col, col);
   100     name = names[0];
   101   }
   102   
   103   void LpCplex::_setColName(int col, const std::string &name)
   104   {
   105     ///\bug Untested
   106     char *names[1];
   107     names[0] = const_cast<char*>(name.c_str());
   108     ///\bug return code unchecked for error
   109     CPXchgcolname(env, lp, 1, &col, names);    
   110   }
   111   
   112   ///\warning Data at index 0 is ignored in the arrays.
   113   void LpCplex::_setRowCoeffs(int i, LpRowIterator b, LpRowIterator e)
   114   {
   115     std::vector<int> indices;
   116     std::vector<int> rowlist;
   117     std::vector<Value> values;
   118 
   119     for(LpRowIterator it=b; it!=e; ++it) {
   120       indices.push_back(it->first);
   121       values.push_back(it->second);
   122       rowlist.push_back(i);
   123     }
   124 
   125     status = CPXchgcoeflist(env, lp, values.size(), 
   126 			    &rowlist[0], &indices[0], &values[0]); 
   127   }
   128   
   129   void LpCplex::_setColCoeffs(int i, LpColIterator b, LpColIterator e)
   130   {
   131     std::vector<int> indices;
   132     std::vector<int> collist;
   133     std::vector<Value> values;
   134 
   135     for(LpColIterator it=b; it!=e; ++it) {
   136       indices.push_back(it->first);
   137       values.push_back(it->second);
   138       collist.push_back(i);
   139     }
   140 
   141     status = CPXchgcoeflist(env, lp, values.size(), 
   142 			    &indices[0], &collist[0], &values[0]); 
   143   }
   144   
   145   void LpCplex::_setCoeff(int row, int col, Value value) 
   146   {
   147     CPXchgcoef(env, lp, row, col, value);
   148   }
   149 
   150   LpCplex::Value LpCplex::_getCoeff(int row, int col) 
   151   {
   152     LpCplex::Value value;
   153     CPXgetcoef(env, lp, row, col, &value);
   154     return value;
   155   }
   156 
   157   void LpCplex::_setColLowerBound(int i, Value value)
   158   {
   159     int indices[1];
   160     indices[0]=i;
   161     char lu[1];
   162     lu[0]='L';
   163     Value bd[1];
   164     bd[0]=value;
   165     status = CPXchgbds(env, lp, 1, indices, lu, bd);
   166  
   167   }
   168 
   169   LpCplex::Value LpCplex::_getColLowerBound(int i)
   170   {
   171     LpCplex::Value x;
   172     CPXgetlb (env, lp, &x, i, i);
   173     return x;
   174   }
   175   
   176   void LpCplex::_setColUpperBound(int i, Value value)
   177   {
   178     int indices[1];
   179     indices[0]=i;
   180     char lu[1];
   181     lu[0]='U';
   182     Value bd[1];
   183     bd[0]=value;
   184     status = CPXchgbds(env, lp, 1, indices, lu, bd);
   185   }
   186 
   187   LpCplex::Value LpCplex::_getColUpperBound(int i)
   188   {
   189     LpCplex::Value x;
   190     CPXgetub (env, lp, &x, i, i);
   191     return x;
   192   }
   193 
   194   //This will be easier to implement
   195   void LpCplex::_setRowBounds(int i, Value lb, Value ub)
   196   {
   197     //Bad parameter
   198     if (lb==INF || ub==-INF) {
   199       //FIXME error
   200     }
   201     
   202     int cnt=1;
   203     int indices[1];
   204     indices[0]=i;
   205     char sense[1];
   206 
   207     if (lb==-INF){
   208       sense[0]='L';
   209       CPXchgsense(env, lp, cnt, indices, sense);
   210       CPXchgcoef(env, lp, i, -1, ub);
   211       
   212     }
   213     else{
   214       if (ub==INF){
   215 	sense[0]='G';
   216 	CPXchgsense(env, lp, cnt, indices, sense);
   217 	CPXchgcoef(env, lp, i, -1, lb);
   218       }
   219       else{
   220 	if (lb == ub){
   221 	  sense[0]='E';
   222 	  CPXchgsense(env, lp, cnt, indices, sense);
   223 	  CPXchgcoef(env, lp, i, -1, lb);
   224 	}
   225 	else{
   226 	  sense[0]='R';
   227 	  CPXchgsense(env, lp, cnt, indices, sense);
   228 	  CPXchgcoef(env, lp, i, -1, lb);
   229 	  CPXchgcoef(env, lp, i, -2, ub-lb);	  
   230 	}
   231       }
   232     }
   233   }
   234 
   235 //   void LpCplex::_setRowLowerBound(int i, Value value)
   236 //   {
   237 //     //Not implemented, obsolete
   238 //   }
   239   
   240 //   void LpCplex::_setRowUpperBound(int i, Value value)
   241 //   {
   242 //     //Not implemented, obsolete
   243 // //     //TODO Ezt kell meg megirni
   244 // //     //type of the problem
   245 // //     char sense[1];
   246 // //     status = CPXgetsense(env, lp, sense, i, i);
   247 // //     Value rhs[1];
   248 // //     status = CPXgetrhs(env, lp, rhs, i, i);
   249 
   250 // //     switch (sense[0]) {
   251 // //     case 'L'://<= constraint
   252 // //       break;
   253 // //     case 'E'://= constraint
   254 // //       break;
   255 // //     case 'G'://>= constraint
   256 // //       break;
   257 // //     case 'R'://ranged constraint
   258 // //       break;
   259 // //     default: ;
   260 // //       //FIXME error
   261 // //     }
   262 
   263 // //     status = CPXchgcoef(env, lp, i, -2, value_rng);
   264 //   }
   265   
   266   void LpCplex::_getRowBounds(int i, Value &lb, Value &ub)
   267   {
   268     char sense;
   269     CPXgetsense(env, lp, &sense,i,i);
   270     lb=-INF;
   271     ub=INF;
   272     switch (sense)
   273       {
   274       case 'L':
   275 	CPXgetcoef(env, lp, i, -1, &ub);
   276 	break;
   277       case 'G':
   278 	CPXgetcoef(env, lp, i, -1, &lb);
   279 	break;
   280       case 'E':
   281 	CPXgetcoef(env, lp, i, -1, &lb);
   282 	ub=lb;
   283 	break;
   284       case 'R':
   285 	CPXgetcoef(env, lp, i, -1, &lb);
   286 	Value x;
   287 	CPXgetcoef(env, lp, i, -2, &x);
   288 	ub=lb+x;
   289 	break;
   290       }
   291   }
   292 
   293   void LpCplex::_setObjCoeff(int i, Value obj_coef)
   294   {
   295     CPXchgcoef(env, lp, -1, i, obj_coef);
   296   }
   297 
   298   LpCplex::Value LpCplex::_getObjCoeff(int i)
   299   {
   300     Value x;
   301     CPXgetcoef(env, lp, -1, i, &x);
   302     return x;
   303   }
   304 
   305   void LpCplex::_clearObj()
   306   {
   307     for (int i=0;i< CPXgetnumcols(env, lp);++i){
   308       CPXchgcoef(env, lp, -1, i, 0);
   309     }
   310     
   311   }
   312   // The routine returns zero unless an error occurred during the
   313   // optimization. Examples of errors include exhausting available
   314   // memory (CPXERR_NO_MEMORY) or encountering invalid data in the
   315   // CPLEX problem object (CPXERR_NO_PROBLEM). Exceeding a
   316   // user-specified CPLEX limit, or proving the model infeasible or
   317   // unbounded, are not considered errors. Note that a zero return
   318   // value does not necessarily mean that a solution exists. Use query
   319   // routines CPXsolninfo, CPXgetstat, and CPXsolution to obtain
   320   // further information about the status of the optimization.
   321   LpCplex::SolveExitStatus LpCplex::_solve()
   322   {
   323     //CPX_PARAM_LPMETHOD 
   324     status = CPXlpopt(env, lp);
   325     //status = CPXprimopt(env, lp);
   326 #if CPX_VERSION >= 800
   327     if (status)
   328     {
   329       return UNSOLVED;
   330     }
   331     else
   332     {
   333       switch (CPXgetstat(env, lp))
   334       {
   335         case CPX_STAT_OPTIMAL:
   336         case CPX_STAT_INFEASIBLE:
   337         case CPX_STAT_UNBOUNDED:
   338           return SOLVED;
   339         default:
   340           return UNSOLVED;
   341       }
   342     }
   343 #else
   344     if (status == 0){
   345       //We want to exclude some cases
   346       switch (CPXgetstat(env, lp)){
   347       case CPX_OBJ_LIM:
   348       case CPX_IT_LIM_FEAS:
   349       case CPX_IT_LIM_INFEAS:               
   350       case CPX_TIME_LIM_FEAS:
   351       case CPX_TIME_LIM_INFEAS:
   352 	return UNSOLVED;
   353       default:
   354 	return SOLVED; 
   355       }
   356     }
   357     else{
   358       return UNSOLVED;
   359     }
   360 #endif
   361   }
   362 
   363   LpCplex::Value LpCplex::_getPrimal(int i)
   364   {
   365     Value x;
   366     CPXgetx(env, lp, &x, i, i);
   367     return x;
   368   }
   369 
   370   LpCplex::Value LpCplex::_getDual(int i)
   371   {
   372     Value y;
   373     CPXgetpi(env, lp, &y, i, i);
   374     return y;
   375   }
   376   
   377   LpCplex::Value LpCplex::_getPrimalValue()
   378   {
   379     Value objval;
   380     //method = CPXgetmethod (env, lp);
   381     //printf("CPXgetprobtype %d \n",CPXgetprobtype(env,lp));
   382     status = CPXgetobjval(env, lp, &objval);
   383     //printf("Objective value: %g \n",objval);
   384     return objval;
   385   }
   386   bool LpCplex::_isBasicCol(int i) {
   387     int cstat[CPXgetnumcols(env, lp)];
   388     CPXgetbase(env, lp, cstat, NULL);
   389     return (cstat[i]==CPX_BASIC);
   390   }  
   391 
   392 //7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!)
   393 // 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.
   394 
   395 // For Simplex, Barrier  
   396 // 1  	CPX_OPTIMAL  
   397 // 	 Optimal solution found  
   398 // 2  	CPX_INFEASIBLE  
   399 // 	 Problem infeasible  
   400 // 3    CPX_UNBOUNDED  
   401 // 	 Problem unbounded  
   402 // 4  	CPX_OBJ_LIM  
   403 // 	 Objective limit exceeded in Phase II  
   404 // 5  	CPX_IT_LIM_FEAS  
   405 // 	 Iteration limit exceeded in Phase II  
   406 // 6  	CPX_IT_LIM_INFEAS  
   407 // 	 Iteration limit exceeded in Phase I  
   408 // 7  	CPX_TIME_LIM_FEAS  
   409 // 	 Time limit exceeded in Phase II  
   410 // 8  	CPX_TIME_LIM_INFEAS  
   411 // 	 Time limit exceeded in Phase I  
   412 // 9  	CPX_NUM_BEST_FEAS  
   413 // 	 Problem non-optimal, singularities in Phase II  
   414 // 10 	CPX_NUM_BEST_INFEAS  
   415 // 	 Problem non-optimal, singularities in Phase I  
   416 // 11 	CPX_OPTIMAL_INFEAS  
   417 // 	 Optimal solution found, unscaled infeasibilities  
   418 // 12 	CPX_ABORT_FEAS  
   419 // 	 Aborted in Phase II  
   420 // 13 	CPX_ABORT_INFEAS  
   421 // 	 Aborted in Phase I  
   422 // 14  	CPX_ABORT_DUAL_INFEAS  
   423 // 	 Aborted in barrier, dual infeasible  
   424 // 15  	CPX_ABORT_PRIM_INFEAS  
   425 // 	 Aborted in barrier, primal infeasible  
   426 // 16  	CPX_ABORT_PRIM_DUAL_INFEAS  
   427 // 	 Aborted in barrier, primal and dual infeasible  
   428 // 17  	CPX_ABORT_PRIM_DUAL_FEAS  
   429 // 	 Aborted in barrier, primal and dual feasible  
   430 // 18  	CPX_ABORT_CROSSOVER  
   431 // 	 Aborted in crossover  
   432 // 19  	CPX_INForUNBD  
   433 // 	 Infeasible or unbounded  
   434 // 20   CPX_PIVOT
   435 //       User pivot used
   436 //
   437 //     Ezeket hova tegyem:
   438 // ??case CPX_ABORT_DUAL_INFEAS           
   439 // ??case CPX_ABORT_CROSSOVER             
   440 // ??case CPX_INForUNBD                   
   441 // ??case CPX_PIVOT              
   442          
   443 //Some more interesting stuff:
   444 
   445 // CPX_PARAM_LPMETHOD  1062  int  LPMETHOD
   446 // 0 Automatic 
   447 // 1 Primal Simplex 
   448 // 2 Dual Simplex 
   449 // 3 Network Simplex 
   450 // 4 Standard Barrier 
   451 // Default: 0 
   452 // Description: Method for linear optimization. 
   453 // 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 
   454   //Hulye cplex
   455   void statusSwitch(CPXENVptr env,int& stat){
   456 #if CPX_VERSION < 900
   457     int lpmethod;
   458     CPXgetintparam (env,CPX_PARAM_LPMETHOD,&lpmethod);
   459     if (lpmethod==2){
   460       if (stat==CPX_UNBOUNDED){
   461 	stat=CPX_INFEASIBLE;
   462       }
   463       else{
   464 	if (stat==CPX_INFEASIBLE)
   465 	  stat=CPX_UNBOUNDED;
   466       }
   467     }
   468 #endif
   469   }
   470 
   471   LpCplex::SolutionStatus LpCplex::_getPrimalStatus()
   472   {
   473     //Unboundedness not treated well: the following is from cplex 9.0 doc
   474     // About Unboundedness
   475 
   476     // The treatment of models that are unbounded involves a few
   477     // subtleties. Specifically, a declaration of unboundedness means that
   478     // ILOG CPLEX has determined that the model has an unbounded
   479     // ray. Given any feasible solution x with objective z, a multiple of
   480     // the unbounded ray can be added to x to give a feasible solution
   481     // with objective z-1 (or z+1 for maximization models). Thus, if a
   482     // feasible solution exists, then the optimal objective is
   483     // unbounded. Note that ILOG CPLEX has not necessarily concluded that
   484     // a feasible solution exists. Users can call the routine CPXsolninfo
   485     // to determine whether ILOG CPLEX has also concluded that the model
   486     // has a feasible solution.
   487 
   488     int stat = CPXgetstat(env, lp);
   489 #if CPX_VERSION >= 800
   490     switch (stat)
   491     {
   492       case CPX_STAT_OPTIMAL:
   493         return OPTIMAL;
   494       case CPX_STAT_UNBOUNDED:
   495         return INFINITE;
   496       case CPX_STAT_INFEASIBLE:
   497         return INFEASIBLE;
   498       default:
   499         return UNDEFINED;
   500     }
   501 #else
   502     statusSwitch(env,stat);
   503     //CPXgetstat(env, lp);
   504     //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL);
   505     switch (stat) {
   506     case 0:
   507       return UNDEFINED; //Undefined
   508     case CPX_OPTIMAL://Optimal
   509       return OPTIMAL;
   510     case CPX_UNBOUNDED://Unbounded
   511       return INFEASIBLE;//In case of dual simplex
   512       //return INFINITE;
   513     case CPX_INFEASIBLE://Infeasible 
   514  //    case CPX_IT_LIM_INFEAS:
   515 //     case CPX_TIME_LIM_INFEAS:
   516 //     case CPX_NUM_BEST_INFEAS:             
   517 //     case CPX_OPTIMAL_INFEAS:              
   518 //     case CPX_ABORT_INFEAS:                
   519 //     case CPX_ABORT_PRIM_INFEAS:           
   520 //     case CPX_ABORT_PRIM_DUAL_INFEAS:      
   521       return INFINITE;//In case of dual simplex
   522       //return INFEASIBLE;
   523 //     case CPX_OBJ_LIM:                    
   524 //     case CPX_IT_LIM_FEAS:             
   525 //     case CPX_TIME_LIM_FEAS:                
   526 //     case CPX_NUM_BEST_FEAS:                
   527 //     case CPX_ABORT_FEAS:                  
   528 //     case CPX_ABORT_PRIM_DUAL_FEAS:        
   529 //       return FEASIBLE;
   530     default:
   531       return UNDEFINED; //Everything else comes here
   532       //FIXME error
   533     }
   534 #endif
   535   }
   536 
   537 //9.0-as cplex verzio statusai
   538 // CPX_STAT_ABORT_DUAL_OBJ_LIM
   539 // CPX_STAT_ABORT_IT_LIM
   540 // CPX_STAT_ABORT_OBJ_LIM
   541 // CPX_STAT_ABORT_PRIM_OBJ_LIM
   542 // CPX_STAT_ABORT_TIME_LIM
   543 // CPX_STAT_ABORT_USER
   544 // CPX_STAT_FEASIBLE_RELAXED
   545 // CPX_STAT_INFEASIBLE
   546 // CPX_STAT_INForUNBD
   547 // CPX_STAT_NUM_BEST
   548 // CPX_STAT_OPTIMAL
   549 // CPX_STAT_OPTIMAL_FACE_UNBOUNDED
   550 // CPX_STAT_OPTIMAL_INFEAS
   551 // CPX_STAT_OPTIMAL_RELAXED
   552 // CPX_STAT_UNBOUNDED
   553 
   554   LpCplex::SolutionStatus LpCplex::_getDualStatus()
   555   {
   556     int stat = CPXgetstat(env, lp);
   557 #if CPX_VERSION >= 800
   558     switch (stat)
   559     {
   560       case CPX_STAT_OPTIMAL:
   561         return OPTIMAL;
   562       case CPX_STAT_UNBOUNDED:
   563         return INFEASIBLE;
   564       default:
   565         return UNDEFINED;
   566     }
   567 #else
   568     statusSwitch(env,stat);
   569     switch (stat) {
   570     case 0:
   571       return UNDEFINED; //Undefined
   572     case CPX_OPTIMAL://Optimal
   573       return OPTIMAL;
   574     case CPX_UNBOUNDED:
   575      return INFEASIBLE;
   576     default:
   577       return UNDEFINED; //Everything else comes here
   578       //FIXME error
   579     }
   580 #endif
   581   }
   582 
   583   LpCplex::ProblemTypes LpCplex::_getProblemType()
   584   {
   585     int stat = CPXgetstat(env, lp);
   586 #if CPX_VERSION >= 800
   587     switch (stat)
   588     {
   589       case CPX_STAT_OPTIMAL:
   590 	return PRIMAL_DUAL_FEASIBLE;
   591       case CPX_STAT_UNBOUNDED:
   592  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
   593       default:
   594         return UNKNOWN;
   595     }
   596 #else
   597     switch (stat) {
   598     case CPX_OPTIMAL://Optimal
   599 	return PRIMAL_DUAL_FEASIBLE;
   600     case CPX_UNBOUNDED:
   601  	return PRIMAL_FEASIBLE_DUAL_INFEASIBLE;
   602 // 	return PRIMAL_INFEASIBLE_DUAL_FEASIBLE;
   603 // 	return PRIMAL_DUAL_INFEASIBLE;
   604 
   605 //Seems to be that this is all we can say for sure
   606     default:
   607 	//In all other cases
   608 	return UNKNOWN;
   609       //FIXME error
   610     }
   611 #endif
   612   }
   613 
   614   void LpCplex::_setMax()
   615   {
   616     CPXchgobjsen(env, lp, CPX_MAX);
   617    }
   618   void LpCplex::_setMin()
   619   {
   620     CPXchgobjsen(env, lp, CPX_MIN);
   621    }
   622 
   623   bool LpCplex::_isMax()
   624   {
   625     if (CPXgetobjsen(env, lp)==CPX_MAX)
   626       return true;
   627     else
   628       return false;
   629   }
   630   
   631 } //namespace lemon
   632