lemon/lp_cplex.cc
author deba
Thu, 10 May 2007 14:56:05 +0000
changeset 2442 27b7c7de9cac
parent 2391 14a343be7a5a
child 2553 bfced05fa852
permissions -rw-r--r--
Bug fix
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     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     //    env = CPXopenCPLEXdevelop(&status);     
    28     env = CPXopenCPLEX(&status);     
    29     lp = CPXcreateprob(env, &status, "LP problem");
    30   }
    31   
    32   LpCplex::~LpCplex() {
    33     CPXfreeprob(env,&lp); 
    34     CPXcloseCPLEX(&env); 
    35   }
    36   
    37   LpSolverBase &LpCplex::_newLp() 
    38   {
    39     //The first approach opens a new environment
    40     LpCplex* newlp=new LpCplex();
    41     return *newlp;
    42   }
    43 
    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   }
    54 
    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   }
    64 
    65   
    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   }
    77 
    78 
    79   void LpCplex::_eraseCol(int i) {
    80     CPXdelcols(env, lp, i, i);
    81   }
    82   
    83   void LpCplex::_eraseRow(int i) {
    84     CPXdelrows(env, lp, i, i);
    85   }
    86   
    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);
    92 
    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   }
   101   
   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   }
   110 
   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   }
   120   
   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;
   127 
   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     }
   133 
   134     status = CPXchgcoeflist(env, lp, values.size(), 
   135 			    &rowlist[0], &indices[0], &values[0]); 
   136   }
   137 
   138   void LpCplex::_getRowCoeffs(int i, RowIterator b) const {
   139     /// \todo implement
   140   }
   141   
   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;
   147 
   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     }
   153 
   154     status = CPXchgcoeflist(env, lp, values.size(), 
   155 			    &indices[0], &collist[0], &values[0]); 
   156   }
   157 
   158   void LpCplex::_getColCoeffs(int i, ColIterator b) const {
   159     /// \todo implement
   160   }
   161   
   162   void LpCplex::_setCoeff(int row, int col, Value value) 
   163   {
   164     CPXchgcoef(env, lp, row, col, value);
   165   }
   166 
   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   }
   173 
   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);
   183  
   184   }
   185 
   186   LpCplex::Value LpCplex::_getColLowerBound(int i) const
   187   {
   188     LpCplex::Value x;
   189     CPXgetlb (env, lp, &x, i, i);
   190     return x;
   191   }
   192   
   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   }
   203 
   204   LpCplex::Value LpCplex::_getColUpperBound(int i) const
   205   {
   206     LpCplex::Value x;
   207     CPXgetub (env, lp, &x, i, i);
   208     return x;
   209   }
   210 
   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     }
   218     
   219     int cnt=1;
   220     int indices[1];
   221     indices[0]=i;
   222     char sense[1];
   223 
   224     if (lb==-INF){
   225       sense[0]='L';
   226       CPXchgsense(env, lp, cnt, indices, sense);
   227       CPXchgcoef(env, lp, i, -1, ub);
   228       
   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   }
   251 
   252 //   void LpCplex::_setRowLowerBound(int i, Value value)
   253 //   {
   254 //     //Not implemented, obsolete
   255 //   }
   256   
   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);
   266 
   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 // //     }
   279 
   280 // //     status = CPXchgcoef(env, lp, i, -2, value_rng);
   281 //   }
   282   
   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   }
   309 
   310   void LpCplex::_setObjCoeff(int i, Value obj_coef)
   311   {
   312     CPXchgcoef(env, lp, -1, i, obj_coef);
   313   }
   314 
   315   LpCplex::Value LpCplex::_getObjCoeff(int i) const
   316   {
   317     Value x;
   318     CPXgetcoef(env, lp, -1, i, &x);
   319     return x;
   320   }
   321 
   322   void LpCplex::_clearObj()
   323   {
   324     for (int i=0;i< CPXgetnumcols(env, lp);++i){
   325       CPXchgcoef(env, lp, -1, i, 0);
   326     }
   327     
   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   }
   379 
   380   LpCplex::Value LpCplex::_getPrimal(int i) const
   381   {
   382     Value x;
   383     CPXgetx(env, lp, &x, i, i);
   384     return x;
   385   }
   386 
   387   LpCplex::Value LpCplex::_getDual(int i) const
   388   {
   389     Value y;
   390     CPXgetpi(env, lp, &y, i, i);
   391     return y;
   392   }
   393   
   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     int cstat[CPXgetnumcols(env, lp)];
   406     CPXgetbase(env, lp, cstat, NULL);
   407     return (cstat[i]==CPX_BASIC);
   408   }  
   409 
   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.
   412 
   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              
   460          
   461 //Some more interesting stuff:
   462 
   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   }
   487 
   488   LpCplex::SolutionStatus LpCplex::_getPrimalStatus() const
   489   {
   490     //Unboundedness not treated well: the following is from cplex 9.0 doc
   491     // About Unboundedness
   492 
   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.
   504 
   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   }
   553 
   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
   570 
   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   }
   599 
   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;
   621 
   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   }
   630 
   631   void LpCplex::_setMax()
   632   {
   633     CPXchgobjsen(env, lp, CPX_MAX);
   634    }
   635   void LpCplex::_setMin()
   636   {
   637     CPXchgobjsen(env, lp, CPX_MIN);
   638    }
   639 
   640   bool LpCplex::_isMax() const
   641   {
   642     if (CPXgetobjsen(env, lp)==CPX_MAX)
   643       return true;
   644     else
   645       return false;
   646   }
   647   
   648 } //namespace lemon
   649